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

Predict Instruction Flow Based On Sequential Segments

IP.com Disclosure Number: IPCOM000120223D
Original Publication Date: 1991-Apr-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 4 page(s) / 216K

Publishing Venue

IBM

Related People

Liu, L: AUTHOR

Abstract

Disclosed is method for predicting processor instruction branch outcome. A conventional approach based on histories predicts the outcome of a branch instruction when the branch is located at a certain point. In this invention certain history of sequential execution flow is employed such that the prediction of a branch can be resolved early without having to locate the branch itself. Background

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

Predict Instruction Flow Based On Sequential Segments

      Disclosed is method for predicting processor instruction
branch outcome. A conventional approach based on histories predicts
the outcome of a branch instruction when the branch is located at a
certain point.  In this invention certain history of sequential
execution flow is employed such that the prediction of a branch can
be resolved early without having to locate the branch itself.
Background

      For high performance processors early resolution of
(conditional) branch instruction results is critical in keeping the
execution pipeline moving smoothly without disruption.  This is
particularly important when parallel executions are involved.  One
popular approach is to predict the branch outcome early, ahead of the
decode or execution of a branch. The most sophisticated method
existing employs the Branch History Table (BHT).  The basic idea of
BHT is to record the past histories of outcome for certain branches
and predicts the subsequent outcome accordingly when such branch
instructions are encountered.  For example, each entry of a
set-associative BHT records the following information for a
particular branch:
           BR_ADDR        Address for the branch instruction
           BR_TARG        Address for the target instruction
                          following the branch

      Major benefit of BHT is to allow the processor instruction unit
(I-unit) fetch instructions (into I-buffer) ahead of time without
disrupting the pipeline (e.g., delay of decode caused by late
fetching of instruction code). When the prediction turns out to be
incorrect (e.g., when the result of branch execution is known) the
BHT history is reset and the instruction execution is backed up to
proper point.  There have been various variations and enhancements to
the basic BHT mechanism.  For instance, not-taken branches (i.e.,
branches that did not result in non-sequential branching previously)
may not be recorded. Also, the BHT may record additional information
like the instruction code for the target instructions.

      All the known implementations of BHT carries out the prediction
of a branch by locating the branch instruction address first.  For
instance, during certain point of time, the BHT control looks for the
address of next branch to predict via certain algorithms.  Once such
a branch address is located, it is used to index to the BHT to find
possible history information for prediction.
Basic Idea of the Invention

      In the conventional BHT approach, locating the successive
branches for prediction not only results in complexity of hardware
but also delays the prediction timing.  We observe that the main
purpose of such branch prediction schemes is not really to locate the
branches, but to predict instruction flow for subsequent executions.
As a result, if we can resolve instruction flow patterns without
...