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. 223-236


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

  Retrieve PDF document (JISE_199801_10.pdf)