Modeling Multigrain Parallelism on Heterogeneous Multi-core Processors

Heterogeneous multi-core processors integrate conventional processing cores with computational accelerators. To maximize performance on these systems, programs must exploit multiple dimensions of parallelism simultaneously, including task-level and data-level parallelism. Unfortunately, parallel program designs with multiple dimensions of parallelism today are ad hoc, resulting in performance that depends heavily on the intuition and skill of the programmer. Formal techniques are needed to optimize parallel program designs. We propose a parallel computational model for steering multi-grain parallelization in heterogeneous multi-core processors. Our model accurately predicts the execution time and scalability of a program using multiple conventional processors and accelerators. The model reveals optimal degrees of multi-dimensional, task-level and data-level concurrency in parallel programs. We use the model to derive mappings of two full computational phylogenetics applications on multi-processors featuring the IBM Cell Broadband Engine.