Supporting highly speculative execution via adaptive branch trees

Tien-Fu Chen*

*Corresponding author for this work

Research output: Contribution to conferencePaperpeer-review

4 Scopus citations

Abstract

Most of the prediction mechanisms predict a single path to continue the execution on a branch. Alternatively, we may exploit parallelism from either possible paths of a branch, discarding wrong paths once the branch is resolved. This paper proposes a concept of Adaptive Branch Trees (ABT) to support highly speculative execution for processors with deeper pipelines and wide issue widths. The basic idea of the adaptive branch tree is to dynamically keep track of alternative branch paths and to speculatively execute the code on the most likely path. Hence, unlike branch prediction mechanisms, the ABT scheme would not miss out misprediction paths since the scheme can eventually go back to other alternative paths when the machine has explored more pending branches. The branch tree is realized by an adaptive branch tree table. A token is associated with each basic block and operations in the entire basic blocks are tagged with the token. With a novel token assignment strategy, we can reconfigure the ABT by a shift operation once one branch is resolved. Our experiment results on the SPEC95 benchmarks show that the proposed approach can achieve significant branch penalty reduction for wide-issue processors.

Original languageEnglish
Pages185-194
Number of pages10
DOIs
StatePublished - 1 Jan 1998
EventProceedings of the 1998 4th International Symposium on High-Performance Computer Architecture, HPCA - Las Vegas, NV, USA
Duration: 31 Jan 19984 Feb 1998

Conference

ConferenceProceedings of the 1998 4th International Symposium on High-Performance Computer Architecture, HPCA
CityLas Vegas, NV, USA
Period31/01/984/02/98

Fingerprint Dive into the research topics of 'Supporting highly speculative execution via adaptive branch trees'. Together they form a unique fingerprint.

Cite this