Patent US5564118A successfully refreshed from Google Patents.
US5564118A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Past-history filtered branch prediction
Assignee: Hewlett Packard Development Co LP
•
Filing: 1994-12-08
•
Granted: 1996-10-08
•
Expires: 2014-12-08
Abstract
Abstract A pipelined processor includes an instruction box including a register mapper, to map register operand fields of a set of instructions and an instruction scheduler, fed by said set of instructions, to reorder the issuance of said set of instructions from said instruction processor. The mapped register operand fields are associated with the corresponding instructions of said reordered set of instructions prior to issuance of the instructions. The processor further includes a branch prediction table which maps a stored pattern of past histories associated with a branch instruction to a more likely prediction direction of the branch instruction. The processor further includes a memory reference tagging store associated with the instruction scheduler so that the scheduler can reorder memory reference instructions without knowing the actual memory location addressed by the memory reference instruction.
Inventors
- 👤 Simon C. Steely, Jr.
- 👤 David J. Sager
- 👤 William B. Noyce
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 09:58
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3802; G06F9/3804; G06F9/3806; G06F9/30003; G06F9/3004; G06F9/30043; G06F9/30098; G06F9/3012; G06F9/30134; G06F9/30141; G06F9/3836; G06F9/3838; G06F9/384; G06F9/3842; G06F9/3848; G06F9/3854; G06F9/3856; G06F9/3858; G06F9/3861; G06F9/3863
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
125 words
A branch prediction apparatus comprising: means, responsive to an address portion of an instruction, for providing a past history branch pattern which is a branch pattern corresponding to a result of whether a branch was taken or not taken for a previous N number of occurrences of said instruction; means, responsive to said branch pattern, for determining whether said instruction should or should not take said branch in accordance with the branch pattern for the respective instruction; and means for distributing entries in the address of an instruction fed to said apparatus wherein said means for distributing entries further comprises: a logic circuit to exclusive or together two lower order bits of the instruction address with two selected higher order bits of the instruction address.
Claim 2
Dependent Claim
125 words
A branch prediction apparatus comprising: means, responsive to an address portion of an instruction, for providing a past history branch pattern which is a branch pattern corresponding to a result of whether a branch was taken or not taken for a previous N number of occurrences of said instruction; means, responsive to said branch pattern, for determining whether said instruction should or should not take said branch in accordance with the branch pattern for the respective instruction; and means for distributing entries in the address of an instruction fed to said apparatus wherein said means for distributing entries further comprises: a logic circuit to exclusive or together two lower order bits of the instruction address with two selected higher order bits of the instruction address.
Claim 3
Dependent Claim
21 words
The apparatus of claim 1 further comprising: means for distributing entries in the past history branch pattern from the providing means.
Claim 4
Dependent Claim
34 words
The apparatus of claim 2 wherein said means for distributing entries in the past history branch pattern comprises: means for concatenating bits of the address of said instruction with the past history branch pattern.
Claim 5
Dependent Claim
69 words
The apparatus of claim 3 wherein said means for determining whether a branch should or should not be taken comprises: a plurality of separate sets of up-down counters, each set of counters comprised of 2 N number of counters and said plurality of sets of counters corresponding to 2 l number of sets where l is the number of bits of the instruction address concatenated to said branch pattern.
Claim 6
Dependent Claim
135 words
A branch prediction apparatus comprising: means, responsive to an address portion of an instruction, for providing a past history branch pattern which is a branch pattern corresponding to a result of whether a branch was taken or not taken for a previous N number of occurrences of said instruction; means, responsive to said branch pattern, for determining whether said instruction should or should not take said branch in accordance with the branch pattern for the respective instruction; means, responsive to the address of the instruction, for storing a predicted past history pattern and a valid bit indicating that a predicted past history pattern is stored in a location in said means for storing a predicted past history pattern said instruction; and means for storing a data bit corresponding to a prediction direction of said instruction.
Claim 7
Dependent Claim
135 words
A branch prediction apparatus comprising: means, responsive to an address portion of an instruction, for providing a past history branch pattern which is a branch pattern corresponding to a result of whether a branch was taken or not taken for a previous N number of occurrences of said instruction; means, responsive to said branch pattern, for determining whether said instruction should or should not take said branch in accordance with the branch pattern for the respective instruction; means, responsive to the address of the instruction, for storing a predicted past history pattern and a valid bit indicating that a predicted past history pattern is stored in a location in said means for storing a predicted past history pattern said instruction; and means for storing a data bit corresponding to a prediction direction of said instruction.
Claim 8
Dependent Claim
32 words
The apparatus as recited in claim 5 further comprising: means, responsive to said valid bit, for selecting between said predicted past history pattern and said past history pattern as the branch pattern.
Claim 9
Dependent Claim
25 words
The apparatus as recited in claim 6 further comprising: means, responsive to said branch pattern, for concatenating bits of said instruction to said branch pattern.
Claim 10
Dependent Claim
71 words
The apparatus as recited in claim 7 wherein said means for determining whether a branch should or should not be taken comprises: a plurality of separate sets of up-down counters, each set of counters comprised of 2 N number of counters and said plurality of sets of counters corresponding to 2 l number of sets where l is the number of bits of the instruction address concatenated to said branch pattern.
Claim 11
Dependent Claim
15 words
The apparatus as recited in claim 8 wherein said counters are non-wrap around up/down counters.
Claim 12
Independent Claim
281 words
An apparatus, comprising: a first register file having K number of addressable storage locations and having a read port and a write port, said read port addressed by an address portion of an instruction to provide a bit pattern corresponding to whether said instruction took a branch over the last N occurrences of said instruction, and said write port addressed by said address portion of said instruction and fed by a bit indicating whether that occurrence of said instruction took the branch; a second register file containing two addressable fields a first field containing a bit pattern corresponding to a predicted past history and a second field containing a valid bit associated with said predicted past history which indicates that a prediction has not been resolved; means, responsive to said valid bit from said second register file for selecting a bit pattern from said first register file and said second register file; means responsive to the bit pattern from said means for selecting a bit pattern and selected bits of said instruction to provide a extended pattern; a plurality of sets of counters each set of said counters having 2 K number of counters, with said extended pattern to providing an address to select one of said counters to provide a most significant bit, said most significant bit indicating whether said instruction should or should not take a branch and with said counter incremented or decremented in accordance with whether a branch was or was not taken by the instruction; a plurality of storage locations, each a single bit wide and each addressed by a logical instruction number of said instruction to store said most significant bit from said selected counter.
Claim 13
Independent Claim
281 words
An apparatus, comprising: a first register file having K number of addressable storage locations and having a read port and a write port, said read port addressed by an address portion of an instruction to provide a bit pattern corresponding to whether said instruction took a branch over the last N occurrences of said instruction, and said write port addressed by said address portion of said instruction and fed by a bit indicating whether that occurrence of said instruction took the branch; a second register file containing two addressable fields a first field containing a bit pattern corresponding to a predicted past history and a second field containing a valid bit associated with said predicted past history which indicates that a prediction has not been resolved; means, responsive to said valid bit from said second register file for selecting a bit pattern from said first register file and said second register file; means responsive to the bit pattern from said means for selecting a bit pattern and selected bits of said instruction to provide a extended pattern; a plurality of sets of counters each set of said counters having 2 K number of counters, with said extended pattern to providing an address to select one of said counters to provide a most significant bit, said most significant bit indicating whether said instruction should or should not take a branch and with said counter incremented or decremented in accordance with whether a branch was or was not taken by the instruction; a plurality of storage locations, each a single bit wide and each addressed by a logical instruction number of said instruction to store said most significant bit from said selected counter.
References Cited (Backward Citations)
US4370711A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-10-08 | 2000-04-08 | 2000-10-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-10-08 | 2004-04-08 | 2004-10-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-10-08 | 2008-04-08 | 2008-10-08 | $7700.00 | Window Closed / Lapsed |