JISE

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

Journal of Information Science and Engineering, Vol. 14 No. 1, pp. 237-253

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

Retrieve PDF document (JISE_199801_11.pdf)