Branch misprediction recovery using a side memory

Details Branch misprediction recovery using a side memory Branch misprediction recovery using a side memory

1999-09-16

2003-11-04

Dam, Tuan Q. (Department: 2124)

Electrical computers and digital processing systems: processing

Processing control

Branching

C712S232000, C712S239000

Reexamination Certificate

active

06643770

ABSTRACT:

FIELD
The present invention relates to an instruction pipeline in a processor. More particularly, the present invention relates to a mispredicted path side memory for an instruction pipeline.
BACKGROUND
The rate at which a computer or other processing system can process information is often dependent on the speed at which the system processor(s) execute instructions. Therefore, a increased processing may advantageously be obtained by improving the speed at which processor process instructions. Many processors, such as a microprocessor found in a computer, use an instruction pipeline to speed the processing of instructions.
FIG. 1
illustrates a known architecture for such an instruction pipeline. The first stage of the pipeline includes a branch prediction unit
100
and a next Instruction Pointer (IP) logic unit
110
that select an instruction to be executed. An instruction cache
120
is accessed in the second stage of the pipeline, and the instruction moves into the third stage. The instruction moves from a third stage unit
130
to a fourth stage unit
140
, and so on, before reaching a branch execution unit
150
in the execution stage. The “intermediate stages” shown in
FIG. 1
imply that any number of stages can exist in a pipeline. The stages may, for example, generate instructions for an instruction decoder.
Consider, for example, the following sequence of instructions:
address X1:
XXX1
JCC-Y1
XXX2
XXX3
XXX4
XXX5
address Y1:
YYY1
YYY2
YYY3
In this case, address X
1
stores a first instruction (“XXX
1
”) followed by a “conditional” jump or branch instruction (“JCC-Y
1
”). The branch is conditional in that the next instruction to be performed may be either the next sequential instruction (“XXX
2
”) or an instruction at a new address (“Y
1
”). The processor does not know which branch, or “path,” will be taken until JCC-Y
1
is executed, i.e., reaches the branch execution unit
150
.
Assume now that the branch prediction unit
100
and the next IP logic unit
110
have selected instruction XXX
1
to be executed. The processor could wait for XXX
1
to move through each stage in the pipeline before processing the next instruction, or JCC-Y
1
. In this case, the branch execution unit
150
would remain idle while JCC-Y
1
moves through the pipeline. To improve the processor's performance, JCC-Y
1
is placed into the first stage as soon XXX
1
moves into the second stage. As a result, JCC-Y
1
will be ready for execution as soon as the branch execution unit
150
is finished with XXX
1
.
When JCC-Y
1
moves into the second stage, however, the processor will not know if XXX
2
or YYY
1
should be placed into the first stage, because this information is only available after JCC-Y
1
has been executed by the branch execution unit
150
. Therefore, the branch prediction unit
100
“predicts” which branch of the program will be needed. By way of example, Table I shows the movement of the above instruction sequence through the pipeline shown in FIG.
1
. As can be seen at time
6
, the branch prediction unit
100
has predicted that instruction YYY
1
will follow JCC-Y
1
. Note that several instruction “clock” cycles may or may not pass the time JCC-Y
1
moves into the second stage and the time YYY
1
is placed into the first stage.
TABLE I
Program Flow
First
Second
Third
Fourth
Int.
Execution
Time
Stage
Stage
Stage
Stage
Stages
Stage
1
XXX1
...
2
JCC-Y1
XXX1
...
3
JCC-Y1
XXX1
...
4
JCC-Y1
XXX1
...
5
JCC-Y1
...
6
YYY1
...
7
YYY2
YYY1
...
...
...
...
...
...
...
...
10
YYY5
YYY4
YYY3
YYY2
...
XXX1
11
YYY6
YYY5
YYY4
YYY3
...
JCC-Y1
12
XXX2
...
13
XXX3
XXX2
...
14
XXX4
XXX3
XXX2
...
15
XXX5
XXX4
XXX3
XXX2
...
When JCC-Y
1
is actually executed at time
11
, the branch prediction unit
100
has “mispredicted” and, in fact, XXX
2
must be processed next. In this case, instructions YYY
1
through YYY
6
, currently in the pipeline, are discarded and the branch execution unit
150
waits for XXX
2
to travel through each pipeline stage before it can be executed. This delay, or mispredicted branch “recovery” time, slows the operation of the processor. Moreover, as the number of stages in a pipeline increases, the delay caused by each mispredicted path may also increase.


REFERENCES:
patent: 5040107 (1991-08-01), Duxbury et al.
patent: 5117490 (1992-05-01), Duxbury et al.
patent: 5119483 (1992-06-01), Madden et al.
patent: 5634103 (1997-05-01), Dietz et al.
patent: 5659722 (1997-08-01), Blaner et al.
patent: 5666507 (1997-09-01), Flora
patent: 5696958 (1997-12-01), Mowry et al.
patent: 5860017 (1999-01-01), Sharangpani et al.
patent: 6049860 (2000-04-01), Krygowski et al.
patent: 6208361 (2001-03-01), Gossett
patent: 6260138 (2001-07-01), Harris
“Integrating a Mispredicted Recovery Cache (MRC) into a Superscalar Pipeline” Bondi, J.O.; Nanda, A.K.; Dutta, S.; Microarchitecture, 1996. MICRO-29.Proceedings of the 29thAnnual IEEE/ACM International Symposium on , 1996 pp. 14-23.

Affiliated with

Also associated with

Rating

Branch misprediction recovery using a side memory does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Branch misprediction recovery using a side memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Branch misprediction recovery using a side memory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3152288