Browse Prior Art Database

Type-B Branch History Table

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

Publishing Venue

IBM

Related People

Ekanadham, K: AUTHOR [+2]

Abstract

A significant reduction in Branch History Table size can be achieved by only considering TYPE-B branches: The I-FETCHING for taken TYPE-A branches is described: a means for handling TYPE-A branches within the cache and thus freeing up the space they previously occupied in a BHT. The size of the BHT can be significantly reduced, and the handling of TYPE-B branches can more easily be extended as they are the sole branches that need be maintained by the BHT. A need exists to coordinate the two branch types so that the TYPE-B action can be relevant to the point in the instruction stream that is the result of the TYPE-A branch action.

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

Type-B Branch History Table

      A significant reduction in Branch History Table size can be
achieved by only considering TYPE-B branches: The I-FETCHING for
taken TYPE-A branches is described:  a means for handling TYPE-A
branches within the cache and thus freeing up the space they
previously occupied in a BHT.  The size of the BHT can be
significantly reduced, and the handling of TYPE-B branches can more
easily be extended as they are the sole branches that need be
maintained by the BHT.  A need exists to coordinate the two branch
types so that the TYPE-B action can be relevant to the point in the
instruction stream that is the result of the TYPE-A branch action.

      Branch History Tables (BHTs), have always been designed around
the concept of a classification of branches into those which are
taken and those which are not taken.  Such a classification makes the
BHT an integral part of the I-FETCH mechanism as it redirects the
I-FETCH from the next-sequential unit of I-FETCH based on the
prediction that the prior I-FETCH unit contains a taken branch.

      A better way to classify branches is in terms of TYPE-A and
TYPE-B.  Type A branches have a single target, a non-varying action.
They are always taken to the same target, or never taken.  They may
be both conditional branches and unconditional branches.  TYPE-B
branches have a varying character.  They have more than one successor
instruction.  They can be both conditional and unconditional.  A BHT
made up of only TYPE-B branches has a size requirement that is only
one-fifth the size of a conventional BHT, as a large number of taken
branches are TYPE-A.

TYPE-A TAKEN DONE WITHIN CACHE

      The TYPE-B branches are handled by the BHT, and if they exhibit
a pattern of action among their targets, this can be accommodated
more easily as all branches within the BHT have a non-constant target
set.  The TYPE-A branches which are not taken are effectively
non-branches and require no special handling.  The handling of the
TYPE-A branches, that are taken to a fixed target, represent the sole
remaining requirement of such a system.  This category of branch must
be handled within the cache controls and must, to all intents and
purposes, be as automatic as the next-sequential I-FETCH.  In fact
this is precisely the way that such an access is handled.  The cache
must be able to automatically link the target access of a TYPE-A
branch within a unit of cache access (Double Word) to the unit of
access...