Partial reverse if-conversion framework for balancing control flow and predication

David I. August, Wen-Mei W Hwu, Scott A. Mahlke

Research output: Contribution to journalArticle

Abstract

Predicated execution is a promising architectural feature for exploiting instruction-level parallelism in the presence of control flow. Compiling for predicated execution involves converting program control flow into conditional, or predicated, instructions. This process is known as if-conversion. In order to apply if-conversion effectively, one must address two major issues: what should be if-converted and when the if-conversion should be performed. A compiler's use of predication as a representation is most effective when large amounts of code are if-converted and when if-conversion is performed early in the compilation procedure. On the other hand, efficient execution of code generated for a processor with predicated execution requires a delicate balance between control flow and predication. The appropriate balance is tightly coupled with scheduling decisions and detailed processor characteristics. This paper presents a compilation framework based on partial reverse if-conversion that allows the compiler to maximize the benefits of predication as a compiler representation while delaying the final balancing of control flow and predication to schedule time.

Original languageEnglish (US)
Pages (from-to)381-423
Number of pages43
JournalInternational Journal of Parallel Programming
Volume27
Issue number5
DOIs
StatePublished - Jan 1 1999

Fingerprint

Flow Control
Flow control
Balancing
Reverse
Partial
Compiler
Compilation
Instruction Level Parallelism
Scheduling
Schedule
Maximise
Framework

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Information Systems

Cite this

Partial reverse if-conversion framework for balancing control flow and predication. / August, David I.; Hwu, Wen-Mei W; Mahlke, Scott A.

In: International Journal of Parallel Programming, Vol. 27, No. 5, 01.01.1999, p. 381-423.

Research output: Contribution to journalArticle

@article{bb9ed20467974d8c8ab24ad5e0fe5238,
title = "Partial reverse if-conversion framework for balancing control flow and predication",
abstract = "Predicated execution is a promising architectural feature for exploiting instruction-level parallelism in the presence of control flow. Compiling for predicated execution involves converting program control flow into conditional, or predicated, instructions. This process is known as if-conversion. In order to apply if-conversion effectively, one must address two major issues: what should be if-converted and when the if-conversion should be performed. A compiler's use of predication as a representation is most effective when large amounts of code are if-converted and when if-conversion is performed early in the compilation procedure. On the other hand, efficient execution of code generated for a processor with predicated execution requires a delicate balance between control flow and predication. The appropriate balance is tightly coupled with scheduling decisions and detailed processor characteristics. This paper presents a compilation framework based on partial reverse if-conversion that allows the compiler to maximize the benefits of predication as a compiler representation while delaying the final balancing of control flow and predication to schedule time.",
author = "August, {David I.} and Hwu, {Wen-Mei W} and Mahlke, {Scott A.}",
year = "1999",
month = "1",
day = "1",
doi = "10.1023/A:1018787007582",
language = "English (US)",
volume = "27",
pages = "381--423",
journal = "International Journal of Parallel Programming",
issn = "0885-7458",
publisher = "Springer New York",
number = "5",

}

TY - JOUR

T1 - Partial reverse if-conversion framework for balancing control flow and predication

AU - August, David I.

AU - Hwu, Wen-Mei W

AU - Mahlke, Scott A.

PY - 1999/1/1

Y1 - 1999/1/1

N2 - Predicated execution is a promising architectural feature for exploiting instruction-level parallelism in the presence of control flow. Compiling for predicated execution involves converting program control flow into conditional, or predicated, instructions. This process is known as if-conversion. In order to apply if-conversion effectively, one must address two major issues: what should be if-converted and when the if-conversion should be performed. A compiler's use of predication as a representation is most effective when large amounts of code are if-converted and when if-conversion is performed early in the compilation procedure. On the other hand, efficient execution of code generated for a processor with predicated execution requires a delicate balance between control flow and predication. The appropriate balance is tightly coupled with scheduling decisions and detailed processor characteristics. This paper presents a compilation framework based on partial reverse if-conversion that allows the compiler to maximize the benefits of predication as a compiler representation while delaying the final balancing of control flow and predication to schedule time.

AB - Predicated execution is a promising architectural feature for exploiting instruction-level parallelism in the presence of control flow. Compiling for predicated execution involves converting program control flow into conditional, or predicated, instructions. This process is known as if-conversion. In order to apply if-conversion effectively, one must address two major issues: what should be if-converted and when the if-conversion should be performed. A compiler's use of predication as a representation is most effective when large amounts of code are if-converted and when if-conversion is performed early in the compilation procedure. On the other hand, efficient execution of code generated for a processor with predicated execution requires a delicate balance between control flow and predication. The appropriate balance is tightly coupled with scheduling decisions and detailed processor characteristics. This paper presents a compilation framework based on partial reverse if-conversion that allows the compiler to maximize the benefits of predication as a compiler representation while delaying the final balancing of control flow and predication to schedule time.

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

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

U2 - 10.1023/A:1018787007582

DO - 10.1023/A:1018787007582

M3 - Article

AN - SCOPUS:0033334647

VL - 27

SP - 381

EP - 423

JO - International Journal of Parallel Programming

JF - International Journal of Parallel Programming

SN - 0885-7458

IS - 5

ER -