Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

Journal of Inforamtion Science and Engineering, Vol.17 No.3, pp.463-489 (May 2001)

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


Der-Lin Pean and Cheng Chen

Department of Computer Science and Information Engineering
National Chiao Tung University
Hsinchu, Taiwan 300, R.O.C.
E-mail: dlpean@csie.nctu.edu.tw

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 dependences. Compared with other popular techniques, our scheme shows dramatic improvement in preliminary performance results.

Keywords: compilers, non-uniform dependence, loop parallelization, parallel compiler, parallel processing, region partitioning technique

Full Text () Retrieve PDF document (200105_07.pdf)

Received May 19, 1999; revised July 21, 1999; accepted November 15, 1999.
Communicated by Jang-Ping Sheu.