- talks - lists.cs.princeton.edu

Y Zhang general exam
by Melissa M Lawson 14 May '08

14 May '08

Yun Zhang will present her research seminar/general exam on Tuesday May 20 at 10AM in room 402. The members of her committee are: David August (advisor), Andrew Appel, and Doug Clark. Everyone is invited to attend her talk and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. ---------------------------- Abstract: Limited memory alias analysis inhibits automatic parallelization for multi-core architecture. Alias analysis generally considers memory accesses to separated parts of recursive data structures, especially cyclic ones, dependent since the analysis has no shape information indicating how the program traverses the data structure. For example, accesses to the left child of a binary tree node are separated from accesses to the right child, but current memory analysis methods conservatively conclude the accesses may alias with each other. This work proposes a three-step memory alias analysis that performs dependence tests on loops that traverse recursive data structures to benefit automatic code parallelization. The first step captures shape information of recursive data structures using separation logic, the second performs backward data flow analysis to form two pointers' definition chains, and the third combines the two definition chains with the shape information of the data structure to see if the two pointer accesses separate or alias between loop iterations. The experimental results show that this new alias analysis technique can effectively locate real cross-iteration dependences, which unveils opportunities for automatic parallelization, eases the work of instruction distribution and reduces data communications between cores. Reading List Books: 1. Modern Compiler Implementation in ML, by A. W. Appel, Cambridge University Press, 1998 2. Advanced compiler design and implementation, by S. S. Muchnick, Morgan Kaufman, 1997 Papers: 3. Shape Analysis with Inductive Recursion Synthesis. B. Guo, N. Vachharajani, and D. I. August, Proceedings of the ACM SIGPLAN 2007 Conference on Programming Language Design and Implementation (PLDI), June 2007. 4. Detecting Parallelism in C Programs with Recursive Data Sturctures, R. Ghiya, L. J. Hendren and Y. Zhu, Computational Complexity, page 159-173, 1998 5. Practical and Accurate Low-level Pointer Analysis, B. Guo, M.J. Bridges, S. Triantafyllis, G. Ottoni, E. Raman, and D. I. August, Proceedings of the Third International Symposium on Code Generation and Optimization (CGO), March 2005. 6. Identifying Parallelism in Programs with Cyclic Graphs, Y. Hwang and J. Saltz, Proceedings of the Proceedings of the 2000 International Conference on Parallel Processing(ICPP), 2000 7. Separation Logic: A Logic for Shared Mutable Data Structures, J. Reynold, Invited Paper, LICS 2002 8. Analysis of Pointers and Structures, D. R. Chase, M. Wegman, F. K. Zadeck, Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation, pp. 296-310, 1990. 9. Automatic Thread Extraction with Decoupled Software Pipelining, G. Ottoni, R. Rangan, A. Stoler, D. I. August, Proceedings of the 38th IEEE/ACM International Symposium on Microarchitecture (MICRO), November 2005 10. Revisiting the Sequential Programming Model for Multi-core, M. Bridges, N. Vachharajani, Y. Zhang, T. Jablin, D. I. August, Proceedings of the 40th IEEE/ACM International Symposium on Microarchitecture (MICRO), 2007 11. Points-to analysis by type inference in programs with structures and unions, B. Steensgaard, Lecture Notes in Computer Science, 1060 (T. Gyimothy, ed.), pp. 136-150, Springer-Verlag, 1996. Proceedings from the International Conference on Compiler Construction. 12. Relevant context inference, R. Chatterjee, B. G. Ryder, and W. A. Landi, Proceedings of the ACM Symposium on Principles of Programming Languages, pp. 133-146, January 1999.

1 0

G Wang FPO
by Melissa M Lawson 12 May '08

12 May '08

Ge Wang will present his FPO on Friday may 16 at 2PM in Room 302. The members of his committee are: Perry Cook, advisor; Paul Lansky (Music) and Roger Dannenberg (CMU), readers; Andrew Appel and Brian Kernighan, nonreaders. A copy of his thesis, "The ChucK Audio Programming Language "A Strongly-timed and On-the-fly Environ/mentality" " is on display in Room 310. Everyone is invited to attend his talk.

1 0

S Sevinc general exam
by Melissa M Lawson 12 May '08

12 May '08

Soner Sevinc will present his research seminar/general exam on Friday May 16 at 10AM in Room 402. The members of his committee are: Larry Peterson (advisor), Jennifer Rexford, and Ed Felten. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ------------------------------------- Large-scale network systems often must support users from multiple organizations that want to use resources owned by other organizations. Managing resources in such an environment must, therefore, be decentralized. Such systems require unique, immutable and verifiable naming of entities, and a security architecture that includes a fine grained authorization. Verification should allow multiple levels of trust to make the security system decentralized. Fail safety is necessary for correct operation of such a large system, limiting the damage a malicious or mis-operating entity can have to a short period of time. PlanetLab being one of such systems is in the stage of decentralization with federation with other similar systems or separating into several autonomous pieces. PlanetLab's current identity based authorization architecture makes decentralization difficult. The features of a more manageable system should include making the sources of authorization explicit, separating identity from rights, and allowing delegation of those rights. The protocols used within the system should support secure communication, possibly leveraging existing security schemes. My talk describes an architecture developed in the context of PlanetLab. The design includes a naming system, support for decentralized trust, and a fine-grained authorization mechanism. I will also describe a prototype implementation that leverages PlanetLab. " Reading List: 1. L.Peterson and B.Davie, "Computer Networks: A Systems Approach", 3rd Edition. 2. Larry Peterson, Andy Bavier, Marc E. Fiuczynski, and Steve Muir, "Experiences Building Planetlab", OSDI 2006 3. A.Bavier, N.Feamster, M.Huang, L.Peterson, and J.Rexford, "In VINI Veritas: Realistic and Controlled Network Experimentation", in Proc. ACM SIGCOMM, Sep 2006. 4. T. Anderson, Timothy Roscoe, "Learning from PlanetLab", 2006, Proceedings of the 3rd conference on USENIX Workshop on Real, Large Distributed Systems - Volume 3 5. M. Blaze, J. Feigenbaum and J. Lacy, "Decentralized trust management", In Proceedings of the 1996 IEEE Symposium on Security and Privacy, pages 164-173, May 1996. 6. Thomas Anderson and Michael Reiter, "*GENI Facility Security*," /GENI Design Document 06-23/, Distributed Services Working Group, September 2006. 7. E. Wobber, M. Abadi, M. Burrows and B. Lampson, "Authentication in the Taos operating system", ACM Transactions on Computer Systems 12(1):3-32, February 1994. 8. T. Jim, "SD3: A trust management system with certified evaluation", In Proceedings of the 2001 IEEE Symposium on Security and Privacy, pages 106-115, May 2001. 9. Jie Dai, Jim Alves-Foss, "Logic Based Authorization Engineering"

1 0

I Mukherjee general exam
by Melissa M Lawson 12 May '08

12 May '08

Indraneel Mukherjee will present his research seminar/general exam on Friday May 16 at 2PM in Room 402. The members of his committee are: Rob Schapire (advisor), David Blei, and Ken Steiglitz. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ---------------------------------------- Abstract: ========= We consider the problem of learning to predict as well as the best in a group of experts making continuous predictions. We assume the learning algorithm has prior knowledge of the maximum number of mistakes of the best expert. We propose a new master strategy that achieves the best known performance for online learning with continuous experts in the mistake bounded model. Our ideas are based on drifting games, a generalization of boosting and online learning algorithms. We also prove new lower bounds based on the drifting games framework which, though not as tight as previous bounds, have simpler proofs and do not require an enormous number of experts. Papers: ======= 1. Yoav Freund and Manfred Opper. Drifting games and Brownian motion. Journal of Computer and System Sciences, 64:113--132, 2002. A preliminary version appeared in the Proceedings of the 13th Annual Conference on Computational Learning Theory, 2000. 2. Yoav Freund. An adaptive version of the boost by majority algorithm. Machine Learning, 43(3):293--318, June 2001. A preliminary version appeared in the Proceedings of the 12th Annual Conference on Computational Learning Theory, 1999. 3. Yoav Freund. Boosting a weak learning algorithm by majority. Information and Computation, 121(2):256--285, 1995. Preliminary versions appeared in the Proceedings of the Third Annual Workshop on Computational Learning Theory, 1990, and in the Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory, 1992. 4. Robert E. Schapire. Drifting games. Machine Learning, 43(3):265-291, 2001. 5. N. Cesa-Bianchi, Y. Freund, D.P. Helmbold, D. Haussler, R. Schapire, and M.K. Warmuth How to use expert advice Journal of the ACM, 44(3):427-485, 1997. 6. N. Cesa-Bianchi, Y. Freund, D.P. Helmbold, and M.K. Warmuth On-line prediction and conversion strategies Machine Learning, 25:71-110, 1996. 7. J. Abernethy, J. Langford, M. Warmuth Continuous Experts and the Binning Algorithm COLT 2006 8. Nick Littlestone and Manfred K. Warmuth The weighted majority algorithm. Information and Computation, 108:212-261, 1994. 9. Joel Spencer Ulam's searching game with a fixed number of lies. Theoretical Computer Science, 95(2):307-321, 1992 10. David Blackwell An analog of the minmax theorem for vector payoffs. Pacific J. Math. Volume 6, Number 1 (1956), 1-8. Books: ====== 1. Stuart Russell, Peter Norvig. Artificial Intelligence: A modern approach. Chapters: 3.1-3.5 4.1-4.3 6 7.1-7.6 11.1-11.5 8.1-8.3 13.1-13.6 14.1-14.5 15.1-15.6 16.1-16.3 17.1-17.4 18.1-18.5 20.1-20.3,20.5-20.6 21.1-21.4 26 2. Luc Devroye, Laszlo Gyorfi, Gabor Lugosi A Probabilistic Theory of Pattern Recognition Chapters: 2,4,6.1,6.2,6.7,6.8 7,8,12,13,14,15,16, 28, 29, 30 3. Nicolo Cesa Bianchi, Gabor Lugosi Prediction Learning and Games Chapters: 2,3, 4.1-4.3, 6.1-6.3,6.7-6.9, 7.1-7.3, 7.7 - 7.8, 8, 9.1-9.5, 9.8 - 9.11, all of 10 except 10.6, 11.1 - 11.5

1 0

J Jiang general exam - time change
by Melissa M Lawson 09 May '08

09 May '08

Joe Wenjie Jiang's general exam, scheduled for Monday May 12, has been moved from 10AM to 9:30AM start time. It will still be held in Room 402.

1 0

Juan Chen talk, Friday May 16
by Andrew W. Appel 08 May '08

08 May '08

1 0

T Jablin general exam
by Melissa M Lawson 07 May '08

07 May '08

Tom Jablin will present his research seminar/general exam on Thursday May 15 at 1PM in Room 402. The members of his committee are: David August (advisor), Doug Clark, and J.P. Singh. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. -------------------------------- Pattern Driven Specialization Overcomes Static Limitations on Automatic Parallelization The multi-core revolution has arrived. Unfortunately, single-threaded applications do not benefit from multiple cores, and the benefit for multi-threaded applications is limited by Amdahl's law. A recent study shows that 32-cores worth of TLP (thread-level parallelism) can be automatically extracted from sequential codes with minor annotation using static profiling, analysis, and state-of-the-art transformations.[1] To achieve the next order of magnitude of TLP, the limits of static profiling must be addressed. Many important applications, interpreters being one example, suffer severely from these limits. In the case of interpretors, it is impossible to characterize the execution patterns without the interpreted code. However, runtime observations can discover regions in the interpreter that, due to predictable patterns in the interpreted program manifesting in the interpretor, are amenable to automatic parallelization. Run-time optimization can exploit this opportunity, eliminating the need to write parallelizers for interpreted languages. In this talk, I show that even if there is little TLP in a static program, there is often considerable parallelism in the program considered with its input set. Programmers and compilers cannot exploit this potential parallelism, but the dynamic system I will propose can. Citation: [1] Revisiting the Sequential Programming Model for the Multicore Era Matthew J. Bridges, Neil Vachharajani, Yun Zhang, Thomas Jablin, and David I. August Proceedings of the 40th IEEE/ACM International Symposium on Microarchitecture (MICRO), December 2007. Reading List Compilers: Principles, Techniques, and Tools by Aho and Ullman Modern Compiler Implementation in ML by Andrew W. Appel Experiments in Program Compilation by Interpreter Specialization by Thibault et al. Identifying Hierarchical Structure in Sequences: A linear-time algorithm by G. G. Nevill-Manning and I. H. Witten Analysis of control flow patterns in the execution of SPEC CPU2000 benchmark programs by Joseph, P. J. and Mattew Jacob, T. Revisiting the Sequential Programming Model for the Multicore Era by Bridges et al. Speculative Decoupled Software Pipelining by Vachharajani et al. Decoupled Software Pipelining with the Synchronization Array by Ottoni et al. Automatic Thread Extraction with Decoupled Software Pipelining by Ottoni et al. A General Approach for Run-Time Specialization and its Application to C by Dynamic Native Optimization of Interpreters by Gregory T. Sullivan, Derek L. Bruening, Iris Baron, Timothy Garnett A Tour of Tempo: A Program Specializer for the C Language by Charles Consel, Julia L. Lawall, Anne-Françoise Le Meur

1 0

reminder: 1-2pm talk today in room 302 on Learning Structured Bayesian Networks by Marie desJardins
by Jennifer Rexford 07 May '08

07 May '08

Speaker: Professor Marie desJardins, University of Maryland Title: Learning Structured Bayesian Networks: Combining Abstraction Hierarchies and Tree-Structured Conditional Probability Tables Date/time: 1-2pm Wednesday May 7 Location: 302 in the CS Building Abstract: In this talk, I will describe our research on incorporating background knowledge in the form of feature hierarchies during Bayesian network learning. Feature hierarchies enable the learning system to aggregate categorical variables in meaningful ways, thus enabling an appropriate "discretization" for a categorical variable. In addition, by choosing the appropriate level of abstraction for the parent of a node, we also support compact representations for the local probability models in the network. We combine this notion of selecting an appropriate abstraction with context-specific independence representations, which capture local ndependence relationships among the random variables in the Bayesian network. Capturing this local structure is important because it reduces the number of parameters required to represent the distribution. This can lead to more robust parameter estimation and structure selection, more efficient inference algorithms, and more interpretable models. I will describe our primary contribution, the Tree-Abstraction-Based Search (TABS) algorithm, which learns a data distribution by inducing the graph structure and parameters of a Bayesian network from training data. TABS combines tree structure and attribute-value hierarchies to compactly represent conditional probability tables. In order to construct the attribute-value hierarchies, we investigate two data-driven techniques: a global clustering method, which uses all of the training data to build the attribute-value hierarchies, and can be performed as a preprocessing step; and a local clustering method, which uses only the local network structure to learn attribute-value hierarchies. Empirical results in several benchmark domains show that (1) combining tree structure and attribute-value hierarchies improves the accuracy of generalization, while providing a significant reduction in the number of parameters in the learned networks, and (2) data-derived hierarchies perform as well or better than expert-provided hierarchies. BIOGRAPHY Dr. Marie desJardins is an associate professor in the Department of Computer Science and Electrical Engineering at the University of Maryland, Baltimore County. Her research is in artificial intelligence, focusing on the areas of machine learning, multi-agent systems, planning, interactive AI techniques, information management, reasoning with uncertainty, and decision theory. Dr. desJardins can be contacted at the Dept. of Computer Science and Electrical Engineering, University of Maryland Baltimore County, 1000 Hilltop Circle, Baltimore MD 21250, mariedj(a)cs.umbc.edu,(410) 455-3967.

1 0

Indranil Gupta talk at 12:30pm today, room 402
by Michael J Freedman 06 May '08

06 May '08

Today, Indranil Gupta from UIUC will be visiting us and speaking at Systems Lunch in room 402 (food at 12:00pm, talk at 12:30pm). The title and abstract of his talk is below. Cheers, --mike ========= Title: Wizards and Fruitflies -- Using Eternal and Ephemeral Overlays for Monitoring Distributed Systems Speaker: Indranil Gupta, Assistant Professor, Department of Computer Science, University of Illinois at Urbana-Champaign Abstract: Many distributed applications running over emerging large-scale distributed infrastructures, such as p2p systems, PlanetLabs and Grids, require the capability to monitor and manage a large distributed set of nodes at run-time. While many solutions exist for network and infrastructure-level monitoring, there is a scarcity of management solutions that work at the level of the distributed application, e.g., for monitoring node availability, count, top-k loaded nodes, querying log-files, etc. At the same time, much work has been done in the community on both persistent overlays such as distributed hash tables (DHTs), as well as unstructured overlays (e.g., Gnutella). However, we find that two alternative, unexplored, and opposing extremes of the design spectrum - eternal and ephemeral overlays - are better suited to solving the above management tasks. We present two systems -- AVMON and MON -- that seek to provide to distributed applications (and deployers) the ability to both monitor long-term availability histories of nodes in a distributed application, as well as to query the group of nodes on the fly. AVMON is a scalable availability monitoring overlay that is resilient to selfish and colluding nodes. AVMON imbues the concept of an eternally persistent (hence eternal) overlay, where peering relationships between nodes, once established, remain forever. Our other system, called MON, allows instant monitoring and management tasks, using the novel concept of an on-demand and short-lived (hence ephemeral) overlay, which survives only for the purpose of an individual management command. Both AVMON and MON are lightweight and fast in terms of memory, computation, bandwidth, and response time. Our mathematical analysis, trace-based simulations, and deployment atop PlanetLab, all demonstrate the practical performance characteristics of these two approaches in systems containing hundreds to thousands of nodes. We touch briefly upon how to use AVMON for building availability-aware services, the usage of MON in PlanetLab, as well as on other instances of eternal and ephemeral overlays we have studied. Speaker Bio: Indranil Gupta is an assistant professor in the Department of Computer Science at the University of Illinois at Urbana-Champaign. He received his PhD in Computer Science from Cornell University in 2004. He is a recipient of the NSF CAREER award in 2005. His research group DPRG works on distributed protocols and systems, with applications to large-scale distributed systems such as peer-to-peer systems and sensor networks. DPRG research is funded by several NSF grants, including multi-disciplinary ones. For more information on DPRG, visit http://dprg.cs.uiuc.edu

1 0

Q Xi general exam
by Melissa M Lawson 05 May '08

05 May '08

Qian Xi will present her research seminar/general exam on Tuesday May 13 at 2PM in Room 402. The members of her committee are: David Walker (advisor), David Blei, and Andrea LaPaugh. Everyone is invited to attend her talk and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. --------------------------- Ad hoc data sources are semi-structured data sources that are widely used in many research fields, but lack useful data analysis and transformation tools. The goal of the PADS system is to help programmers manipulate ad hoc data sources by providing automatic support for the generation of data processing tools. The tool generation infrastructure has multiple parts in it: (1) a simple tokenization phase (2) a rough data format inference phase (3) a data format refinement phase (4) a tool generation phase One serious limitation of the current implementation involves the tokenization phase. In particular, the current system is unable to handle ambiguous tokens. In this research, we tackle the token ambiguity problem with a more general approach. Two probabilistic models, a character-by-character Hidden Markov Model and a hierarchical model, are established by extracting statistical information from a collection of training data sources, labeled using a tool generated from hand-written descriptions. We show how to incorporate the learned Markov models into the rest of the algorithm to enhance format inference. We will explain the algorithms and implementations behind our new system and we will evaluate its success using a number of measures. Books: - Benjamin C. Pierce: Types and Programming Languages, Chapter 1-11, 13-24. - Stuart J. Russell, Peter Norvig: Artificial Intelligence, A Modern Approach (2nd edition), Chapter 13, 15 (15.1-15.3, 15.6) - Christopher M. Bishop: Pattern Recognition and Machine Learning, Chapter 8, Chapter 13 (13.1-13.2) Papers: - Kathleen Fisher, David Walker, Kenny Q. Zhu, and Peter White. From Dirt to Shovels: Fully Automatic Tool Generation from Ad Hoc Data. Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 2008. - Nicholas Kushmerick, Daniel S. Weld, Robert Doorenbos. Wrapper Induction for Information Extraction. International Joint Conference on Artificial Intelligence, 1997. - David Pinto, Andrew McCallum, Xing Wei and W. Bruce Croft. Table Extraction Using Conditional Random Fields. Proceedings of the 2003 annual national conference on Digital government research. - Geert Jan Bex, Frank Neven, Thomas Schwentick, and Karl Tuyls. Inference of concise DTDs from XML data. Proceedings of the 32nd international conference on Very Large Data Bases, 2006. - Vinayak Borkar, Kaustubh Deshmukhy, and Sunita Sarawagiz. Automatic Segmentation of Text into Structured Records. Proceedings of the 2001 ACM SIGMOD international conference on Management of data, 2001. - Arvind Arasu and Hector Garcia-Molina. Extracting Structured Data From Web Pages. Proceedings of the ACM SIGMOD international conference on Management of data, pages 337¨C348, 2003. - E. M. Gold. Language Identification in the Limit. Information and Control, 1967. - Stephen Soderland. Learning Information Extraction Rules for Semistructured and Free Text. Machine Learning, 1999.

1 0