Research Accomplishments

• Analysis and Optimization of Multithreaded Programs

  The key problem with analyzing multithreaded programs is the need to characterize the effect of all potential interleavings of statements from parallel threads. My research group pioneered a compositional approach to this problem in which the algorithm analyzes each thread once to obtain a result that characterizes all potential interactions between that thread and other parallel threads. We have used this approach to develop a variety of analyses for different kinds of multithreaded programs. Here are several specific analyses:

  • The first flow-sensitive pointer analysis algorithm for programs with structured multithreading. The results have been used by a variety of research groups to enable optimizations and further analyses. We have a Web page that discusses this topic in more depth.

  • The first combined pointer and escape analysis for programs with the unstructured form of multithreading present in Java. See our PPoPP 2001 paper on this topic for details.

  • The first incrementalized pointer and escape analysis. Instead of analyzing the whole program, this algorithm builds on our compositional analysis to analyze only those parts of the program that may deliver useful optimization opportunities. An analysis policy monitors the analysis results to direct the incremental investment of analysis resources to those parts of the program that offer the highest expected optimization return. See our PLDI 2001 paper on this topic for details.

  • A new symbolic analysis for characterizing regions of allocated memory blocks. In addition to loops and array accesses, the analysis is designed for programs that use pointers, pointer arithmetic, and recursion. The results have been used for static race detection for parallel divide and conquer programs, automatic parallelization of sequential divide and conquer programs, static detection of array bounds violations, and elimination of array bounds checks. Basically, the analysis can verify that the program is completely free of a wide range of memory access anomalies that can cause a wide range of very nasty errors.
  All of these algorithms have been implemented, either in the Stanford SUIF compiler infrastructure (for C) or the MIT Flex compiler infrastructure (for Java) and have been used to analyze and and perform a range of optimizations on complete benchmark programs. See my home page for pointers to pages that discuss the research in more detail.

  I have also prepared an invited paper and an invited talk for SAS 2001 on the analysis of multithreaded programs.

• Analysis and Optimization of Divide and Conquer Programs

  Divide and conquer programs present an imposing set of analysis challenges. The natural formulation of these programs is recursive. For efficiency reasons, programs often use dynamic memory allocation to match the sizes of the data structures to the problem size, and often use pointers into arrays and pointer arithmetic to identify subproblems. Traditional analyses from the field of parallelizing compilers are of little or no help for this class of programs --- they are designed to analyze loop nests that access dense matrices using affine array index expressions, not recursive procedures that use pointers and pointer arithmetic.

  We have developed the following analyses and optimizations:

  • A new analysis that symbolically characterizes accessed regions of memory blocks. Because the analysis computes symbolic bounds for both pointers and array indices, it can be used to solve a wide variety of program analysis problems. To avoid problems associated with the use of traditional fixed-point techniques, the analysis formulates the problem as a system of symbolic constraints. It then reduces the system to a linear program; the solution to the linear program yields a solution to the original symbolic constraint system.

    We used this algorithm to solve a range of analysis problems, including static race detection for parallel divide and conquer programs, automatic parallelization of sequential divide and conquer programs, static detection of array bounds violations, and elimination of array bounds checks. See our PLDI 2000 paper on this topic for more details.

  • A new algorithm for increasing the granularity of the base case in divide and conquer programs. This algorithm unrolls recursive calls to reduce control flow overhead and increase the size of basic blocks in the computation. The result is a significant increase in the performance. See our LCPC 2000 paper on this topic for more details.

  • The first published analysis for automatically parallelizing divide and conquer programs. This analysis has since been superseded by the symbolic bounds analysis listed above. Nevertheless, you can see our PPoPP 1999 paper on this topic for more details.
  See my home page for pointers to pages that discuss this research in more detail.

• Synchronization Optimizations

  My research group has investigated a variety of ways of eliminating synchronization overhead in multithreaded and automatically parallelized programs. These optimizations eliminate mutual exclusion synchronization, reduce its frequency, replace it with more efficient optimistic synchronization primitives, and replicate objects to eliminate the need for synchronization. Specific techniques include: /P>

  • Synchronization Elimination: We have developed several combined pointer and escape analyses that are designed, in part, to find unnecessary synchronization operations. Our OOPSLA 1999 paper presents an escape analysis that finds objects that do not escape their allocating thread. The compiler uses the results of this analysis to generate customized, synchronization-free versions of the operations that execute on such objects. Our PPoPP 2001 paper presents an algorithm that analyzes interactions between threads to find and eliminate synchronization operations that are temporally separated by thread creation actions.

  • Lock Coarsening: Lock coarsening reduces the frequency with which the computation acquires and releases locks. We have developed two approaches: data lock coarsening , which associates one lock with multiple objects that tend to be accessed together, and computation lock coarsening, which coalesces multiple critical sections that acquire and release the same lock multiple times into a single critical section that acquires and releases the lock only once. Our experimental results show that lock elimination can significantly reduce the synchronization overhead in programs that use mutual exclusion synchronization.

    Our JPDC 1998 paper presents an algorithm that performs both data and computation lock coarsening for object-based programs. Our POPL 1997 paper presents a set of general transformations that move lock constructs both within and between procedures to coarsen the lock granularity.

  • Dynamic Feedback: There is a trade-off associated with lock coarsening: increasing the granularity reduces the synchronization overhead, but also increases the size of the critical regions, which may reduce the amount of available concurrency. We have developed an algorithm that generates several different versions of the program; the versions differ in how aggressively they apply the lock coarsening transformation. When the program runs, the generated code samples the performance of each version, then uses the version with the best performance. The code periodically resamples to adapt to changes in the best version. Our TOCS 1999 paper presents the algorithm and experimental results. We also published a PLDI 1997 paper on this topic.

  • Optimistic Synchronization: Optimistic synchronization primitives such as load linked/store conditional provide an attractive alternative to mutual exclusion locks. Our PPoPP 1997 paper presents our experience using optimistic synchronization to implement atomic operations in automatically parallelized object-based programs. Our results show that using optimistic synchronization can improve the performance and significantly reduce the amount of memory required to execute the computation.

  • Adaptive Replication: In many programs it is possible to eliminate synchronization bottlenecks by replicating frequently accessed objects that cause these bottlenecks. Each thread that updates such an object creates its own local replica and performs all updates locally on that replica with no synchronization and no interaction with other threads. When the computation needs to access the final value of the object, it combines the values stored in the replicas to generate the final value. A key question is determining which objects to replicate - replicating all objects can cause significant and unnecessary memory and computation overheads. We have developed a technique that dynamically measures the contention at objects to replicate only those objects that would otherwise cause synchronization bottlenecks.

    Our ICS 1999 paper presents experimental results from an implementation of this technique. The results show that, for our set of benchmark programs, adaptive replication can improve the overall performance by up to a factor of three over versions that use no replication, and can reduce the memory consumption by up to a factor of four over versions that fully replicate updated objects. Furthermore, adaptive replication never significantly harms the performance and never increases the memory usage without a corresponding increase in the performance.

  • Data Race Freedom: A multithreaded program has a data race if two threads concurrently access the same location without synchronization, and at least one of the accesses is a write. Data races typically reflect the failure of the programmer to correctly synchronize an atomic operation, and are viewed as one of the primary complications associated with developing multithreaded programs.

    We have recently developed an extended type system for Java; this system guarantees that any well-typed program is free of data races. It enables the programmer to specify the protection mechanism for each object as part of the object's type. The type can specify either the mutual exclusion lock that protects the object from unsynchronized concurrent accesses, or that threads can safely access the object without synchronization because either 1) the object is immutable, 2) the object is accessible to only the current thread and is not shared between threads, or 3) the current thread holds the unique reference to the object. The type checker uses the type declarations to verify that the program uses each object only in accordance with its declared protection mechanisms.

    The result is that programmers can aggressively remove superfluous synchronization without introducing data races. See our OOPSLA 2001 paper on this topic for more details.

• Automatic Parallelization

  Traditional parallelizing compilers uses data dependence analysis to parallelize loop nests that access dense matrices using affine access functions. While this approach works well in its target domain, it is not designed for irregular, object-based programs whose parallel tasks include the computation of many different procedures.

  We have developed a new analysis approach, commutativity analysis , that exploits the structure of the object-oriented paradigm to view the computation as consisting of operations on objects. It then analyzes the computation at this granularity to determine if operations commute (i.e. generate the same result regardless of the order in which they execute). If all of the operations in a given computation commute, the compiler can automatically generate parallel code. We have used this technique to successfully parallelize a variety of complete application programs, with the automatically parallelized versions running between 14 and 19 times faster (on a 24 processor machine) than the original sequential versions. See our TOPLAS 1997 paper on this topic for more details.

• Future Directions

  I am currently exploring ways to relate the referencing properties of objects to the changing roles that they play in the computation. Conceptually, each object's role depends, in part, on the data structures in which it participates. As the object moves between data structures, its role often changes to reflect its new relationships. We are developing dynamic analyses to discover these roles, and static analyses that verify that the program uses each object correctly in its current role. We expect to use the results to enhance the programmer's understanding of large programs and to optimize various aspects of distributed programs such as communication and failure propagation. One early result is a new type system for ensuring that multithreaded programs are free of data races. This system allows the programmer to identify how threads obtain and relinquish control of different kinds of objects, ensuring that the program observes the correct acquisition protocol for each object. See our OOPSLA 2001 paper on this topic for more details.

  In collaboration with Daniel Jackson, I am investigating ways to check that a program correctly implements high-level design properties expressed using object models. My contribution focuses on new, very precise, program analyses that leverage the design information to focus the analysis on properties of interest to the programmer. The National Science Foundation is currently supporting this research through an ITR grant.

  Finally, I have a range of Java analysis and optimization projects underway. These include the exploration of techniques for implementing Real-Time Java, space optimizations for Java programs, techniques that leverage program analysis information to provide very fast atomic transactions, and a range of memory system optimizations such as region-based allocation, elimination of write barriers, and (leveraging program analysis information about object lifetimes) explicit alloc/free optimizations.

• Other Areas

  I have also done research in hardware synthesis and credible compilation .