HP Labs Technical Reports

Parallelization of Control Recurrences for ILP Processors

Schlansker, Michael S.; Kathail, Vinod; Anik, Sadun

HPL-94-75

Keyword(s):

Abstract: The performance of applications executing on processors with instruction level parallelism is often limited by control and data dependences. Performance bottlenecks caused by dependences can frequently be eliminated through transformations which reduce the height of critical paths through the program. While height reduction techniques are not always helpful, their utility can be demonstrated in an increasingly broad range of important situations. This report focuses on the height reduction of control recurrences within loops with data dependent exits. Loops with data dependent exits are trasformed so as to dependences. A compilation approach to effect these transformations is described. The techniques presented in this report used in combination with prior work on reducing the height of data dependences provide a comprehensive approach to accelerating loops with conditional exits. In many cases, loops with conditional exits provide a degree of parallelism traditionally associated with vectorization. Multiple iterations of a loop can be retired in a single cycle on a processor with adequate instruction level parallelism with no cost in code redundancy. In more difficult cases, height reduction requires redundant computation or may not be feasible.

Back to Index