- talks - lists.cs.princeton.edu

Colloquium Speaker, Feb. 10, 2010- John Ousterhout
by Nicole E. Wagenblast 08 Feb '10

08 Feb '10

RAMCloud: Scalable High-Performance Storage Entirely in DRAM John Ousterhout, Stanford University 4:30pm Small Auditorium CS 105 Disk-oriented approaches to online storage are becoming increasingly problematic: they do not scale gracefully to meet the needs of new large-scale Web applications, and improvements in disk capacity have out-stripped improvements in access speed. In this talk I will describe a new approach to datacenter storage called RAMCloud, where information is kept entirely in DRAM and large-scale systems are created by aggregating the main memories of thousands of commodity servers. A RAMCloud can provide durable and available storage with 100-1000x the throughput of disk-based systems and 100-1000x lower access latency. By combining low latency and large scale, RAMClouds will enable a new class of applications that manipulate large datasets more intensively than has ever been possible before.

1 1

[Fwd: Hellenic Studies Lecture: Thursday, February 11, 2010]
by Michele J. Brown 03 Feb '10

03 Feb '10

1 0

Brighten Godfrey talk on Distributed Compact Routing Thrus 3pm
by Nicole E. Wagenblast 02 Feb '10

02 Feb '10

Title: Distributed Compact Routing Speaker: Brighten Godfrey, UIUC Time: 3pm, Thursday, Feb 4th Room: CS 302 Abstract: Common wisdom is that the way to scale networks to large size is hierarchy: routing is performed on higher level aggregates across domains, separately from routing within domains. We live with the consequences: inflated path lengths, and the use of location-dependent addresses (IP addresses in the Internet) which complicate management, mobility, and multihoming. I will present Distributed Compact Routing, a protocol which (1) guarantees scalability, in the form of roughly \sqrt{n} state for a network of n nodes; (2) guarantees approximately-shortest paths, in the form of constant stretch; and (3) routes directly on flat, location-independent identifiers. Our work builds on recent theoretical advances in the area of compact routing. Past attempts to translate these centralized algorithms to practical distributed protocols have had limited success, compromising state or stretch guarantees or assuming special topologies. Our results thus represent a significant step forward in routing technology, which we believe has direct applicability to many kinds of networks including peer-to-peer networks, Internet routing, and content-centric networks. Joint work with Ankit Singla, Kevin Fall, Gianluca Iannaccone, and Sylvia Ratnasamy.

1 0

Colloquium Speaker, Wednesday, February 3, 2010-Tandy Warnow
by Nicole E. Wagenblast 01 Feb '10

01 Feb '10

Speaker: Tandy Warnow, University of Texas at Austin Title: *Simultaneous Alignment and Phylogenetic Tree Estimation* Wednesday, February 3, 2010 4:30 PM Small Auditorium (CS 105) Abstract: Molecular sequences evolve under processes that include substitutions, insertions, and deletions (jointly called \\\"indels\\\"), as well as other mechanisms (e.g., duplications and rearrangements). The inference of the evolutionary history of these sequences has thus been performed in two stages: the first estimates the alignment on the sequences, and the second estimates the tree given that alignment. While such methods seem to work well on relatively small datasets, these two-stage approaches can produce highly incorrect trees and alignments when applied to large datasets, or ones that evolve with many indels. In this talk, I will present a new method, SATe, that my lab has been developing that uses maximum likelihood to estimate the alignment and tree at the same time, and that can be used to analyze datasets with up to 1000 sequences on a desktop in 24 hours. Our study, using both real and simulated data, shows that this method produces much more accurate trees than the current best methods. Tandy Warnow is Professor of Computer Sciences at the University of Texas at Austin. Her research combines mathematics, computer science, and statistics to develop improved models and algorithms for estimating complex and large-scale evolutionary histories in both biology and historical linguistics. Tandy received her PhD in Mathematics at UC Berkeley under the direction of Gene Lawler, and did postdoctoral training with Simon Tavare and Michael Waterman at USC. She received the National Science Foundation Young Investigator Award in 1994, and the David and Lucile Packard Foundation Award in Science and Engineering in 1996. Tandy is a member of five graduate programs at the University of Texas, including Computer Science; Ecology, Evolution, and Behavior; Molecular and Cellular Biology; Mathematics; and Computational and Applied Mathematics. She is also the director for the multi-disciplinary CIPRES (Cyber-Infrastructure for Phylogenetic Research) Project, currently funded by the NSF under their Information Technology Program. _______________________________________________ talks mailing list talks(a)lists.cs.princeton.edu https://lists.cs.princeton.edu/mailman/listinfo/talks

1 0

Colloquium Speaker, Wednesday, February 3, 2010-Tandy Warnow
by Michele J. Brown 28 Jan '10

28 Jan '10

Speaker: Tandy Warnow, University of Texas at Austin Title: *Simultaneous Alignment and Phylogenetic Tree Estimation* Wednesday, February 3, 2010 4:30 PM Small Auditorium (CS 105) Abstract: Molecular sequences evolve under processes that include substitutions, insertions, and deletions (jointly called \\\"indels\\\"), as well as other mechanisms (e.g., duplications and rearrangements). The inference of the evolutionary history of these sequences has thus been performed in two stages: the first estimates the alignment on the sequences, and the second estimates the tree given that alignment. While such methods seem to work well on relatively small datasets, these two-stage approaches can produce highly incorrect trees and alignments when applied to large datasets, or ones that evolve with many indels. In this talk, I will present a new method, SATe, that my lab has been developing that uses maximum likelihood to estimate the alignment and tree at the same time, and that can be used to analyze datasets with up to 1000 sequences on a desktop in 24 hours. Our study, using both real and simulated data, shows that this method produces much more accurate trees than the current best methods. Tandy Warnow is Professor of Computer Sciences at the University of Texas at Austin. Her research combines mathematics, computer science, and statistics to develop improved models and algorithms for estimating complex and large-scale evolutionary histories in both biology and historical linguistics. Tandy received her PhD in Mathematics at UC Berkeley under the direction of Gene Lawler, and did postdoctoral training with Simon Tavare and Michael Waterman at USC. She received the National Science Foundation Young Investigator Award in 1994, and the David and Lucile Packard Foundation Award in Science and Engineering in 1996. Tandy is a member of five graduate programs at the University of Texas, including Computer Science; Ecology, Evolution, and Behavior; Molecular and Cellular Biology; Mathematics; and Computational and Applied Mathematics. She is also the director for the multi-disciplinary CIPRES (Cyber-Infrastructure for Phylogenetic Research) Project, currently funded by the NSF under their Information Technology Program.

1 0

J Hung generals
by Melissa Lawson 15 Jan '10

15 Jan '10

Jack Tzu-Han Hung will present his research seminar/general exam on Wednesday January 20 at 9AM in room 402. The members of his committee are David August (advisor), Doug Clark, and Margaret Martonosi. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam are welcome to do so. His abstract and reading list follow below. -------------------------------------------------------------- (Abstract) Recently, multicore systems have emerged as the dominant architecture in computing. Unfortunately, sequential programs do not benefit much from the new architecture. To keep up to the decades-old performance growth trend, some propose new programming languages or extensions for explicitly parallel programming [9, 2, 5, 3, 10, 8]. This approach leaves great burden to the programmers, including code rewriting effort and concerns for correctness and performance. An alternative is to use compilation techniques to extract the implicit parallelism from traditional, sequential programs. Most works focus on parallelizing the hottest loop in the program [12, 6, 4]; a few previous works attempt to exploit hybrid parallelism from several independent loops [11]. Hence, without considering the loop nest as a whole, these techniques leave a significant amount of parallelism unexploited. This work aims to extract various types of parallelism existing in a loop nest, using a dynamic programmingbased framework. Specifically, with a bottom-up traversal of the loop nest, every loop is examined to see if data or pipeline parallelism can be extracted and is assessed to see if the parallelization strategy is beneficial. The framework produces the final parallelized code that provides the optimal combination of the parallelization techniques. With manual parallelization, we experiment with six benchmarks, selected from different domains, including streaming applications (StreamIt benchmark) and data-intensive applications (SPECfp and MineBench). Our initial results show a (geo-mean) speedup of 3.35x (on an 8-core machine), while prior approaches (i.e., parallelizing one single loop or independent loops) only produce a speedup of 2.85x. (Reading List) [Papers] [1] J. R. B. Davies. Parallel loop constructs for multiprocessors. Master's thesis, Department of Computer Science, University of Illinois, Urbana, IL, May 1981. [2] M. I. Gordon, W. Thies, and S. Amarasinghe. Exploiting coarse-grained task, data, and pipeline parallelism in stream programs. In ASPLOS-XII: Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, pages 151-162, New York, NY, USA, 2006. ACM. [3] J. Gummaraju, J. Coburn, Y. Turner, and M. Rosenblum. Streamware: programming general-purpose multicore processors using streams. In ASPLOS XIII: Proceedings of the 13th international conference on Architectural support for programming languages and operating systems, pages 297-307, New York, NY, USA, 2008. ACM. [4] J. Huang, A. Raman, Y. Zhang, T. B. Jablin, T.-H. Hung, and D. I. August. Decoupled software pipelining creates parallelization opportunities. In Proceedings of the 2010 International Symposium on Code Generation and Optimization, April 2010. [5] M. Kudlur and S. Mahlke. Orchestrating the execution of stream programs on multicore platforms. In PLDI '08: Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation, pages 114-124, New York, NY, USA, 2008. ACM. [6] G. Ottoni, R. Rangan, A. Stoler, and D. I. August. Automatic thread extraction with decoupled software pipelining. In Proceedings of the 38th Annual IEEE/ACM International Symposium on Microarchitecture, pages 105-116, November 2005. [7] E. Raman, G. Ottoni, A. Raman, M. Bridges, and D. I. August. Parallel-stage decoupled software pipelining. In Proceedings of the 2008 International Symposium on Code Generation and Optimization, April 2008. [8] W. Thies, V. Chandrasekhar, and S. Amarasinghe. A practical approach to exploiting coarse-grained pipeline parallelism in C programs. In Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture, December 2007. [9] W. Thies, M. Karczmarek, and S. Amarasinghe. StreamIt: A language for streaming applications. In Proceedings of the 12th International Conference on Compiler Construction, 2002. [10] A. Udupa, R. Govindarajan, and M. J. Thazhuthaveetil. Synergistic execution of stream programs on multicores with accelerators. In LCTES '09: Proceedings of the 2009 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, pages 99-108, New York, NY, USA, 2009. ACM. [11] H. Zhong, S. A. Lieberman, and S. A. Mahlke. Extending multicore architectures to exploit hybrid parallelism in singlethread applications. 2007. [12] H. Zhong, M. Mehrara, S. Lieberman, and S. Mahlke. Uncovering hidden loop level parallelism in sequential applications. In Proc. of the 14th International Symposium on High- Performance Computer Architecture, 2008. [13] L. Lamport. The parallel execution of DO loops. In Communications of the ACM, 1974. [14] J. Allen and K. Kennedy. Automatic loop interchange. In Proc. of the 1984 SIGPLAN symposium on Compiler construction, 1984. [15] W. Lee, R. Barua, M. Frank, D. Srikrishna, J. Babb, V. Sarkar, and S. Amarasinghe. Space-time scheduling of instruction-level parallelism on a raw machine. In Proc. of the eighth international conference on Architectural support for programming languages and operating systems, 1998. [16] A. Lim and M. Lam. Maximizing parallelism and minimizing synchronization with affine transforms. In the Proc. of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 1997. [17] A. Lim, G. Cheong, and M. Lam. An affine partitioning algorithm to maximize parallelism and minimize communication. In the Proc. of the 13th international conference on Supercomputing, 1999. [Text Books] [18] Modern Compiler Implementation in ML, by A. W. Appel, Cambridge University Press, 1998. [19] Compilers: Principles, Techniques, and Tools (2nd Edition) by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman, Addison Wesley, 2006.

1 0

S Gerrish general exam
by Melissa Lawson 15 Jan '10

15 Jan '10

Sean Gerrish will present his research seminar/general exam on Wednesday January 20, at 11AM in room 402. The members of his committee are: David Blei (advisor), Ed Felten, and Christiane Fellbaum. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam are welcome to do so. His abstract and reading list follow below. -------------------------------------- Modeling Influence in Text Corpora Identifying the most influential documents in a corpus is an important problem in many fields, ranging from information science and historiography to text summarization and news aggregation. A traditional method of assessing the impact of articles is to analyze the citations to it. The impact factor of a journal, for example, is based largely on academic citation analysis; and Googles successful PageRank algorithm is based on hyperlink citations between Webpages. Often, however, citation information is not present: certain legal documents, news stories, blog posts, sermons, and email, for example, all might lack such citation metadata, while there is a clear notion of influence among articles in these collections. In this talk, I will describe an unsupervised method for determining the influence of a document. Our intuition is that language changes over time, and that influential documents contribute to this change. I will formalize this intuition with a probabilistic graphical model and present an algorithm which takes a sequence of documents as input and computes a vector of "influence" for each document characterizing the document's influence. I will also discuss evaluation of this method and describe when this method provides a citation-free measure of bibliometric impact. Books / chapters 1. Selected chapters from Machine Learning and Pattern Recognition, Bishop Chapters: 1; 2; 3.1-3.2; 4.3-4.5; 7.1; 8; 9; 10; 11.1-11.4; 12.1-12.3; 14.1, 14.3 2. An Introduction to Probabilistic Graphical Models (unpublished manuscript), by Michael I. Jordan, 2002 Chapters: 2, 3, 4, 5, 8, 9,11 Papers: 1. D. Blei, A. Ng, and M. Jordan. "Latent Dirichlet Allocation", JMLR, 3:993-1022, 2003. 2. D. Blei and J. Lafferty. "Dynamic Topic Models", in ICML, 2006. 3. M. Jordan, Z. Ghahramani, T. Jakkola, and L. Saul. "An introduction to variational methods for graphical models.", Machine Learning, 37(2):183-233, 1999. 4. R. Nallapati and W. Cohen. "Link-plsa-lda: A new unsupervised model for topics and influence of blogs", in Proceedings of the International Conference on Weblogs and Social Media (ICWSM), 2008. 5. Gelman, A., Meng, X.L., & Stern, H. "Posterior predictive assessment of model fitness via realized discrepancies", Statistica Sinica, 6:733-807, 1996. 6. G. E. P. Box. "Sampling and Bayes' Inference in Scientific Modelling and Robustness", Journal of the Royal Statistical Society, 143(4):383-430. 1980. 7. L. Deitz, S. Bickel, and T. Scheffer. "Unsupervised prediction of citation influences", in Proceedings of the 24th International Conference on Machine Learning. Corvallis, Oregon, USA, June 2007. 8. D. Cohn and T. Hofmann. "The missing link - a probabilistic model of document content and hyptertext connectivity", in T. Leen et al, eds, Advances in Neural Information Processing Systems 13. 9. T. Griffiths and M. Steyvers. "Finding Scientific Topics", Proc Natl Acad Sci USA, 101 Suppl 1:5228-5235, April 2004. 10. A. Budanitsky and G. Hirst. "Evaluating WordNet-based Measures of Lexical Semantic Relatedness.", Computational Linguistics , 32 (1): 13-47, 2006. 11. Clinton, J. and Jackman, S. and Rivers, D. "The Statistical Analysis of Roll Call Data,", American Political Science Review. 98(2) 2004.

1 0

Xiaojuan Ma preFPO
by Melissa Lawson 06 Jan '10

06 Jan '10

Xiaojuan Ma will present her preFPO on Wednesday January 13 at 1:30PM in room 402. The members of her committee are: Perry Cook, advisor; Marilyn Tremaine (Rutgers) and Christiane Fellbaum, readers; Szymon Rusinkiewicz and Ken Steiglitz, nonreaders. Everyone is invited to attend her talk. Her abstract follows below. ------------------------------------------------- Title: A Multimedia Augmented Online Language Assistant for People with Aphasia and Other Language Barriers Abstract: Communication among language users take place usually in the spoken or written mode, as in face-to-face conversations, reading of books and newspapers, television watching and Internet browsing. However, for people with language disabilities (e.g. aphasia), people with low literacy, and people with poor command of a language, receiving and expressing information in this way is difficult. In particular, because of the inability to comprehend words and or to find words that express intended concepts, people with language barriers may be faced with great challenges performing everyday tasks such as ordering food in a restaurant and visiting a doctor. As an alternative to words, pictures and sounds have been designed, tested, verified and used to evoke concepts in computer interfaces, education, industry, and advertisement. However, icons created by artists, user-uploaded photos, auditory icons and earcons cannot always satisfy the need for communicating everyday concepts for people with language problems. We are building a Multimedia Augmented Online Language Assistant, which employs various multimedia forms, including web images, icons, animations, videos, and environmental sounds with the goal of assisting comprehension of common concepts. The Language Assistant is implemented as a popup dictionary in the form of a web browser extension. Users can select an unfamiliar word on a webpage to view its associated visual/auditory representation in a popup box. The Language Assistant can enhance concept understanding as people browse information on the Internet, and support face-to-face communication when people want to illustrate a term via a picture, a video or a sound when their conversation partner does not understand the spoken word. The Multimedia Augmented Online Language Assistant consists of a backend lexical network associated with large scale of multimedia data, and web interfaces to access the multimedia-concept associations. To develop the backend multimedia enhanced lexical database, we went through a cycle of design, construction, evaluation, and modification for each stimulus-to-concept associations. As an example we describe the creation of SoundNet, a nonspeech audio-to-concept semantic network which is part of the database. Soundnails, five-second environmental auditory representations, were extracted from sound effects libraries, and assigned to a vocabulary of common concepts. Two large scale studies were conducted via Amazon Mechanical Turk to evaluate the efficacy of soundnail representations. The first was a tagging study which collected human interpretations of the sources, locations, and interactions involved in the sound scene. The second study investigated how well people can understand words encoded in soundnails which are embedded in sentences compared to conventionally used icons and animations. Modification guidelines were proposed based on the study results. Through a series of studies, we verified that web images are as effective as stylized icons in conveying nouns, videos outperformed other stimuli in illustrating verbs, and nonspeech audio clips are better in distinguishing concepts like thunder, alarm, and sneezing. The Multimedia Augmented Online Language Assistant was shown to enhance information comprehension, and we are exploring its application in assisting communication involving medical care issues for people with language barriers and low levels of and medical literacy.

1 0

11am Wed Dec 16 talk by Michael Schapira on incentives issues in Internet routing
by Jennifer Rexford 16 Dec '09

16 Dec '09

Michael Schapira (http://www.cs.yale.edu/homes/schapira/) is visiting from Tuesday through Thursday this week. If you would like to meet with him, please drop me a note (jrex(a)cs.princeton.edu). Speaker: Michael Schapira, Yale University and UC Berkeley Title: Interdomain Routing: Stability, Security and Selfishness Date/time: 11am-noon on Wednesday December 16 Location: Room 402 in the Computer Science building Abstract: The Border Gateway Protocol (BGP) establishes routes between the many independently-administered networks that make up the Internet. Over the past two decades there has been exponential growth in the scale and complexity of the Internet. However, BGP has not changed significantly in comparison and, consequently, does not always cope well with modern-day challenges (bounded computational resources, economically driven manipulations, security attacks, and more). Understanding, ``fixing'' and redesigning interdomain routing necessitates taking a principled approach that bridges theory and systems research, and breaks traditional disciplinary barriers. I shall present conceptual frameworks for addressing today's challenges and novel routing schemes that improve on the existing ones. Specifically, I shall present (1) a necessary condition for BGP safety, i.e., guaranteed BGP convergence to a ``stable'' routing outcome; (2) an economic approach to BGP security; and (3) Neighbor-Specific BGP -- a modest extension to BGP that allows network administrators more expressive routing policies while improving global network stability. I shall also discuss the surprising implications of these results for other areas of research: distributed computing, game theory and mechanism design. Finally, I shall outline interesting directions for future work.

1 1

Colloquium Speaker, Dec. 16, 2009- David Naumann
by Nicole E. Wagenblast 14 Dec '09

14 Dec '09

Smart Assertions for Dumb Provers David Naumann, Stevens Institute of Technology 4:30 PM Small Auditorium CS 105 Assertions are widely used for runtime checking of software correctness, and increasingly used for compile time checking of simple properties like array index bounds. Structural integrity of pointer based data structures and design patterns often involves recursively defined properties which are costly to check at runtime and which appear to be unsuited to static checking using fully automated theorem provers. Remarkably, judicious use of ghost state lets programmers express recursive properties in pure first order logic and successfully use fast provers based on SAT solving. In this talk I will introduce the technique in elementary terms, for programmers, who may find it immediately useful in testing. I will also outline research questions about how to use the technique in frame conditions, in refactoring, in foundational proofs, in refinement types, in terms of aspects, and in checking information flow properties.

1 1