Partitioning and mapping nested loops on multicomputers

摘要

Minimizing interprocessor communication is the key to a parallelized program running on multicomputers. This paper addresses a compilation technique to achieve the goal of generating an efficient parallelized code with both reducing the incurred communication cost and preserving parallelism. First, we transform a nested loop into a transformed structure with supporting an evaluation function to evaluate these transformed structures to obtain a certain parallelized code with less parallel executing time. Next, a mapping strategy is proposed to map the transformed structure onto hy-percubes to be executed in parallel in a way with workload balance and low communication cost over processors.