Lang-Sheng Liu, Chin-Wen Ho and Jang-Ping Sheu
Department of Electrical Engineering
National Central University
Chung-Li 32054, Taiwan, R.O.C.
From execution time analysis of programs, nested loops are often the most time-consuming part and the main source of parallelism. In this paper, an index shift method is proposed to improve the parallelism of nested loops with only slight modification to original programs. The idea behind this index shift method is to defer or advance the execution steps of some statements such that the parallelism of the loops can be increased under the Hyperplane method. Based on this method, an algorithm, under the assumption that a time function is fixed, is devised to improve the parallelism of nested loops.
Keywords: hyperplane method, nested loops, parallel processing, systolic arrays
Received May 10, 1991; revised November 1, 1991.
Communicated by Wen-Tsuen Chen.
*This work was supported by the National Science Council under Grant NSC 79-0408-E-008-04.