US5367703A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for enhanced branch history prediction accuracy in a superscalar processor system
Assignee: International Business Machines Corp
•
Filing: 1993-01-08
•
Granted: 1994-11-22
•
Expires: 2013-01-08
Abstract
Abstract A method and system for enhanced branch history prediction accuracy in a superscalar processor system by maintaining branch history tables which include a separate branch history for each instruction fetch position within a multi-instruction access. In a superscalar processor system which is capable of accessing multiple instructions simultaneously, a branch history table is established which includes a predictive field for each possible instruction fetch position within a multi-instruction access. Each group of predictive fields is accessed within the branch history table utilizing a portion of the instruction fetch address, such as the low order address bits. A particular predictive field within the group is then selected which corresponds to the position of the branch instruction within the instruction fetch. The content of the selected predictive field is then utilized to predict whether or not a branch is taken for the corresponding branch instruction. Each predictive field preferably comprises a two bit binary counter which is incremented or decremented in response to a branch being "taken" or "not taken" and then stored again within the branch history table.
Inventors
- 👤 David S. Levitan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 03:31
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3836; G06F9/3842; G06F9/3844
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
215 words
A method for enhanced branch history prediction accuracy in a superscalar processor system which is capable of fetching and dispatching up to N instructions simultaneously, said method comprising the steps of: establishing a branch history table containing multiple predictive fields, each of said multiple predictive fields containing data indicative of a likelihood that execution of a particular associated instruction will result in a branch within an executing set of instructions; accessing a selected point within said branch history table utilizing at least a portion of a fetch address which is utilized to access an ordered sequence of M instructions within said superscalar processor system; reading out an ordered sequence of M predictive fields from said selected point within said branch history table, each one of said ordered sequence of M predictive fields being associated with a particular instruction at a corresponding position within said ordered sequence of M instructions; and utilizing an associated one of said M predictive fields to determine a likelihood that execution of a corresponding instruction within said ordered sequence of M instructions will result in a branch within said executing set of instructions, wherein variations in relative position of an instruction within said ordered sequence of M instructions will result in utilization of an alternate predictive field, thereby enhancing predicative accuracy.
Claim 2
Independent Claim
215 words
A method for enhanced branch history prediction accuracy in a superscalar processor system which is capable of fetching and dispatching up to N instructions simultaneously, said method comprising the steps of: establishing a branch history table containing multiple predictive fields, each of said multiple predictive fields containing data indicative of a likelihood that execution of a particular associated instruction will result in a branch within an executing set of instructions; accessing a selected point within said branch history table utilizing at least a portion of a fetch address which is utilized to access an ordered sequence of M instructions within said superscalar processor system; reading out an ordered sequence of M predictive fields from said selected point within said branch history table, each one of said ordered sequence of M predictive fields being associated with a particular instruction at a corresponding position within said ordered sequence of M instructions; and utilizing an associated one of said M predictive fields to determine a likelihood that execution of a corresponding instruction within said ordered sequence of M instructions will result in a branch within said executing set of instructions, wherein variations in relative position of an instruction within said ordered sequence of M instructions will result in utilization of an alternate predictive field, thereby enhancing predicative accuracy.
Claim 3
Dependent Claim
52 words
The method for enhanced branch history predicative accuracy in a superscalar processor according to claim 1, wherein said step of establishing a branch history table containing multiple predictive fields comprises the step of establishing a branch history table containing multiple predictive fields wherein each predictive field comprises a two bit binary counter.
Claim 4
Dependent Claim
89 words
The method for enhanced branch history predicative accuracy in a superscalar processor according to claim 1, wherein said step of accessing a selected point within said branch history table utilizing at least a portion of a fetch address which is utilized to access an ordered sequence of M instructions within said superscalar processor system comprises accessing a selected point within said branch history table utilizing low order address bits of a fetch address which is utilized to access an ordered sequence of M instructions within said superscalar processor system.
Claim 5
Dependent Claim
45 words
The method for enhanced branch history predicative accuracy in a superscalar processor according to claim 2, further including the step of incrementing said two bit binary counter each time execution of said particular associated instruction results in a branch within said executing set of instructions.
Claim 6
Dependent Claim
47 words
The method for enhanced branch history predicative accuracy in a superscalar processor according to claim 4, further including the step of decrementing said two bit binary counter each time execution of said particular associated instruction does not result in a branch within said executing set of instructions.
Claim 7
Independent Claim
219 words
A system for enhanced branch history prediction accuracy in a superscalar processor system which is capable of fetching and dispatching up to N instructions simultaneously, said system comprising: means for establishing a branch history table containing multiple predictive fields, each of said multiple predictive fields containing data indicative of a likelihood that execution of a particular associated instruction will result in a branch within an executing set of instructions; means accessing a selected point within said branch history, table utilizing at least a portion of a fetch address which is utilized to access an ordered sequence of M instructions within said superscalar processor system; means for reading out an ordered sequence of M predictive fields from said selected point within said branch history table, each one of said ordered sequence of M predictive fields being associated with a particular instruction at a corresponding position within said ordered sequence of M instructions; and means for utilizing an associated one of said M predictive fields to determine a likelihood that execution of a corresponding instruction within said ordered sequence of M instructions will result in a branch within said executing set of instructions, wherein variations in relative position of an instruction within said ordered sequence of M instructions will result in utilization of an alternate predictive field, thereby enhancing predicative accuracy.
Claim 8
Independent Claim
219 words
A system for enhanced branch history prediction accuracy in a superscalar processor system which is capable of fetching and dispatching up to N instructions simultaneously, said system comprising: means for establishing a branch history table containing multiple predictive fields, each of said multiple predictive fields containing data indicative of a likelihood that execution of a particular associated instruction will result in a branch within an executing set of instructions; means accessing a selected point within said branch history, table utilizing at least a portion of a fetch address which is utilized to access an ordered sequence of M instructions within said superscalar processor system; means for reading out an ordered sequence of M predictive fields from said selected point within said branch history table, each one of said ordered sequence of M predictive fields being associated with a particular instruction at a corresponding position within said ordered sequence of M instructions; and means for utilizing an associated one of said M predictive fields to determine a likelihood that execution of a corresponding instruction within said ordered sequence of M instructions will result in a branch within said executing set of instructions, wherein variations in relative position of an instruction within said ordered sequence of M instructions will result in utilization of an alternate predictive field, thereby enhancing predicative accuracy.
Claim 9
Dependent Claim
51 words
The system for enhanced branch history predicative accuracy in a superscalar processor according to claim 6, wherein said means for establishing a branch history table containing multiple predictive fields comprises means for establishing a branch history table containing multiple predictive fields wherein each predictive field comprises a two bit binary counter.
Claim 10
Dependent Claim
91 words
The system for enhanced branch history predicative accuracy in a superscalar processor according to claim 6, wherein said means for accessing a selected point within said branch history table utilizing at least a portion of a fetch address which is utilized to access an ordered sequence of M instructions within said superscalar processor system comprises means for accessing a selected point within said branch history table utilizing low order address bits of a fetch address which is utilized to access an ordered sequence of M instructions within said superscalar processor system.
Claim 11
Dependent Claim
44 words
The system for enhanced branch history predicative accuracy in a superscalar processor according to claim 7, further including means for incrementing said two bit binary counter each time execution of said particular associated instruction results in a branch within said executing set of instructions.
Claim 12
Dependent Claim
46 words
The method for enhanced branch history predicative accuracy in a superscalar processor according to claim 9, further including means for decrementing said two bit binary counter each time execution of said particular associated instruction does not result in a branch within said executing set of instructions.
References Cited (Backward Citations)
US4477872A
Cited
US4679141A
Cited
US4943908A
Cited
US5297281A
Cited
US5136697A
Cited
US5303356A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-11-21 | 1998-05-23 | 1998-11-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-11-21 | 2002-05-23 | 2002-11-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-11-21 | 2006-05-23 | 2006-11-22 | $7700.00 | Window Closed / Lapsed |