Pipelining Design Techniques - Fundamentals of Computer Organization and Architecture - page 206

13. Trap Unit (T). This unit reports traps upon their occurrences.
14. Done Unit (D). This unit writes the architectural register file.

Two main techniques are employed in the UltraSPARC III in dealing with branches.
These are explained below:

Branch Prediction The UltraSPARC III uses a branch prediction technique

that combines the static and the dynamic branch prediction techniques explained
before. In this case, branch prediction takes place in the IIU unit. It uses a
branch prediction table and a hardware implementation of a dynamic prediction
algorithm.

BRANCH PREDICTION TABLE The branch prediction table (BPT) is a hardware
implementation of a table of a two-bit finite state machine (FSM). It is a saturated
up-down counter. When a branch is encountered, the branch target address and

/
or the branch history are used to find the table index of the location where the pre-
diction for the branch is found. The branch condition is predicted to be taken if it
corresponds to one of two FSM states: strong not taken or weak not taken. The
branch condition is predicted to be taken if it corresponds to one of two FSM
states: weak taken or strong taken. The counter is incremented each time a branch
is taken; otherwise it is decremented, hence the name up-down counter. If a counter
reaches the strong taken state (11-state), it stays there as long as the branch is taken
and if it reaches the strong not taken (00-state), it stays there as long as the branch is
not taken, hence the name saturation. The BPT in the UltraSPARC III consists of
16K-entry (16K 2-bit saturation up-down counters).

GLOBAL SHARE DYNAMIC PREDICTION ALGORITHM The global share (gshare)
algorithm uses two levels of branch-history information to dynamically predict
the direction of branches. The first level registers the history of the last k branches
faced. This represents the global branching behavior. This level is implemented by
providing a global branch history register. This is basically a shift register that enters
a 1 for every taken branch and a 0 for every untaken branch. The second level of
branch history information registers the branching of the last s occurrences of the
specific pattern of the k branches. This information is kept in the branch prediction
table. The gshare algorithm works by taking the lower bits of the branch target
address and XORing them with the history register to get the index that should be
used with the prediction table.
The UltraSPARC III uses a modified version of the gshare algorithm. This modi-
fication requires that the predictor be pipelined over two stages, that is, if the original
gshare algorithm were used, the predictor would be indexed by an old copy of the
program counter (PC). With the modified gshare algorithm, each time the predictor
is accessed, eight counters are read out and the three low-order bits of the PC register
are used to select one of them at the B pipeline stage.