Statement-Level Communication-Free Hyperplane Partitioning Techniques for Parallelizing Compilers on Multicomputers

This paper addresses the problems of communication -free partitions of statement-iterations of nested loops and data accessed by these statement-iterations. Communication-free hyperplane partitions of disjoint subsets of data and statement-iterations are considered. This approach is more possible than existing methods in finding the data and program distribution patterns that can cause the processor fully-parallel execution without any interprocessor communication. In addition, this approach can be applied to the more general loop models such as the imperfectly nested loop or multiple imperfectly nested loops, not like most of the existing methods that can be applied only to the perfectly nested loop or multiple perfectly nested loops. Due to the limitation of space, this paper only proposes the compilation technique of statement-level communication-free hyperplane partitioning for a perfectly nested loop. Keywords: Communication-free partitioning, data distribution, data locality, hy..