Exposing Parallelism and Locality in a Runtime Parallel Optimization Framework [abstract] (DOI, PDF)
David A. Penry, Daniel J. Richins, Tyler S. Harris, David Greenland, and Koy D. Rehme
Proceedings of the 2010 ACM International Conference on Computing Frontiers (CF), May 2010.

The widespread use of tens to hundreds of processor cores in commodity systems will require widespread deployment of parallel applications. Despite advances in parallel programming models, it seems unlikely that the average programmer will be able to negotiate the twin shoals of understanding how to map parallelism well on a particular architecture and the likelihood that the particular architecture will not even be known at development time. Furthermore, for many important applications, a good mapping depends upon data or application characteristics not known until runtime.

Runtime parallel optimization has been suggested as a means to overcome these difficulties. For runtime parallel optimization to be effective, parallelism and locality which are expressed in the programming model need to be communicated to the runtime system. We suggest that the compiler should expose this information to the runtime using a representation which is independent of the programming model. We term such a representation an exposed parallelism and locality (EPL) representation. An EPL representation allows a single runtime environment to support many different models and architectures and to perform automatic parallelization optimization.

In order to accomplish these goals, an EPL representation needs to be task-based, multi-relational, hierarchical, and concise. This paper describes these four properties. It also presents an optimizing runtime, ADOPAR, which uses an EPL representation.