Lab for High Performance Computing SERC, Indian Institute of Science
Home | People | Research | Awards/Honours | Publications | Lab Resources | Gallery | Contact Info | Sponsored Research
Tech. Reports | Conferences / Journals | Theses / Project Reports

Modulo-Variable Expansion Sensitive Scheduling

Proceedings of the 5th International Conference on High-Performance Computing (HiPC-98)
Chennai, India, December 1998


  1. Madhavi G. Valluri, Supercomputer Education and Research Center
  2. R. Govindarajan, Supercomputer Education and Research Centre; Department of Computer Science and Automation


Modulo scheduling is an aggressive scheduling technique for loops that exploits instruction-level parallelism by overlapping successive iterations of the loop. Due to the nature of modulo scheduling, the lifetime of a variable can overlap with a subsequent definition of itself. To handle such overlapping lifetimes, modulo-variable expansion (MVE) is used, wherein the constructed schedule is unrolled a number of times.

In this paper we propose a technique to improve the constructed schedule while performing MVE. In our approach, we unroll the data dependence graph of the original loop and re-schedule it with a MVE-sensitive scheduler. Such an approach is expected to result in better initiation rates as compared to the traditional approach. We have implemented our approach and evaluated its performance on a large number of scientific benchmark kernels.

This paper won the Best Paper award at the conference.


Full Text