JISE


  [1] [2] [3] [4] [5] [6] [7] [8]


Journal of Information Science and Engineering, Vol. 7 No. 4, pp. 543-563


Compiler Techniques for Extracting Loop-Level Parallelism


Sheng-De Wang and Chien-Min Wang+
Department of Electrical Engineering 
National Taiwan University 
Taipei, Taiwan 10764, R.O.C.. 
+Institute of Information Science 
Academia Sinica 
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

  Retrieve PDF document (JISE_199104_05.pdf)