Modulo scheduling with multiple initiation intervals

Abstract

Modulo scheduling is a well defined local scheduling based software pipelining technique. One disadvantage of traditional modulo scheduling is that it has a single initiation interval (II) for loops with multiple execution paths. Thus, shorter or more frequently executed paths will be penalized by longer or less frequently executed paths. Furthermore, for architectures with predicated execution, this single-II must be large enough to satisfy the resource and recurrence requirements of all operations from all execution paths rather than the requirements of the most constrained path. In this paper, a multiple-II modulo scheduling technique is proposed for architectures with predicated execution. This enhancement to modulo scheduling maintains the benefits of a local scheduling based approach while reducing the effective II.