The Program Decision Logic Approach to Predicated Execution [abstract] (ACM DL, PDF, PostScript)
David I. August, John W. Sias, Jean-Michel Puiatti, Scott A. Mahlke, Daniel A. Connors, Kevin M. Crozier, and Wen-mei W. Hwu
Proceedings of the 26th International Symposium on Computer
Architecture (ISCA), May 1999.
Modern compilers must expose sufficient amounts of
Instruction-Level Parallelism (ILP) to achieve the promised
performance increases of superscalar and VLIW processors. One of the
major impediments to achieving this goal has been inefficient
programmatic control flow. Historically, the compiler has translated
the programmer's original control structure directly into assembly
code with conditional branch instructions. Eliminating inefficiencies
in handling branch instructions and exploiting ILP has been the
subject of much research. However, traditional branch handling
techniques cannot significantly alter the program's inherent control
structure. The advent of predication as a program control
representation has enabled compilers to manipulate control in a form
more closely related to the underlying program logic. This work takes
full advantage of the predication paradigm by abstracting the program
control flow into a logical form referred to as a program decision
logic network. This network is modeled as a Boolean equation and
minimized using modified versions of logic synthesis techniques.
After minimization, the more efficient version of the program's
original control flow is re-expressed in predicated code.
Furthermore, this paper proposes extensions to the HPL PlayDoh
predication model in support of more effective predicate decision
logic network minimization. Finally, this paper shows the ability of
the mechanisms presented to overcome limits on ILP previously imposed
by rigid program control structure.