From now on, all processors will consist of a large number of processing cores, and programs will run fast only if they can run in parallel on these cores. However, finding parallelism in programs is a very difficult job, and has succeeded only in limited domains like scientific computing. There have been few successes in the more general domain of irregular programs that manipulate large pointer-based data structures like graphs. The Galois project will implement and evaluate a new approach to parallelizing such irregular programs based on optimistic parallelization and a small amount of information from library writers. Preliminary results on problems like Delaunay mesh generation are very promising.
Irregular programs that manipulate pointer-based data structures are known to be difficult to parallelize. The Galois project is implementing a novel approach for optimistic parallel execution of such programs. The Galois programming model is an object-based shared-memory model. There are three main aspects to Galois: (i) a small number of syntactic constructs for packaging optimistic parallelization as data structure manipulations, (ii) assertions about methods in class libraries, and (iii) a runtime system for detecting and recovering from unsafe accesses made by an optimistic computation to shared memory. The funding for this project will be used to develop techniques for verifying class library assertions, and continuing the implementation of the Galois system.
