US5752014A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Automatic selection of branch prediction methodology for subsequent branch instruction based on outcome of previous branch prediction
Assignee: International Business Machines Corp
•
Filing: 1996-04-29
•
Granted: 1998-05-12
•
Expires: 2016-04-29
Abstract
Abstract A processor and method for speculatively executing branch instructions utilizing a selected branch prediction methodology are disclosed. The processor has one or more execution units for executing instructions, including a branch processing unit for executing branch instructions. The branch processing unit includes selection logic for selecting one of a plurality of branch prediction methodologies and a branch prediction unit for predicting the resolution of a conditional branch instruction utilizing the selected branch prediction methodology. The branch processing unit further includes execution facilities for speculatively executing the conditional branch instruction based upon the prediction. Based upon the outcome of the prediction, the selection logic selects a branch prediction methodology for predicting a subsequent conditional branch instruction so that branch prediction accuracy is enhanced. In one embodiment, the multiple branch prediction methodologies include static and dynamic branch prediction.
Inventors
- 👤 Soummya Mallick
- 👤 Albert John Loper
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 14:28
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3836; G06F9/3842; G06F9/3846; G06F9/3848
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
109 words
A processor, comprising: one or more execution units for executing instructions, said one or more execution units including a branch processing unit for executing branch instructions, said branch processing unit including: selection logic for selecting one of a plurality of branch prediction methodologies; a branch prediction unit for predicting a resolution of a conditional branch instruction utilizing said selected branch prediction methodology; and means for speculatively executing said branch instruction according to said prediction; wherein said selection logic automatically selects a branch prediction methodology from said plurality of branch prediction methodologies for predicting a resolution of a subsequent conditional branch instruction in response to an outcome of said prediction.
Claim 2
Dependent Claim
109 words
A processor, comprising: one or more execution units for executing instructions, said one or more execution units including a branch processing unit for executing branch instructions, said branch processing unit including: selection logic for selecting one of a plurality of branch prediction methodologies; a branch prediction unit for predicting a resolution of a conditional branch instruction utilizing said selected branch prediction methodology; and means for speculatively executing said branch instruction according to said prediction; wherein said selection logic automatically selects a branch prediction methodology from said plurality of branch prediction methodologies for predicting a resolution of a subsequent conditional branch instruction in response to an outcome of said prediction.
Claim 3
Dependent Claim
16 words
The processor of claim 1, wherein said plurality of branch prediction methodologies includes dynamic branch prediction.
Claim 4
Dependent Claim
39 words
The processor of claim 2, and further comprising: a branch history table, wherein said branch history table stores an indication whether said conditional branch instruction should be predicted as taken or not taken if dynamic branch prediction is utilized.
Claim 5
Dependent Claim
16 words
The processor of claim 3, wherein said plurality of branch prediction methodologies includes static branch prediction.
Claim 6
Dependent Claim
60 words
The processor of claim 4, said selection logic comprising: means, responsive to a first selected number of incorrect predictions of conditional branch instructions utilizing dynamic branch prediction, for selecting static branch prediction; and means, responsive to a resolution of a second selected number of statically predicted conditional branch instructions as all taken or not taken, for selecting dynamic branch prediction.
Claim 7
Dependent Claim
42 words
The processor of claim 1, wherein said processor has an associated memory for storing instructions, said processor further comprising a fetcher, wherein said fetcher fetches from memory one or more instructions for execution within a speculative execution path indicated by said prediction.
Claim 8
Dependent Claim
31 words
The processor of claim 6, said processor further comprising: means for cancelling said instructions within said speculative execution path in response to a resolution of said conditional branch instruction as mispredicted.
Claim 9
Dependent Claim
153 words
A data processing system, comprising: a bus; a a memory coupled to said bus, wherein said memory stores instructions to be executed; a fetcher for fetching instructions from said memory, said fetcher being coupled to said memory via said bus; one or more execution units for executing fetched instructions, said one or more execution units including a branch processing unit for executing branch instructions, said branch processing unit including: selection logic for selecting one of a plurality of branch prediction methodologies; a branch prediction unit for predicting a resolution of a conditional branch instruction utilizing said selected branch prediction methodology; and means for speculatively executing said branch instruction according to said prediction; wherein based upon an outcome of said prediction, said selection logic automatically selects a branch prediction methodology from said plurality of branch prediction methodolgies for predicting a resolution of a subsequent conditional branch instruction, such that branch prediction accuracy is enhanced.
Claim 10
Dependent Claim
153 words
A data processing system, comprising: a bus; a a memory coupled to said bus, wherein said memory stores instructions to be executed; a fetcher for fetching instructions from said memory, said fetcher being coupled to said memory via said bus; one or more execution units for executing fetched instructions, said one or more execution units including a branch processing unit for executing branch instructions, said branch processing unit including: selection logic for selecting one of a plurality of branch prediction methodologies; a branch prediction unit for predicting a resolution of a conditional branch instruction utilizing said selected branch prediction methodology; and means for speculatively executing said branch instruction according to said prediction; wherein based upon an outcome of said prediction, said selection logic automatically selects a branch prediction methodology from said plurality of branch prediction methodolgies for predicting a resolution of a subsequent conditional branch instruction, such that branch prediction accuracy is enhanced.
Claim 11
Dependent Claim
18 words
The data processing system of claim 8, wherein said plurality of branch prediction methodologies includes dynamic branch prediction.
Claim 12
Dependent Claim
43 words
The data processing system of claim 9, and further comprising: a branch history table, wherein said branch history table stores an indication whether or not said conditional branch instruction should be predicted as taken or not taken if dynamic branch prediction is utilized.
Claim 13
Dependent Claim
18 words
The data processing system of claim 10, wherein said plurality of branch prediction methodologies includes static branch prediction.
Claim 14
Dependent Claim
62 words
The data processing system of claim 11, said selection logic comprising: means, responsive to a first selected number of incorrect predictions of conditional branch instructions utilizing dynamic branch prediction, for selecting static branch prediction; and means, responsive to a resolution of a second selected number of statically predicted conditional branch instructions as all taken or not taken, for selecting dynamic branch prediction.
Claim 15
Dependent Claim
29 words
The data processing system of claim 8, wherein said fetcher fetches from said memory one or more instructions for execution within a speculative execution path indicated by said prediction.
Claim 16
Dependent Claim
32 words
The data processing system of claim 13, and further comprising: means for cancelling said instructions within said speculative execution path in response to a resolution of said conditional branch instruction as mispredicted.
Claim 17
Independent Claim
119 words
A method within a processor for speculatively executing a conditional branch instruction, said method comprising: selecting one of a plurality of branch prediction methodologies to predict a resolution of a conditional branch instruction; predicting a resolution of said conditional branch instruction as taken or not taken utilizing said selected branch prediction methodology; speculatively executing said conditional branch instruction according to said prediction; thereafter, resolving said conditional branch instruction as taken or not taken; and in response to said resolution of said branch instruction, utilizing an outcome of said prediction to automatically select a branch prediction methodology from said plurality of branch prediction methodologies for predicting a resolution of a subsequent conditional branch instruction, wherein branch prediction accuracy is enhanced.
Claim 18
Independent Claim
119 words
A method within a processor for speculatively executing a conditional branch instruction, said method comprising: selecting one of a plurality of branch prediction methodologies to predict a resolution of a conditional branch instruction; predicting a resolution of said conditional branch instruction as taken or not taken utilizing said selected branch prediction methodology; speculatively executing said conditional branch instruction according to said prediction; thereafter, resolving said conditional branch instruction as taken or not taken; and in response to said resolution of said branch instruction, utilizing an outcome of said prediction to automatically select a branch prediction methodology from said plurality of branch prediction methodologies for predicting a resolution of a subsequent conditional branch instruction, wherein branch prediction accuracy is enhanced.
Claim 19
Dependent Claim
23 words
The method for speculatively executing a conditional branch instruction of claim 15, wherein said plurality of branch prediction methodologies includes dynamic branch prediction.
Claim 20
Dependent Claim
40 words
The method for speculatively executing a conditional branch instruction of claim 16, said method further comprising: storing an indication of whether or not said subsequent conditional branch instruction should be predicted as taken or not taken utilizing dynamic branch prediction.
Claim 21
Dependent Claim
23 words
The method for speculatively executing a conditional branch instruction of claim 17, wherein said plurality of branch prediction methodologies includes static branch prediction.
Claim 22
Dependent Claim
73 words
The method for speculatively executing a conditional branch instruction of claim 18, wherein said step of selecting one of a plurality of branch prediction methodologies comprises: in response to a first selected number of incorrect predictions of branch instructions utilizing dynamic branch prediction, selecting static branch prediction; and in response to a resolution of a second selected number of statically predicted branch instructions as all taken or not taken, selecting dynamic branch prediction.
Claim 23
Dependent Claim
32 words
The method for speculatively executing a conditional branch instruction of claim 15 said method further comprising fetching one or more instructions for execution within a speculative execution path indicated by said prediction.
Claim 24
Dependent Claim
36 words
The method for speculatively executing a conditional branch instruction of claim 20, said method further comprising cancelling said instructions within said speculative execution path in response to a resolution of said conditional branch instruction as mispredicted.
References Cited (Backward Citations)
US5507028A
Cited
US5584001A
Cited
US5454117A
Cited
GB2283595A
Cited
US5553255A
Cited
JPH08241198A
Cited
US5634103A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-05-11 | 2001-11-10 | 2002-05-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-05-11 | 2005-11-10 | 2006-05-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-05-11 | 2009-11-10 | 2010-05-12 | $7700.00 | Window Closed / Lapsed |