"Amorphous Data Parallelism" Keshav Pingali University of Texas, Austin Client-side applications running on multicore processors are likely to be irregular programs that deal with complex, pointer-based data structures such as graphs and trees. In her 2007 Turing award lecture, Fran Allen raised an important question about such programs: do irregular programs have data parallelism, and if so, how do we exploit it on multicore processors? In this talk, we argue using concrete examples that irregular programs have an amorphous data-parallelism that arises from the use of iterative algorithms that manipulate worklists of various sorts. We then describe the approach taken in the Galois project to exploit this parallelism. There are three main aspects to the Galois system: (1) a small number of syntactic constructs for packaging amorphous data-parallelism as iterations over ordered and unordered sets, (2) assertions about methods in class libraries, and (3) a runtime system for managing the exploitation of amorphous data-parallelism. We present experimental results that demonstrate that the Galois approach is practical, and discuss ongoing work on this system. Biography: Keshav Pingali is the W.A."Tex" Moncrief Chair of Computing in the Computer Sciences department at the University of Texas, Austin. He received the B.Tech. degree in Electrical Engineering from IIT, Kanpur, India in 1978, the S.M. and E.E. degrees from MIT in 1983, and the Sc.D. degree from MIT in 1986. He was on the faculty of the Department of Computer Science at Cornell University from 1986 to 2006, where he held the India Chair of Computer Science. Pingali's research has focused on programming languages and compiler technology for program understanding, restructuring, and optimization. His group is known for its contributions to memory-hierarchy optimization; some of these have been patented. Algorithms and tools developed by his projects are used in many commercial products such as Intel's IA-64 compiler, SGI's MIPSPro compiler, and HP's PA-RISC compiler. In his current research, he is investigating optimistic parallelization techniques for multicore processors, and language-based fault tolerance. Among other awards, Pingali has won the President's Gold Medal at I.I.T. Kanpur (1978), IBM Faculty Development Award (1986-88), NSF Presidential Young Investigator Award (1989-94), Ip-Lee Teaching Award of the College of Engineering at Cornell (1997), and the Russell teaching award of the College of Arts and Sciences at Cornell (1998). In 2000, he was a visiting professor at I.I.T., Kanpur where he held the Rama Rao Chaired Professorship. Since 2007, he has been the co-Editor-in-chief of the ACM Transactions on Programming Languages and Systems (TOPLAS).