An Optimized Three Region Partitioning Technique to Maximize Parallelism of Nested Loops With Non-uniform Dependences

摘要

There are many methods for nested loop partitioning exist; however, most of them perform poorly when they partition loops with non-uniform dependences. This paper proposes a generalized and optimized loop partitioning mechanism which can exploit parallelism in nested loops with non-uniform dependences. Our approach based on the region partitioning technique divides the loop into variable size partitions. Furthermore, the proposed algorithm partitions a nested loop using the copy-renaming and optimized partitioning techniques so as to minimize the serial part of the iteration space. Thus, it out performs previous partition mechanisms for nested loops with non-uniform depend- ences. Compared with other popular techniques, our scheme shows dramatic improve- ment in preliminary performance results.