Modulo scheduling of loops in control-intensive non-numeric programs

Daniel M. Lavery, Wen-Mei W Hwu

Research output: Contribution to journalConference articlepeer-review

Abstract

Much of the previous work on modulo scheduling has targeted numeric programs, in which, often, the majority of the loops are well-behaved loop-counter-based loops without early exits. In control-intensive non-numeric programs, the loops frequently have characteristics that make it more difficult to effectively apply modulo scheduling. These characteristics include multiple control flow paths, loops that are not based on a loop counter, and multiple exits. In these loops, the presence of unimportant paths with high resource usage or long dependence chains can penalize the important paths. A path that contains a hazard such as another nested loop can prohibit modulo scheduling of the loop. Control dependences can severely restrict the overlap of the blocks within and across iterations. This paper describes a set of methods that allow effective modulo scheduling of loops with multiple exits. The techniques include removal of control dependences to enable speculation, extensions to modulo variable expansion, and a new epilogue generation scheme. These methods can be used with superblock and hyperblock techniques to allow modulo scheduling of the selected paths of loops with arbitrary control flow. A case study is presented to show how these methods, combined with superblock techniques, enable modulo scheduling to be effectively applied to control-intensive non-numeric programs. Performance results for several SPEC CINT92 benchmarks and Unix utility programs are reported and demonstrate the applicability of modulo scheduling to this class of programs.

Original languageEnglish (US)
Pages (from-to)126-137
Number of pages12
JournalProceedings of the Annual International Symposium on Microarchitecture
StatePublished - Dec 1 1996
EventProceedings of the 1996 29th Annual IEEE/ACM International Symposium on Microarchitecture, MICRO-29 - Paris, Fr
Duration: Dec 2 1996Dec 4 1996

ASJC Scopus subject areas

  • Hardware and Architecture
  • Software

Fingerprint Dive into the research topics of 'Modulo scheduling of loops in control-intensive non-numeric programs'. Together they form a unique fingerprint.

Cite this