Browse Prior Art Database

Maintaining Array Tags in the Branch History Table

IP.com Disclosure Number: IPCOM000100513D
Original Publication Date: 1990-May-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 2 page(s) / 100K

Publishing Venue

IBM

Related People

Emma, PG: AUTHOR [+5]

Abstract

For a processor with a Latin Square Layout (*) foreknowledge of the SAC (Set Associative Class) of an access can allow that access to fetch four sequential DWs from the point of access or allow the other SACs to respond to different cache accesses. If the processor has a branch history table (BHT), the ARRAY TAGS can be stored in the BHT. This article indicates an algorithm that will maintain these TAGS. (The ARRAY TAG specifies which ARRAY contains the DW of the line accessed. The ARRAY which contains the DW targeted by the taken branch can be computed from the ARRAY TAG and the OFFSET.)

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

Maintaining Array Tags in the Branch History Table

       For a processor with a Latin Square Layout (*)
foreknowledge of the SAC (Set Associative Class) of an access can
allow that access to  fetch four sequential DWs from the point of
access or allow the other SACs to respond to different cache
accesses.  If the processor has a branch history table (BHT), the
ARRAY TAGS can be stored in the BHT.  This article indicates an
algorithm that will maintain these TAGS.  (The ARRAY TAG specifies
which ARRAY contains the DW of the line accessed.  The ARRAY which
contains the DW targeted by the taken branch can be computed from the
ARRAY TAG and the OFFSET.)

      For a machine with a BHT, the non-branch history errors can be
serviced without an initial directory lookup.  A directory lookup is
still required to assure that the line fetched from has the correct
address tags.  The BHT can maintain ARRAY TAGS which allow the
identification of the ARRAY associated with the target of the taken
branch.  These can be entered at the time that the branch is entered
into the BHT or at the time of the cache miss caused by the target
fetch (if they are different).  The two major cases that have to be
considered  in detail have to do with the branch being guessed
incorrectly and guessed correctly and the Target Fetch generates a
cache miss.  If the branch is guessed incorrectly and the correct
target address does not generate a miss, then the updating of the BHT
for the taken branch can accommodate the updating of the ARRAY TAG so
as to provide the correct ARRAY TAGS.

      The interesting case is the one where multiple branches target
the same I-LINE and at the time of the cache miss they are still
extant in the BHT.  Thus, their "common" ARRAY TAGS will be vitiated
by an incorrect choice of SAC. This can occur if I-LINE was forced
out of the cache and was restored by another branch action and placed
in a different set associative class.  The restoration of the I-LINE
may be performed by either a branch wrong guess (BWG) or a branch
correct guess (BCG).

      If a BCG causes an I-Miss, then one can minimize the occurrence
of inconsistent ARRAY TAGS by placing the I-Line into the cache based
on the existing ARRAY TAG bits.  Such a replacement will guarantee
that all the branches that are currently holding identical ARRAY TAGS
for the I-LINE will now point to the correct set associative class.

      In the event of a BWG that is accompanied by a cache miss for
the corr...