Here, There Be Dragons: Beyond the Polyhedral Model
Keshav Pingali
Department of Computer Science
and
Institute for Computational Engineering and Science
University of Texas at Austin
The programming languages research community has worked on static
parallelization of programs for almost 50 years, and at this point, we have
an impressive array of analysis techniques and restructuring tools,
many of them based on the polyhedral model. Nevertheless, in spite of
successes in some domains like dense linear algebra, this approach
has not been successful in attacking the multicore software problem.
I believe that to rise to the multicore challenge, our community must
rethink some fundamental assumptions that we make about parallelism in
programs. In particular, I will argue that our current program-centric
abstractions like dependence graphs are inadequate, and propose a new
theory of parallelism in programs, based on a data-centric foundation
called the operator formulation of algorithms. This new approach
reveals that (i) a generalized form of data-parallelism called
amorphous data-parallelism is ubiquitous in applications, but (ii)
depending on the structure of the algorithm, techniques ranging from
optimistic parallelization to static parallelization may be needed
to exploit this parallelism. The operator formulation also leads to a simple
classification of algorithms that provides guidance for which techniques
may be needed to parallelize a particular algorithm. Finally, I will
describe a system based on these ideas called Galois for programming
multicore processors.