Browse Prior Art Database

Using History to Improve the Handling of Address Generation Interlocks in Branch Instructions

IP.com Disclosure Number: IPCOM000108030D
Original Publication Date: 1992-Jan-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 6 page(s) / 337K

Publishing Venue

IBM

Related People

Eickemeyer, RJ: AUTHOR

Abstract

Several techniques are described for improving the handling of branch instructions in the presence of address-generation interlocks (AGIs). An AGI is an execution delay caused by an unresolved register dependency where the register is used for computing an address, such as the target address computation in a branch instruction. AGI information from one execution of a particular branch instruction can be used to affect the execution of the branch the next time that it occurs. This can range from modifying branch prediction algorithms to actually saving the fact that an AGI occurred.

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

Using History to Improve the Handling of Address Generation Interlocks in Branch Instructions

       Several techniques are described for improving the
handling of branch instructions in the presence of address-generation
interlocks (AGIs).  An AGI is an execution delay caused by an
unresolved register dependency where the register is used for
computing an address, such as the target address computation in a
branch instruction.  AGI information from one execution of a
particular branch instruction can be used to affect the execution of
the branch the next time that it occurs.  This can range from
modifying branch prediction algorithms to actually saving the fact
that an AGI occurred.

      In a pipelined computer, branch instructions may cause
performance degradation by emptying the pipeline.  Filling the
pipeline requires processor cycles which cannot be used for
instruction execution.  Instruction-level parallel processors, such
as superscalar and superpipelined processors, process instructions
faster than scalar processors.  Branch instruction delays can be even
more detrimental in these processors because multiple instructions
that could execute each cycle are delayed waiting for the branch
instruction.  It is, therefore, important to reduce the time for the
average branch instruction.

      A potential performance problem with branch instructions is the
AGI.  This can occur when the branch instruction (or any instruction)
attempts to compute an address by which to reference storage.  This
address computation is typically the addition of some of the
following:  the contents of one or more registers, a constant value
from the instruction, or the address of the branch instruction
itself.  If a register is used for address generation and that
register is modified by a previous instruction (a dependency), then
address computation cannot proceed until that register is available.
The delay caused by waiting for the register value is known as an
AGI.  This problem results in performance degradation.

      Several techniques exist to attempt to reduce branch
instruction execution time.  Branch prediction techniques save some
information about previous executions of each branch in an attempt to
predict the direction of conditional branches the next time.
Prediction can be by means of one or more bits associated with each
branch and stored in a special hardware structure or as one or more
bits stored with each instruction in an instruction cache.  In this
case the address of the branch target instruction (the instruction
dynamically following the branch) is computed for the instruction on
the sequential path or the taken path depending on the prediction
direction.  The predicted target is fetched from the memory subsystem
and instruction execution begins.  When the true direction of the
branch is known, an incorrect prediction results in the nullification
of the wrongly executing instructions.  If the predictio...