- talks - lists.cs.princeton.edu

Taewook Oh generals
by Melissa M. Lawson 16 Apr '12

16 Apr '12

Taewook Oh will present his research seminar/general exam on Monday April 23 at 10AM in Room 402. The members of his committee are David August (advisor), Brian Kernighan, and Andrew Appel. 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] Program specialization improves the performance of a program by optimizing it with respect to invariants in the program and its input. For example, by specializing an interpreter with respect to the script, a compiler can produce a highly optimized interpreter customized for the given script. To specialize loops in the program, applying unrolling during specialization is essential. Existing specializers, however, require explicit user annotations to the program to achieve the optimal degree of unrolling. To address this problem, we present a new program specialization technique called IPLS(Invariant-induced Pattern based Loop Specialization), which maximizes the benefit of unrolling without user annotations. First, IPLS traces the values of instructions in the loop that depend solely on invariants and recognizes repeating patterns of these values across multiple iterations. Then, it generates a specialized loop for the recognized pattern by unrolling the original loop to match the pattern length. Without any hints from the user about the program, IPLS specializes loops to reflect the structure of the loop induced by the invariants, so it gets the most of the benefit from unrolling. Experiments show that proposed technique effectively specializes real-world programs that the prior techniques fail to specialize, with a geomean speedup of 14.4% over the original codes. [Reading list] * Textbooks 1. A. W. Appel. Modern Compiler Implementation in C. Cambridge University Press, 1998 2. J. L. Hennessy and D. A. Patterson. Computer Architecture: A Quantitative Approach. Morgan Kaufmann, San Francisco, CA, 1996 * Research Papers 1. W. W. Hwu, S. A. Mahlke, W. Y. Chen, P. P. Chang, N. J. Warter, R. A. Bring- mann, R. G. Ouellette, R. E. Hank, T. Kiyohara, G. E. Haab, J. G. Holm, and D. M. Lavery, The superblock: An effective technique for VLIW and superscalar compilation, The Journal of Supercomputing, vol. 7, pages 229-248, January 1993. 2. S. A. Mahlke, D. C. Lin, W. Y. Chen, R. E. Hank, R. A. Bringmann, and W. W. Hwu, Effective compiler support for predicated execution using the hyperblock, in Proceedings of the 25th International Symposium on Microarchitecture, pages 45–54, December 1992. 3. C.-Y. Fu, M. D. Jennings, S. Y. Larin, and T. M. Conte, Value speculation scheduling for high performance processors, In Proceedings of the 8th Interna- tional Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-VIII), pages 262–271, 1998. 4. A. Gelnstrup, H. Makholm, and J. P. Secher, C-Mix: specialization of C pro- grams, eds, J. Hatcliff, T. Mogenses, and P. Thiemann, Partial Evaluation: Practice and Theory, LNCS, vol. 1706, pages 108-153, Springer-Verlag, 1999. 5. C. Consel, L. Hornof, F. Noel, J. Noye, and N. Volansche, A uniform approach for compile-time and run-time specialization, In Selected Papers from the 1996 International Seminar on Partial Evaluation, pages 54–72, Dagstuhl Castle, Ger- many, Feb. 1996. Springer-Verlag, Berlin, Germany. 6. B. Grant, M. Mock, M. Philipose, C. Chambers, and S. J. Eggem. Annotation- directed run-time specialization in C, In Proceedings of the ACM SIGPLAN Svmvosium on Partial Evaluation and Semantics-Based Program manipulation, pages 163–178, Amsterdam, The Netherlands, June 1997. ACM. 7. A. Shankar, S. S. Sastry, R. Bodik, and J. E. Smith. Runtime specialization with optimistic heap analysis, In OOPSLA 05: Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, pages 327–343, 2005. 8. A. Gal, B. Eich, M. Shaver, D. Anderson, D. Mandelin, M. R. Haghighat, B. Kaplan, G. Hoare, B. Zbarsky, J. Orendorff, J. Ruderman, E. W. Smith, R. Re- itmaier, M. Bebenita, M. Chang, and M. Franz, Trace-based Just-in-Time Type Specialization for Dynamic Languages, In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 465– 478, 2009. ACM. 9. C. F. Bolz, A. Cuni, M. Fijakowski, and A. Rigo. Tracing the Meta-Level: PyPy’s Tracing JIT Compiler, In ICOOOLPS, pages 18–25, Genova, Italy, 2009. ACM 10. A. Yermolovich, C. Wimmer, and M. Franz. Optimization of Dynamic Lan- guages Using Hierarchical Layering of Virtual Machines, In DLS, pages 79–88, Orlando, Florida, USA, 2009. ACM.

1 0

4:30pm Wed Apr 11 talk on network virtualization in data centers by Changhoon Kim
by Jennifer Rexford 11 Apr '12

11 Apr '12

Speaker: Dr. Changhoon Kim, Microsoft Azure Title: Network Virtualization for Large Data Centers and Enterprises Location: CS 105 (the small auditorium) Date/time: 4:30pm on Wednesday April 11 Abstract: Data centers are the digital-era analogue of factories and gaining huge popularity among service providers and enterprises. The golden rule of designing and operating a data center is maximizing the amount of useful work per dollar spent. To meet this goal, the most desirable technical feature is agility—the ability to assign any computing resources to any tenants any time. Anything less inevitably results in stranded resources and poor performance perceived by data-center users. In this talk, I first show how and why conventional networks specifically designed for large data centers inhibit, rather than facilitate, agility. Location-dependent constraints, huge and unpredictable performance variances, and poor scalability are the main culprits. Then I put forward network virtualization as key architecture that ensures agility at scale. The core properties of my network-virtualization architecture—abstraction, isolation, and efficiency—allow service providers to build a network that is not susceptible to the location dependencies and poor scalability in the first place, eliminating the huge burden of complicated and less effective cross-layer optimizations needed to outmaneuver the constraints. Then I explain how I turn this architecture into an operational system that virtualizes mega data-center networks for a real-world cloud service. In particular, I show how my virtualization architecture and its realization uniquely take advantage of a few critical opportunities and technical trends available in data centers, ranging from the power of a software switch present in every hypervisor, to the principle of separating network state from host state, and to the availability of commodity switching ASICs. Finally I evaluate how faithfully the resulting system meets the goal of offering a powerful and simple virtual-network abstraction—an imaginary switch that can host as many servers as a customer desires, offering predictably and uniformly high capacity between any servers under any traffic patterns, and yet dedicated only to the customer. Bio Changhoon Kim works at Windows Azure, Microsoft's cloud-service division, and leads research and engineering projects on the architecture, performance, management, and operation of datacenter and enterprise networks. His research themes span network virtualization, self-configuring networks, and debugging and diagnosis of large-scale distributed systems. Changhoon received Ph.D. from Princeton University in 2009, where he worked with Prof. Jennifer Rexford. Many of his research outcomes (including SEATTLE, VL2, VNet, Seawall, and the relay-routing technology for VPNs) are either directly adopted by production service providers or under review by standard bodies, such as IETF. In particular, his VL2 work was published in the Research Highlights section of the Communications of the ACM (CACM) as an invited paper, which the editors recognize as "one of the most important research results published in CS in recent years".

1 1

Dominic Kao MSE thesis talk
by Melissa M. Lawson 10 Apr '12

10 Apr '12

Dominic Kao will present his MSE thesis talk on Monday April 16 at 2PM in room 402. The members of his committee are: Yael Niv (PSY), her postdoc Carlos Diuk, and Adam Finkelstein, reader. Everyone is invited to attend his talk. His abstract follows below. --------------------- The world has already spent 5.93 million years playing the video game World of Warcraft. What makes video games rewarding? We suggest that one important factor in a player's enjoyment of a game is the schedule of rewards, specifically, we hypothesized that variable rewards are more interesting and enticing than a fixed reward size. To test this hypothesis we studied several variable reward schedules contrasted with a fixed reward schedule in a custom-built video game. We found that variable reward schedules were preferred, except when the schedule’s range included very small or non-existent (zero) rewards. Participants consistently mischaracterized the variable reward schedule as having a higher mean than the fixed schedule. We further hypothesized that reward schedule preference is an indicator for game genre preference. Ultimately, the conclusions made can be applied more broadly to the now ubiquitous game mechanics that surround us in both the real and virtual world.

1 0

J Huang preFPO
by Melissa M. Lawson 05 Apr '12

05 Apr '12

Jialu Huang will present her preFPO on Monday April 9 at 1PM in Room 301 (note room!!) The members of her committee are: David August, advisor; David Walker and Kai Li, readers; Doug Clark and JP Singh, nonreaders. Everyone is invited to attend her talk. Her abstract follows below. ========================================================================================= Abstract: Automatic parallelization is a promising approach to deliver scalable multi-threaded programs for multi-core architectures. Most existing techniques parallelize independent loops and insert global synchronizations at the end of each loop invocation. For programs with few loop invocations, these global synchronizations do not limit parallel execution performance. However, for programs with many loop invocations, those synchronizations can easily become the performance bottleneck since they frequently force all threads to wait, losing potential parallelization opportunities. Some automatic parallelization techniques apply static analyses to enable cross-invocation parallelization. Instead of waiting, threads can execute iterations from follow-up invocations if they do not cause any conflict. However, static analyses must be conservative, and therefore cannot handle programs with irregular dependence patterns. In order to enable more parallelization across loop invocations, this thesis presents two novel automatic parallelization techniques: BLISS and SBS. Unlike existing techniques relying on static analyses, these two techniques take advantage of runtime information to achieve much more aggressive parallelization. BLISS constructs a custom runtime engine which non-speculatively observes dependences at runtime and synchronizes iterations only when necessary; while SBS applies software speculative barriers to permit some of the threads to execute past the invocation boundaries. The two techniques are complimentary in the sense that they can parallelize programs with potentially very different characteristics. SBS is most effective when a program's cross-invocation dependences rarely cause a runtime conflict. BLISS' runtime engine imposes a marginal amount of overhead, but it also enables the technique to effectively parallelize programs whose dependences can cause frequent conflicts. Preliminary implementation and evaluation demonstrate that both techniques can achieve much better scalability compared to existing automatic parallelization techniques. ==============================================================================================

1 0

J Terrace preFPO
by Melissa M. Lawson 05 Apr '12

05 Apr '12

Jeff Terrace will present his preFPO on Thursday April 12 at 4PM in Room 302 (note room!). The members of his committee are: Michael Freedman, advisor; Adam Finkelstein and Phil Levis (Stanford), readers; Vivek Pai and Szymon Rusinkiewicz, nonreaders. Everyone is invited to attend his talk. His abstract follows below. --------------------- Metaverses are three-dimensional virtual worlds where anyone can add and script new objects. Metaverses today, such as Second Life, are dull, lifeless, and stagnant because users can see and interact with only a tiny region around them, rather than a large and immersive world. Current metaverses impose this distance restriction on visibility and interaction in order to scale to large worlds, as the restriction avoids appreciable shared state in underlying distributed systems. We present a brief summary of the design and implementation of the Sirikata metaverse server. The Sirikata server scales to support large, complex worlds, even as it allows users to see and interact with the entire world. It achieves both goals simultaneously by leveraging properties of the real world and 3D environments in its core systems, such as a novel distributed data structure for virtual object queries based on visible size. A virtual-world environment becomes a truly engaging platform when users have the ability to insert 3D content into the world. However, arbitrary 3D content is often not optimized for real-time rendering, limiting the ability of clients to display large scenes consisting of hundreds or thousands of objects. We present the design and implementation of an automatic, unsupervised conversion process that transforms 3D content into a format suitable for real-time rendering while minimizing loss of quality. The resulting progressive format includes a base mesh, allowing clients to quickly display the model, and a progressive portion for streaming additional detail as desired. Sirikata’s public, open-source content repository is currently using this method and has processed over 700 3D models. 3D meshes are large--often several megabytes in size. When a client enters a scene containing many objects, it can take a long time to download meshes, resulting in poor visual fidelity. A progressive mesh format allows a client to download a low-resolution version of a mesh at a much lower cost in bandwidth, but deciding how to order downloads has a huge impact on performance. Should a client download a higher texture resolution for one model, or stream additional vertices for another? Worse, underpowered clients might not be able to display a high resolution mesh, resulting in wasted time downloading unneeded content. We present the design and implementation of a framework for evaluating scheduling algorithms for progressive meshes and we perform this evaluation on several different algorithms. The result is a mesh scheduling algorithm that optimizes for visual fidelity given a fixed bandwidth constraint.

1 0

W Clarkson FPO
by Melissa M. Lawson 03 Apr '12

03 Apr '12

Will Clarkson will present his FPO on Monday April 9 at 8:30AM in the 3rd Floor Conference Room in Sherrerd Hall. Note time and location! The members of his committee are: Ed Felten, advisor; Andrew Appel and Adam Finkelstein, readers; Brian Kernighan and Rebecca Fiebrink, nonreaders. A copy of his thesis, "Breaking Assumptions: Distinguishing Between Seemingly identical Items Using Cheap Sensors", is on display in Room 310. Everyone is invited to attend his talk.

1 0

11am Fri Mar 30 talk on smart energy in CS 105
by Jennifer Rexford 30 Mar '12

30 Mar '12

Speaker: Shivkumar Kalyanaraman, IBM Research Title: Smarter Energy: The Promise of Cyber-Physical Systems Location: 105 Computer Science Building (a.k.a. the "small auditorium") Date/time: 11am-noon on Friday March 30 Abstract: This talk will review how the climate change problem is linked to the fossil-fuel energy problem, and overview various options for sustainable energy and their relative contributions. We then discuss smarter energy, and how sensing, networking, real-time analytics, actuation and control come together in a "cyber-physical" system. The talk will discuss key IBM Research and some commercial initiatives worldwide -- ranging from deep rainforest microgrids in Brunei, smart grid tomography in Australia, integration of fickle wind energy and plug-in hybrid electric vehicles (PHEV) in Denmark, context-sensitive "smart" demand-response systems for residential use. Bio: Shivkumar Kalyanaraman is a Senior Technical Staff Member (STSM) & Senior Manager of the Next Gen Systems & Smarter Planet Solutions Department at IBM India Research Labs, Bangalore. He was previously a Manager of the Next Generation Telecom Research group and a Research Staff Member since 2008. He was a full Professor at the Department of Electrical, Computer and Systems Engineering at Rensselaer Polytechnic Institute in Troy, NY. He received a B.Tech degree in Computer Science from the Indian Institute of Technology, Madras, India in July 1993, followed by M.S. and Ph.D. degrees at the Ohio State University in 1994 and 1997 respectively. He also holds an Executive M.B.A. (EMBA) degree from Rensselaer Polytechnic Institute (2005). His current research in IBM is at the intersection of emerging wireless technologies and IBM middleware and systems technologies with applications to large-scale smarter planet problems (grids, traffic, finance etc). He was selected by MIT's Technology Review Magazine in 1999 as one of the top 100 young innovators for the new millenium. He served as the TPC Co-chair of IEEE INFOCOM 2008, and General co-chair of ACM SIGCOMM 2010 in New Delhi. He is on the editorial board of IEEE/ACM Transactions of Networking. He is a Fellow of the IEEE, and an ACM Distinguished Scientist.

1 0

A Bhaskara preFPO
by Melissa M. Lawson 28 Mar '12

28 Mar '12

Aditya Bhaskara will present his preFPO on Monday April 2 at 1PM in Room 301. His committee is: Moses Charikar, advisor; Sanjeev Arora and Zeev Dvir, readers; Bernard Chazelle and Amit singer (Math), nonreaders. Everyone is invited to attend his talk. His abstract follows below. Title: Finding Dense Sub-structures in Graphs and Matrices A basic primitive in graph optimization is that of finding small induced subgraphs of a given graph with ``many'' edges. Questions of this nature arise often in practice, for instance in finding ``communities'' in social networks, and in clustering type problems. From the theory side, this captures questions such as ``small-set expansion'', which has proved to be an intriguing open problem. A simple formalization we study is the Densest-k-subgraph problem, where the objective, given a graph G, is to find an induced subgraph on k vertices with as many edges as possible. There is a vast gap in our understanding of this problem in terms of the approximation ratio we can achieve. I will discuss the state of the art in approximation algorithms, and try to point out why it is difficult to write convex programming relaxations for the problem. This is akin to difficulties that arise in other problems which have a ``small-support'' constraint, such as those arising in compressed sensing. An interesting aspect of the densest-k-subgraph problem is that random instances seem to be the hardest for obtaining approximation algorithms. A question related to this is that of computing the q->p (operator) norm of a matrix. Such norms are generalizations of singular values, and in general, computing them is not a convex optimization problem. We will see conditions under which it is possible to compute them efficiently, and attempt to obtain a `characterization', by complementing this with hardness results. We also study generalizations of singular values to three-dimensional tensors, a problem which arises in applications involving 3D data. The question is believed to be very hard (even to approximate) in general. We study the following `planted' variant: suppose we know that the tensor is "rank-k + small noise" (but we do not have access to such a decomposition), then can we solve the tensor analog of largest singular value? We show that this can be done in time exponential in $k$ (but almost linear in the size of the tensor). Results in the talk will be based on joint works with Sanjeev Arora, Moses Charikar, Eden Chlamtac, Uriel Feige, Ravi Kannan, and Aravindan Vijayaraghavan.

1 0

Colloquium Speaker Umesh Vazirani, Tues March 27- 4:30pm
by Nicole E. Wagenblast 26 Mar '12

26 Mar '12

Certifiable Quantum Dice Umesh Vazirani , University of California, Berkeley Tuesday, March 27 4:30pm Computer Science Small Auditorium (Room 105) A source of independent and uniform random bits is a basic resource in many computational tasks, such as cryptography, game theoretic protocols, algorithms and physical simulations. In the classical world it is impossible to construct a random number generator whose output can be certified to be a uniformly random n-bit string, since there seems to be no basis on which to reject any particular output in favor of any other. Quantum mechanics allows for a remarkable random number generator: its output is certifiably random in the sense that if the output passes a simple statistical test, and a no-signaling condition is met between the two boxes in the randomness generating device (based, say, on the speed of light limit imposed by special relativity), even a quantum skeptic (viz Einstein's famous quote ``God does not play dice with the Universe''), would be convinced that the output is truly random, independent of the validity of quantum mechanics. Based on joint work with Thomas Vidick.

1 1

R Manokaran preFPO
by Melissa M. Lawson 26 Mar '12

26 Mar '12

Rajsekar Manokaran will present his preFPO on Wednesday March 28 at 1:30PM in Room 402. The members of his committee are: Sanjeev Arora, advisor; Moses Charikar and Zeev Dvir, readers; Mark Braverman and Bernard Chazelle, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ------------------- Title: Approximability using Mathematical Relaxations A standard approach to coping with the NP-hardness of a combinatorial optimization problem involves designing algorithms that guarantee a solution within a factor p of the optimum (a.k.a an p-approximation algorithm). We study the approximability of various fundamental graph optimization problems using linear programming~(LP) relaxations. In the first part of the thesis, we study simple LP relaxations for Metric Labeling, and a variety of Packing and Covering problems. For all these problems, we show that the relaxation already obtains the best approximation, upto known algorithmic barriers. The novelty here is the generality of the technique: the proof only uses simple "local" properties of the relaxation, oblivious of the actual approximation factor, p, obtained thus. In the second part, we use insights obtained from the above in studying the approximability of a large class of ordering problems, including the Maximum Acyclic Subgraph problem. Here, we show that a trivial algorithm, that outputs a random ordering irrespective of the instance in hand, already achieves the best appromximation factor upto known algorithmic techniques. In the final part, we study implications of "average-case" algorithmic barriers. In particular, we show that the densest-k-subgraph problem is hard to approximate to within any constant factor assuming random k-AND formulas are hard to distinguish from well satisfiable ones. These results are based on joint works with Noga Alon, Sanjeev Arora, Moses Charikar, Venkatesan Guruswami, Johan Hastad, Amit Kumar, Dana Moshkovitz, Joseph Naor, Prasad Raghavendra, Roy Schwartz, Madhur Tulsiani, Nisheeth Vishnoi and Omri Weinstein

1 0