Height Reduction of Control Recurrences for ILP Processors

Michael Schlansker,Vinod Kathail,Sadun Anik
schlansk@hplabs.hpl.hp.com, kathail@hplabs.hpl.hp.com

Abstract

The performance of applications executing on processors with instruction level parallelism is often limited by control and data dependencies. Performance bottlenecks caused by dependencies 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 a broad range of important situations.

This paper focuses on the height reduction of control recurrences within loops with data dependent exits. Loops with exits are transformed so as to alleviate performance bottlenecks resulting from control dependencies. A compilation approach to effect these transformations is described. The techniques presented in this paper used in combination with prior work on reducing the height of data dependencies 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 the code redundancy. In more difficult cases, height reduction requires redundant computation or may not be feasible.

Talk Overheads (0 bytes)