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.