[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.223-236 (March 1998)
KU-Loop Scheme: An Efficient Loop Unfolding
Scheme for Multithreaded Computation*

Sangho Ha and Heunghwan Kim+
Department of Computer Science
Soonchunghyang University
Asan 336-745, Korea
+ Department of Computer Science
Cheongju 360-742, Korea

Multithreading is attractive in that it can tolerate latency and synchronization by effectively overlapping communication with computation. While several compiler techniques have been developed to produce multithreaded codes from functional language programs, it is very difficult to find effective loop implementation for multithreaded computation. In this paper, we will suggest a loop unfolding scheme, KU-Loop. In this scheme, parallel loops can be implemented more efficiently than sequential loops by effectively overlapping loop-setup with loop execution. In addition, we suggest equations to statically approximate the optimal loop unfolding degree for each loop class using profile information. Finally, we will analyze our loop unfolding scheme by means of simulation over several benchmarks and compare simulation results with the results of the equations.

Keywords: multithreading, loop unfolding, loop unfolding degree, synchronization, communication

Received May 1, 1997; revised November 20, 1997.
Communicated by Chung-Ta King.
* This paper was supported by the Korea Science & Engineering Foundation.