Optimistic Parallelism Requires Abstractions

Milind Kulkarni, Keshav Pingali, Bruce Walter, Ganesh Ramanarayanan, Kavita Bala, and Paul Chew

CACM 2009 · Communications of the ACM · 52(9):89-97 · Research Highlights · September 2009

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 structures like graphs, has seemed intractable.

The Galois project is taking a fresh look at auto-parallelization. Rather than attempt to parallelize all programs no matter how obscurely they are written, we are designing programming abstractions that permit programmers 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 refinement application and a graphics application that performs agglomerative clustering, demonstrate that this approach is promising.

BibTeX

@article{kulkarni09cacm,
  author    = {Milind Kulkarni and Keshav Pingali and Bruce Walter and Ganesh Ramanarayanan and Kavita Bala and Paul Chew},
  title     = {Optimistic Parallelism Requires Abstractions},
  journal   = {Communications of the ACM},
  volume    = {52},
  number    = {9},
  pages     = {89--97},
  publisher = {ACM},
  year      = {2009},
  month     = sep,
  doi       = {10.1145/1562164.1562188}
}