Turning Predicate Information to Advantage to Improve Compiler Scheduling and Branch Prediction

Beth Simon
December 27, 2001

Architectural support for predicated execution has been proposed as a manner of attacking performance bottlenecks resulting from modern processor pipeline design. Predication is the process of removing control flow in a program and replacing it with predicate define data flow. Predication has the potential to reduce performance penalties from mispredicted branches and to make greater use of functional unit resources. However, this potential can be squandered or even turned into a performance loss if both the compiler producing the predicated code and the hardware executing the predicated code are not cognizant of the relationships between and values expressed by the predicates. In this dissertation we expose the importance of utilizing predicate information in both the compiler, for scheduling predicated code, and in the architecture for maintaining branch prediction accuracy in the face of predicated code. For the compiler, we define Predicated Static Single Assignment (PSSA). PSSA is a compiler-internal representation which maintains full-path information about predicates and their relationships. This complete information enables us to implement predicate-sensitive scheduling optimizations like predicated speculation and control height reduction that are not possible with less-complete predicate knowledge systems. In the hardware, we show the negative impact that predicate region formation can have on the predictability of branches in the program. We specifically evaluate the impact of misprediction migration -- the problem of increased mispredictions from branches located within predicated regions. We evaluate several predicate update branch prediction architectures targeted at both local and global prediction schemes with a goal of utilizing available predicate define information to restore high branch prediction accuracies.

How to view this document

The authors of these documents have submitted their reports to this technical report series for the purpose of non-commercial dissemination of scientific work. The reports are copyrighted by the authors, and their existence in electronic format does not imply that the authors have relinquished any rights. You may copy a report for scholarly, non-commercial purposes, such as research or instruction, provided that you agree to respect the author's copyright. For information concerning the use of this document for other than research or instructional purposes, contact the authors. Other information concerning this technical report series can be obtained from the Computer Science and Engineering Department at the University of California at San Diego, techreports@cs.ucsd.edu.

[ Search ]

This server operates at UCSD Computer Science and Engineering.
Send email to webmaster@cs.ucsd.edu