Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1999-01-25
2001-08-07
Kim, Kenneth S. (Department: 2783)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S240000
Reexamination Certificate
active
06272623
ABSTRACT:
BACKGROUND OF THE INVENTION
A. Field of the Invention
The invention generally relates to computer architecture, and, more particularly, to branch prediction.
B. Description of the Related Art
Modern high performance computer processors typically employ pipelining to increase performance. “Pipelining” refers to a processing technique in which multiple sequential instructions are executed in an overlapping manner. A general description of pipelining can be found in “Computer Organization & Design” by David A. Patterson and John L. Hennessy (2d ed. 1988, pp. 436-516).
FIG. 1
shows the timing of instruction processing in a conventional five-stage pipeline processor architecture. With such an architecture, the processor can simultaneously process different stages of up to five successive instructions. The five stages shown in
FIG. 1
are: IF (instruction fetch), ID (instruction decode), EX (execute instruction), MEM (memory access), and WB (write back to register).
For example, at clock cycle
1
, the processor fetches instruction I
1
. At clock cycle
2
, the processor decodes instruction I
1
and fetches instruction I
2
. In the same manner, the processor continues to process instructions as they are received; by clock cycle
5
, the processor writes back the result of instruction I
1
, accesses memory for instruction I
2
, executes instruction I
3
, decodes instruction I
4
, and fetches instruction I
5
. In contrast, a non-pipelined architecture would complete processing of an entire instruction (e.g. instruction I
1
) before beginning to process the next instruction (e.g., instruction I
2
).
When program flow is perfectly sequential, a pipelined architecture can achieve significant performance advantages over non-pipelined architecture. In actual programs, however, approximately twenty percent of program instructions are branches. Branch instructions cause a program to deviate from a sequential flow. Consequently, the instruction to be executed (the target of the branch) may not be the next instruction in the fetch sequence.
A processor may recognize that an instruction is a branch instruction in the IF stage (the first stage of the five-stage pipeline). For conditional branch instructions, however, the processor typically cannot determine whether the branch should be taken until it reaches the EX stage (the third stage of the five-stage pipeline). By this time, the processor has already fetched and begun processing the next two instructions. The processing of those two instructions is wasted and inefficient if the branch instruction redirects program flow to another location.
Referring to
FIG. 1
, if instruction I
1
is a conditional branch instruction that redirects flow to instruction I
6
, the processor does not recognize this until clock cycle
3
(EX), when the processor is executing instruction I
1
. By this time, the processor has already fetched instruction I
2
during clock cycle
2
, and decoded instruction I
2
and fetched instruction I
3
during clock cycle
3
. This processing of instructions I
2
and I
3
is wasted, however, because branch instruction I
1
causes flow to skip to instruction I
6
, with no further processing of instructions I
2
or I
3
. Moreover, the branching causes a stall in the pipeline while the correct instruction (I
6
) is fetched. These inefficiencies caused by branches become exacerbated when deeper pipelines or superscalar processors are used because it takes longer to resolve a branch.
One approach to solving this problem, called branch prediction, involves making accurate, educated determinations about whether an instruction will result in a branch to another location. Branch prediction is premised on the assumption that, under similar circumstances, the outcome of a conditional branch will likely be the same as prior outcomes. Because branch prediction can be implemented in the IF stage of processing, there is no wasted instruction processing if the result of the conditional branch is always predicted correctly.
Conventional branch prediction techniques include correlation-based schemes and global branch history with index sharing (“gshare”). Although these techniques are somewhat effective, the frequency of erroneous prediction using these techniques may be unacceptable. There remains, therefore, a need for a branch prediction scheme that reduces the frequency of erroneous prediction.
SUMMARY OF THE INVENTION
In accordance with the invention, as embodied and broadly described herein, a method of predicting whether a branch will be taken involves reading bits from a local history table and concatenating them with bits from a global history register. The result of the concatenation is combined with bits from the instruction address by performing an exclusive or operation. The result of the exclusive or operation is used to read a branch prediction table.
In accordance with the invention, an apparatus for predicting whether a branch will be taken comprises a local history table and a global history register. The local history table and the global history table are connected to inputs of a concatenating circuit. The output of the concatenating circuit is connected to one input of an exclusive or circuit, with an instruction address source being connected to another input. The output of the exclusive or circuit is connected to an input of a branch prediction table.
It is to be understood that both the foregoing general description and following detailed description are intended only to exemplify and explain the invention as claimed.
REFERENCES:
patent: 5553253 (1996-09-01), Pan et al.
patent: 5687360 (1997-11-01), Chang
patent: 5758142 (1998-05-01), McFarling et al.
patent: 5901307 (1999-05-01), Potter et al.
patent: 5935241 (1999-08-01), Shiell et al.
David A. Patterson and John L. Hennessy, Computer Organization & Design 436-516 (Morgan Kaufmann Publishers, Inc., 1988).
Finnegan Henderson Farabow Garrett & Dunner L.L.P.
Kim Kenneth S.
Sun Microsystems Inc.
LandOfFree
Methods and apparatus for branch prediction using hybrid... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for branch prediction using hybrid..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for branch prediction using hybrid... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2513308