Optimistic parallelism requires abstractions
Authors:
Open Access
- 10 June 2007
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 211-222
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.Keywords
This publication has 31 references indexed in Scilit:
- Transactional collection classes2007
- LightcutsACM Transactions on Graphics, 2005
- Multigrain parallel Delaunay Mesh generation2005
- Language support for lightweight transactions2003
- An Algorithm for Three-Dimensional Mesh Generation for Arbitrary Regions with CracksEngineering with Computers, 2001
- The LRPD test: speculative run-time parallelization of loops with privatization and reduction parallelizationIEEE Transactions on Parallel and Distributed Systems, 1999
- Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator1996
- Commutativity-based concurrency control for abstract data typesIEEE Transactions on Computers, 1988
- Virtual timeACM Transactions on Programming Languages and Systems, 1985
- Multidimensional binary search trees used for associative searchingCommunications of the ACM, 1975