Browse Prior Art Database

Statistical Branch Prediction

IP.com Disclosure Number: IPCOM000120402D
Original Publication Date: 1991-Apr-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 4 page(s) / 144K

Publishing Venue

IBM

Related People

Brown, T: AUTHOR

Abstract

Disclosed is an efficient way to achieve better branch performance on the RISC System/6000* (hereinafter RS/6000) machine.

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

Statistical Branch Prediction

      Disclosed is an efficient way to achieve better branch
performance on the RISC System/6000* (hereinafter RS/6000) machine.

      Analysis of the SPEC programs (refer to Table 1) shows there is
additional improvement which can be obtained over the current
sequential dispatch branch prediction scheme employed in the machine.
The programs listed in Table 1 have high branch frequency and small
basic block (average is 5, including the branch).  Although this has
additional hardware to reduce branch latency from 3 to 1 cycles (more
than 1 cycle for adjacent missed prediction), up to 8 instructions
can execute in a single cycle.  At this rate, conditional branches
become a serious pipeline blockage preventing continuous multiple
instruction flow, hence a degradation in performance.  Statistical
branch prediction is proposed to reduce a branch latency, hence
increase system performance.  Various branch prediction strategies
exist today.  What is unique about this proposal is its
cost-effective implementation on the machines.

      Statistical branch prediction can be achieved without creating
new branch instructions.  Currently, all branch instructions have 1
unused bit in field B0 (bit 10th).  This bit can be used for branch
steering.  The use of this bit has the following advantages:
      1) No new instructions need to be created.
      2) Since this bit is unused, software compatibility is
achieved; that is, the RS/6000 machine can execute branch
instructions which use this bit as a prediction bit without any side
effect.
      3) Branch tuning does not require recompilation. Dynamic tuning
is extremely useful for tuning huge software, such as Operating
System and commercial data base application.
      4) Branch tuning is a post compiler process and there is no new
branch instruction; hence, no changes to the current compiler are
required for this architectural enhancement.

      DATA:
BRANCH PREDICTION HIT RATE OF VARIOUS SCHEME:
programs:             SPICE   XLISP ESPRESSO EQNTOTT MATRIX DNASA
     of instr.           40M     40M     40M    40M    10M     40M
% of all branches     24.7%   22.8%   31.0%  33.4%  20.1%   9.8%
% of cc branch        57.2%   60.2%   79.3%  49.2%  94.8%   94.0%
% of cmps.             8.9%   12.7%    9.0%  14.5%  0.2%    0.1% % of
cmps.
precedes brns.        80-90%  40-60%  60-80% 50-80% nodata nodata
seq. dispatch         40.6%   66.0%   53.4%  71.4%  0.7%    5.0%
target dispatch       59.4%   34.0%   46.6%  28.6%  99.3%   95.0%
statistical dispatch  98.0%   88.0%   87.0%  90.0%  99.9%   99.9%
branch history table with sequential dispatch      of entries (fully
associative table):
  1                   57.0%   66.0%   57.0%  71.0%  99.0%   99.0%
  2      ...