Browse Prior Art Database

Branch Anticipation and Prediction Algorithm

IP.com Disclosure Number: IPCOM000110520D
Original Publication Date: 1992-Dec-01
Included in the Prior Art Database: 2005-Mar-25
Document File: 2 page(s) / 73K

Publishing Venue

IBM

Related People

Jackson, RT: AUTHOR [+2]

Abstract

This algorithm is an evolutionary step over existing branch prediction algorithms. Its main goal is to save machine cycles by processing branches as early as possible.

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

Branch Anticipation and Prediction Algorithm

       This algorithm is an evolutionary step over existing
branch prediction algorithms.  Its main goal is to save machine
cycles by processing branches as early as possible.

      In a super-scalar processor, where a number of instructions are
dispatched to the multiple execution units on a given cycle, it is
particularly important for the branch processor to be able to deal
with branch instructions well ahead in the instruction stream to
avoid proportionately long delays when branch instructions are
encountered.

      In many cases involving loops, a branch instruction is detected
prior to the contents of the general-purpose registers from which the
target address is to be calculated having been resolved.

      To deal with this situation, a branch table is provided, as
shown in Fig. 1.  When a branch instruction is detected, the table is
addressed by the appropriate low order bits of the branch instruction
address (Instruction <,2> Counter), and the remainder of the
instruction counter compared with the Branch Address field read out
of the table.

      A match indicates that this entry applies to the history of
that particular instruction.  The T bits indicate branch history on
previous executions and the target address field shows the address
from which instruction fetching should commence.

      The table entry can be further extended to contain one or more
of the sequential instructions to be fetched down this new path so
that they are immediately available for e...