Modeling Multigrain Parallelism on Heterogeneous Multi-Core Processors: A Case Study of the Cell BE

Heterogeneous multi-core processors invest the most significant portion of their transistor budget in customized "Accelerator" cores, while using a small number of conventional low-end cores for supplying computation to accelerators. To maximize performance on heterogeneous multi-core processors, programs need to expose multiple dimensions of parallelism simultaneously. Unfortunately, programming with multiple dimensions of parallelism is to date an ad hoc process, relying heavily on the intuition and skill of programmers. Formal techniques are needed to optimize multi-dimensional parallel program designs. This paper presents a model of multi-dimensional parallel computation for steering the parallelization process on heterogeneous multi-core processors.