Browse Prior Art Database

Subhistory-Based Two-Level Dynamic Branch Predictor

IP.com Disclosure Number: IPCOM000105068D
Original Publication Date: 1993-Jun-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 4 page(s) / 89K

Publishing Venue

IBM

Related People

Chan, JC: AUTHOR [+3]

Abstract

The two-level adaptive branch predictor reported recently [1] has provided an interesting alternative for designing the dynamic branch predictor. Fig. 1 shows one version of its implementation. Basically, in such an approach, two tables are required for predicting the outcome of a branch. The first table, called the Branch History Table (BHT), is accessed using a hashed index from the branch address under considera tion. The bit pattern stored in the entry associated with that branch address, in the ideal case, represents the last M outcomes of the branch. The pattern thus obtained is then used as an index to access the second table, called the Pattern History Table (PHT). The informa tion obtained from the second table serves as an input to a branch predictor which performs the actual branch prediction.

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

Subhistory-Based Two-Level Dynamic Branch Predictor

      The two-level adaptive branch predictor reported recently [1]
has provided an interesting alternative for designing the dynamic
branch predictor.  Fig. 1 shows one version of its implementation.
Basically, in such an approach, two tables are required for
predicting the outcome of a branch.  The first table, called the
Branch History Table (BHT), is accessed using a hashed index from the
branch address under considera tion.  The bit pattern stored in the
entry associated with that branch address, in the ideal case,
represents the last M outcomes of the branch.  The pattern thus
obtained is then used as an index to access the second table, called
the Pattern History Table (PHT).  The informa tion obtained from the
second table serves as an input to a branch predictor which performs
the actual branch prediction.  Typical branch predictor used in the
last step of this approach is the N-bit counter branch predictor.

       A drawback with this approach is that the prediction is done
exclu sively based on the history of the "branch pattern", completely
ignoring the information provided by the branch history itself.  It
is known that the history of a branch provides an indispensable
information for predicting the future behavior of the branch and
therefore should not be ignored.

      In this invention, we propose a method for two-level branch
predic tion which uses the information provided by the branch history
as well.  The idea is in fact an extension of the work reported in
[2].  The logical and the physical implementations of  the new idea
are shown in Figs. 2 and 3, respectively.  As shown in Fig. 2, two
tables are also required.  The first table is called the Branch
Pattern Table (BPT) and the second table is called the Branch
Subhistory Table (BST).  Both tables are accessed simultaneously
using two independently hashed indices from the branch address.  The
pattern obtained from the access to the BPT represents the results of
the most recent M branches...