Sheng-De Wang and Chien-Min Wang+
Department of Electrical Engineering
National Taiwan University
Taipei, Taiwan 10764, R.O.C..
+Institute of Information Science
Nankang, Taipei, Taiwan 11529, R.O.C.
In this paper, we propose compiler techniques for extracting parallelism within a nested loop. By analyzing the data dependences between statement in stances, we propose a new technique, called cycle breaking, to transform a sequential loop into parallel form. Three versions of cycle breaking are presented for extracting parallelism within nested loops. It is proved that, for a class of data dependence graphs, the proposed technique extracts more parallelism than two well-known techniques in the literature. Then, the impact of loop reordering on the parallelism extracted by cycle breaking is investigated. It is observed that the execution order of loops can dramatically affect parallelism. Methods to determine an optimal execution order of loops for a single dependence cycle are presented. These compiler techniques can greatly enhance the parallelism of a nested loop.
Keywords: compilers, data dependence graphs, loop transformations, multi-processor systems, parallel loops, parallelism extraction
Received June 16, 1991; revised November 1, 1991.
Communicated by Wen-Tsuen Chen.
*The preliminary version of this paper was presented at the First Workshop on Parallel Processing which was held at National Tsing Hua University, Hsinchu, Taiwan, in December, 1990.