Profile-assisted instruction scheduling

William Y. Chen, Scott A. Mahlke, Nancy J. Warter, Sadun Anik, Wen-Mei W Hwu

Research output: Contribution to journalArticle

Abstract

Instruction schedulers for superscalar and VLIW processors must expose sufficient instruction-level parallelism to the hardware in order to achieve high performance. Traditional compiler instruction scheduling techniques typically take into account the constraints imposed by all execution scenarios in the program. However, there are additional opportunities to increase instruction-level parallelism for the frequent execution scenarios at the expense of the less freuent ones. Profile information identifies these important execution scenarios in a program. In this paper, two major categories of profile information are studied: control-flow and memory-dependence. Profile-assisted code scheduling techniques have been incorporated into the IMPACT-I compiler. These techniques are acyclic global scheduling and software pipelining. This paper describes the scheduling algorithms, highlights the modifications required to use profile information, and explains the hardware and compiler support for dealing with hazards that arise from aggressive use of profile information. The effectiveness of these profile-based scheduling techniques is evaluated for a range of superscalar and VLIW processors.

Original languageEnglish (US)
Pages (from-to)151-181
Number of pages31
JournalInternational Journal of Parallel Programming
Volume22
Issue number2
DOIs
StatePublished - Apr 1 1994

Fingerprint

Instruction Scheduling
Scheduling
Compiler
Superscalar
Instruction Level Parallelism
Hardware
Scenarios
Information use
Scheduling algorithms
Software pipelining
Flow control
Hazards
Flow Control
Scheduler
Scheduling Algorithm
Data storage equipment
Hazard
Profile
High Performance
Sufficient

Keywords

  • Instruction scheduling
  • profile information

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Cite this

Profile-assisted instruction scheduling. / Chen, William Y.; Mahlke, Scott A.; Warter, Nancy J.; Anik, Sadun; Hwu, Wen-Mei W.

In: International Journal of Parallel Programming, Vol. 22, No. 2, 01.04.1994, p. 151-181.

Research output: Contribution to journalArticle

Chen, William Y. ; Mahlke, Scott A. ; Warter, Nancy J. ; Anik, Sadun ; Hwu, Wen-Mei W. / Profile-assisted instruction scheduling. In: International Journal of Parallel Programming. 1994 ; Vol. 22, No. 2. pp. 151-181.
@article{cb222274cbd4422eb6ad94fd42d1aeaa,
title = "Profile-assisted instruction scheduling",
abstract = "Instruction schedulers for superscalar and VLIW processors must expose sufficient instruction-level parallelism to the hardware in order to achieve high performance. Traditional compiler instruction scheduling techniques typically take into account the constraints imposed by all execution scenarios in the program. However, there are additional opportunities to increase instruction-level parallelism for the frequent execution scenarios at the expense of the less freuent ones. Profile information identifies these important execution scenarios in a program. In this paper, two major categories of profile information are studied: control-flow and memory-dependence. Profile-assisted code scheduling techniques have been incorporated into the IMPACT-I compiler. These techniques are acyclic global scheduling and software pipelining. This paper describes the scheduling algorithms, highlights the modifications required to use profile information, and explains the hardware and compiler support for dealing with hazards that arise from aggressive use of profile information. The effectiveness of these profile-based scheduling techniques is evaluated for a range of superscalar and VLIW processors.",
keywords = "Instruction scheduling, profile information",
author = "Chen, {William Y.} and Mahlke, {Scott A.} and Warter, {Nancy J.} and Sadun Anik and Hwu, {Wen-Mei W}",
year = "1994",
month = "4",
day = "1",
doi = "10.1007/BF02577873",
language = "English (US)",
volume = "22",
pages = "151--181",
journal = "International Journal of Parallel Programming",
issn = "0885-7458",
publisher = "Springer New York",
number = "2",

}

TY - JOUR

T1 - Profile-assisted instruction scheduling

AU - Chen, William Y.

AU - Mahlke, Scott A.

AU - Warter, Nancy J.

AU - Anik, Sadun

AU - Hwu, Wen-Mei W

PY - 1994/4/1

Y1 - 1994/4/1

N2 - Instruction schedulers for superscalar and VLIW processors must expose sufficient instruction-level parallelism to the hardware in order to achieve high performance. Traditional compiler instruction scheduling techniques typically take into account the constraints imposed by all execution scenarios in the program. However, there are additional opportunities to increase instruction-level parallelism for the frequent execution scenarios at the expense of the less freuent ones. Profile information identifies these important execution scenarios in a program. In this paper, two major categories of profile information are studied: control-flow and memory-dependence. Profile-assisted code scheduling techniques have been incorporated into the IMPACT-I compiler. These techniques are acyclic global scheduling and software pipelining. This paper describes the scheduling algorithms, highlights the modifications required to use profile information, and explains the hardware and compiler support for dealing with hazards that arise from aggressive use of profile information. The effectiveness of these profile-based scheduling techniques is evaluated for a range of superscalar and VLIW processors.

AB - Instruction schedulers for superscalar and VLIW processors must expose sufficient instruction-level parallelism to the hardware in order to achieve high performance. Traditional compiler instruction scheduling techniques typically take into account the constraints imposed by all execution scenarios in the program. However, there are additional opportunities to increase instruction-level parallelism for the frequent execution scenarios at the expense of the less freuent ones. Profile information identifies these important execution scenarios in a program. In this paper, two major categories of profile information are studied: control-flow and memory-dependence. Profile-assisted code scheduling techniques have been incorporated into the IMPACT-I compiler. These techniques are acyclic global scheduling and software pipelining. This paper describes the scheduling algorithms, highlights the modifications required to use profile information, and explains the hardware and compiler support for dealing with hazards that arise from aggressive use of profile information. The effectiveness of these profile-based scheduling techniques is evaluated for a range of superscalar and VLIW processors.

KW - Instruction scheduling

KW - profile information

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

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

U2 - 10.1007/BF02577873

DO - 10.1007/BF02577873

M3 - Article

AN - SCOPUS:0028409599

VL - 22

SP - 151

EP - 181

JO - International Journal of Parallel Programming

JF - International Journal of Parallel Programming

SN - 0885-7458

IS - 2

ER -