Improving static branch prediction in a compiler

Brian L. Deitrich, Ben Chung Chen, Wen-Mei W Hwu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

An ILP (Instruction-Level Parallelism) compiler uses aggressive optimizations to reduce a program's running time. These optimizations have been shown to be effective when profile information is available. Unfortunately, users are not always willing or able to profile their programs. A method of overcoming this issue is for an ILP compiler to statically infer the information normally obtained from profiling. This paper investigates one aspect of this inference: the static prediction of conditional-branch direction. The goals of this work are to utilize the source-level information available in a compiler when performing static branch prediction, to identify static-branch-prediction cases in which there is a high confidence that a branch will go in one direction at run time, to gain an intuitive understanding into the reasons why the static-branch-prediction heuristics are effective, and ultimately to improve the accuracy of the static branch prediction. The effectiveness of the static-branch-prediction heuristics developed in this paper is demonstrated on a set of programs from SPEC CINT92, SPEC CINT95, and the IMPACT compiler.

Original languageEnglish (US)
Title of host publicationProceedings - 1998 International Conference on Parallel Architectures and Compilation Techniques, PACT 1998
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages214-221
Number of pages8
ISBN (Electronic)0818685913
DOIs
StatePublished - Jan 1 1998
Event1998 International Conference on Parallel Architectures and Compilation Techniques, PACT 1998 - Paris, France
Duration: Oct 12 1998Oct 18 1998

Publication series

NameParallel Architectures and Compilation Techniques - Conference Proceedings, PACT
ISSN (Print)1089-795X

Other

Other1998 International Conference on Parallel Architectures and Compilation Techniques, PACT 1998
CountryFrance
CityParis
Period10/12/9810/18/98

Fingerprint

Branch Prediction
Compiler
Instruction Level Parallelism
Branch
Heuristics
Optimization
Profiling
Confidence
Intuitive
Prediction

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Cite this

Deitrich, B. L., Chen, B. C., & Hwu, W-M. W. (1998). Improving static branch prediction in a compiler. In Proceedings - 1998 International Conference on Parallel Architectures and Compilation Techniques, PACT 1998 (pp. 214-221). (Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/PACT.1998.727253

Improving static branch prediction in a compiler. / Deitrich, Brian L.; Chen, Ben Chung; Hwu, Wen-Mei W.

Proceedings - 1998 International Conference on Parallel Architectures and Compilation Techniques, PACT 1998. Institute of Electrical and Electronics Engineers Inc., 1998. p. 214-221 (Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Deitrich, BL, Chen, BC & Hwu, W-MW 1998, Improving static branch prediction in a compiler. in Proceedings - 1998 International Conference on Parallel Architectures and Compilation Techniques, PACT 1998. Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT, Institute of Electrical and Electronics Engineers Inc., pp. 214-221, 1998 International Conference on Parallel Architectures and Compilation Techniques, PACT 1998, Paris, France, 10/12/98. https://doi.org/10.1109/PACT.1998.727253
Deitrich BL, Chen BC, Hwu W-MW. Improving static branch prediction in a compiler. In Proceedings - 1998 International Conference on Parallel Architectures and Compilation Techniques, PACT 1998. Institute of Electrical and Electronics Engineers Inc. 1998. p. 214-221. (Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT). https://doi.org/10.1109/PACT.1998.727253
Deitrich, Brian L. ; Chen, Ben Chung ; Hwu, Wen-Mei W. / Improving static branch prediction in a compiler. Proceedings - 1998 International Conference on Parallel Architectures and Compilation Techniques, PACT 1998. Institute of Electrical and Electronics Engineers Inc., 1998. pp. 214-221 (Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT).
@inproceedings{2258d4fc4177433b91b8752a03e06ec6,
title = "Improving static branch prediction in a compiler",
abstract = "An ILP (Instruction-Level Parallelism) compiler uses aggressive optimizations to reduce a program's running time. These optimizations have been shown to be effective when profile information is available. Unfortunately, users are not always willing or able to profile their programs. A method of overcoming this issue is for an ILP compiler to statically infer the information normally obtained from profiling. This paper investigates one aspect of this inference: the static prediction of conditional-branch direction. The goals of this work are to utilize the source-level information available in a compiler when performing static branch prediction, to identify static-branch-prediction cases in which there is a high confidence that a branch will go in one direction at run time, to gain an intuitive understanding into the reasons why the static-branch-prediction heuristics are effective, and ultimately to improve the accuracy of the static branch prediction. The effectiveness of the static-branch-prediction heuristics developed in this paper is demonstrated on a set of programs from SPEC CINT92, SPEC CINT95, and the IMPACT compiler.",
author = "Deitrich, {Brian L.} and Chen, {Ben Chung} and Hwu, {Wen-Mei W}",
year = "1998",
month = "1",
day = "1",
doi = "10.1109/PACT.1998.727253",
language = "English (US)",
series = "Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "214--221",
booktitle = "Proceedings - 1998 International Conference on Parallel Architectures and Compilation Techniques, PACT 1998",
address = "United States",

}

TY - GEN

T1 - Improving static branch prediction in a compiler

AU - Deitrich, Brian L.

AU - Chen, Ben Chung

AU - Hwu, Wen-Mei W

PY - 1998/1/1

Y1 - 1998/1/1

N2 - An ILP (Instruction-Level Parallelism) compiler uses aggressive optimizations to reduce a program's running time. These optimizations have been shown to be effective when profile information is available. Unfortunately, users are not always willing or able to profile their programs. A method of overcoming this issue is for an ILP compiler to statically infer the information normally obtained from profiling. This paper investigates one aspect of this inference: the static prediction of conditional-branch direction. The goals of this work are to utilize the source-level information available in a compiler when performing static branch prediction, to identify static-branch-prediction cases in which there is a high confidence that a branch will go in one direction at run time, to gain an intuitive understanding into the reasons why the static-branch-prediction heuristics are effective, and ultimately to improve the accuracy of the static branch prediction. The effectiveness of the static-branch-prediction heuristics developed in this paper is demonstrated on a set of programs from SPEC CINT92, SPEC CINT95, and the IMPACT compiler.

AB - An ILP (Instruction-Level Parallelism) compiler uses aggressive optimizations to reduce a program's running time. These optimizations have been shown to be effective when profile information is available. Unfortunately, users are not always willing or able to profile their programs. A method of overcoming this issue is for an ILP compiler to statically infer the information normally obtained from profiling. This paper investigates one aspect of this inference: the static prediction of conditional-branch direction. The goals of this work are to utilize the source-level information available in a compiler when performing static branch prediction, to identify static-branch-prediction cases in which there is a high confidence that a branch will go in one direction at run time, to gain an intuitive understanding into the reasons why the static-branch-prediction heuristics are effective, and ultimately to improve the accuracy of the static branch prediction. The effectiveness of the static-branch-prediction heuristics developed in this paper is demonstrated on a set of programs from SPEC CINT92, SPEC CINT95, and the IMPACT compiler.

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

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

U2 - 10.1109/PACT.1998.727253

DO - 10.1109/PACT.1998.727253

M3 - Conference contribution

AN - SCOPUS:0003320262

T3 - Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT

SP - 214

EP - 221

BT - Proceedings - 1998 International Conference on Parallel Architectures and Compilation Techniques, PACT 1998

PB - Institute of Electrical and Electronics Engineers Inc.

ER -