Loop Unfolding and Its Degree Determination for Multithreaded Computation

Multithreading is attractive in that it can tolerate latency and synchronization, which are the two fundamental problems for scalability in parallel architectures, by effectively overlapping communication with computation. While several compiler techniques have been developed to produce multithreaded codes from functional language programs, we can hardly find effective loop implementation for the multithreaded environment. In this paper, we will suggest a loop unfolding scheme, KU-Loop, to effectively unfold loops in the multithreaded environment. In this scheme, parallel loops are implemented more efficiently than sequential loops by effectively overlapping loop-setup with loop execution. In addition, we will suggest the 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 simulation over several benchmarks, and compare simulation results with the equations. Keywords:..