Browse Prior Art Database

THE CORRELATION BRANCH TARGET ADDRESS CACHE (BTAC)

IP.com Disclosure Number: IPCOM000007765D
Original Publication Date: 1996-Aug-01
Included in the Prior Art Database: 2002-Apr-22
Document File: 3 page(s) / 176K

Publishing Venue

Motorola

Related People

Paul Rossbach: AUTHOR

Abstract

PowerPC microprocessors as well as many other current high performance microprocessors perform branch prediction with a Branch Target Address Cache (BTAC) working in conjunction with a Branch History Table (BHT). Ideally the BHT will provide the correct branch direction (taken or not taken), and the BTAC will augment a taken prediction with the correct target address. Since both structures are accessed during the fetch of the branch (before the calculated target address can be obtained), proces- sor cycles are saved. Some machines boost perform- ance further by using what is known as a Correla- tion BHT. "Correlation" or "Adaptive" Branch Prediction is a method that has been applied to BHTs to improve performance by introducing the past his- tory of all branches into the prediction along with the normal current branch fetch address. Thus, a Correlation BHT is indexed not just by bits from the fetch address, but also by bits from the global branch history. However, a Correlation BHT and a traditional BTAC ofien differ on predicted branch direction. For example, though the Correlation BHT might predict a branch not taken, a BTAC hit implies that the branch should be predicted taken. Further, there are some branches whose targets are different for different instruction paths to the branch. The traditional BTAC may predict the wrong address for these branches because it will predict whatever address was calculated for the last instance of the branch. A third problem with the traditional BTAC is the.competition for BTAC space that often arises among multiple branches in the same fetch packet. Since a BTAC access is based on fetch address, two or more branches within a superscalar machine's fetch packet can compete for the same BTAC entry, degrading performance.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 37% of the total text.

Page 1 of 3

M-LA Technical Developments

THE CORRELATION BRANCH TARGET ADDRESS CACHE (BTAC)

by Paul Rossbach

  PowerPC microprocessors as well as many other current high performance microprocessors perform branch prediction with a Branch Target Address Cache (BTAC) working in conjunction with a Branch History Table (BHT). Ideally the BHT will provide the correct branch direction (taken or not taken), and the BTAC will augment a taken prediction with the correct target address. Since both structures are accessed during the fetch of the branch (before the calculated target address can be obtained), proces- sor cycles are saved. Some machines boost perform- ance further by using what is known as a Correla- tion BHT. "Correlation" or "Adaptive" Branch Prediction is a method that has been applied to BHTs to improve performance by introducing the past his- tory of all branches into the prediction along with the normal current branch fetch address. Thus, a Correlation BHT is indexed not just by bits from the fetch address, but also by bits from the global branch history. However, a Correlation BHT and a traditional BTAC ofien differ on predicted branch direction. For example, though the Correlation BHT might predict a branch not taken, a BTAC hit implies that the branch should be predicted taken. Further, there are some branches whose targets are different for different instruction paths to the branch. The traditional BTAC may predict the wrong address for these branches because it will predict whatever address was calculated for the last instance of the branch. A third problem with the traditional BTAC is the.competition for BTAC space that often arises among multiple branches in the same fetch packet. Since a BTAC access is based on fetch address, two or more branches within a superscalar machine's fetch packet can compete for the same BTAC entry, degrading performance.

  The Correlation BTAC helps solve the aforemen- tioned problems. This is done by introducing the element of adaptive branch history into the BTAC storage structure. While the traditional BTAC matches the fetch address to determine hit/miss, the Correlation BTAC must match first the fetch

address, and second the global branch history to determine hit/miss. Thus, the BTAC access is now analogous to the BHT access, and the two should be in agreement more otten. Further, a single branch may now occupy multiple locations, so for branches whose target address can vary, different targets may be associated with different global history vectors. Finally, since there may be multiple entries for a single fetch address, the competition between mul- tiple branches within the same fetch group is reduced.

  The Correlation BTAC is designed for use in superscalar microprocessors that use branch predic- tion to improve performance. The Correlation BTAC complements a Correlation BHT, which is also expected to be a part of the microarchitecture. This new BTAC design should improve overall BTAC hit rate, an...