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 levels of par-allelism simultaneously including vectorization, multithreading, and message passing. Unfortunately, hybrid parallel program designs 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 heteroge-neous multi-core processors. Our model accurately predicts the execution time and scalability of multiple threads and cores. The model reveals optimal degrees of task-level and loop-level concurrency in par-allel programs. We use the model to optimize the performance of two full computational phylogenetics applications on the IBM Cell Broadband Engine