The Importance of Prepass Code Scheduling for Superscalar and Superpipelined Processors

Pohua P. Chang, Daniel M. Lavery, Scott A. Mahlke, William Y. Chen, Wen mei W. Hwu

Research output: Contribution to journalArticle

Abstract

Superscalar and superpipelined processors utilize parallelism to achieve peak performance that can be several times higher than that of conventional scalar processors. In order for this potential to be translated into the speedup of real programs, the compiler must be able to schedule instructions so that the parallel hardware is effectively utilized. Previous work has shown that prepass code scheduling helps to produce a better schedule for scientific programs, but the importance of prescheduling has never been demonstrated for control-intensive non-numeric programs. These programs are significantly different from the scientific programs because they contain frequent branches. The compiler must do global scheduling in order to find enough independent instructions. In this paper, the code optimizer and scheduler of the IMPACT-I C compiler is described. Within this framework, we study the importance of prepass code scheduling for a set of production C programs. It is shown that, in contrast to the results previously obtained for scientific programs, prescheduling is not important for compiling control-intensive programs to the current generation of superscalar and superpipelined processors. However, if some of the current restrictions on upward code motion can be removed in future architectures, prescheduling would substantially improve the execution time of this class of programs on both superscalar and superpipelined processors.

Original languageEnglish (US)
Pages (from-to)353-370
Number of pages18
JournalIEEE Transactions on Computers
Volume44
Issue number3
DOIs
StatePublished - Mar 1995

Fingerprint

Superscalar
Scheduling
Compiler
Hardware
Schedule
Scheduler
Execution Time
Parallelism
Speedup
Branch
Scalar
Restriction

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this

The Importance of Prepass Code Scheduling for Superscalar and Superpipelined Processors. / Chang, Pohua P.; Lavery, Daniel M.; Mahlke, Scott A.; Chen, William Y.; Hwu, Wen mei W.

In: IEEE Transactions on Computers, Vol. 44, No. 3, 03.1995, p. 353-370.

Research output: Contribution to journalArticle

Chang, Pohua P. ; Lavery, Daniel M. ; Mahlke, Scott A. ; Chen, William Y. ; Hwu, Wen mei W. / The Importance of Prepass Code Scheduling for Superscalar and Superpipelined Processors. In: IEEE Transactions on Computers. 1995 ; Vol. 44, No. 3. pp. 353-370.
@article{5d6c00c4f4e54b77b01e90fd954ba22f,
title = "The Importance of Prepass Code Scheduling for Superscalar and Superpipelined Processors",
abstract = "Superscalar and superpipelined processors utilize parallelism to achieve peak performance that can be several times higher than that of conventional scalar processors. In order for this potential to be translated into the speedup of real programs, the compiler must be able to schedule instructions so that the parallel hardware is effectively utilized. Previous work has shown that prepass code scheduling helps to produce a better schedule for scientific programs, but the importance of prescheduling has never been demonstrated for control-intensive non-numeric programs. These programs are significantly different from the scientific programs because they contain frequent branches. The compiler must do global scheduling in order to find enough independent instructions. In this paper, the code optimizer and scheduler of the IMPACT-I C compiler is described. Within this framework, we study the importance of prepass code scheduling for a set of production C programs. It is shown that, in contrast to the results previously obtained for scientific programs, prescheduling is not important for compiling control-intensive programs to the current generation of superscalar and superpipelined processors. However, if some of the current restrictions on upward code motion can be removed in future architectures, prescheduling would substantially improve the execution time of this class of programs on both superscalar and superpipelined processors.",
author = "Chang, {Pohua P.} and Lavery, {Daniel M.} and Mahlke, {Scott A.} and Chen, {William Y.} and Hwu, {Wen mei W.}",
year = "1995",
month = "3",
doi = "10.1109/12.372029",
language = "English (US)",
volume = "44",
pages = "353--370",
journal = "IEEE Transactions on Computers",
issn = "0018-9340",
publisher = "IEEE Computer Society",
number = "3",

}

TY - JOUR

T1 - The Importance of Prepass Code Scheduling for Superscalar and Superpipelined Processors

AU - Chang, Pohua P.

AU - Lavery, Daniel M.

AU - Mahlke, Scott A.

AU - Chen, William Y.

AU - Hwu, Wen mei W.

PY - 1995/3

Y1 - 1995/3

N2 - Superscalar and superpipelined processors utilize parallelism to achieve peak performance that can be several times higher than that of conventional scalar processors. In order for this potential to be translated into the speedup of real programs, the compiler must be able to schedule instructions so that the parallel hardware is effectively utilized. Previous work has shown that prepass code scheduling helps to produce a better schedule for scientific programs, but the importance of prescheduling has never been demonstrated for control-intensive non-numeric programs. These programs are significantly different from the scientific programs because they contain frequent branches. The compiler must do global scheduling in order to find enough independent instructions. In this paper, the code optimizer and scheduler of the IMPACT-I C compiler is described. Within this framework, we study the importance of prepass code scheduling for a set of production C programs. It is shown that, in contrast to the results previously obtained for scientific programs, prescheduling is not important for compiling control-intensive programs to the current generation of superscalar and superpipelined processors. However, if some of the current restrictions on upward code motion can be removed in future architectures, prescheduling would substantially improve the execution time of this class of programs on both superscalar and superpipelined processors.

AB - Superscalar and superpipelined processors utilize parallelism to achieve peak performance that can be several times higher than that of conventional scalar processors. In order for this potential to be translated into the speedup of real programs, the compiler must be able to schedule instructions so that the parallel hardware is effectively utilized. Previous work has shown that prepass code scheduling helps to produce a better schedule for scientific programs, but the importance of prescheduling has never been demonstrated for control-intensive non-numeric programs. These programs are significantly different from the scientific programs because they contain frequent branches. The compiler must do global scheduling in order to find enough independent instructions. In this paper, the code optimizer and scheduler of the IMPACT-I C compiler is described. Within this framework, we study the importance of prepass code scheduling for a set of production C programs. It is shown that, in contrast to the results previously obtained for scientific programs, prescheduling is not important for compiling control-intensive programs to the current generation of superscalar and superpipelined processors. However, if some of the current restrictions on upward code motion can be removed in future architectures, prescheduling would substantially improve the execution time of this class of programs on both superscalar and superpipelined processors.

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

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

U2 - 10.1109/12.372029

DO - 10.1109/12.372029

M3 - Article

AN - SCOPUS:0029276217

VL - 44

SP - 353

EP - 370

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

SN - 0018-9340

IS - 3

ER -