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 journalConference article

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
EventProceedings of the 1999 26th Annual International Symposium on Computer Architecture - ISCA '99 - Atlanta, GA, USA
Duration: May 2 1999May 4 1999

Fingerprint

Flow control

ASJC Scopus subject areas

  • Hardware and Architecture

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.

Program decision logic approach to predicated execution. / August, David I.; Sias, John W.; Puiatti, Jean Michel; Mahlke, Scott A.; Connors, Daniel A.; Crozier, Kevin M.; Hwu, Wen mei W.

In: Conference Proceedings - Annual International Symposium on Computer Architecture, ISCA, 01.01.1999, p. 208-219.

Research output: Contribution to journalConference article

August DI, Sias JW, Puiatti JM, Mahlke SA, Connors DA, Crozier KM et al. Program decision logic approach to predicated execution. Conference Proceedings - Annual International Symposium on Computer Architecture, ISCA. 1999 Jan 1;208-219.
August, David I. ; Sias, John W. ; Puiatti, Jean Michel ; Mahlke, Scott A. ; Connors, Daniel A. ; Crozier, Kevin M. ; Hwu, Wen mei W. / Program decision logic approach to predicated execution. In: Conference Proceedings - Annual International Symposium on Computer Architecture, ISCA. 1999 ; pp. 208-219.
@article{86fc06d671e64340939fbe839b399a81,
title = "Program decision logic approach to predicated execution",
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.",
author = "August, {David I.} and Sias, {John W.} and Puiatti, {Jean Michel} and Mahlke, {Scott A.} and Connors, {Daniel A.} and Crozier, {Kevin M.} and Hwu, {Wen mei W.}",
year = "1999",
month = "1",
day = "1",
language = "English (US)",
pages = "208--219",
journal = "Conference Proceedings - Annual International Symposium on Computer Architecture, ISCA",
issn = "1063-6897",
publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - JOUR

T1 - Program decision logic approach to predicated execution

AU - August, David I.

AU - Sias, John W.

AU - Puiatti, Jean Michel

AU - Mahlke, Scott A.

AU - Connors, Daniel A.

AU - Crozier, Kevin M.

AU - Hwu, Wen mei W.

PY - 1999/1/1

Y1 - 1999/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0032672878&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032672878&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:0032672878

SP - 208

EP - 219

JO - Conference Proceedings - Annual International Symposium on Computer Architecture, ISCA

JF - Conference Proceedings - Annual International Symposium on Computer Architecture, ISCA

SN - 1063-6897

ER -