Modulo-Variable Expansion Sensitive Scheduling

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

Authors

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

Abstract

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.

Download

Full Text