Patent US6350732B1 successfully refreshed from Google Patents.
US4763245A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Branch prediction mechanism in which a branch history table is updated using an operand sensitive branch table
Assignee: International Business Machines Corp
•
Filing: 1985-10-30
•
Granted: 1988-08-09
•
Expires: 2005-10-30
Abstract
Abstract A data-dependent branch table is a mechanism that is sensitive to operands that will be tested in order to determine branch action outcomes. The data dependent branch table operates in conjunction with a branch history table to anticipate those instances where the branch history table will make an erroneous prediction, and corrects the branch history table prior to the time that the actual prediction is made.
Inventors
- 👤 Philip G. Emma
- 👤 James H. Pomerene
- 👤 Gururaj S. Rao
- 👤 Rudolph N. Rechtschaffen
- 👤 Howard E. Sachar
- 👤 Frank J. Sparacio
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 22:36
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3836; G06F9/3842; G06F9/3848
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
219 words
In a computing machine, apparatus for predicting the outcome of branch instructions, the combination comprising: a processor; a memory for storing information to be processed by said processor, said information including instructions and operands; a branch history table for storing prior actions of branch instructions that are processed by said processor; means for detecting the occurrence of specific ones of said operands with specific ones of said branch instructions and with said prior actions of said branch instructions; means for determining specific occurrences of said branch instructions, and said prior actions resulting from said specific occurrences of said branch instructions; a storage means for storing said specific occurrences of branch instructions and said resulting actions; means for monitoring stores made to operands in said memory by said processor to determine if a given operand being stored to is one of said specific operands stored in said storage means; and means responsive to said specific occurrences of branch instructions and said resulting actions for determining, if the subsequent branch action of a given branch instruction in said storage means is different than the branch action of said given branch instruction in said branch history table, including means for updating the branch action of said given branch instruction in said branch history table, in the event that the branch actions differ.
Claim 2
Dependent Claim
219 words
In a computing machine, apparatus for predicting the outcome of branch instructions, the combination comprising: a processor; a memory for storing information to be processed by said processor, said information including instructions and operands; a branch history table for storing prior actions of branch instructions that are processed by said processor; means for detecting the occurrence of specific ones of said operands with specific ones of said branch instructions and with said prior actions of said branch instructions; means for determining specific occurrences of said branch instructions, and said prior actions resulting from said specific occurrences of said branch instructions; a storage means for storing said specific occurrences of branch instructions and said resulting actions; means for monitoring stores made to operands in said memory by said processor to determine if a given operand being stored to is one of said specific operands stored in said storage means; and means responsive to said specific occurrences of branch instructions and said resulting actions for determining, if the subsequent branch action of a given branch instruction in said storage means is different than the branch action of said given branch instruction in said branch history table, including means for updating the branch action of said given branch instruction in said branch history table, in the event that the branch actions differ.
Claim 3
Dependent Claim
241 words
In a computing machine, apparatus for predicting the outcome of branch instructions, the combination comprising: a processor; a memory for storing information to be processed by said processor, said information including instructions and operands; a branch history table (BHT) for storing prior branch actions of branch instructions which are processed by said processor; means for detecting occurrences of specific ones of said operands with specific ones of said branch instructions and with said prior actions of said branch instructions; means for determining specific occurrences of said branch instructions, and said prior actions resulting from said specific occurrences of said branch instructions; a data-dependent branch table (DDBT) for storing said specific occurrences of said branch instructions and said resulting actions, including addresses of said specific ones of said operands the addresses of said specific ones of said branch instructions, and said branch actions; first means for monitoring stores made to operands in said memory by said processor to determine if a given operand being stored to is one of said specific operands stored in said DDBT; second means responsive to said specific occurrences of branch instructions and said resulting actions for determining if the subsequent branch action of a given branch instruction in said DDBT is different than the branch action of said given branch instruction in said BHT; and third means for updating the branch action of said given branch instruction in said BHT, in the event the branch actions differ.
Claim 4
Dependent Claim
241 words
In a computing machine, apparatus for predicting the outcome of branch instructions, the combination comprising: a processor; a memory for storing information to be processed by said processor, said information including instructions and operands; a branch history table (BHT) for storing prior branch actions of branch instructions which are processed by said processor; means for detecting occurrences of specific ones of said operands with specific ones of said branch instructions and with said prior actions of said branch instructions; means for determining specific occurrences of said branch instructions, and said prior actions resulting from said specific occurrences of said branch instructions; a data-dependent branch table (DDBT) for storing said specific occurrences of said branch instructions and said resulting actions, including addresses of said specific ones of said operands the addresses of said specific ones of said branch instructions, and said branch actions; first means for monitoring stores made to operands in said memory by said processor to determine if a given operand being stored to is one of said specific operands stored in said DDBT; second means responsive to said specific occurrences of branch instructions and said resulting actions for determining if the subsequent branch action of a given branch instruction in said DDBT is different than the branch action of said given branch instruction in said BHT; and third means for updating the branch action of said given branch instruction in said BHT, in the event the branch actions differ.
Claim 5
Dependent Claim
28 words
The combination claimed in claim 2, wherein said branch action includes the branch instruction address (BA) and the target instruction address (TA) specific occurrences of a branch instruction.
Claim 6
Dependent Claim
31 words
The combination claimed in claim 3, wherein said third means for updating includes means for updating whichever of BA and TA differ in the event the comparison of branch actions differ.
Claim 7
Dependent Claim
31 words
The combination claimed in claim 2, wherein said branch action includes an action bit which is indicative of whether or not said given branch instruction was taken on its last execution.
Claim 8
Dependent Claim
28 words
The combination claimed in claim 5, wherein said third means for updating includes means for updating said action bit in the event the comparison of action bits differ.
Claim 9
Dependent Claim
31 words
The combination claimed in claim 3, wherein said branch action includes an action bit which is indicative of whether or not said given branch instruction was taken on its last execution.
Claim 10
Dependent Claim
34 words
The combination claimed in claim 7, wherein said third means for updating includes means for updating whichever of BA, TA. or the action bit differ in the event the comparison of branch actions differ.
Claim 11
Independent Claim
238 words
A method of processing branch instructions in a computing machine, wherein said computing machine includes a processor, a memory for storing information to be processed by said processor, said information including instructions and operands, a branch history table (BHT) for storing prior branch actions of instructions processed by said processor, and a data-dependent branch table (DDBT) that stores addresses of operands, addresses of branch instructions, branch actions of said branch instructions, and associations between specific ones of said operands and specific ones of said branch instructions, and said prior actions of said branch instructions; said method comprising the steps of: detecting the occurrences of specific ones of said operands with specific ones of said branch instructions and with said prior actions of said branch instructions; determining specific occurrences of said branch instructions, and said prior actions resulting from specific occurrences of said branch instructions; monitoring all stores made to operands stored in said memory by said processor to determine if a given operand being stored to is one of a said specific operands stored in said DDBT; responding to said specific occurrences of branch instructions and said resulting actions for determining if the subsequent branch action of a given branch instruction in said DDBT is different than the branch action of said given branch instruction in said BHT; and updating the branch action of said given branch instruction in said BHT, in the event the branch actions differ.
Claim 12
Independent Claim
238 words
A method of processing branch instructions in a computing machine, wherein said computing machine includes a processor, a memory for storing information to be processed by said processor, said information including instructions and operands, a branch history table (BHT) for storing prior branch actions of instructions processed by said processor, and a data-dependent branch table (DDBT) that stores addresses of operands, addresses of branch instructions, branch actions of said branch instructions, and associations between specific ones of said operands and specific ones of said branch instructions, and said prior actions of said branch instructions; said method comprising the steps of: detecting the occurrences of specific ones of said operands with specific ones of said branch instructions and with said prior actions of said branch instructions; determining specific occurrences of said branch instructions, and said prior actions resulting from specific occurrences of said branch instructions; monitoring all stores made to operands stored in said memory by said processor to determine if a given operand being stored to is one of a said specific operands stored in said DDBT; responding to said specific occurrences of branch instructions and said resulting actions for determining if the subsequent branch action of a given branch instruction in said DDBT is different than the branch action of said given branch instruction in said BHT; and updating the branch action of said given branch instruction in said BHT, in the event the branch actions differ.
Claim 13
Dependent Claim
50 words
The method of claim 9, wherein said branch action includes the branch instruction address (BA) and the target instruction address (TA) of specific occurrences of a branch instruction, and said step of updating includes updating whichever of BA and TA differ in the event the comparison of branch actions differ.
Claim 14
Dependent Claim
54 words
The method of claim 9, wherein said branch action includes an action bit which is indicative of whether or not said given branch instruction was taken on its last execution, and said step of updating includes updating said action bit in said branch history table in the event the comparison of action bits differ.
Claim 15
Dependent Claim
55 words
The method of claim 10, wherein said branch action includes an action bit which is indicative of whether or not said given branch instruction was taken on its last execution, and said step of updating includes updating whichever of BA, TA or the action bit differ in the event the comparison of branch actions differ.
References Cited (Backward Citations)
US3559183A
Cited
US4155120A
Cited
US4430706A
Cited
US4500959A
Cited
US4594659A
Cited
US4691277A
Cited
US4679141A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1991-08-09 | 1992-02-08 | 1992-08-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1995-08-09 | 1996-02-08 | 1996-08-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1999-08-09 | 2000-02-08 | 2000-08-09 | $7700.00 | Window Closed / Lapsed |