Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Branch History Indexing with Execution Path Information

IP.com Disclosure Number: IPCOM000105644D
Original Publication Date: 1993-Aug-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 2 page(s) / 85K

Publishing Venue

IBM

Related People

Liu, L: AUTHOR

Abstract

Disclosed is a technique for incorporating execution path information in branch history lookup, in order to achieve higher accuracies. The idea is to imbed execution path address information in indexing to history table.

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

Branch History Indexing with Execution Path Information

      Disclosed is a technique for incorporating execution path
information in branch history lookup, in order to achieve higher
accuracies.  The idea is to imbed execution path address information
in indexing to history table.

      Many branch prediction methods are carried through history
tables.  Examples of such history tables are: Branch History Table
(BHT), Decode History Table (DHT), Sequential-Segment History Table
(SSHT), etc..  Typically, when a branch outcome is to be predicted,
certain address bits for the branch or for a preceding address (e.g.,
for SSHT) is used to index to an entry or congruence class of the
history table for retrieval of history information.  In [1]  it is
observed that branch prediction accuracy may be improved by including
execution path information in the history.  This invention proposes
methods for implementing branch history tables incorporating dynamic
execution path information.

      The basic idea of the invention will be illustrated through an
implementation for a simple Decode History Table (DHT).  Consider a
simple DHT (direct-mapped) D with 1-bit per history entry, indicating
whether the associated branch was taken or not.  When prediction is
desired for a branch instruction (at address A) that is being
decoded, a history entry D{A}  is indexed via certain address bits of
A.

      Consider a design in which a branch prediction is influenced by
the past two taken branches.  For each taken branch instruction b let
Tb be the address (e.g., 31-bit) of the associated branch target
instruction.  When a particular branch b (at address A) is to be
predicted for outcome, the last two successive taken branches b1 and
b2 are considered for the history search.  The indexing to a history
entry in D is now carried out through a hashing value derived from A,
Tb1 and Tb2 (if no other information is included in the path
derivation).  The history value (1-bit) will indicate the branch
prediction, and may be reset if the prediction turns out to be
incorrect.  The target address information for (successive 2) taken
branches can be dynamically tracked during execution using a shift
register.

      The hashing of index (to D) from three addresses may be
achieved in many ways.  One example is to take some (e.g., 4) lower
order address bits of Tb1 and Tb2 and XOR with particular bits of A.
In this way the hashing and the shift register may be efficiently
implemented with reasonable hardware.

      With the new indexing scheme, DHT a...