Optimistic parallelism requires abstractions

Authors:

Abstract
The problem of writing software for multicore processors is greatly simplified if we could automatically parallelize sequential programs. Although auto-parallelization has been studied for many decades, it has succeeded only in a few application areas such as dense matrix computations. In particular, auto-parallelization of irregular programs, which are organized around large, pointer-based data struc- tures like graphs, has seemed intractable. The Galois project is taking a fresh look at auto- parallelization. Rather than attempt to parallelize all pro- grams no matter how obscurely they are written, we are designing programming abstractions that permit program- mers to highlight opportunities for exploiting parallelism in sequential programs, and building a runtime system that uses these hints to execute the program in parallel. In this paper, we describe the design and implementation of a system based on these ideas. Experimental results for two real-world irregular applications, a Delaunay mesh refine- ment application and a graphics application that performs agglomerative clustering, demonstrate that this approach is promising.

This publication has 31 references indexed in Scilit: