Partitioning and Mapping Techniques for Compiling Nested Loops on Hypercube Multicomputers

[[abstract]]Minimizing interprocessor communication is the key to a parallelized program on execution in 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 an n-nested loop into a k-projected structure with supporting an evaluation function to evaulate these projected structures to obtain a certain k-projected structure with less parallel executing time. Next, a mapping strategy is proposed to map the k-projected structure onto hypercubes to be executed in parallel in a way with workload balance and low communication cost amoung all of processors