Program Decision Logic Optimization Using Predication and Control Speculation

Wen Mei W. Hwu, David I. August, John W. Sias

Research output: Contribution to journalArticle

Abstract

The mainstream arrival of predication, a means other than branching of selecting instructions for execution, has required compiler architects to reformulate fundamental analyses and transformations. Traditionally, the compiler has generated branches straightforwardly to implement control flow designed by the programmer and has then performed sophisticated “global” optimizations to move and optimize code around them. In this model, the inherent tie between the control state of the program and the location of the single instruction pointer serialized run-time evaluation of control and limited the extent to which the compiler could optimize the control structure of the program (without extensive code replication). Predication provides a means of control independent of branches and instruction fetch location, freeing both compiler and architecture from these restrictions; effective compilation of predicated code, however, requires sophisticated understanding of the program's control structure. This paper explores a representational technique which, through direct code analysis, maps the program's control component into a canonical database, a reduced ordered binary decision diagram (ROBDD), which fully enables the compiler to utilize and manipulate predication. This abstraction is then applied to optimize the program's control component, transforming it into a form more amenable to instruction level parallel (ILP) execution.

Original languageEnglish (US)
Pages (from-to)1660-1675
Number of pages16
JournalProceedings of the IEEE
Volume89
Issue number11
DOIs
StatePublished - Nov 2001

Fingerprint

Binary decision diagrams
Global optimization
Flow control

Keywords

  • Boolean functions
  • Computer architecture
  • Instruction level parallelism
  • Optimization compilers
  • Predication

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Cite this

Program Decision Logic Optimization Using Predication and Control Speculation. / Hwu, Wen Mei W.; August, David I.; Sias, John W.

In: Proceedings of the IEEE, Vol. 89, No. 11, 11.2001, p. 1660-1675.

Research output: Contribution to journalArticle

Hwu, Wen Mei W. ; August, David I. ; Sias, John W. / Program Decision Logic Optimization Using Predication and Control Speculation. In: Proceedings of the IEEE. 2001 ; Vol. 89, No. 11. pp. 1660-1675.
@article{665bff38427047b786da63508a6dbb4f,
title = "Program Decision Logic Optimization Using Predication and Control Speculation",
abstract = "The mainstream arrival of predication, a means other than branching of selecting instructions for execution, has required compiler architects to reformulate fundamental analyses and transformations. Traditionally, the compiler has generated branches straightforwardly to implement control flow designed by the programmer and has then performed sophisticated “global” optimizations to move and optimize code around them. In this model, the inherent tie between the control state of the program and the location of the single instruction pointer serialized run-time evaluation of control and limited the extent to which the compiler could optimize the control structure of the program (without extensive code replication). Predication provides a means of control independent of branches and instruction fetch location, freeing both compiler and architecture from these restrictions; effective compilation of predicated code, however, requires sophisticated understanding of the program's control structure. This paper explores a representational technique which, through direct code analysis, maps the program's control component into a canonical database, a reduced ordered binary decision diagram (ROBDD), which fully enables the compiler to utilize and manipulate predication. This abstraction is then applied to optimize the program's control component, transforming it into a form more amenable to instruction level parallel (ILP) execution.",
keywords = "Boolean functions, Computer architecture, Instruction level parallelism, Optimization compilers, Predication",
author = "Hwu, {Wen Mei W.} and August, {David I.} and Sias, {John W.}",
year = "2001",
month = "11",
doi = "10.1109/5.964444",
language = "English (US)",
volume = "89",
pages = "1660--1675",
journal = "Proceedings of the IEEE",
issn = "0018-9219",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "11",

}

TY - JOUR

T1 - Program Decision Logic Optimization Using Predication and Control Speculation

AU - Hwu, Wen Mei W.

AU - August, David I.

AU - Sias, John W.

PY - 2001/11

Y1 - 2001/11

N2 - The mainstream arrival of predication, a means other than branching of selecting instructions for execution, has required compiler architects to reformulate fundamental analyses and transformations. Traditionally, the compiler has generated branches straightforwardly to implement control flow designed by the programmer and has then performed sophisticated “global” optimizations to move and optimize code around them. In this model, the inherent tie between the control state of the program and the location of the single instruction pointer serialized run-time evaluation of control and limited the extent to which the compiler could optimize the control structure of the program (without extensive code replication). Predication provides a means of control independent of branches and instruction fetch location, freeing both compiler and architecture from these restrictions; effective compilation of predicated code, however, requires sophisticated understanding of the program's control structure. This paper explores a representational technique which, through direct code analysis, maps the program's control component into a canonical database, a reduced ordered binary decision diagram (ROBDD), which fully enables the compiler to utilize and manipulate predication. This abstraction is then applied to optimize the program's control component, transforming it into a form more amenable to instruction level parallel (ILP) execution.

AB - The mainstream arrival of predication, a means other than branching of selecting instructions for execution, has required compiler architects to reformulate fundamental analyses and transformations. Traditionally, the compiler has generated branches straightforwardly to implement control flow designed by the programmer and has then performed sophisticated “global” optimizations to move and optimize code around them. In this model, the inherent tie between the control state of the program and the location of the single instruction pointer serialized run-time evaluation of control and limited the extent to which the compiler could optimize the control structure of the program (without extensive code replication). Predication provides a means of control independent of branches and instruction fetch location, freeing both compiler and architecture from these restrictions; effective compilation of predicated code, however, requires sophisticated understanding of the program's control structure. This paper explores a representational technique which, through direct code analysis, maps the program's control component into a canonical database, a reduced ordered binary decision diagram (ROBDD), which fully enables the compiler to utilize and manipulate predication. This abstraction is then applied to optimize the program's control component, transforming it into a form more amenable to instruction level parallel (ILP) execution.

KW - Boolean functions

KW - Computer architecture

KW - Instruction level parallelism

KW - Optimization compilers

KW - Predication

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

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

U2 - 10.1109/5.964444

DO - 10.1109/5.964444

M3 - Article

AN - SCOPUS:33646905963

VL - 89

SP - 1660

EP - 1675

JO - Proceedings of the IEEE

JF - Proceedings of the IEEE

SN - 0018-9219

IS - 11

ER -