May 2010 - talks - lists.cs.princeton.edu

N Johnson general exam
by Melissa Lawson 04 May '10

04 May '10

Nick Johnson will present his research seminar/general exam on Monday May 10 at 10AM in Room 402. The members of his committee are: David August (advisor), Andrew Appel, and Brian Kernighan. 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. -------------------------------------------- Effective Composition of Optimizing Transformations via Obstacle Identification Abstract Optimizing transformations interact in complicated, non-linear and often unknown ways. This prevents most compilers from applying transformations in an optimal manner. Multicore exacerbates this problem; the performance difference between the best and average transform sequences is orders of magnitude. Common practice uses applicability and profitability guards to decide whether each transformation should be applied greedily or not at all, but may miss intermediate strategies with better performance. I present the obstacle identification technique, which uses the dual of those guards to identify limiting qualities of the program structures. By repeatedly relaxing program structure and retesting the guards, we enumerate those relaxations which improve applicability or profitability (obstacles). We demonstrate the promise of the obstacle identification technique by applying it to the problem of interacting transformations. This technique offers a competitive solution. References [1] F. Agakov, E. Bonilla, J. Cavazos, B. Franke, G. Fursin, M. F. P. O'Boyle, J. Thomson, M. Toussaint, and C. K. I. Williams. Using machine learning to focus iterative optimization. In CGO '06: Proceedings of the International Symposium on Code Generation and Optimization, pages 295-305, Washington, DC, USA, 2006. IEEE Computer Society. [2] L. Almagor, Keith D. Cooper, Alexander Grosul, Timothy J. Harvey, Steven W. Reeves, Devika Subramanian, Linda Torczon, and Todd Waterman. Finding effective compilation sequences. In LCTES '04: Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, pages 231-239, New York, NY, USA, 2004. ACM Press. [3] Andrew W. Appel. Modern Compiler Implementation in C. Cambridge University Press, 1998. [4] Keith D. Cooper, Alexander Grosul, Timothy J. Harvey, Steven Reeves, Devika Subramanian, Linda Torczon, and Todd Waterman. ACME: Adaptive compilation made efficient. In LCTES '05: Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, pages 69{77, New York, NY, USA, 2005. ACM. [5] J. Ferrante, K. J. Ottenstein, and J. D. Warren. The program dependence graph and its use in optimization. ACM Transactions on Programming Languages and Systems, 9:319-349, July 1987. [6] Jialu Huang, Arun Raman, Yun Zhang, Thomas B. Jablin, Tzu-Han Hung, and David I. August. Decoupled Software Pipelining Creates Parallelization Opportunities. In Proceedings of the 2010 International Symposium on Code Generation and Optimization, April 2010. [7] S. Muchnick. Advanced Compiler Design and Implementation. Morgan- Kaufmann Publishers, San Francisco, CA, 1997. [8] Easwaran Raman, Guilherme Ottoni, Arun Raman, Matthew J. Bridges, and David I. August. Parallel-stage decoupled software pipelining. In CGO '08: Proceedings of the sixth annual IEEE/ACM international symposium on Code generation and optimization, pages 114-123, New York, NY, USA, 2008. ACM. [9] Ross Tate, Michael Stepp, Zachary Tatlock, and Sorin Lerner. Equality saturation: A new approach to optimization. In POPL '10: Proceedings of the 37th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 2010. [10] Spyridon Triantafyllis, Manish Vachharajani, and David I. August. Compiler optimization-space exploration. Journal of Instruction-Level Parallelism, 7, 2005. [11] M. Wolf, D. Maydan, and D. Chen. Combining loop transformations considering caches and scheduling. In Proceedings of the 29th Annual International Symposium on Microarchitecture, pages 274-286, December 1996.

1 0

3pm Tue May 4 talk on algebraic modeling of policy-based routing
by Jennifer Rexford 03 May '10

03 May '10

Speaker: Tim Griffin, University of Cambridge Title: Exploring the Stratified Shortest Paths Problem Date/time: 3pm Tuesday May 4 Location: room 302 in the Computer Science building Abstract: The Border Gateway Protocol (BGP) is the keystone among Internet routing protocols as it maintains connectivity in the entire global Internet. BGP has evolved into a rather mysterious beast. Theoretical work over the last ten years has made it clear that BGP represents something novel in the context of routing protocols: BGP does not compute globally optimal paths, but only locally optimal paths. The talk will explain how this exotic type of routing can be understood in an algebraic setting. The Stratified Shortest-Paths Problem (SSPP) is presented as a very simple example of this type of algebra. The SSPP is meant to capture the essence of a BGP-like path problem without BGP's many operational complexities. Bio: Tim Griffin is a Senior Lecturer and Fellow at King's College, University of Cambridge. His research interests include network protocol design and analysis, with a focus on Internet routing protocols.

1 0

Vladimir Kim general exam
by Melissa Lawson 03 May '10

03 May '10

Vladimir Kim will present his research seminar/general exam on Friday May 7 at 10AM in Room 302 (note room!). The members of his committee are: Tom Funkhouser (advisor), Adam Finkelstein, and Bernard Chazelle. His abstract and reading list follow below. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. ----------------------------------------- Abstract: I present a framework for symmetry-guided texture synthesis and processing. It is motivated by the long-standing problem of how to optimize, transfer, and control the spatial patterns in textures. The key idea is that symmetry representations that measure autocorrelations with respect to all transformations of a group are a natural way to describe spatial patterns in many real-world textures. To leverage this idea, we provide methods to transfer symmetry representations from one texture to another, process the symmetries of a texture, and optimize textures with respect to properties of their symmetry representations. These methods are automatic and robust, as they don't require explicit detection of discrete symmetries. Applications are investigated for optimizing, processing and transferring symmetries and textures. Reading List: A planar-reflective symmetry transform for 3D shapes Author Podolak, Joshua and Shilane, Philip and Golovinskiy, Aleksey and Rusinkiewicz, Szymon and Funkhouser, Thomas Booktitle ACM Transactions on Graphics (Proc. SIGGRAPH) Year 2006 Discovering Structural Regularity in 3D Geometry Author M. Pauly and N. J. Mitra and J. Wallner and H. Pottmann and L. Guibas Journal ACM Transactions on Graphics (Proc. SIGGRAPH) Year 2008 Volume 27 Symmetrization (inproceedings) Author N. J. Mitra and L. Guibas and M. Pauly Booktitle ACM Transactions on Graphics (Proc. SIGGRAPH) Year 2007 Partial and Approximate Symmetry Detection for 3D Geometry Author N. J. Mitra and L. Guibas and M. Pauly Booktitle ACM Transactions on Graphics (Proc. SIGGRAPH) Year 2006 Volume 25 Number 3 Image De-fencing (article) Author Yanxi Liu and Tamara Belkina and James H. Hays and Roberto Lublinerman Journal International Conference on Computer Vision Year 2008 Month June Near Regular Texture Analysis and Manipulation Author Yanxi Liu and Wen-Chieh Lin and James H. Hays Journal ACM Transactions on Graphics (Proc. SIGGRAPH) Year 2004 Volume 23 Number 1 Quantitative Evaluation of Near Regular Texture Synthesis Algorithms Author Lin, Wen-Chieh and Hays, James and Wu, Chenyu and Liu, Yanxi and Kwatra, Vivek Booktitle Computer Vision and Pattern Recognition Year 2006 Pages 427--434 A Reflective Symmetry Descriptor for 3D Models Author M. Kazhdan and B. Chazelle and D. Dobkin and T. Funkhouser and S. Rusinkiewicz Journal Algorithmica Year 2003 Pyramid-based texture analysis/synthesis Author Heeger, David J. and Bergen, James R. Booktitle ACM Transactions on Graphics (Proc. SIGGRAPH) Year 1995 Address New York, NY, USA Texture Synthesis by Non-parametric Sampling Author Alexei A. Efros and Thomas K. Leung Booktitle IEEE ICCV Year 1999 Month September Image Quilting for Texture Synthesis and Transfer Author Alexei A. Efros and William T. Freeman Journal ACM Transactions on Graphics (Proc. SIGGRAPH) Year 2001 As-Rigid-As-Possible Shape Manipulation Author Takeo Igarashi and Tomer Moscovich and John F. Hughes Journal ACM Transactions on Graphics (Proc. SIGGRAPH) Year 2005 Volume 24 Number 3

1 0