A systematic approach to branch speculation

Gianfranco Bilardi, Alex Nicolau, Joe Hummel

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

Abstract

A general theoretical framework is developed for the study of branch speculation. The framework yields a systematic way to select the schedule in a given set that, for any (estimated) bias of the branch, minimizes the expected execution time. Among other things, it is shown that in some cases the optimal schedule is neither of those resulting from aggressively speculating on any given outcome of the conditional. Our results can be useful in either static or dynamic approaches. We propose a simple run-time estimator for the bias and discuss how to combine it with schedule selection. A number of examples motivate and illustrate the techniques, and show that our approach yields better performance in the case of highly unpredictable branches.

Original languageEnglish (US)
Title of host publicationLanguages and Compilers for Parallel Computing - 10th International Workshop, LCPC 1997, Proceedings
EditorsPen-Chung Yew, Chua-Huang Huang, P. Sadayappan, Zhiyuan Li, Siddharta Chatterjee, David Sehr
PublisherSpringer Verlag
Pages394-411
Number of pages18
ISBN (Print)3540644725, 9783540644729
DOIs
StatePublished - 1998
Event10th Annual International Workshop on Languages and Compilers for Parallel Computing, LCPC 1997 - Minneapolis, United States
Duration: Aug 7 1997Aug 9 1997

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1366
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th Annual International Workshop on Languages and Compilers for Parallel Computing, LCPC 1997
Country/TerritoryUnited States
CityMinneapolis
Period8/7/978/9/97

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'A systematic approach to branch speculation'. Together they form a unique fingerprint.

Cite this