US5935241A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Multiple global pattern history tables for branch prediction in a microprocessor
Assignee: Texas Instruments Inc
•
Filing: 1997-12-10
•
Granted: 1999-08-10
•
Expires: 2017-12-10
Abstract
Abstract A microprocessor (10) and a system (300) incorporating the same is disclosed, in which branch prediction is effected in response to the type of program in which branching instructions are contained. A fetch unit (26) includes a branch target buffer (56) and a plurality of pattern history tables (53). Select logic (80) receives signals indicating, for each branching instruction, the type of program containing the instruction, and selects one of the pattern history tables (53) for use in generating a prediction code in response to a portion of a branch history field (BH) in an entry (63) of the branch target buffer (56) corresponding to the instruction address. Disclosed examples of the signals used in selecting the pattern history table (53) include an indication (U/S) of the privilege level (e.g., user-level or supervisor-level) of the instruction. A range register unit (75) for determining whether the instruction is contained within an address range is also disclosed as used in the selection of the pattern history table (53).
Inventors
- 👤 Jonathan H. Shiell
- 👤 George Z. N. Cai
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 21:03
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3802; G06F9/3804; G06F9/3806; G06F9/3836; G06F9/3842; G06F9/3848
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
156 words
A microprocessor, comprising: an execution unit for executing instructions according to a plurality of program types; a memory for storing instruction codes of instructions; and a fetch unit, for addressing the memory to retrieve instruction codes for execution by the execution unit, comprising: a branch history circuit, for storing a sequence of results of branching instructions executed by the execution unit; a plurality of pattern history tables coupled to the branch history circuit, each having a plurality of indexed prediction code entries, and each having an output for presenting the contents of one of the prediction code entries corresponding to a branch history field from the branch history circuit; an addressing circuit for selecting an address for an instruction to be fetched; and select logic, coupled to receive a program type indicator, for selectively forwarding, to the addressing circuit, the output of one of the plurality of pattern history tables corresponding to the program type indicator.
Claim 2
Dependent Claim
156 words
A microprocessor, comprising: an execution unit for executing instructions according to a plurality of program types; a memory for storing instruction codes of instructions; and a fetch unit, for addressing the memory to retrieve instruction codes for execution by the execution unit, comprising: a branch history circuit, for storing a sequence of results of branching instructions executed by the execution unit; a plurality of pattern history tables coupled to the branch history circuit, each having a plurality of indexed prediction code entries, and each having an output for presenting the contents of one of the prediction code entries corresponding to a branch history field from the branch history circuit; an addressing circuit for selecting an address for an instruction to be fetched; and select logic, coupled to receive a program type indicator, for selectively forwarding, to the addressing circuit, the output of one of the plurality of pattern history tables corresponding to the program type indicator.
Claim 3
Dependent Claim
16 words
The microprocessor of claim 1, wherein the branch history circuit comprises a global branch history buffer.
Claim 4
Dependent Claim
54 words
The microprocessor of claim 1, wherein the branch history circuit comprises: a branch target buffer comprised of a plurality of entries, each entry having a tag field corresponding to the instruction address of an associated branching instruction, having a branch history field for storing a sequence of previous branches of its associated branching instruction.
Claim 5
Dependent Claim
64 words
The microprocessor of claim 3, wherein each of the plurality of entries in the branch target buffer further comprises a target field for storing a branch target address; and wherein the addressing circuit, responsive to the select logic forwarding an output corresponding to a branch-taken prediction, selects an address corresponding to the branch target address of the entry corresponding to the associated branching instruction.
Claim 6
Dependent Claim
27 words
The microprocessor of claim 1, wherein the program type indicator of a branching instruction comprises a privilege level indicator corresponding to a program containing the branching instruction.
Claim 7
Dependent Claim
23 words
The microprocessor of claim 5, wherein the privilege level indicator comprises a bit of a code segment register corresponding to the branching instruction.
Claim 8
Dependent Claim
33 words
The microprocessor of claim 1, wherein the program type indicator of a branching instruction comprises at least one bit of a page table entry for a portion of memory containing the branching instruction.
Claim 9
Dependent Claim
32 words
The microprocessor of claim 1, wherein the program type indicator of a branching instruction comprises at least one bit of a segment descriptor for a portion of memory containing the branching instruction.
Claim 10
Dependent Claim
27 words
The microprocessor of claim 1, wherein the program type indicator of a branching instruction comprises at least one bit of the instruction address of the branching instruction.
Claim 11
Dependent Claim
56 words
The microprocessor of claim 1, wherein the select logic comprises: a multiplexer having inputs for receiving outputs from each of the plurality of pattern history tables and having an output coupled to the branch history circuit, for selecting the output of one of the plurality of pattern history tables for forwarding to the branch history circuit.
Claim 12
Dependent Claim
46 words
The microprocessor of claim 10, wherein the program type indicator for a branching instruction comprises a privilege level indicator corresponding to a program containing the branching instruction; and wherein the multiplexer of the select logic has a control input coupled to receive the privilege level indicator.
Claim 13
Dependent Claim
48 words
The microprocessor of claim 11, wherein the select logic further comprises: logic for generating control signals to the multiplexer responsive to a logical combination of the privilege level indicator and to a global bit of a page table entry for a portion of memory containing the branching instruction.
Claim 14
Dependent Claim
68 words
The microprocessor of claim 1, wherein the select logic comprises: a first pair of range registers for storing a maximum and a minimum address value, respectively; and a first comparator for comparing a portion of the instruction address of a branching instruction to the contents of the first pair of range registers; wherein the program type indicator comprises the result of the comparing performed by the first comparator.
Claim 15
Dependent Claim
91 words
The microprocessor of claim 13, wherein the select logic further comprises: a second pair of range registers for storing a maximum and a minimum address value, respectively; a second comparator for comparing a portion of the instruction address of the branching instruction to the contents of the second pair of range registers; and logic for generating an in/out signal corresponding to the result of a selected one of the first and second comparators, selected responsive to the state of a privilege level indicator corresponding to a program containing the branching instruction.
Claim 16
Dependent Claim
25 words
The microprocessor of claim 14, wherein the program type indicator comprises a combination of the state of the in/out signal with the privilege level indicator.
Claim 17
Dependent Claim
50 words
The microprocessor of claim 15, wherein the select logic comprises: a multiplexer having inputs for receiving outputs from each of the plurality of pattern history tables, having an output coupled to the branch target buffer, and having control inputs coupled to receive the in/out signal and the privilege level indicator.
Claim 18
Independent Claim
88 words
A method of operating a pipelined microprocessor to speculatively execute branching instructions in a program of microprocessor instructions, comprising the steps of: detecting a branch instruction at a fetch stage of the pipelined microprocessor; responsive to the detecting step, retrieving at least a portion of a branch history field; determining a program type corresponding to the branch instruction; and generating a branch prediction corresponding to the retrieved portion of the branch history field from one of a plurality of pattern history tables selected according to the program type.
Claim 19
Independent Claim
88 words
A method of operating a pipelined microprocessor to speculatively execute branching instructions in a program of microprocessor instructions, comprising the steps of: detecting a branch instruction at a fetch stage of the pipelined microprocessor; responsive to the detecting step, retrieving at least a portion of a branch history field; determining a program type corresponding to the branch instruction; and generating a branch prediction corresponding to the retrieved portion of the branch history field from one of a plurality of pattern history tables selected according to the program type.
Claim 20
Dependent Claim
76 words
The method of claim 17, further comprising: responsive to the detecting step, applying an instruction address to a branch target buffer, the branch target buffer having a plurality of entries, each having a tag field for storing an instruction identifier, and having a branch history field for storing branch results; wherein the retrieving step is performed responsive to a portion of the applied instruction address matching the tag field of one of the plurality of entries.
Claim 21
Dependent Claim
27 words
The method of claim 17, wherein the determining step comprises: interrogating the state of a privilege level indicator corresponding to the program containing the detected branching instruction.
Claim 22
Dependent Claim
24 words
The method of claim 19, wherein the privilege level indicator comprises a bit of a code segment register corresponding to the detected branching instruction.
Claim 23
Dependent Claim
33 words
The method of claim 17, wherein the determining step comprises: interrogating the state of at least one bit of a page table entry for a portion of memory containing the detected branching instruction.
Claim 24
Dependent Claim
32 words
The method of claim 17, wherein the determining step comprises: interrogating the state of at least one bit of a segment descriptor for a portion of memory containing the detected branching instruction.
Claim 25
Dependent Claim
40 words
The method of claim 17, wherein the determining step comprises: comparing the detected branching instruction address to the contents of a first pair of range registers to determine if the detected branching instruction address is within the range specified thereby.
Claim 26
Dependent Claim
110 words
The method of claim 23, wherein the determining step further comprises: comparing the detected branching instruction address to the contents of a plurality of pairs of range registers to determine if the detected branching instruction address is within the ranges specified thereby; and interrogating the state of a privilege level indicator corresponding to the program containing the detected branching instruction; and further comprising: selecting one of the plurality of pattern history tables responsive to the state of the privilege level indicator and to the result of the comparing step performed by one of the plurality of pairs of range registers selected responsive to the state of the privilege level indicator.
References Cited (Backward Citations)
US5577217A
Cited
US5574871A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-08-09 | 2003-02-08 | 2003-08-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-08-09 | 2007-02-08 | 2007-08-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-08-09 | 2011-02-08 | 2011-08-10 | $7700.00 | Window Closed / Lapsed |