Tutorials Program -- Monday, June 15
Please choose one tutorial from the morning (M1 or M2) and one from the afternoon (A1 or A2).
|8:30 am - 12:00 pm||M1||The Concurrent Collections Parallel Programming Model - Foundations and Implementation Challenges|
|Kathleen Knobe (Intel) and Vivek Sarkar (Rice University)|
|8:30 am - 12:00 pm||M2||Building Memory-Efficient Java Applications: Practices and Challenges|
|Gary Sevitsky (IBM Research)|
|1:30 pm - 5:00 pm||A1||CHESS: Analysis and Testing of Concurrent Programs|
|Sebastian Burckhardt, Madanlal Musuvathi, and Shaz Qadeer (Microsoft Research)|
|1:30 pm - 5:00 pm||A2||Code Transformation Techniques for Software Protection|
|Christian Collberg (University of Arizona)|
Breaks: Snacks will be available at 10:00 am and 3:00 pm. Lunch will be served at noon.
The Concurrent Collections Parallel Programming Model - Foundations and Implementation Challenges
Presenters: Kathleen Knobe and Vivek Sarkar
Monday, June 15, 2009. 8:30 AM - 12:00 PM Slides
Concurrent Collections (CnC) is a new approach to parallelism intended for mainstream programmers and domain experts. A CnC program is represented as a graph in which only the semantic constraints are explicit. It avoids unnecessary constraints found in explicitly serial and explicitly parallel languages. This provides maximum flexibility for algorithmic tuning and compiler and runtime optimizations. At the same time, the programmer is relieved of the burden of using explicit synchronization and scheduling constructs found in other parallel languages.
The specific topics to be covered in the tutorial include:
- CnC language, semantic foundations, and safety properties
- CnC implementation techniques, including details of two existing systems, one based on C++ and one based on Java
- Discussion of a few simple CnC applications, downloadable from the CnC release
- Comparison with other parallel programming models
- Open problems and interesting areas for future research
The content for these topics come from our experiences with the C++ release of CnC which builds on the Intel Threading Building Blocks runtime and is freely available at http://software.intel.com/en-us/articles/intel-concurrent-collections-for-cc/, and a more recent Java-based implementation under development at Rice University which builds on the Habanero runtime.
This tutorial should be relevant to practitioners and researchers interested in enabling software to execute efficiently on parallel computers without the complexity of explicit parallel programming. It will be useful to anyone who would like to learn enough about CnC to try it out on their own. In addition, the semantic foundations and implementation techniques described in the tutorial will be useful for language designers and implementers (who may choose to build CnC implementations on other serial languages or for other target architectures), as well as to application and library programmers (who may choose to use CnC as a design methodology). There are many open research questions that arise within the language, the runtime system, optimization phases and tool development, which will be of interest to researchers in the area of parallel software. Lastly, CnC supports a separation of concerns that make it an attractive tool for both educators and algorithm developers.
Kathleen Knobe worked at Compass (aka Massachusetts Computer Associates) from 1980 to 1991 where she designed compilers for a wide range of parallel platforms for Thinking Machines, MasPar, Alliant, Numerix, and several government projects. In 1991 she decided to finish her education. After graduating from MIT in 1997, she joined Digital Equipment's Cambridge Research Lab (CRL). She stayed through the DEC/Compaq/HP mergers and CRL's absorption into Intel. Her professional interests remained focused on parallelism either through compiler technology or language design. She currently works in Geoff Lowney's group (Software Solutions Group / Software Pathfinding and Innovation / Scalable Tools - SSG/SPI/ST). Her major projects include Data Optimization (compiler transformations for locality), the Subspace Model of computation (a compiler internal form for parallelism), Array Static Single Assignment form (a method of achieving for array and loop-base code the advantages that SSA has for scalars), Weak Dynamic Single Assignment form (a global method for eliminating overwriting of data to maximize scheduling flexibility), Stampede (a programming model for streaming media applications), and TStreams (a new parallel programming model described in the attached abstract). TStreams has been renamed Concurrent Collections (CnC).
Vivek Sarkar is the E.D. Butcher Professor of Computer Science at Rice University. He conducts research in programming languages, program analysis, compiler optimizations and virtual machines for parallel and high performance computer systems, and currently leads the Habanero Multicore Software Research project at Rice (www.habanero.rice.edu). Prior to joining Rice, he was Senior Manager of Programming Technologies at IBM Research. His past projects at IBM include the X10 programming language, the Jikes Research Virtual Machine for the Java language, the ASTI optimizer used in IBM's XL Fortran product compilers, the PTRAN automatic parallelization system, and profile-directed partitioning and scheduling of Sisal programs. In 1997, he was on sabbatical as a visiting associate professor at MIT, where he was a founding member of the MIT RAW project. Vivek holds a B.Tech. degree from the Indian Institute of Technology, Kanpur, an M.S. degree from University of Wisconsin-Madison, and a Ph.D. from Stanford University. Vivek was elected to the IBM Academy of Technology in 1995, and inducted as an ACM Fellow in 2008. He has given tutorials at several past conferences including PLDI 1993, POPL 1996, ASPLOS 1996, PLDI 2000, OOPSLA 2003, ECOOP 2004, OOPSLA 2006, PPoPP 2007, PLDI 2007, PLDI 2008, and has also taught many short courses and full-length courses.
M2: Building Memory-Efficient Java Applications: Practices and Challenges
Presenter: Gary Sevitsky
Monday, June 15, 2009. 8:30 AM - 12:00 PM
It is easy these days to build Java applications with large memory requirements - in fact it takes significant effort not to. It is common to see multi-gigabyte heaps with tens of millions of objects, where as much as 80% of memory is the overhead of the data representation. Bloated designs have a serious on impact on scalability, power consumption, performance, and deployment schedules. Pervasive memory problems are the result of many factors, including a pile-up of framework abstractions that programmers must integrate, and limitations of the Java language and runtime. The magnitude of problems can be surprising. At the same time, it suggests there is much room for improvement.
This tutorial aims to raise awareness, for researchers and developers, of the typical practices leading to memory consumption in Java - from basic Java building blocks through high-level framework and application code. We present a systematic catalog of costly patterns gathered from real-world case studies. Patterns are organized around common design problems such as modeling data types, representing relationships, and managing object lifetime. For developers the goal is to enable informed tradeoffs, and to show how dramatic improvements are sometimes possible without sacrificing sound design. For researchers interested in improving the state of memory usage through new analyses, optimizations, tools, or language features, the tutorial provides an understanding of developer practices and the limits they face, as well as discussion of opportunities for solutions.
Gary Sevitsky is a Research Staff Member at IBM TJ Watson Research Center. Since joining IBM Research in 1998, Gary Sevitsky has been part of a group studying performance and memory usage in large object-oriented systems. The group has developed Java performance and memory analysis tools that have been used extensively on IBM products and customer applications. The group has also worked directly on dozens of performance engagements over the past eight years, and has been mining these experiences to catalog the ways in which framework-based systems are often inefficient. Gary has given numerous talks at IBM and at universities cataloging performance and memory problems from case studies and documenting the systemic bloat common in large object-oriented systems.
A1: CHESS: Analysis and Testing of Concurrent Programs
Presenters: Sebastian Burckhardt, Madanlal Musuvathi, and Shaz Qadeer
Monday, June 15, 2009. 1:30 PM - 5:30 PM
Hardware advances have forced programmers to develop concurrent software. Unfortunately, concurrent programs are extremely hard to write, analyze, test, and debug. CHESS is a research platform developed at Microsoft Research to address many of these challenges. CHESS works on user-mode native (C/C++) or managed (C#) programs and has demonstrably scaled to large industrial-scale software. CHESS can predictably and systematically drive a given program along a specified set of thread interleavings. This predictable control allows CHESS to successfully find and reproduce concurrency errors. These "Heisenbugs" are otherwise very hard to find or reproduce.
Over the past three years, CHESS has matured as an extensible platform for building analysis tools for concurrency. This tutorial will provide hands-on experience in using the various features of this platform. The tutorial will also demonstrate ways to build custom analysis tools and interleaving search strategies using CHESS. Researchers interested in concurrency analysis and testing, and educators interested in teaching concurrency should find this tutorial helpful. CHESS is available for download with both an academic and a commercial license at http://research.microsoft.com/CHESS.
Sebastian Burckhardt is a Researcher at Microsoft Research. He is interested in many aspects of the verification and design of concurrent software, in particular relating to shared-memory programs and relaxed memory models. He received his PhD from the University of Pennsylvania in 2007.
Madanlal Musuvathi is a Researcher at Microsoft Research. He is interested in the analysis of complex and large-scale systems, focusing on building analysis tools to improve the productivity of software developers and testers. His research is inter-disciplinary and includes systems, networking, program analysis, model checking, verification, and theorem proving. He received his Ph.D. from Stanford University in 2004.
Shaz Qadeer is a Senior Researcher at Microsoft Research. His work aims to improve software reliability by providing programmers with automated tools to analyze their programs. He is interested in a variety of program analysis techniques, such as model checking, automated theorem proving, type systems, and run-time verification. Most of his work has focused on applying these techniques to analysis of concurrent software. He received his Ph.D. from University of California at Berkeley in 1999.
A2: Code Transformation Techniques for Software Protection
Presenter: Christian Collberg
Monday, June 15, 2009. 1:30 PM - 5:00 PM
In this tutorial we will describe techniques for software protection, i.e. techniques for protecting secrets contained in computer programs from being discovered, modified, or redistributed. Important applications include protecting against software piracy, license check tampering, and cheating in on-line multi-player games. The attack model is very liberal: we assume that an adversary can study our program's code (maybe first disassembling or decompiling it), execute it to study its behavior (perhaps using a debugger), or alter it to make it do something different than what we intended (such as bypassing a license check). In a typical defense scenario we use code transformation techniques to add confusion to our code to make it more difficult to analyze (statically or dynamically), tamper-protection to prevent modification, and watermarking to assert our intellectual property rights (by embedding a hidden copyright notice or unique customer identifier).
Christian Collberg received a BSc in Computer Science and Numerical Analysis and a Ph.D. in Computer Science from Lund University, Sweden. He is currently an Associate Professor in the Department of Computer Science at the University of Arizona and has also worked at the University of Auckland, New Zealand, and the Chinese Academy of Sciences in Beijing. Prof. Collberg is a leading researcher in the intellectual property protection of software, and also maintains an interest in compiler and programming language research. In his spare time he writes songs, sings, and plays guitar for The Zax and hopes one day to finish up his Great Swedish Novel.