April 2014 - talks - lists.cs.princeton.edu

Nick Johnson Pre-FPO
by Melissa M. Lawson 10 Apr '14

10 Apr '14

Nick Johnson will present his preFPO on Thursday April 17 at 9AM in Room 402. The members of his committee are: David August, advisor; David Wentzlaff and Jae Lee (SKKU), readers; David Walker and Andrew Appel, nonreaders. Everyone is invited to attend his talk. His abstract follows below. --------- Title: Static Dependence Analysis in an Infrastructure for Automatic Parallelization. Now that parallel architectures are common, software must exploit parallel functional units to fully utilize hardware resources and achieve efficient execution. Although developers may restructure their applications for explicit parallelism, that process requires developers to reason about low-level details of the execution environment to avoid concurrency bugs and achieve parallel performance. A favorable alternative is automatic thread extraction, since it relieves the developer of the arduous task of (re-)developing applications with each new architecture. This dissertation presents compiler middle-ware to support automatic thread extraction---analyses and transformations that allow the compiler to deliver parallel performance from sequentially-specified input programs. Specifically, this thesis contributes, 1. Collaborative Dependence Analysis: Compilers use static analysis to determine facts about the input code. These facts restrict compiler transformations to ensure correctness. The collaborative dependence analysis framework combines simple analysis algorithms into an ensemble algorithm. Such ensembles are structured for collaboration: the ensemble algorithm disproves dependence queries which no member analysis algorithm disproves alone. Preliminary results demonstrate that this framework has a large impact on even speculative thread extraction systems: for some benchmarks, the strength of analysis is the difference between a 28x speedup and an 11x slowdown (geomean) measured on 50 cores. 2. Scaling Analysis to Parallelize Larger Scopes: As scopes grow large, the burden of analysis becomes prohibitive. Observing that parallelization depends on the strongly-connected components of the PDG (the DAG_SCC), this dissertation presents a faster algorithm to compute the DAG_SCC. This algorithm greedily identifies dependence edges which cannot affect parallelization. It reduces analysis time by skipping such unimportant dependence edges, instead spending analysis effort on the remaining, important queries. Overall, this faster algorithm reduces analysis time by half while maintaining precision. The dissertation presents an end-to-end integration of these contributions. This infrastructure has proved robust and flexible; many works from the Liberty Research Group have built upon this infrastructure.

1 0

Colloquium Speaker: Stefanie Jegelka Tues April 8th 4:30pm
by Nicole E. Wagenblast 07 Apr '14

07 Apr '14

Efficient learning with combinatorial structure Stefanie Jegelka , University of California, Berkeley Tuesday, April 8, 4:30pm Computer Science 105 Learning from complex data such as images, text or biological measurements invariably relies on capturing long-range, latent structure. But the combinatorial structure inherent in real-world data can pose significant computational challenges for modeling, learning and inference. In this talk, I will view these challenges through the lens of submodular set functions. Considered a "discrete analog of convexity", the combinatorial concept of submodularity captures intuitive yet nontrivial dependencies between variables and underlies many widely used concepts in machine learning. Practical use of submodularity, however, requires care. My first example illustrates how to efficiently handle the important class of submodular composite models. The second example combines submodularity and graphs for a new family of combinatorial models that express long-range interactions while still admitting very efficient inference procedures. As a concrete application, our results enable effective realization of combinatorial sparsity priors on real data, significantly improving image segmentation results in settings where state-of-the-art methods fail. Motivated by good empirical results, we provide a detailed theoretical analysis and identify practically relevant properties that affect complexity and approximation quality of submodular optimization and learning problems. Stefanie Jegelka is a postdoctoral researcher at UC Berkeley, working with Michael I. Jordan and Trevor Darrell. She received a Ph.D. in Computer Science from ETH Zurich in 2012, in collaboration with the Max Planck Institute for Intelligent Systems, and completed her studies for a Diploma in Bioinformatics with distinction at the University of Tuebingen (Germany) and the University of Texas at Austin. She was a fellow of the German National Academic Foundation (Studienstiftung) and its scientific college for life sciences, and has received a Google Anita Borg Europe Fellowship and an ICML Best Paper Award. She has also been a research visitor at Georgetown University Medical Center and Microsoft Research and has held workshops and tutorials on submodularity in machine learning.

1 0

Colloquium Speaker Elad Hazan, Thurs April 3, 4:30pm
by Nicole E. Wagenblast 03 Apr '14

03 Apr '14

Sublinear Optimization for Machine Learning Elad Hazan, Technion, Israel Institute of Technology Thursday, April 3, 4:30pm Computer Science 105 In many modern optimization problems, particularly those arising in machine learning, the amount data is too large to apply standard convex optimization methods. We'll discuss new optimization algorithms that make use of randomization to prune the data produce a correct solution albeit running in time which is smaller than the data representation, i.e. sublinear running time. We'll present such sublinear-time algorithms for linear classification, support vector machine training, semi-definite programming and other optimization problems. These new algorithms are based on a primal-dual approach, and use a combination of novel sampling techniques and the randomized implementation of online learning algorithms. We'll describe information-theoretic lower bounds that show our running times to be nearly best possible in the unit-cost RAM model. The talk will be self contained - no prior knowledge in convex optimization or machine learning is assumed. Elad Hazan is an associate professor of operations research at the Technion, Israel Institute of Technology. His main research area is machine learning and its relationship to optimization, game theory and computational complexity. Elad received his Ph.D. in computer science from Princeton University. He is the recipient of several best paper awards including the Goldberg Best Paper award (twice), and the European Research Council starting grant.

1 1

Colloquium Speaker Arti Gupta Weds April 2, 4:30pm
by Nicole E. Wagenblast 02 Apr '14

02 Apr '14

Software Verification: Locks and MLoCs* Arti Gupta ( NEC Labs America ) Wednesday, April 2, 4:30pm Computer Science 105 Software verification deals with proving or falsifying correctness properties of programs, and has broad applications from ensuring safety of mission-critical software to improving program robustness and programmer productivity. This area has long held theoretical interest, but the inherent undecidability of the general problem and intractability of specific formulations have been barriers to practical success. Approaches based on automatic techniques for state space exploration, such as model checking and symbolic execution, have seen a resurgence of interest in recent years, driven largely by advancements in solvers for Boolean Satisfiability (SAT) and Satisfiability Modulo Theories (SMT). These solvers perform the underlying search for proofs or bugs, typically by reasoning over abstract models of programs. While abstraction is critical in scaling to real-life programs, it is equally important to ensure enough precision in the models and the analysis to verify specific properties of interest. In this talk, I will describe my work in foundational techniques that address these twin challenges of precision and scalability in verifying sequential and multi-threaded programs. I will also share the lessons learnt in my efforts in driving them to industry practice where they are routinely used in a modular methodology to find complex bugs in software projects, some with millions of lines of code. Finally, I will discuss future extensions and applications of this verification framework. *MLoC: Million Lines of Code Aarti Gupta received her PhD in Computer Science from Carnegie Mellon University. Her broad research interests are in the areas of formal analysis of programs/systems and automatic decision procedures. At NEC Labs she leads research in systems analysis and verification. She has given several invited keynotes highlighting the foundational research contributions of her group in verification and their successful industrial deployment. She has served as an Associate Editor for Formal Methods in System Design (since 2005) and for the ACM Transactions on Design Automation of Electronic Systems (2008-2012). She has also served as Co-Chair for the International Workshop on Satisfiability Modulo Theories (SMT) 2010, the International Conference on Computed Aided Verification (CAV) 2008, and Formal Methods in Computer Aided Design (FMCAD) 2006. She is currently serving on the Steering Committee of CAV.

1 2