The Branch Target Buffer (BTB) can reduce the performance penalty of branches in pipelined processors by predicting the path of the branch and caching information used by the branch. This paper discusses two major issues in the design of BTBs with the theme of achieving maximum performance with a limited number of bits allocated to the BTB design. First is the issue of BTB management -- when to enter and discard branches from the BTB. Higher performance can be obtained by entering branches into the BTB only when they experience a branch taken execution. A new method for discarding branches from the BTB is examined. This method discards the branch with the smallest expected value for improving performance, outperforming the LRU strategy by a small margin, at the cost of additional complexity.
The second major issue discussed is the question of what information to store in the BTB. A BTB entry can consist of one or more of the following: branch tag (i.e. the branch address), prediction information, the branch target address, and instructions at the branch target. A variety of BTB designs, with one or more of these fields, are evaluated and compared. This study is then extended to multilevel BTBs, in which different levels have different amounts of information per entry. For the specific implementation assumptions used, multilevel BTBs improved performance over single level BTBs only slightly, at the cost of additional complexity. Multi-level BTBs may provide significant performance improvements for other implementations, however.
Design target miss ratios for BTBs are also developed, so that the performance of BTBs for real workloads may be estimated.
Title
Branch Target Buffer Design and Optimization
Published
1989-12-23
Full Collection Name
Electrical Engineering & Computer Sciences Technical Reports
Other Identifiers
CSD-89-552
Type
Text
Extent
66 p
Archive
The Engineering Library
Usage Statement
Researchers may make free and open use of the UC Berkeley Library’s digitized public domain materials. However, some materials in our online collections may be protected by U.S. copyright law (Title 17, U.S.C.). Use or reproduction of materials protected by copyright beyond that allowed by fair use (Title 17, U.S.C. § 107) requires permission from the copyright owners. The use or reproduction of some materials may also be restricted by terms of University of California gift or purchase agreements, privacy and publicity rights, or trademark law. Responsibility for determining rights status and permissibility of any use or reproduction rests exclusively with the researcher. To learn more or make inquiries, please see our permissions policies (https://www.lib.berkeley.edu/about/permissions-policies).
