Browse Prior Art Database

Splitting BHT for Variable TARGET Representations

IP.com Disclosure Number: IPCOM000060035D
Original Publication Date: 1986-Feb-01
Included in the Prior Art Database: 2005-Mar-08
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Liu, L: AUTHOR [+2]

Abstract

A Branch History Table (BHT) has been used as a powerful mechanism in predicting the outcomes of conditional branches in high performance processors. Normally, a BHT is implemented as a set-associative array in which each entry consists of a pair and other necessary status information. At a "valid" BHT entry the SOURCE and/or TARGET addresses (e.g., by cutting off a few high-order bits in the halfword addresses). Even with such better address representations, the TARGET addresses in a BHT still typically require on the order of 24 bits to represent. In a practical workload it is well-known that taken branches do not usually go too far (forward or backward) from the branch instructions themselves. A new mechanism for more efficient representation of BHT addresses based on this observation is set forth below.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

Splitting BHT for Variable TARGET Representations

A Branch History Table (BHT) has been used as a powerful mechanism in predicting the outcomes of conditional branches in high performance processors. Normally, a BHT is implemented as a set-associative array in which each entry consists of a pair <SOURCE, TARGET> and other necessary status information. At a "valid" BHT entry the SOURCE and/or TARGET addresses (e.g., by cutting off a few high-order bits in the halfword addresses). Even with such better address representations, the TARGET addresses in a BHT still typically require on the order of 24 bits to represent. In a practical workload it is well-known that taken branches do not usually go too far (forward or backward) from the branch instructions themselves. A new mechanism for more efficient representation of BHT addresses based on this observation is set forth below. An organization is proposed in which the BHT is split into two parts, called an A-Table and a B- Table. The B-Table is organized similar to the conventional BHTs. The A-Table is also similarly structured, except that the TARGET fields are much shorter. A valid TARGET field in the A-Table contains the "branch halfword distance", which is the address distance (counted by halfword units) between the branch instruction and the target. In order to facilitate the description, a postulation of certain design parameter values is set forth. Consider an A-Table and a B-Table with 700 and 324 entries, respectively. Each of these two tables consists of a number of hash classes, with 4 entries in each class manipulated by certain least recently used (LRU) algorithms (just like the usual BHT replacement organizations). These two tables are "disjoint" on the SOURCE columns. For a branch address that is to be predicted upon both tables, the tables are searched in parallel for a match against SOURCE fields. The TARGET fields in the A- Table are implemented with 7 bits each, which represents an integer between - 16 and 111. A taken branch executed is said to be a "long" branch if the branch halfword distance is beyond t...