Simultaneous prediction of multiple branches for superscalar processing

System and method for predicting a multiplicity of future branches simultaneously (parallel) from an executing program, to enable the simultaneous fetching of multiple disjoint program segments. Additionally, the present invention detects divergence of incorrect branch predictions and provides correction for such divergence without penalty. By predicting an entire sequence of branches in parallel, the present invention removes restrictions that decoding of multiple instructions in a superscalar environment must be limited to a single branch group. As a result, the speed of today's superscalar processors can be significantly increased. The present invention includes three main embodiments: (1) the first embodiment is directed to a simplex multibranch prediction device, that can predict a plurality of branch groups in one cycle and provide early detection of wrong predictions; (2) the second embodiments is directed to a duplex multibranch prediction device that can detect divergence in a predicted stream, and provide redirection (correction) within the stream; and (3) the third embodiment is directed to an n-plex multibranch prediction device, that can predict n multiplicity of branch predictions simultaneously and provide an early detection of wrong predictions as well as correction of wrong predictions.

DESCRIPTION 
1. Technical Field 
The present invention relates generally to a system and method for 
dynamically and simultaneously predicting the outcome of a sequence of 
branches. More particularly, the present invention relates to a system and 
method for predicting a sequence of multiple disjoint instruction segments 
simultaneously, and for generating the corresponding multiplicity of 
instruction-fetch addresses to a parallel memory system which provides the 
instruction sequences to a superscalar processor that can decode and 
execute multiple instructions in parallel. 
2. Background Art 
In nominal instruction flow, instructions are decoded in sequence, i.e., 
instructions are fetched and decoded from sequential locations in memory. 
A branch instruction is an instruction that causes a disruption in this 
flow, i.e., a taken branch causes decoding to be discontinued along the 
sequential path, and resumed starting at a new location in memory. The new 
location in memory is called the branch-target address. Since instruction 
fetching is overlapped with the decoding and execution of other 
instructions, branches degrade pipeline performance. 
For example, consider a pipeline whose stages are: i) instruction decode 
(denoted DEC); ii) address generation (denoted AGEN) for operand 
addresses, or in the case of branch instructions, for branch target 
addresses; iii) cache access (denoted CACHE) to fetch operands, or in the 
case of branch instructions, to fetch branch-target instructions, and iv) 
execute (denoted EXEC) to perform the functional operation on the input 
operands as specified by the instruction. FIG. 1 shows an example of 
instruction flow in this pipeline. 
As shown in FIG. 1, a new instruction can be decoded on every cycle such 
that four instructions can be in some phase of operation simultaneously. 
For example, on cycle #4, instructions I1-I4 are all being processed by 
the pipeline. When the branch instruction is decoded on cycle #5, further 
decoding stops. The branch-target address must be computed by AGEN, and 
the target instruction (denoted TARG) must be fetched from CACHE before it 
can enter the pipeline. 
In this example, the branch instruction (BR) causes two empty slots to 
appear in the pipeline. These slots appear during cycles 9 and 10 of the 
EXEC phase in FIG. 1. These are cycles during which no useful work is 
being done by the processor, hence these cycles represent performance 
degradation. 
The particular branch instruction used in this example is the least severe 
of the taken branches: it is called an unconditional branch, since it 
unconditionally transfers control from the branch instruction (BR) to the 
target instruction. (TARG). That is, at the time that the branch 
instruction is decoded, it is known that the transfer of control to TARG 
will take place. A more costly branch instruction in terms of performance 
is the conditional branch instruction: this instruction specifies that 
control is to be transferred to TARG only if some condition is met. The 
condition is usually determined by the outcome of some instruction that 
precedes the branch. 
A conditional branch instruction would cause a nominal penalty of one 
additional cycle in the example above, since a conditional branch must 
complete execution (EXEC) to determine whether control is to be 
transferred to TARG. If it is determined by EXEC that control is not to be 
transferred to TARG, then the instruction that is to be decoded following 
the branch is the next-sequential (by address) instruction which follows 
the branch. Thus, even when a conditional branch instruction is not taken, 
there is still a nominal delay of three cycles associated with the branch 
in this example. 
Note that if it can be determined at decode time that a conditional branch 
instruction will not be taken, then there is no penalty associated with 
the branch instruction, i.e., the next sequential instruction can be 
decoded immediately following the decode of the branch instruction. 
However, if it is determined at decode time that the branch instruction 
will be taken, then there is still a two-cycle penalty associated with the 
branch, i.e., the target address must be generated and the target 
instruction must be fetched, but the cycle in which the branch is executed 
is saved. 
Mechanisms that attempt to predict the outcomes of conditional branches at 
decode time are called "decode-time prediction mechanisms." If such a 
mechanism predicts correctly, it will save three cycles for branches that 
are not taken, and one cycle for branches that are taken in the pipeline 
above. One particular type of decode-time predictor is called the "Decode 
History Table" (DHT) as described in U.S. Pat. No. 4,477,872, by Losq et 
al., and in U.S. Pat. No. 4,430,706, by Sand. 
The DHT is a table of entries, where an entry is accessed based on a 
transformation (hash or truncation) on the bits that compose the address 
of a branch instruction. The entry itself comprises a single bit: the bit 
is set if the corresponding branch instruction was taken the last time 
that it was executed, otherwise the bit is not set. When a conditional 
branch instruction is decoded, the DHT is accessed with the address of the 
branch instruction. If the DHT entry is set, then it is guessed that the 
branch will be taken; the target address is generated, and the target 
instruction is fetched, and decoded on the third cycle following the 
decode of the branch instruction (thereby saving one cycle of delay). If 
the DHT entry is not set, then it is guessed that the branch will not be 
taken; the next-sequential instruction is decoded on the cycle following 
the decode of the branch instruction (thereby saving three cycles of 
delay). If it is found that the DHT predicted erroneously (i.e., the 
prediction did not agree with the branch outcome as computed in EXEC), 
then the corresponding entry is corrected. 
Thus, a decode-time prediction mechanism offers an opportunity to avoid all 
penalty associated with not-taken branches as well as the execution-time 
penalty (typically one cycle) for taken branches. The reduction in branch 
penalty is dependent upon the accuracy of the particular decode-time 
mechanism used. However, even a decode-time mechanism having 100% accuracy 
cannot eliminate all branch penalty. 
Specifically, whenever there is a taken branch, there is a penalty equal to 
the time to generate the target address and fetch the target instruction. 
Therefore, the only way to reduce branch penalty even further is to 
anticipate taken branches and to fetch target instructions prior to the 
time that the branch instructions are actually encountered by the decoder. 
Mechanisms that attempt to do this are called "prefetch-time prediction 
mechanisms." 
Implicit in the discussion above is the assumption that an autonomous 
instruction-prefetching engine exists. In the absence of a prefetch-time 
prediction mechanism, a simple prefetch engine may comprise: i) a simple 
incrementer used to step through sequential instruction addresses, ii) an 
instruction buffer for holding sequential instructions to be decoded by 
the instruction decoder, iii) a means for using the sequential addresses 
produced by the incrementer to fetch sequential blocks of instructions 
from the cache and place them in the instruction buffer, and iv) a means 
for the processor to supply a new starting address (e.g., a branch-target 
address) to the incrementer in the event of a taken branch instruction. 
By "autonomous," it is meant that the prefetch engine is free-running and 
relatively independent of the instruction decoder. Hence, in the absence 
of taken branches the instruction buffer will always contain 
next-sequential instructions to be decoded by the instruction decoder, and 
there will be no penalty for correctly guessed conditional branches that 
are not taken. 
A prefetch-time prediction mechanism is a mechanism that is incorporated 
into the prefetch engine (as opposed to a decode-time mechanism, which 
operates in conjunction with the decoder). A prefetch-time mechanism must 
autonomously redirect instructions prefetching down a branch-target path 
immediately following the prefetch of a predicted taken branch. By so 
doing, the prefetch-time mechanism ensures that the instruction buffer 
contains the branch target instruction at the time that the branch 
instruction is decoded. If successful in this endeavor, then the branch 
target instruction can be decoded immediately following the decode of the 
branch instruction. Thus, a prefetch-time mechanism eliminates all branch 
penalty, even for taken branches, when it predicts correctly. 
Most, if not all, prefetch-time prediction mechanisms are variations on the 
"Branch History Table" (BHT) as first described in U.S. Pat. No. 
3,559,183, by Sussenguth. This is the prefetch-time analog of the Decode 
History Table described above. That is, the BHT is a table of entries, 
where an entry is accessed based on a transformation (hash or truncation) 
on the bits that compose the address of the block of instructions being 
prefetched. 
The entry itself is much more complex than a DHT entry for three reasons. 
First, the BHT mechanism operates "blindly" at prefetch time, i.e., it 
merely fetches blocks of instructions without the benefit of being able to 
examine the content of these blocks, i.e., without the assistance of an 
instruction decoder. Second, and very importantly, the fetch quantum is a 
"block" of instructions that is not necessarily aligned on instruction 
boundaries, and therefore may contain multiple instructions and 
instruction fragments; the quanta are not single instructions. Third, the 
BHT mechanism must output a predicted target address when it predicts the 
presence of a taken branch within a block. 
Thus, a BHT entry must be able to identify that its associated block of 
instructions contains a taken branch, based on the processor's having 
previously encountered a taken branch within that block. Further, it must 
be able to identify where within the block the taken branch instruction 
resides, since the particular branch instruction may or may not be 
relevant to current instruction fetching depending on where the block is 
entered, i.e., depending on current branch activity. Finally, it must 
specify the branch target address, so that prefetching can be immediately 
redirected down the target path should the particular branch be relevant 
to the current prefetch activity. 
When the processor encounters a branch instruction that is found to be 
taken, it creates a BHT entry based on the address of the branch. The 
entry itself will contain the branch target address. If the particular 
section of code that contains that branch is ever reencountered, then the 
BHT entry is able to cause prefetching to be redirected to the historical 
target address at the time that the branch instruction is prefetched. 
When the BHT redirects prefetching, it also enqueues information regarding 
this action (e.g., the address at which it "believes" there is a taken 
branch, and the target address of the branch) at the processor. As the 
processor subsequently executes the code that has been prefetched, it has 
three opportunities to determine whether or not the BHT was correct. If 
the BHT correctly anticipated the branch, then there is no penalty 
associated with the branch. Otherwise, there may be a severe penalty 
associated with having made an incorrect prediction. (The terms "guess" 
and "prediction" are used interchangeably and are synonymous in the art.) 
There are three points in the processor pipeline at which a branch 
wrong-guess (BWG) may be detected. These points are at decode time (DEC), 
at address-generation time (AGEN), and at execution time (EXEC). 
At decode time (DEC), a branch wrong-guess (BWG) can manifest itself in one 
of two ways. First, if the decoder encounters an unconditionally taken 
branch, and the BHT has given no indication of this branch, then it is 
known that the BHT is wrong. The appropriate action at this point is to 
execute the branch in the canonical way, and to create a new BHT entry to 
indicate the presence of the branch. Second, if the BHT has indicated a 
taken branch at a given address, and the instruction that is decoded at 
this address is not a branch instruction, then it is known that the BHT is 
in error. The appropriate action at this point is to delete the offending 
entry from the BHT, and to abort the redirection in instruction 
prefetching that was effected by the presence of the entry. Note that in 
this latter case, the BHT may have caused cycles of penalty to be incurred 
via redirection of instruction prefetch when there was no branch 
instruction in the code. 
At address-generation time (AGEN), a BWG manifests itself if the target 
address that is generated is not the same as the target address that was 
predicted (and enqueued at the processor) by the BHT. The appropriate 
actions at this point are to correct the target address in the BHT entry, 
abort the instruction prefetching that was directed down the erroneous 
target path, and redirect instruction prefetching down the correct target 
path. 
At execution time (EXEC), the only branches that can possibly cause a BWG 
are conditional branches, since the resolution of the branch condition is 
performed during EXEC. A BWG occurs if EXEC determines that the branch is 
taken when the BHT gave no indication of such, or if EXEC determines that 
the branch is not taken when the BHT indicated that the branch would be 
taken. In either case, the appropriate actions are to update the BHT to 
indicate the new action of the branch and to redirect instruction prefetch 
in accordance with the new action. 
Thus far, the discussion has been restricted to pipelined processors that 
decode instructions one-at-a-time. It has been shown that branch 
instructions are a major disruptive force to pipeline flow, and that a 
class of history-based prediction mechanisms can eliminate much of the 
delay caused by branches. 
In superscalar processors, multiplicities of instructions are decoded 
simultaneously (e.g., see Johnson, M., Superscalar Processor Design, 
Prentice Hall, Chapters 1-2, (1991) incorporated herein by reference). The 
performance implications of branches are even more severe in this arena. 
Specifically, in order to sustain multiple instruction-decodes per cycle, 
it is necessary to sustain multiple instruction-fetches per cycle. Since 
branches are the principle source of uncertainty in the instruction 
fetching process, good branch prediction is a requirement for reasonable 
superscalar design. 
Further and even more importantly, most programs have a branch instruction 
on the average of every 3 to 5 instructions. Since this is an average, and 
the distribution is not necessarily uniform, there are frequent instances 
of code that contain a branch every 1 to 2 instructions. Since branches 
are this pervasive in general programs, a truly robust superscalar 
processor must be able to predict more than one branch instruction 
simultaneously, and to initiate the appropriate instruction-prefetching. 
The importance of branch prediction as it relates to instruction fetching 
is illustrated by the abstract of "Limits on Multiple Instruction Issue," 
by Michael D. Smith, Mike Johnson, and Mark A. Horowitz in Computer 
Architecture News, Vol. 17, No. 2, April 1989, pp. 290-302, which states 
that: 
This paper investigates the limitations on designing a processor which can 
sustain an execution rate of greater than one instruction per cycle on 
highly-optimized, nonscientific applications. We have used trace-driven 
simulations to determine that these applications contain enough 
instruction independence to sustain an instruction rate of about two 
instructions per cycle. In a straightforward implementation, cost 
considerations argue strongly against decoding more than two instructions 
in one cycle. Given this constraint, the efficiency in instruction 
fetching rather than the complexity of the execution hardware limits the 
concurrency attainable at the instruction level. 
In the "Future Directions" section of the paper, the authors conclude: 
The real difficulty lies in providing the instruction bandwidth required by 
the execution unit given the frequency of branches and the random 
alignment of instructions in memory. Techniques used to sustain fetch 
bandwidth requirements in typical pipelined RISC processors do not provide 
an adequate solution for superscalar architectures. 
The conclusion that instruction-fetching bandwidth limits multiple-decode 
is substantiated further in "Single Instruction Parallelism is Greater 
Than Two," by Michael Butler, Tse-Yu Yeh, Yale Patt, Mitch Alsup, Hunter 
Scales and Michael Shebanow, Computer Architecture News, Vol. 19, No. 3, 
pp. 276, 286, May 1991. The abstract states that: 
Recent studies have concluded that little parallelism (less than two 
operations per cycle) is available in single instruction streams. Since 
the amount of available parallelism should influence the design of the 
processor, it is important to verify how much parallelism really exists. 
In this study, we model the execution of the SPEC benchmarks under 
differing resource constraints. We repeat the work of the previous 
researchers, and show that under the hardware resource constraints they 
imposed, we get similar results. On the other hand, when all constraints 
are removed except those required by the semantics of the program, we have 
found degrees of parallelism in excess of 17 instructions per cycle. 
Finally, and perhaps most important for exploiting single instruction 
stream parallelism now, we show that if the hardware is properly balanced, 
one can sustain from 2.0 to 5.8 instructions per cycle on a processor that 
is reasonable to design today. 
In this study, the authors only process one branch per cycle, but in the 
"Conclusions" section, the authors state that: 
"Allowing multiple branches per cycle would increase the amount of 
available parallelism," 
and further state: 
Our results of 2.0 to 5.8 instructions per cycle come from a restricted 
data flow engine that has a limited window size and issue rate, consistent 
with what is reasonable today. As levels of integration and bandwidth 
increase, window sizes and issue rates will increase correspondingly. In 
the limit, our unbounded window size and issue rate machine (the UDF) 
shows instructions per cycle in the 17 to 1165 range. While we are not 
suggesting that this is possible (yet), we expect numbers well in excess 
of 5 instructions per cycle. 
This would clearly require predicting more than one branch, and fetching 
more than one branch-group per cycle. A branch-group is a sequence of 
instructions whose addresses are sequential, i.e., it is a non-disjoint 
sequence. 
Therefore, a truly robust superscalar processor must be able to predict 
more than one branch instruction simultaneously, and to initiate the 
appropriate instruction-prefetching. 
DISCLOSURE OF INVENTION 
A conditional branch instruction is an instruction that causes a disruption 
in the straight-line execution of a program based on the outcome of a 
previous calculation. If the branch instruction is taken, then the next 
instruction that is executed is not the instruction that sequentially 
follows the branch instruction; instead, it will come from another part of 
the program. 
In traditional processors that decode only one instruction per cycle, 
branch instructions have significant performance implications for two 
reasons. First, the processor is typically delayed pending the outcome of 
the calculation that is used to resolve the branch. Second, when the 
branch is taken, a disruption occurs in the pipeline between instruction 
fetching and instruction execution, since instruction fetching is 
nominally a next-sequential process. There is extensive existing art 
relating to the prediction of single branches in the instruction stream, 
allowing some of these delays to be reduced or eliminated in single-decode 
processors. 
In the field of "superscalar processors," an attempt is made to decode 
multiplicities of instructions simultaneously. Since branches are 
pervasive in typical programs, and can occur as frequently as every other 
instruction in some programs, attempts at building superscalar processors 
have been limited to date. 
A survey of the literature reveals that it is well understood that the 
intrinsic presence of branch instructions prevents the practical 
implementation of superscalar processors that decode more than two or 
three instructions per cycle except in a few very special cases. Although 
this limitation and the reason for it are well understood, there have been 
no proposed satisfactory solutions to the problem thus far. Many 
practitioners accept the interbranch distance as a fundamental limit to 
multiple decoding. 
The present invention is a new mechanism that solves the problems mentioned 
above. The present invention provides a means for simultaneously 
predicting the outcome of multiple branches per cycle in an executing 
program. The multiplicity of branches that are predicted form a logical 
sequence of branches that occur in the program. By predicting an entire 
sequence of branches in parallel, the present invention removes the old 
restriction (discussed above) that the decoding of multiple instructions 
must be limited to a single branch group. 
As a result, not only does the present invention drastically improve the 
performance of superscalar processing, but it is a prerequisite invention 
for very high degrees of multiple decoding, i.e., it enables a new level 
of superscalar processing that was previously assumed to be impossible. 
The present invention performs the simultaneous prediction of multiple 
branches that logically form a sequence. It further initiates the multiple 
disjoint instruction-fetches that compose the predicted branch sequences. 
The present invention implements two conceptual elements that must be 
present to perform reliable multiprediction and multiprefetching. First, a 
MultiBranch History Table (MBHT) mechanism maintains entries that provide 
information about multiple branch groups, i.e., an MBHT entry describes a 
sequence of branch groups by storing the branch and target address of two 
or more branch instructions in each entry. Second, since historical branch 
prediction is not perfect, the predictive accuracy of a predicted branch 
sequence decreases geometrically with the length of the sequence. 
Therefore, the present invention maintains a high accuracy via multiple 
MBHT mechanisms that are searched in parallel with different offsets into 
the predicted sequence to detect divergence within the predicted sequence 
as early as possible. 
Generally, to predict and prefetch n branch groups simultaneously, an MBHT 
entry provides information about a sequence of n branches. Additionally, n 
or fewer MBHT mechanisms are searched in parallel: one MBHT per branch 
group for some subset of the n branches. The parallel search provides an 
early recovery mechanism in the event that the multiple tables indicate 
divergence within the predicted stream. 
The present invention includes three main embodiments: (1) the first 
embodiment is directed to a simplex multibranch prediction device that can 
predict a plurality of branch groups in one cycle and provide early 
detection of wrong predictions; (2) the second embodiment is directed to 
an n-plex multibranch prediction device, that can predict a multiplicity 
of n branch instructions simultaneously and provide an early detection of 
wrong predictions as well as correction of wrong predictions; and (3) the 
third embodiment is directed to a duplex multibranch prediction device 
that can detect divergence in a predicted stream, and provide redirection 
(correction) within the stream. 
The structure and operation of the third embodiment, the duplex multibranch 
prediction device, will now be summarized. The duplex multibranch 
predicting device simultaneously predicts a plurality of branch 
instructions. It is coupled to an instruction cache of a superscalar 
processor. The predictions are used to fetch branch groups of instructions 
to be placed in the instruction cache. 
The duplex multibranch predicting device includes the following elements: a 
primary pre-fetch address register, a primary multiple-branch history 
table, a secondary multiple-branch history table, a comparator, and an 
update queue. 
The primary multibranch history table predicts target addresses of a first 
plurality of branch instructions simultaneously, based on the execution 
history of the first plurality of branch instructions. 
The secondary multibranch history table lags at least one branch 
instruction behind the primary multibranch history table. The secondary 
multibranch history table predicts target addresses of a second plurality 
of branch instructions simultaneously, based on an execution history of 
the second plurality of branch instructions. Additionally, the secondary 
multibranch history table is used to check for divergence in predictions 
made by the primary multibranch history table. 
The comparator is coupled to the primary multibranch history table and to 
the secondary branch history table. The comparator compares predictions 
made by the primary multibranch history table with predictions made by the 
secondary multibranch history table to detect divergence. 
Lastly, the update queue is coupled to the primary branch history table and 
to the secondary branch history table. The update queue is used for 
updating the execution history of the primary multibranch history table 
and the secondary multibranch history table, based on outcome of sequences 
of branch instructions executed by the superscalar processor. 
In summary, a major feature of the present invention is to predict a 
multiplicity of future branches simultaneously, to enable the simultaneous 
fetching of multiple disjoint program segments. Predicting multiplicities 
of branches is essential to overcoming the existing limits of 
instruction-level parallelism. This multiplies the maximum processing 
speed of a computer significantly. For example, it could increase the 
present limits of executing 2-5.8 instructions per cycle as found by 
Butler et al., to their projected, 17-1165 instructions per cycle. 
Additionally, the present invention detects divergence of incorrect branch 
predictions and provides correction for such divergence without penalty.

BEST MODE FOR CARRYING OUT THE INVENTION 
Defining Terms 
The following is a short list of terms and their corresponding meanings: 
______________________________________ 
Branch Address The address at which the branch 
instruction resides. 
Target Address The address to which control is 
passed when a branch is taken. 
Branch Group A sequence of instructions whose 
addresses are sequential, i.e., 
it is a non-disjoint sequence. 
Each branch group begins with a 
branch-target instruction, and 
continues with all instructions 
that are sequential to and 
including the first taken branch. 
Disjoint Refers to a group of instructions 
which do not all reside in 
sequential locations within 
program memory. 
Triple A general term, used to specify a 
sequence of 3; i.e., a trio of 
taken branches, a sequence of 3 
branch groups, or starting 
addresses of three branch groups 
which will be executed in order. 
Branch-wrong-guess 
The event when the branch 
prediction mechanism makes an 
erroneous prediction of the 
outcome of a branch instruction. 
Steady-state operation 
Operation where all predictions 
correspond to the branches 
actually taken upon execution. 
ENDOP Refers specifically to the 
completion of execution of any 
instruction. 
______________________________________ 
I. Overview 
There are three main embodiments that describe the present invention: the 
first embodiment is directed to a simplex multibranch prediction device; 
the second embodiment is directed to a general n-plex multibranch history 
device with divergence detection and redirection; and the third embodiment 
is directed to a specific duplex multibranch prediction device with 
divergence detection and redirection. 
Following the "Best Mode for Carrying Out the Invention" section is an 
appendix section. Appendix A is a table that illustrates cycle-by-cycle 
operation of the duplex multibranch prediction device. 
A branch group is a sequence of instructions whose addresses are 
sequential, i.e., it is a non-disjoint sequence. The first instruction of 
a branch group is a branch-target instruction. A branch instruction causes 
instruction sequencing to jump from one branch group to the next. 
Each branch group begins with a branch-target instruction, and continues 
with all instructions that are sequential to the target instruction up to 
and including the first taken branch. The branch that terminates the 
branch group jumps to a new branch group or the same branch group starting 
address. A general multiple-instruction sequence comprises a sequence of 
branch groups, i.e., it comprises a sequence of disjoint 
instruction-sequences. 
FIG. 2 illustrates a high-level block diagram of a computer based 
environment in which the present invention operates. Referring to FIG. 2, 
a superscalar processor ("processor") 203 is capable of decoding and 
executing multiple instructions on each processing cycle. In prior art, 
the number of instructions that could be decoded on each cycle was limited 
to the number of instructions in a branch group. The present invention, to 
be described below, overcomes this limitation. 
A long multiple-instruction sequence generally contains multiple branch 
groups. In order to sustain the decoding of long multiple-instruction 
sequences on each cycle, it is necessary to fetch the constituent branch 
groups of each sequence on each cycle. Therefore, instruction busses must 
be sufficiently wide to permit entire branch groups to be fetched. 
Additionally, since the constituent branch groups must be fetched from 
disjoint locations in memory simultaneously, a multiported cache 202 is 
required to service multiple disjoint instruction-fetches in parallel. The 
structure and operation of a multiported cache 202 is well known to those 
skilled in the art. 
One preferred embodiment of the present invention is a Multibranch 
Prediction Device 201. The Multibranch prediction device 201 predicts the 
multiple branches per cycle that connect the branch groups. The 
Multibranch prediction device 201 also initiates the fetches of these 
branch groups from the multiported cache 202. 
When processor 203 initiates a program or recovers from a 
branch-wrong-guess (BWG), processor 203 provides a restart address on its 
address bus 214. This is the starting address of the first branch group of 
the instruction stream that is to be processed. The address is transmitted 
to the multiported cache 202 and to the multibranch prediction device 201 
on address bus 214. 
The first branch group is fetched from the multiported cache 202, by the 
processor 203 on one of the n instruction busses 212 (where n is an 
integer). Each of these n busses is capable of transmitting an entire 
branch group in a single cycle, i.e., the busses 212 provide an extremely 
wide connection. 
While the first branch group is being fetched from the multiported cache 
202, the restart address on bus 214 is also used to effect a look-up in 
the multibranch prediction device 201. The device 201 predicts the n 
branch groups that will follow the first branch group. The multibranch 
prediction device 201 predicts all n groups in a single cycle, and it 
provides the starting instruction address of each group, to the 
multiported cache 202 on the n address busses 211. 
Note that the multibranch prediction device 201, the multiported cache 202, 
and the superscalar processor 203 form a pipeline. On the first cycle 
described above, the first branch group is fetched from the multiported 
cache 202 while the next n branch groups are predicted by the multibranch 
prediction device 201. The first branch group is transmitted to the 
processor 203 on one of the busses 212, and the addresses of the next n 
branch groups are transmitted to the multiported cache 202 on the n 
address busses 211. 
On a second cycle, the instructions of the first branch group are decoded 
by the superscalar processor 203 while the next n branch groups are all 
fetched simultaneously from the multiported cache 202. These n branch 
groups are transmitted to the processor 203 on busses 212. At the same 
time, the multibranch prediction device 201 iterates on itself to predict 
the next n branch groups. 
On a third cycle and every cycle thereafter, n branch groups are decoded 
simultaneously by the superscalar processor 203. The decoding rate of n 
branch groups per cycle is sustained until the processor 203 determines 
that the multibranch prediction device 201 has mispredicted a branch. In 
this event, the process restarts with a new instruction address as 
described above for the first cycle. 
As the superscalar processor 203 completes the execution of instructions, 
it places information about each completed branch in a branch completion 
queue 204. The processor 203 can enqueue information about a sequence of n 
branches on every cycle. The processor 203 transmits the information to 
the branch completion queue 204 on the n busses 213. 
The branch completion queue (queue) 204 dequeues information on a 
first-in-first-out (FIFO) basis. The queue 204 must be able to hold as 
many as 2n entries. Note that a sequence of n+1 entries represents a 
single branch group followed by n successive branch groups. Therefore, 
whenever n+k entries are enqueued, k-1 sequences of n+1 branch groups are 
described by those entries. 
Whenever n+k entries are enqueued, the associated k-1 sequences of 
(n+1)-tuples are transferred to the multibranch prediction device. 201 on 
a subset of the 2n busses 215. After the transfer is complete, the entire 
queue 204 is shifted right k-1 positions so that k-1 oldest entries are 
discarded. Operation of a queue is well understood by those skilled in the 
art. 
To summarize, FIG. 2 illustrates the general case in which n branch groups 
are predicted per cycle. One preferred embodiment details the operation of 
multibranch prediction device for n=2, i.e., a specific embodiment for a 
multibranch prediction device that predicts two branches per cycle. The 
point n=2 is chosen as the simplest case that demonstrates the invention, 
but it is understood by those skilled in the art that this is not a 
limitation. 
II. An Example Program Sequence 
FIG. 3 is a symbolic illustration of a typical program. The program 
contains branch groups, each of which is a short group of sequential 
instructions that ends in a taken branch. Each taken branch causes a jump 
to the beginning of a new branch group. 
For example, there is a branch group that begins at symbolic address A and 
contains n.sub.a instructions. The last instruction in the branch group is 
a taken branch that goes to a new branch group that begins at symbolic 
address B. 
At an offset of b instructions from address B, there is a conditional 
branch that may be taken to address C, or it may fall through to a next 
sequential instruction. If the conditional branch falls through, there is 
an unconditional branch at an offset of n.sub.b-1 instructions from 
address B that is taken to address X. 
The other branches in this program are: from the branch group that begins 
at address D to the branch group that begins at address E; from the branch 
group that begins at address X to the branch group that begins at address 
Y; from the branch group that beings at address E to the branch group that 
begins at address A; from the branch group that begins at address Y to the 
branch group that begins at address A; and from the branch group that 
beings at address C to the branch group that beings at address D. 
As previously mentioned, this embodiment demonstrates the case where n=2, 
i.e., in this description of the operation of the device, 2 branches are 
predicted per cycle. Then for this case, (n+1)-tuples are 3-tuples, also 
called triples. The right most column in FIG. 3 lists the addresses 
associated with the triples of branch groups that occur as the program in 
the left column executes. 
For example, the first triple listed is ABC. This triple represents that 
the branch group that begins at address A was followed by a sequence of 
the two branch groups that begin at addresses B and C, respectively. The 
second triple represents that B is followed by C and D, respectively. 
For the triples shown, it is assumed that the conditional branch at address 
B+b is taken on its first three executions, not taken on its next three 
executions, and then taken again. Therefore, the program flow is ABCDE, 
for three iterations, followed by ABXY for three iterations, followed 
again by ABCDE. This means that the triple ABC changes to ABX, and the 
triple BCD changes to BXY after three iterations, and then both triples 
change back. The remaining triples, CDF, DEA, EAB, XYA, and YAB, do not 
change. 
The following description of the multibranch prediction device uses the 
example in FIG. 3 to demonstrate its operation. 
III. A Simplex Multibranch Prediction Device 
FIG. 4 illustrates a block diagram of a simplex multibranch prediction 
device that can predict two branches per cycle. This is the simplest 
device that illustrates the present invention. This device is called 
"simplex" because it comprises a single table. The single table in this 
device is called a multibranch history table 401, denoted MBHT. 
Each entry in the MBHT 401 contains information about a sequence of two 
branch groups. Two outputs 411 and 412 from the MBHT 401 characterize the 
pair. The first output 411 describes a first branch group, denoted BG1, 
and the second output 412 describes a second branch group, denoted BG2. 
Each branch is characterized by two addresses, e.g., BG1 comprises the pair 
of addresses BA1 and TA1. The first address is the address of the branch 
instruction, BG1. The second address is the address of the corresponding 
target instruction, TA1. The compound entry &lt;BG1,BG2&gt; contains four 
addresses, and is stored in a location in the table that is determined by 
the first address of its corresponding triple. Please note that BG1 and 
BG2 in FIG. 4 corresponds to instruction addresses IAn in FIG. 2. 
For example, the program in FIG. 3 contains the triple ABC. Execution of 
this triple would cause an entry to be made in MBHT 401. The location of 
the entry would be determined by address A. For this particular program, 
the fields of the entry corresponding to the triple ABC are: BA1=A+na-1; 
TA1=B; BA2=B+b and TA2=C. 
Referring to FIG. 3, if the MBHT 401 were subsequently searched using 
address A, this entry would be found. This search can be implemented using 
combinational logic to compare the address held in PFAR 402 to the address 
fields of entries in MBHT 401. The entry indicates that there is a taken 
branch at address A+na-1 that goes to address B, and another taken branch 
at address B+b that goes to address C. The entry thus contains sufficient 
information to represent transitions from A to B and from B to C, i.e., it 
exactly describes the locations of all instructions necessary to execute 
the triple ABC. 
As pictured in FIG. 4, the MBHT 401 is direct mapped, but it should be 
understood that it can be implemented as a set associative structure. Such 
implementations are well understood in the industry. Further, it should be 
understood that within such a structure, not all of BA1 must be stored; 
rather, a portion of BA1 is used to locate the entry within the structure, 
thereby rendering that portion of it implicit to its location. Further, 
since BA2 is known to be a short offset from TA1, it is obvious to the 
routineer that BA2 could be represented as that offset. These are all 
implementation trade-offs that have to do with economy of table space; 
none of them are central to the subject invention. 
The MBHT 401 is searched based on the address in a prefetch address 
register 402, denoted PFAR. When the MBHT 401 is being read, a selector 
403 routes the address in PFAR 402 to the address inputs 413 of MBHT 401. 
The address in PFAR 402 is the starting address of an instruction 
sequence, and if a corresponding entry is found in MBHT 401, then the 
outputs BG1 411 and BG2 412 are addresses of branch groups that are 
believed to follow in the instruction sequence. 
Note that if an entry is found in MBHT 401, then an address triple on lines 
410, 411, and 412 represents a predicted triple of branch groups. The 
predicted triple is enqueued on a pending guess queue 404 where the triple 
is subsequently used to filter unnecessary updates. 
Recall from FIG. 2 that triples are transmitted from the branch completion 
queue 204 to the multibranch prediction device 201 along busses 215. These 
busses 215 enter the multibranch prediction device 201 as lines 414, 415, 
and 416 in FIG. 4, i.e., these busses entering FIG. 4 transmit the 
addresses of branch group triples. 
As completed triples arrive on busses 414,415, and 416, a comparator 
circuit 405 compares them to predicted triples in pending guess queue 404. 
If the comparator circuit 405 determines that the pending guess queue 404 
does not contain a completed triple whose addresses are on lines 414, 415, 
and 416, then it infers that the triple is not known to the MBHT 401, and 
it enqueues the arriving triple on the update queue 406 after receiving an 
activation signal 417 from comparator circuit 405. If the comparator 
circuit 405 determines that the pending guess queue 404 does contain the 
completed triple on lines 414, 415, and 416, then the corresponding entry 
is deleted from the pending guess queue 404, and the arriving triple is 
not enqueued on the update queue 406. 
If there are entries enqueued in the update queue 406, they are transferred 
to the MBHT 401 on cycles when the MBHT 401 is not being searched. To make 
this transfer, selector circuit 403 routes a first address of the triple 
418 to the address inputs 413 of the MBHT 401, and the remaining addresses 
of the triple are routed to MBHT 401 via data inputs 419, and 420 of the 
MBHT 401 where they are stored. 
In steady-state operation in which all predictions are correct, the device 
in FIG. 4 drives itself. That is, as long as branch triples are predicted 
correctly, the third address of each triple 412 is routed through a 
selector circuit 407 (the selector circuit acts as a 2:1 multiplexer) and 
loaded into PFAR 402 where it is used as a starting address to search the 
MBHT 401 on the next cycle. 
From FIG. 2, when the processor 203 initiates a program or recovers from a 
branch-wrong-guess (BWG), it provides a restart address on its address bus 
214. This bus 214 is connected to the multibranch prediction device 201 
and corresponds to START input 408 shown in FIG. 4. Referring back to FIG. 
4, START input 408 is a starting address for a first branch group of the 
instruction stream that is to be processed. 
Therefore, following a power-on sequence, or following a branch wrong 
guess, selector circuit 407 is set to route the START input 408 to the 
PFAR 402. Once the device has started up, the selector circuit 407 is 
switched to route output 412 to the PFAR 402 as described above for 
steady-state operation. (Switching can be performed a number of ways. For 
example, the processor can send a control signal on restart address bus 
214, shown in FIG. 2, to selector 407. Other methods are possible and 
would be readily apparent to those skilled in the art.) 
For example, consider the program in FIG. 3 as it interacts with the device 
in FIG. 4. When the program begins from address A, selector circuit 407 
causes PFAR 402 to be loaded from the START input 408, which should be 
receiving address A. The MBHT 401 is searched, and assuming that the 
triple ABC has been stored there, outputs 411 and 412 will produce 
addresses D and E respectively. 
On the third cycle (clock cycle or processor cycle), the PFAR 402 is loaded 
with address E, and operation continues as described above to produce 
output pairs AB, CD, EA, BC, etc., on successive cycles. Steady-state 
operation continues until there is a branch wrong guess. Following a 
branch wrong guess, the device is restarted from the START input 408. A 
more detailed description of the operation follows in a later section, 
including updating the MBHT 401. 
IV. An n-plex Multibranch Prediction Device 
The subject invention comprises two elements that should be present to 
perform reliable multiprediction. First, and by definition, a 
multiprediction device must provide a multiplicity of branch predictions 
simultaneously. This aspect of the invention has already been described in 
the previous subsections. Second, for the multipredictor to perform 
accurately and reliably, the device should contain elements to detect and 
correct divergences in the multiplicity of branch predictions. 
A device that predicts branch behavior based on past history can predict 
with a low margin of error, but not perfectly, i.e., it is inevitable that 
some of the predictions are wrong. In a device that predicts one branch at 
a time, mispredictions decrease accuracy straightforwardly. In a 
multipredictor, the accuracy degenerates geometrically with the length of 
the sequence being predicted, i.e., mispredictions have a more dramatic 
impact on multipredictors. 
The discussion thus far, with reference to FIG. 4, has been limited to a 
device for which n=2, i.e., simplex, but with no capability to detect 
divergence in the second predicted branch. FIG. 4 could be generalized to 
a device that provides n predictions per cycle by expanding the entries in 
the MBHT 401 to include n address pairs: &lt;BA1,TA1&gt;, &lt;BA2,TA2&gt;, . . . , 
&lt;BAn,TAn&gt;. This generalization would still lack the capability for 
detecting divergence within the predicted n-tuple. 
FIG. 5 illustrates a block diagram of a general n-plex multibranch 
prediction device that provides n predictions per cycle, and that also 
provides a means for early detection and correction of each of those n 
predictions. FIG. 5 represents the most general implementation that 
carries out the elements of the subject invention. 
FIG. 5 contains n copies of the multibranch prediction device depicted in 
FIG. 4, with each of those devices expanded to provide n simultaneous 
predictions as described above. 
Specifically, each of the boxes MBHTn, . . . , MBHT2, MBHT1 in FIG. 5 
contains the device shown in FIG. 4, with the entries in the MBHT 401 
expanded to include n address pairs. The device in FIG. 4 is further 
modified for use in FIG. 5 by removing the selector circuit 407 and the 
feedback path 412 from the device, and routing the primary input 408 
directly to the PFAR 402. This input 408 is driven in an appropriate 
manner by the remaining circuitry in FIG. 5. A description of the 
operation of the n-plex multibranch prediction device in FIG. 5 follows. 
From FIG. 2, when the processor 203 initiates a program or recovers from a 
branch-wrong-guess (BWG), it provides a restart address on its address bus 
214. This bus 214 going to the multibranch prediction device 201 is the 
START input 510 in FIG. 5. This is the starting address of the first 
branch group of the instruction stream that is to be processed. 
Therefore, following a power-on sequence, or following a branch wrong 
guess, selector circuit 501 is set to route the START input 510 to the 
PFAR (not shown) contained in MBHTn 502. Once the device has started up, 
the selector circuit 501 is switched to route output instruction address 
IAn 511 to MBHTn 502 so that the table becomes self-driven as was 
described for FIG. 4. 
MBHTn 502 is called the "Primary Multibranch History Table," and its role 
is to provide predictions that are n branches further into the instruction 
stream than the previous predictions. This is why the nth predicted 
instruction address IAn 511 is routed back to the input of the primary 
table 502 on each cycle. 
If it were the case that the primary MBHT 502 never mispredicted a branch, 
the n-1 remaining MBHTs and selection circuitry would not be required. 
That is, FIG. 4 can be obtained directly from FIG. 5 by deleting all 
hardware from FIG. 5 except the input selector 501 and the primary MBHT 
502. The n-1 remaining MBHTs and selection logic in FIG. 5 provide early 
detection and correction for divergence in the branch sequence predicted 
from the primary MBHT prediction device 502. 
The output of FIG. 5 is an n-tuple of predicted instruction addresses 512, 
labeled IA1, IA2, . . . , IAn. Instruction address IAn 511 is the nth 
address of the n-tuple, and it is used to drive the primary MBHT 502 as 
described above. Each of the remaining n-1 instruction addresses drives a 
distinct secondary MBHT. 
For example, instruction address IA1 513 drives secondary MBHT1 503. Note 
that the original source of IA1 513 is the first branch target address of 
the n-tuple predicted by the primary MBHT 502. The output of the secondary 
table MBHT1 503 is an n-tuple of branch target addresses that are 
predicted as successive to IA1 513. 
Simultaneously, instruction address IA2 514 drives secondary MBHT2 504. 
Note that the original source of IA2 514 is the second branch target 
address of the n-tuple predicted by the primary MBHT 502. The output of 
the secondary table MBHT2 504 is an n-tuple of branch target addresses 
predicted as successive to IA2 514. 
Comparator circuit 505 compares address IA2 514 to the first instruction 
address output 515 of the secondary MBHT1 503. Recall that since secondary 
MBHT1 503 is driven by IA1 511, its first instruction address output 515 
should be the same as IA2 514 as predicted by the primary MBHT 502. That 
is, the first output 515 of MBHT1 503 should be the same as the second 
output 514 of MBHTn 502. 
Similarly, the first output 516 of MBHT2 504 should be the same as the 
third output 517 of MBHTn 502. A comparator circuit 506 makes this 
determination. Each of the n-1 secondary MBHTs have a comparator circuit 
which compares the first output address of the n-tuple predicted by the 
associated secondary MBHT to the appropriate address of the n-tuple that 
was predicted by the primary MBHT 502 on the previous cycle. If all MBHTs 
contain consistent information, all comparator outputs will indicate that 
all addresses match. 
If any comparator does not find a match, then the secondary MBHT that is 
associated with that comparator contains information that is inconsistent 
with the primary MBHT 502. In this event, the information in the secondary 
MBHT is assumed to be correct, and the information in the primary MBHT 502 
is assumed to be faulty. 
This assumption is partially based on the arguments given in the third 
paragraph of this subsection, i.e., the first output of each table is 
inherently more accurate than the kth (each successive) output. For each 
secondary MBHT, it is the first output of the MBHT that is compared to the 
appropriate output, but not the first output, of the primary MBHT 502. 
Thus, the secondary MBHTs are given priority over the primary MBHT in the 
event of a miscompare. 
The encoder circuit 507 determines whether there are any miscompares. If 
there are no miscompares, then the encoder output 518 causes the selector 
circuit 508 to route the outputs of the primary MBHT 502 to the register 
509 where they are stored for use on the next cycle. 
IF there is exactly one miscompare, then the encoder circuit 507 causes the 
selector circuit 508 to route the outputs of the associated secondary MBHT 
to the register 509. For example, if the comparator 505 determines that a 
first output 515 of MBHT1 503 is not the same as IA1 513 as predicted on 
the previous cycle, then the outputs of MBHT1 503 are routed through the 
selector 508 to the register 509. 
If there are multiple miscompares, then the first of the MBHTs that 
miscompares is given priority, since that MBHT indicates the first point 
of divergence in the predicted stream. The first of the secondary MBHTs is 
the right most table as it is pictured in FIG. 5. For example, if both 
comparators 505 and 506 indicate miscompares, the encoder circuit 507 will 
give priority to MBHT1 503. 
Note that the register 509 that holds the selected n-tuple is redundant 
with respect to the PFARs of the n MBHTs, i.e., it holds the n PFAR 
contents. This register need not be present in the FIGURE, but is shown 
this way to clearly distinguish predictions made on subsequent cycles. 
Also note that the "UPDATES" input 519 in FIG. 5 is included for 
completeness. This is the set of busses that are used to transmit the 
executed (n+1)-tuples for storage in the MBHTs, i.e., these are the busses 
215 in FIG. 2. The update operation was not described in this subsection, 
but was described in the previous subsection, and will be described in 
more depth in the next subsection. 
The secondary MBHT's provide two functions. First, the first address output 
of an n-tuple provides a means for detecting divergence in the n-tuple 
predicted by the primary MBHT. For example, output 515 of MBHT1 503 is 
compared to IA2 514 to determine whether the second address predicted by 
the primary MBHT 502 has diverged. 
The second function provided by a secondary MBHT is that it can provide the 
replacement n-tuple(s) if its first address does not match the associated 
address from the primary MBHT. For example, MBHT1 503 provides the n-tuple 
output 520 if the first address of the n-tuple 515 does not match IA1 514 
from the primary MBHT 502. 
That is, the first address output of a secondary MBHT provides divergence 
detection, and the remaining n-1 addresses provide immediate correction to 
the divergence. Therefore, the last n-1 addresses are not necessary in an 
implementation that only requires divergence detection. Divergence 
correction can be provided by the primary MBHT 502 on a subsequent cycle 
once the divergence has been detected. A more economical, but slightly 
slower implementation would have secondary MBHTs that only output a single 
address. 
A further reduction to the design would be to eliminate some of the 
secondary MBHTs. That is, it is not necessary to provide divergence 
detection at every branch in the n-tuple; it may be sufficient to detect 
divergence on every other branch. This is strictly a cost-performance 
trade-off. A general k-plex multiprediction device is constructed from k&lt;n 
MBHTs. If k=1, there is no divergence detection. 
A final note is that in theory, all MBHTs should contain identical 
information, since all of the information comes from the same processor. 
Were this the case, there would never be miscompares, and the Secondary 
MBHTs would not be needed. 
In fact, the MBHTs are finite, have limited set-associatives, have limited 
porting, etc., so distinct MBHTs will not be able to store identical 
information. Further, since the executed stream will have breaks and 
mispredicted branches in it, there will be incomplete information coming 
in on the update busses 519. That is, it may be advisable to store 
incomplete tuples in some of the MBHTs; particularly if the secondary 
MBHTs do not store full n-tuples, as was described above. In practice, the 
MBHTs will not contain identical information; the extent to which they 
differ is implementation-dependent. 
FIG. 6 shows the high-level logic flow for generic multiprediction. In a 
step 601, the first address of a new instruction sequence is used to 
search the primary MBHT. This search results in n predicted addresses. 
These n addresses are used by the next three steps 602, 603, and 604 
simultaneously. 
In a step 602, the last address of the n-tuple predicted by the previous 
step 601 is staged as the next starting address that is to be used on the 
next search of the primary MBHT, i.e., on the next cycle of the first step 
601. Simultaneously in a step 603, the remaining n-1 addresses are used to 
search secondary MBHTs. Also simultaneously in a step 604, the n addresses 
that were predicted in a previous step 601 are used to fetch the n 
instruction streams, and stage them for execution by the processor. 
In a decision step 605, the outputs of the secondary MBHTs obtained in the 
previous step 603 are compared to the outputs obtained from the primary 
MBHT in the previous step 601. If there is an inconsistency in the 
predicted streams, t]hen the next starting address is changed in a step 
606. The next starting address is chosen to be the one predicted by the 
first of the MBHTs that differs as is determined in step 605. 
Meanwhile in a step 607, the processor decodes and executes the instruction 
streams that were fetched in a previous step 604. If the actual execution 
of branches differs from the sequence of branches that was predicted in a 
previous step 601, then the next starting address is determined by the 
actual executed sequence in the processing step 607. This substitution is 
made in a selection step 608 if it is required. 
The address selected in the final step 608 is used to restart the process 
from the initial step 601. 
V. Duplex Multibranch Prediction Device 
In Section III, simplex multiprediction was described in detail. Simplex 
multiprediction is the simplest multiprediction scheme, but it does not 
contain any aspect of divergence detection and redirection. In Section IV, 
n-plex multiprediction was described in general. This is the most generic 
multipredictor that contains full divergence detection and correction. 
In this section, duplex multiprediction is described in detail. Duplex 
multiprediction is the simplest example of n-plex prediction, i.e., it is 
simple enough to describe in detail, yet sufficiently complex to 
illustrate divergence detection. 
FIG. 7 illustrates a block diagram of a duplex multiprediction device that 
is capable of predicting two branches per cycle, and is capable of 
detecting and correcting divergence in the second branch of the predicted 
pair. 
FIG. 7 includes two copies of the simplex multipredictor device shown in 
FIG. 4, a comparator circuit 718 used for divergence detection, and two 
selector circuits 709 and 710 used to redirect the predicted stream. The 
two simplex multipredictor devices are called the primary and secondary 
multibranch history tables, PMBHT 701 and SMBHT 711, respectively. 
It is helpful to compare FIG. 4 with FIG. 7 so that elements of the 
distinct MBHTs are apparent. First, the actual MBHT 401 in FIG. 4 appears 
as the two MBHTs, 701 and 711 in, FIG. 7, as was just mentioned. The PFAR 
402 that is used to search the MBHT 401 in FIG. 4 appears as a primary and 
a secondary PFARs, labeled PPFAR 702 and SPFAR 712, respectively, in FIG. 
7. The selector circuit 403 in FIG. 4 becomes the two selector circuits 
703 and 713 in FIG. 7. The pending guess queue 404 in FIG. 4 appears as 
the primary and secondary pending guess queues 704 and 714, respectively, 
in FIG. 7. The comparator associated with the pending guess queue 405 in 
FIG. 4 appears as the two comparators 705 and 715 in FIG. 7. Finally, the 
update queue 406 in FIG. 4 appears as the primary and secondary update 
queues 706 and 716, respectively, in FIG. 7. 
The starting input selector 408 in FIG. 4 is the same as the starting input 
selector 708 in FIG. 7. Recall from the discussion of the n-plex 
multiprediction that only the primary MBHT receives its input from this 
selector. The new hardware in FIG. 7 is the comparator 718 and the two 
selectors 709 and 710 that were already mentioned. A description of the 
operation of the device in FIG. 7 follows. 
From FIG. 2, when the processor 203 initiates a program or recovers from a 
branch-wrong-guess (BWG), it provides a restart address on its address bus 
214. This bus 214 going to the multibranch prediction device 201 is the 
START input 719 in FIG. 7. This is the starting address of the first 
branch group of the instruction stream that is to be processed. 
Therefore, following a power-on sequence, or following a branch wrong 
guess, selector circuit 708 is set to route the START input 719 to the 
PPFAR 702. Once the device has started up, the selector circuit 708 is 
switched to route output 726 to the PPFAR 702 for steady-state operation. 
In steady-state operation, the first address output of the duplex 
multibranch prediction device, BG1 725, is loaded into SPFAR 712 where it 
is used to drive the secondary MBHT 711 on the subsequent cycle. At the 
same time, the second address output of the device BG2 726 is loaded into 
PPFAR 702 where it is used to drive the primary MBHT 701 on the subsequent 
cycle. 
Using the second address 726 to drive the primary MBHT 701 allows the 
primary MBHT 701 to stay two branches ahead of the last predicted pair, 
i.e., the primary MBHT 701 predicts two new branches on each cycle. Using 
the first address 725 to drive the secondary MBHT 711 causes the secondary 
MBHT 711 to lag one branch behind the primary MBHT 701. 
Therefore, a first output 723 of the secondary MBHT 711 should match a 
second output 722 of the primary MBHT 701 from the previous cycle. But 
note that the second output 722 of the primary MBHT 701 from the previous 
cycle was stored in the PPFAR 702 at the end of that cycle. Therefore, the 
comparator 718 compares the address from the first output 723 of the 
secondary MBHT 711 with the address in the PPFAR 702 on every cycle. 
As long as the comparator circuit 718 determines that these addresses 
match, the primary MBHT 701 continues to drive the duplex multibranch 
prediction device. Specifically, the comparator 718 causes the selectors 
709 and 710 to route the outputs 721 and 722 from the primary MBHT 701 to 
the outputs 725 and 726, respectively, of the duplex multibranch 
prediction device 700. As explained above, the first output 725 will be 
used to drive the secondary MBHT 711, and the second output 726 will be 
used to drive the primary MBHT 701 on the next cycle. 
If the comparator circuit 718 determines that the two addresses do not 
match, then the secondary MBHT 711 will drive the duplex multibranch 
prediction device on the next cycle. Specifically, the comparator 718 
causes the selectors 709 and 710 to route the outputs 723 and 724 from the 
secondary MBHT 711 to the outputs 725 and 726, respectively, of the duplex 
multibranch prediction device 700. 
This concludes the basic description of the operation of the duplex 
multibranch prediction device 700. Note that both tables PMBHT 701 and 
SMBHT 711 are loaded with information about branch group triples from the 
busses (S1, S2, S3) 727. 
The updates to the tables PMBHT 701 and SMBHT 711 work just as they did in 
the description of the simplex MultiBranch prediction device 400. Very 
simply, when MBHT 701, 711 makes a prediction, they record the prediction 
in pending guess queues 704, 714. As executed triples arrive on the busses 
727, they are compared to the predicted triples in the pending guess 
queues 706, 716. If the actual triple does not match the predicted triple, 
then the actual triple is placed onto the update queue 706, 716. Entries 
in the update queue are written into MBHTs 701, 711 during idle cycles. 
In theory, if both MBHTs 701 and 711 were infinitely large fully 
associative tables, and both could receive and store all triples 
completely and in a timely fashion, then there would be no need for the 
secondary MBHT 711. In practice, the MBHTs 701 and 711 will not always 
contain consistent information, and divergence will occur in the predicted 
stream. 
VI. Example of Operation of a Duplex Multibranch Predictor 
In this section, a detailed description is given of the operation of the 
device shown in FIG. 7 while running the program shown in FIG. 3. In the 
program flow, it is assumed that the branch instruction at address B+b in 
FIG. 3 is taken for the first six iterations, and not taken thereafter. 
Then the branch groups that are executed are six iterations of ABCDE, 
followed by multiple iterations of ABXY. 
Note that FIG. 7 is not detailed enough to convey the precise operations of 
its constituent queues, or of the processor pipeline. Since these precise 
workings determine the exact way in which the device operates, it is 
necessary to specify them. In other words, queues are generally referred 
to in FIG. 7 and may be customized for particular application systems. 
Note that any set of precise rules can be specified, and each precise set 
may change the general operation of the device, but the basic invention 
remains the same. 
For the purpose of illustration, the following 8 rules are used in 3 
different categories: 
Operation of the Processor Pipeline: 
Rule 1--When a branch instruction is executed, its target address is staged 
for instruction fetching on the actual execution cycle of the branch. 
Rule 2--A branch group is considered to have executed on the cycle 
immediately following its execution cycle. That is, any triples S1. S2. S3 
that are completed by executing the branch group will be sent to the 
duplex multiprediction device 700 on the cycle immediately following the 
execution of the branch group. 
Rule 3--If there is a secondary MBHT 711 hit on a cycle in which there is a 
primary MBHT 705 miss, then the outputs of the secondary MBHT 711 are 
staged to drive the instruction fetching on the following cycle. 
Management of the Update Queues, and Updating of the MBHTs: 
Rule 4--Assume that there is a mechanism that prevents duplicate entries 
from being placed into an Update Queue 706, 716. For example, if the 
Primary Update Queue 706 contains the triple ABC, and a new copy of the 
triple ABC arrives on the update busses 727, then the new copy will not be 
placed into the Primary Update Queue 706, even if there is no entry ABC in 
the Primary Pending Guess Queue 704. 
Rule 5--When the processor 203 executes two branch groups simultaneously, 
this generally results in two triples being transmitted to the duplex 
multiprediction device 700 simultaneously. Assume that an update queue 
706, 716 can only process one triple per cycle, and that there is no 
buffer present to hold a second triple. Then if two triples arrive 
simultaneously, the first triple is only sent to the Primary Update Queue 
706, and the second triple is only sent to the Secondary Update Queue 716. 
Rule 6--Nominally, the MBHT 701, 711 is searched on every cycle, and 
updates cannot be done at the same time as searches. Therefore, to ensure 
that updates in the update queue 706, 716 are eventually put into the MBHT 
701, 711, updates are given priority for one cycle on the cycle following 
a miss. 
Management of the Pending Guess Queues. 
Rule 7--When a triple S2, S2, S3 arrives on the update bus 727 and is 
compared to all entries in a pending guess queue 704, 714, if at least one 
match is found in the pending guess queue 704, 714, then the oldest entry 
that matches is deleted, and all entries that are older than that entry 
are deleted from the queue. 
Rule 8--When the processor 203 discovers that a branch has been guessed 
incorrectly, all entries in the pending guess queue 704, 714 are deleted. 
APPENDIX A illustrates a cycle-by-cycle operation (the first 56 cycles of 
operation) of duplex multiprediction device 700 shown in FIG. 7 running 
the program in FIG. 3 subject to the eight rules above. The leftmost 
columns show the cycle number, starting with 0 and increasing to 55. There 
are four major subdivisions of the remaining columns. 
The first set of columns shows the flow within the superscalar processor 
203 and multiported cache 202. The Address Stage column shows the 
instruction addresses that are staged for fetching on the following cycle. 
The Cache Access column shows the branch groups that are fetched during 
the cycle. The Processor operation is shown in two columns: Decode, and 
Execute. These columns show the branch groups that are decoded and 
executed during the corresponding cycles. ENDOP group triples are shown in 
two columns because there can be two triples that ENDOP per cycle, as per 
Rule 5 above. Note that ENDOP Triples appear on the cycle following the 
execution of the last branch group of the triple, as per Rule 2 above. 
The three remaining subdivisions of columns show the resources within the 
duplex multibranch prediction device 700. Two of the subdivisions are for 
the Primary MBHT 700, and the Secondary MBHT 711. The COME column 
between the two shows the operation of the comparator 718 in FIG. 7 as it 
compares the first output of the Secondary MBHT 711 to the contents of the 
PPFAR 702, which nominally contains the second output of the Primary MBHT 
701 from the preceding cycle. 
The operation of each of the MBHTs 701, 711 is detailed in seven columns 
per MBHT. The first of the columns is the PFAR 702, 712, which shows the 
address that is used to search the MBHT 701, 711. The next two columns, 
BG1 721, 725 and BG2 723, 724, are the two outputs that result from having 
searched MBHTs 701, 711 with the contents of PFAR 702, 712. Note that the 
outputs 721, 722 and 723, 724, respectively, become available on the 
cycles following the loading of the PFAR 702, 712. The remaining four 
columns show the operation of the four queues 704, 706, 714, 716. 
For the Pending Guess Queues 704, 714, and for the Update Queues 706, 716, 
there is an Enqueue column that shows entries being placed into the queue, 
and a Dequeue column that shows entries leaving the queue. Typically, 
triples are enqueued in the Pending Guess Queue on the cycle that the 
corresponding MBHTs 701, 711 outputs appear. As triples ENDOP at the 
processor 203, they are used to dequeue matching entries from the Pending 
Guess Queues 704, 714 on the same cycle. If no matching entries are found, 
then the ENDOP triples are enqueued in the Update Queue 706, 716 subject 
to Rule 5 above, i.e., one triple per MBHTs 701, 711. 
When MBHTs 701, 711 can accept an update, the corresponding entry is 
dequeued from its Pending Guess Queues 704,714 on the same cycle in which 
the update is done. Note that if the MBHTs 701, 711 are idle when an ENDOP 
triple is received, the triple is effectively enqueued and dequeued 
simultaneously as the MBHTs 701, 711 are updated. This is denoted in 
APPENDIX A by showing the triple in parentheses in both the Enqueue and 
Dequeue columns on the update cycle, e.g., see the Secondary Update Queue 
column for cycle #7 in the Appendix. 
In this example flow, the first branch group of the program has starting 
address A. The flow starts on Cycle #0 with instruction address A stated 
for instruction fetching. Note that the address that is staged for 
instruction fetching is also used to search the Primary MBHT 701, so the 
PPFAR 702 is also loaded with the address A on Cycle #0. In this example, 
it is assumed that both MBHTs 701, 711 start with no valid entries in 
them. 
On Cycle #1, the Cache is accessed, and the branch group at address A is 
fetched. The outputs of the Primary MBHT 701 also become available. Since 
the MBHT 701 is empty, the result of the search is a miss; see the PBG1 
721 and PBG2 722 columns. Since there is a miss, the multibranch 
prediction device 700 cannot yet begin to drive the instruction fetching, 
and the nominal pipeline flow must proceed in a relatively slow fashion. 
On Cycle #2 branch group A is decoded, and on Cycle #3 it is executed by 
the processor 703. As per Rule 3 above, B is discovered as the successor 
to A on the execution of cycle of A, that is, on Cycle #3. Therefore, the 
address of B is placed into Address Stage, and is also loaded into the 
PPFAR 702 on Cycle #3. 
Since the MBHTs 701, 711 are still empty, B flows through the pipeline in 
exactly the same manner as did A. The one exception is that when B 
executes on Cycle #6 and its successor is found to be C, this represents 
the first triple of the run, i.e., the sequence ABC has been discovered. 
Therefore, the triple ABC appears at ENDOP on Cycle #7 as per Rule 2 
above. Since this is the only ENDOP triple, Rule 5 is not relevant, and 
the triple ABC is sent to both MBHTs 701, 711 on Cycle #7. 
Note that the Primary MBHT 701 is busy on Cycle #7 because a search was 
staged for address C on the preceding cycle. Therefore, the arriving 
triple ABC is placed into the Primary Update Queue 706 on Cycle #7. Since 
no primary search was staged on Cycle #7, the Primary MBHT 701 is 
available for an update on Cycle #8. The Output column is labeled 
"Update-ABC" on Cycle #8 to indicate the update activity. Note that ABC is 
dequeued from the Update Queue when the update is done. Also note that 
even if the PPFAR 702 had been loaded on Cycle #7, the update would have 
been given priority over the search because there was a miss on Cycle #7 
as per Rule #6. 
The Secondary MBHT 711 is idle on Cycle #7 because searches on the 
Secondary MBHT 711 are only generated on behalf of Primary MBHT 701 n 
bits, and there has been no primary hit. Therefore the arriving triple ABC 
is immediately stored in the Secondary MBHT 711 on Cycle #7. The Output 
column is labeled "Update-ABC" on Cycle #7 to indicate the update. Also, 
as mentioned before, the triple ABC is shown in parenthesis being enqueued 
and dequeued simultaneously from the Secondary Update Queue 716. This 
notation is used to convey the fact that the entry ABC is not in the queue 
at the end of the cycle, but the queue is busy during the cycle 
determining that the entry should not remain in the queue. 
Execution of branch groups, and updating of MBHTs 701, 711 with ENDOP 
triples continues in the same manner through Cycle #15. By Cycle #15, the 
branch groups A, B, C, D, and E have all been executed, and the triples 
ABC, BCD, and CDE have been discovered and entered into both tables. On 
Cycle #15, A is discovered as the successor to E when E executes. Address 
A is staged for instruction fetching, and is loaded into the PPFAR 702 on 
this cycle. 
This time, searching the Primary MBHT 701 with address A results in a hit 
on Cycle #16, and the outputs are B and C respectively. This hit is the 
result of having stored the triple ABC on Cycle #8 above. The hit results 
in addresses B and C being staged for instruction fetching, address C 
being loaded into PPFAR 702, and address B being loaded into SPFAR 712 all 
on Cycle #16. The hit also represents that a guess is made that the 
sequence ABC is upcoming. Therefore, the triple ABC is placed into the 
Primary Pending Guess Queue 704. 
On Cycle #17, the result of searching the Primary MBHT 701 with address C 
is the output pair D and E. These addresses are staged for the next 
instruction fetch, and the triple CDE is enqueued in the Primary Pending 
Guess Queue 704. The result of searching the Secondary MBHT 711 with 
address B is the output pair C and D. The first output C is compared to 
the contents of PPFAR 702, which is also C, so no corrective action is 
taken. PPFAR 702 is loaded with E, and SPFAR 712 is loaded with D. 
Since the triple EAB has not yet occurred, the Primary MBHT 701 search on 
address E results in a miss on Cycle #18. This ensures that the triple DEA 
in the primary Update Queue 706 will be entered into the Primary MBHT 701 
on Cycle #19 as per Rule #6. Searching the Secondary MBHT 711 on address D 
results in the output pair E and A. Since there is a primary miss, the 
output of the secondary table is used to drive the instruction fetching as 
per Rule #3. Since the secondary table only stays one branch group ahead 
of the instruction fetching, only the single fetch A is staged on Cycle 
#18, and A is loaded into PPFAR 702. Note that the A is shown in 
parenthesis in the PPFAR 712 on this cycle, since it is known that the 
search on A will be delayed by one cycle because of the update that is to 
be done as per Rule #6. 
On Cycle #19, the processor 203 executes its first simultaneous pair of 
branch groups, B and C. The Primary MBHT 701 is updated with the triple 
DEA, and the PPFAR 702 continues to hold address A. Since the Secondary 
MBHT 711 is idle, it immediately accepts the triple EAB for update as it 
ENDOPs on this cycle. Since the Primary MBHT is busy updating the triple 
DEA, the newly arriving triple EAB is enqueued at the update queue 706, 
716. 
On Cycle #20, the two triples ABC and BCD ENDOP simultaneously. The first 
triple ABC is sent to the Primary MBHT 701, and the second triple BCD is 
sent to the Secondary MBHT 711 as per Rule #5. At the Primary MBHT 701, 
the triple ABC is discovered in the Pending Guess Queue 204, which 
indicates that the Primary MBHT 701 already has knowledge of the triple. 
The resulting action is to dequeue ABC from the Primary Pending Guess 
Queue 704 as per Rule #7. Similarly, at the Secondary MBHT 711, the triple 
BCD is discovered in the Pending Guess Queue 714, which indicates that the 
Secondary MBHT 711 already has knowledge of the triple. The resulting 
action is to dequeue BCD from the Secondary Pending Guess Queue 714 as per 
Rule #7. 
On Cycle #21, the two triples CDE and DEA ENDOP simultaneously. A similar 
set of actions as for Cycle #20 occur, resulting in CDE being dequeued 
from the Primary Pending Guess Queue 701, and DEA being dequeued from the 
Secondary Pending Guess Queue 711. Address E is loaded into PPFAR 702 on 
Cycle #21. 
On Cycle #22, the result of searching the Primary MBHT 701 on address E is 
a miss. Note that the ENDOP triple EAB has occurred on Cycle #19, and it 
is present in the Primary Update Queue 706, but the Primary MBHT 701 has 
been fully utilized since Cycle #15, and the update of EAB has not yet 
occurred. Thus, the Primary MBHT 701 misses on address E. Note that Rule 
#6 guarantees that the update will be done on the next cycle; this is the 
reason for having a Rule #6, or something like it. 
On Cycle #23, the Primary MBHT 701 is updated with EAB. From this cycle on, 
the five triples ABC, BCD, CDE, DEA, and EAB are indicated by both tables, 
and instruction fetching reaches steady-state. The multibranch prediction 
device 700 successfully initiates two fetches per cycle for the next 
eleven cycles, and the processor executes two branch groups per cycle for 
Cycles #27-34. 
On Cycle #34, the seventh execution of the branch group at B occurs, and 
this time the successor is found to be X, not C as was the case in the 
first six executions. This represents an incorrect branch prediction, so 
it causes the pipeline to restart on Cycle #35. 
The restart of Cycle #35 is accomplished by staging address X for 
instruction fetching, clearing the remainder of the pipeline, clearing 
both pending guess queues 704, 714, and suppressing the outputs 721, 722, 
723, 724 of both MBHTs 701, 711. This suppression is denoted by putting 
parentheses around the outputs in APPENDIX A. The pipeline then begins 
processing the sequence A, B, X, Y, etc., and the two MBHTs 701, 711 are 
eventually updated with the new triples. 
A point of interest is Cycle #42, in which the Primary MBHT 701 remembers 
that A is followed by B and C. Note that C is no longer part of the actual 
sequence. Nonetheless, an instruction fetch is staged for C, and PPFAR 702 
is loaded with C while SPFAR 712 is loaded with B. 
On Cycle #43, the Secondary MBHT 711 indicates that B is followed by X and 
Y. Compare circuit 718 detects the divergence, and redirects the 
instruction fetching in accordance with the Secondary MBHT 711 outputs 
723, 724. 
Note that the same divergence is detected again on Cycle #48. This is 
because the actual triple ABX first ENDOPTed on Cycle #35 as the second 
triple of a pair of triples. The bandwidth limitation of the queues 
imposed by Rule #5 prevents this triple from being sent to the Primary 
MBHT 701. The triple ABX is first transmitted to the Primary MBHT 701 on 
Cycle #46, but because the Primary MBHT 701 is busy, it never gets updated 
with this triple in the APPENDIX. 
Since the Primary MBHT 701 predicts two branch groups ahead per cycle, and 
since the sequence A, B, X, Y contains four branch groups, the Primary 
MBHT 701 does not need not know about the triple ABX after this second 
redirection. From Cycle #48 onward, the Primary MBHT 701 is searched only 
on addresses Y and B, so the triple BAX is never reencountered by the 
Primary MBHT 701 in this flow. 
From Cycle #48 onward, instruction fetching once again hits the 
steady-state rate of two branch groups per cycle. Starting from Cycle #51 
onward, the processor execution also hits the steady-state rate of two 
branch groups per cycle. This concludes the example. 
While the invention has been particularly shown and described with 
reference to preferred embodiments thereof, it will be understood by those 
skilled in the art that various changes in form and details may be made 
therein without departing from the spirit and scope of the invention. 
3 APPENDIX A 
Clock Superscalar Processor 203 Primary MBHT 701 Secondary MBHT 711 
In- Pending Pending struction Guess Q. Update Queue 
Guess Q Update Queue Fetch ENDOP Outputs 704 706 COM- Outputs 714 716 A 
ddress Cache Processor Triples PPFAR PBG1 PBG2 En- De- En- De- E 
SPFAR SBG1 SBG2 En- De- En- De- Cycle Stage Access Decode Execute 
Triple1 Triple2 702 721 722 queue queue queue queue 718 712 723 724 
queue queue queue queue 
0 A -- -- -- -- -- A -- -- -- -- -- -- -- -- -- -- -- -- -- 1 -- A 
-- -- -- -- -- miss miss -- -- -- -- -- -- -- -- -- -- -- -- 2 -- -- A 
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 3 B -- -- A -- -- 
B -- -- -- -- -- -- -- -- -- -- -- -- -- -- 4 -- B -- -- -- -- -- miss 
miss -- -- -- -- -- -- -- -- -- -- -- -- 5 -- -- B -- -- -- -- -- -- -- 
-- -- -- -- -- -- -- -- -- -- -- 6 C -- -- B -- -- C -- -- -- -- -- -- 
-- -- -- -- -- -- -- -- 7 -- C -- -- ABC -- -- miss miss -- -- ABC -- 
-- -- Update-ABC -- -- (ABC) (ABC) 8 -- -- C -- -- -- -- Update-ABC -- 
-- -- ABC -- -- -- -- -- -- -- -- 9 D -- -- C -- -- D -- -- -- -- -- -- 
-- -- -- -- -- -- -- -- 10 -- D -- -- BCD -- -- miss miss -- -- BCD -- 
-- -- Update-BCD -- -- (BCD) (BCD) 11 -- -- D -- -- -- -- Update-BCD -- 
-- -- BCD -- -- -- -- -- -- -- -- 12 E -- -- D -- -- E -- -- -- -- -- 
-- -- -- -- -- -- -- -- -- 13 -- E -- -- CDE -- -- miss miss -- -- CDE 
-- -- -- Update-CDE -- -- (CDE) (CDE) 14 -- -- E -- -- -- -- Update-CDE 
-- -- -- CDE -- -- -- -- -- -- -- -- 15 A -- -- E -- -- A -- -- -- -- 
-- -- -- -- -- -- -- -- -- -- 16 B,C A -- -- DEA -- C B C ABC -- DEA -- 
-- B Update-DEA -- -- (DEA) (DEA) 17 D,E B,C A -- -- -- E D E CDE -- -- 
DEA C=C D C D BCD -- -- -- 18 A D,E B,C A -- -- (A) miss miss -- -- -- 
-- E=E -- E A DEA -- -- -- 19 -- A D,E B,C EAB -- A Update-DEA -- -- EAB D 
EA -- -- Update-EAB -- -- (EAB) (EAB) 20 B,C -- A D,E ABC BCD C B C ABC A 
BC -- -- -- B -- -- -- BCD -- -- 21 D,E B,C -- A CDE DEA E D E CDE CDE 
-- -- C=C D C D BCD DEA -- -- 22 A D,E B,C -- EAB -- (A) miss miss -- -- 
(EAB) -- E=E -- E A DEA -- EAB -- 23 -- A D,E B,C -- -- A Update-EAB -- 
-- -- EAB -- -- -- -- -- -- -- -- 24 B,C -- A D,E ABC BCD C B C ABC ABC 
-- -- -- B -- -- -- BCD -- -- 25 D,E B,C -- A CDE DEA E D E CDE CDE -- 
-- C=C D C D BCD DEA -- -- 26 A,B D,E B,C -- EAB -- B A B EAB -- (EAB) 
-- E=E A E A DEA -- (EAB) -- 27 C,D A,B D,E B,C -- -- D C D BCD -- -- -- 
B=B C B C ABC -- -- -- 28 E,A C,D A,B D,E ABC BCD A E A DEA ABC -- -- 
D=D E D E CDE BCD -- -- 29 B,C E,A C,D A,B CDE DEA C B C ABC CDE -- -- 
A=A B A B EAB DEA -- -- 30 D,E B,C E,A C,D EAB ABC E D E CDE EAB -- -- 
C=C D C D BCD ABC -- -- 31 A,B D,E B,C E,A BCD CDE B A B EAB BCD -- -- 
E=E A E A DEA CDE -- -- 32 C,D A,B D,E B,C DEA EAB D C D BCD DEA -- -- 
B=B C B C ABC EAB -- -- 33 E,A C,D A,B D,E ABC BCD A E A DEA ABC -- -- 
D=D E D E CDE BCD -- -- 34 B,C E,A C,D A,B CDE DEA C B C ABC CDE -- -- 
A=A B A B EAB DEA -- -- 35 X clear clear clear EAB ABX X (D) (E) clear 
clear (EAB) -- -- -- (C) (D) clear clear ABX -- 36 -- X -- -- -- -- -- 
miss miss -- -- -- -- -- -- Update-EAB -- -- -- EAB 37 -- -- X -- -- -- 
-- -- -- -- -- -- -- -- -- Update-ABX -- -- -- ABX 38 Y -- -- X -- -- Y 
-- -- -- -- -- -- -- -- -- -- -- -- -- -- 39 -- Y -- -- BXY -- -- miss 
miss -- -- BXY -- -- -- Update-BXY -- -- (BXY) (BXY) 40 -- -- Y -- -- -- 
-- Update-BXY -- -- -- BXY -- -- -- -- -- -- -- -- 41 A -- -- Y -- -- A 
-- -- -- -- -- -- -- -- -- -- -- -- -- -- 42 B,C A -- -- XYA -- C B C 
ABC -- XYA -- -- B -- -- -- -- -- -- 43 X,Y B,(C) A -- -- -- Y (D) (E) 
CDE -- -- -- X.noteq.C -- X Y BXY -- XYA -- 44 -- X,Y B A -- -- -- miss 
miss -- -- -- -- -- -- Update-XYA -- -- -- XYA 45 -- -- X,Y B YAB -- -- 
Update-XYA -- -- YAB XYA -- -- Update-YAB -- -- (YAB) (YAB) 46 A -- -- 
X,Y ABX -- A Update-YAB clear clear ABX YAB -- -- Update-ABX -- -- (ABX) 
(ABX) 47 B,C A -- -- BXY XYA C B C ABC -- BXY -- -- B Update-XYA -- -- 
(XYA) (XYA) 48 X,Y B,(C) A -- -- -- Y (D) (E) -- -- -- -- X.noteq.C -- X Y 
BXY -- -- -- 49 A,B X,Y B A -- -- B A B UAB -- -- -- -- A -- -- -- -- 
-- -- 50 X,Y A,B X,Y B YAB -- Y X Y BXY YAB -- -- B=B X B X ABX -- YAB 
-- 51 A,B X,Y A,B X,Y ABX -- Y A B YAB -- (ABX) -- Y=Y A Y A XYA ABX -- 
-- 52 X,Y A,B X,Y A,B BXY XYA B A B YAB BXY -- -- B=B A B X ABX XYA -- 
-- 53 A,B X,Y A,B X,Y YAB ABX Y X Y BXY YAB -- -- B=B X B X ABX ABX -- 
-- 54 X,Y A,B X,Y A,B BXY XYA B A B YAB YAB -- -- Y=Y A Y A XYA XYA -- 
-- 55 A,B X,Y A,B X,Y YAB ABX Y X Y BXY BXY -- -- B= B X B X ABX ABX -- 
--