MIT Department of Electrical Engineering & Computer Science

E E C S

Commutativity Analysis: A New Analysis Technique for Parallelizing Compilers

Martin Rinard
University of California at Santa Barbara

Thursday, May 1, 1997
3:00 PM (2:45 refreshments)
Room NE43-518
EECS Special Seminar

Abstract

Parallel computing is an attractive and potentially important source of performance for a wide range of applications in many areas of computer science. The difficulty of developing parallel software, however, has limited the ability of developers to exploit the full potential of parallel computing. In principle, a parallelizing compiler (a compiler that accepts a sequential program and automatically produces a parallel program that generates the same result) would eliminate many of the obstacles that currently hamper the development of efficient and correct parallel software. But current analysis techniques for parallelizing compilers work well only for a limited set of computations: loops that access dense matrices using affine access functions.

This talk presents a new analysis technique, commutativity analysis, that is designed to automatically parallelize a new class of computations: object-based computations that manipulate dynamic, linked data structures such as trees and graphs. In the first part of the talk, I will present the basic analysis technique, describe some extensions that are required to apply the technique to practical programs, and discuss how commutativity analysis differs from traditional analysis techniques for parallelizing compilers.

In the second part of the talk, I will discuss optimizations required to map the parallelized programs efficiently onto parallel machines. I will focus on synchronization optimizations for programs that use mutual exclusion synchronization. Although these optimizations were developed in the context of our prototype compiler, they are generally applicable to a wide range of parallel programs. I will present experimental results that characterize both the overall performance of several automatically parallelized benchmark programs and the performance impact of the synchronization optimizations on these programs.

Finally, I will briefly discuss potential applications of commutativity analysis to programs such as servers and migratory programs that have not traditionally been considered targets for automatic parallelization.

URL of this page: http://www-eecs.mit.edu/AY96-97/events/48.html
Created: Apr 28, 1997 | Modified: Jun 24, 1997
This announcement is from the MIT EECS 1996-97 archive. | Current events
To MIT EECS home page | Your comments and inquiries are welcome.