[Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14]

Journal of Inforamtion Science and Engineering, Vol.14 No.1, pp.237-253 (March 1998)
Efficient Run-Time Parallelization for DO Loops*

Chao-Tung Yang, Shian-Shyong Tseng+, Ming-Huei Hsieh+
and Shih-Hung Kao+
 ROCSAT Ground Segment
Nat'l. Space Program Offi.
Hsinchu, Taiwan 300, R.O.C.
+ Department of Computer and Information Science
National Chiao Tung University
Hsinchu, Taiwan 300, R. O. C.

A run-time technique based on the inspector-executor scheme is proposed in this paper to find available parallelism on loops. Our inspector can determine the wavefronts by building a DEF-USE table for each loop of a program. Additionally, the process the inspector uses to find the wavefronts can be parallelized fully without any synchronization. Our executor executes loop iterations concurrently. For each wavefront, the auto-adapted function is used to get a tailored thread number instead of using a fixed number of thread for execution. Experimental results show that our new parallel inspector can handle complex data dependency patterns and significantly reduce the execution time.

Keywords: run-time, loop parallelization, inspector, executor, parallelizing compiler, multiprocessor systems

Received April 24, 1997; revised December 5, 1997.
Communicated by PeiZong Lee.
*

  • This work was supported in part by National Science Council of the Republic of China under Grants No. NSC84-2213-E009-090 and NSC85-2213-E009-082.
  • A preliminary version of this paper, entitled "Run-time parallelization for loops," appeared in Proceedings of The 1996 Hawaii International Conference on Systems Sciences, HICSS-29, Maui, Hawaii, Vol.1, pp.233-242, Jan. 1996.