HyperLink   The Benefit of Predicated Execution for Software Pipelining.
Publication Year:
  Nancy J. Warter, Daniel M. Lavery, Wen-mei Hwu
  Proceedings of the 26th Annual Hawaii Int'l Conference on system Sciences, Wailea, pp 497-506, Hawaii, Jan. 5-8, 1993

Software pipelining is a compile-time scheduling technique that overlaps successive loop iterations to expose operation- level parallelism. An important problem with the development of effective software pipelining algorithms is how to handle loops with conditional branches. Conditional branches increase the complexity and decrease the effectiveness of software pipelining algorithms by introducing many possible execution paths into the scheduling scope. This paper presents an empirical study of the importance of an architectural support, referred to as predicated execution, on the effectiveness of software pipelining. In order to perform an in-depth analysis, we focus on Rau's modulo scheduling algorithm for software pipelining. Three versions of the modulo scheduling algorithm, one with and two without predicated execution support, are implemented in a prototype compiler. Experiments based on important loops from numeric applications show that predicated execution support substantially improve the effectiveness of the modulo scheduling algorithm.