Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
2000-09-11
2002-11-05
Coggins, Wynn W. (Department: 3625)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S216000, C712S217000, C712S218000, C712S219000, C712S237000, C712S239000, C712S240000
Reexamination Certificate
active
06477640
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to data processing systems, and more particularly to, predicting multiple branch instructions deep into an instruction flow and performing out of order branch resolution on the multiple branch predictions.
BACKGROUND OF THE INVENTION
In the integrated circuit (IC) industry, branch instruction prediction is being used to improve the performance of central processing units (CPU). In a software program, branch instructions are used to selectively send instruction execution flow in one of two different directions based upon some criterion (e.g., if A>B then goto here else goto there, if X=Y then goto here else goto there, if V bit set then goto here else goto there, etc.). If a processor is forced to wait until the path of the branch is clearly determined before fetching instructions for execution from memory, a “gap” in instruction execution flow is experienced within the CPU. It has been found that it is more beneficial to “predict” or “guess” which path the branch will eventually traverse and execute instructions down this speculative path before resolution of the exact branch path is determined. If the CPU correctly predicts the branch path more often than not, performance improvements can usually be achieved by removing the execution “gaps” from the CPU's instruction flow (i.e., the CPU is not sitting idle as long).
However, branch instruction prediction is becoming even more complex in modem microprocessors. It is now desired that a processor predict multiple branches deep in the flow of instruction execution and compound speculation on top of speculation. There are significant performance advantages for CPUs that can predict accurately through multiple branch instructions whereby computer instructions that are multiple branch instructions deep are being speculatively executed. However, when predicting through multiple branch instructions, a significant amount of hardware overhead is usually needed in prior art designs. In many cases, the algorithms that control these larger resources inefficiently schedule or assign the resources whereby otherwise available resources are not available for efficient use. In addition, this additional hardware may not be easily scalable to more complex architectures in order to further improve performance in subsequent generations of the microprocessor's family line. Furthermore, this multiple-branch prediction capability in the architecture may result in difficulty in recovering from a mispredicted branch whereby performance may be adversely impacted if mispredictions occur too frequently.
Therefore, a need exists in the industry for a branch prediction architecture which allows for one or more of branch prediction that progresses multiple branch instructions deep, correction of branch mispredictions in a more efficient manner, reduced hardware overhead associated with the branch architecture, ease of extendibility to more complicated computer architectures to deeper branch prediction, improved allocation of resources, and improved performance.
REFERENCES:
patent: 4200927 (1980-04-01), Hughes et al.
patent: 4775927 (1988-10-01), Hester et al.
patent: 5353421 (1994-10-01), Emma et al.
patent: 5394529 (1995-02-01), Brown et al.
patent: 5454117 (1995-09-01), Puziol et al.
patent: 5560032 (1996-09-01), Nguyen et al.
patent: 5860017 (1999-01-01), Sharangpani et al.
patent: 5903918 (1999-05-01), Bauman et al.
patent: 6029240 (2000-02-01), Blaner et al.
patent: 518420 (1992-12-01), None
patent: WO9712317 (1997-04-01), None
Gwennap, Linley; “Hal reveals multichip SPARC processor;” Microprocessor Report, v9, n3, p1(7), Mar. 6, 1995.*
Wilson, Ron; “CPU Designers look beyond superscalar;” Electronic Engineering Times, n917, p14(2); Sep. 2, 1996.*
Feibus, Mike; “The P6 Lite will take a big fat bite of chip-set, board markets;” PC Week, v13, n11, pA16(1); Mar. 18, 1996.
Burgess Bradley G.
Denman Marvin A.
Holloway David C.
Rupley, II Jeffrey Pidge
Coggins Wynn W.
Motorola Inc.
Thompson, Jr. Forest
LandOfFree
Apparatus and method for predicting multiple branches and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for predicting multiple branches and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for predicting multiple branches and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2989204