Program decision logic approach to predicated execution

David I. August, John W. Sias, Jean Michel Puiatti, Scott A. Mahlke, Daniel A. Connors, Kevin M. Crozier, Wen mei W Hwu

Research output: Contribution to journalArticle

13 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)208-219
Number of pages12
JournalConference Proceedings - Annual International Symposium on Computer Architecture, ISCA
StatePublished - Jan 1 1999
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Program decision logic approach to predicated execution'. Together they form a unique fingerprint.

  • Cite this

    August, D. I., Sias, J. W., Puiatti, J. M., Mahlke, S. A., Connors, D. A., Crozier, K. M., & Hwu, W. M. W. (1999). Program decision logic approach to predicated execution. Conference Proceedings - Annual International Symposium on Computer Architecture, ISCA, 208-219.