Browse Prior Art Database

First-Time Conditional Branch Detection

IP.com Disclosure Number: IPCOM000099530D
Original Publication Date: 1990-Jan-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 1 page(s) / 38K

Publishing Venue

IBM

Related People

Emma, PG: AUTHOR [+5]

Abstract

In a processor design which includes two DHTs (decode history tables) each having a distinct hash of the branch address, it is possible to determine whether the branch instruction has been previously encountered on a probabilistic basis. If the separate DHTs are initialized to all zeros and all ones, then the hashing of a branch address that has never been seen before will return a b'10'. After the branch action has been resolved, the DHT will be updated based on the branch action. This update synchronizes the hashed location in the two DHTs to the same value.

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

First-Time Conditional Branch Detection

       In a processor design which includes two DHTs (decode
history tables) each having a distinct hash of the branch address, it
is possible to determine whether the branch instruction has been
previously encountered on a probabilistic basis.  If the separate
DHTs are initialized to all zeros and all ones, then the hashing of a
branch address that has never been seen before will return a b'10'.
After the branch action has been resolved, the DHT will be updated
based on the branch action.  This update synchronizes the hashed
location in the two DHTs to the same value.

      After the DHTs have been in operation for a certain number of
branches each table will contain approximately 50% ones and 50%
zeroes.  A not-previously encountered branch will in the absence of
hash collisions still retrieve a b'10' and in the presence of hash
collisions have a 50% chance of retrieving different action bits from
the two DHTs.  The pattern b'01' is unambiguously associated with a
hash collision as the DHTs are assumed initialized to give a b'10'.
The hash collision frequency can be controlled by increasing the size
of the DHTs.

      In those designs where the penalty for a Branch Wrong Guess on
a Taken branch is particularly onerous, the indication that a hash
collision has occurred or that the branch has not been seen before
can be used to achieve a performance improvement over a single DHT
which is twice the size.  Further, t...