US5394529A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Branch prediction unit for high-performance processor
Assignee: Hewlett Packard Development Co LP
•
Filing: 1993-07-01
•
Granted: 1995-02-28
•
Expires: 2013-07-01
Abstract
Abstract A pipelined CPU executes instructions of variable length, and references memory using various data widths. Macroinstruction pipelining is employed (instead of microinstruction pipelining), with queueing between units of the CPU to allow flexibility in instruction execution times. A branch prediction method employs a branch history table which records the taken vs. not-taken history of branch opcodes recently used, and uses an empirical aglorithm to predict which way the next occurrence of this branch will go, based upon the history table. The branch history table stores in each entry a number of bits for each branch address, each bits indicating "taken" or "not-taken" for one occurrence of the branch. The table is indexed by branch address. A register stores the empirical aglorithm, and upon occurrence of a branch its history is fetched from the table and used to select a location in the register containing a prediction for this particular pattern of branch history.
Inventors
- 👤 John F. Brown, III
- 👤 Shawn Persels
- 👤 Jeanne Meyer
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 09:53
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3836; G06F9/3842; G06F9/3848; F; F02; F02B; F02B75/00; F02B75/02; F02B2075/022; F02B2075/025
Claims Analysis
Total Claims: 31
Claim 1
Independent Claim
179 words
A method of branch prediction, comprising the steps of: a) storing a record of whether a conditional branch executed by a processor is taken or not taken for each conditional branch instruction executed by a processor, said storing being by memory address for each conditional branch instruction, said record including a plurality of occurrences of either a taken indicator or a not-taken indicator or both for each conditional branch instruction at each said memory address; b) when a conditional branch instruction is executed using one said memory address, predicting whether or not the branch will be taken in response to said record accessed using said one memory address and based upon a multi-bit prediction pattern, using said taken and not-taken indicators in said record; said prediction pattern being a multi-bit value in a register, said register being writable by said processor for dynamically changing the prediction pattern during operation of said processor, said record for said one memory address being used for selection within said multi-bit value; c) fetching instruction in an instruction stream in response to said prediction.
Claim 2
Independent Claim
179 words
A method of branch prediction, comprising the steps of: a) storing a record of whether a conditional branch executed by a processor is taken or not taken for each conditional branch instruction executed by a processor, said storing being by memory address for each conditional branch instruction, said record including a plurality of occurrences of either a taken indicator or a not-taken indicator or both for each conditional branch instruction at each said memory address; b) when a conditional branch instruction is executed using one said memory address, predicting whether or not the branch will be taken in response to said record accessed using said one memory address and based upon a multi-bit prediction pattern, using said taken and not-taken indicators in said record; said prediction pattern being a multi-bit value in a register, said register being writable by said processor for dynamically changing the prediction pattern during operation of said processor, said record for said one memory address being used for selection within said multi-bit value; c) fetching instruction in an instruction stream in response to said prediction.
Claim 3
Dependent Claim
15 words
A method according to claim 1 wherein said record includes at least four said occurrences.
Claim 4
Dependent Claim
21 words
A method according to claim 1 wherein said record is a table indexed by instruction address in a range of addresses.
Claim 5
Dependent Claim
33 words
A method according to claim 1 wherein said record is a plurality of bits, each bit providing one of said taken or not taken indicators for a branch instruction at an instruction address.
Claim 6
Dependent Claim
34 words
A method according to claim 1 including the step of entering into said record the correct one of said taken or not taken indicators for each branch instruction after each branch instruction is executed.
Claim 7
Independent Claim
143 words
A method of branch prediction, comprising the steps of: a) storing a record of whether a conditional branch is taken or not taken for each conditional branch instruction executed by a processor, said record including a plurality of occurrences of either a taken indicator or a not-taken indicator or both for each conditional branch instruction at each memory address; wherein said record is a plurality of bits, each bit providing one of said taken or not taken indicators for a branch instruction at an instruction address; b) when a conditional branch instruction is executed, predicting whether or not the branch will be taken based upon said record and upon a prediction pattern using said taken and not-taken indicators; wherein said record is used to address a register containing said prediction pattern; c) fetching instructions in an instruction stream in response to said prediction.
Claim 8
Independent Claim
143 words
A method of branch prediction, comprising the steps of: a) storing a record of whether a conditional branch is taken or not taken for each conditional branch instruction executed by a processor, said record including a plurality of occurrences of either a taken indicator or a not-taken indicator or both for each conditional branch instruction at each memory address; wherein said record is a plurality of bits, each bit providing one of said taken or not taken indicators for a branch instruction at an instruction address; b) when a conditional branch instruction is executed, predicting whether or not the branch will be taken based upon said record and upon a prediction pattern using said taken and not-taken indicators; wherein said record is used to address a register containing said prediction pattern; c) fetching instructions in an instruction stream in response to said prediction.
Claim 9
Dependent Claim
51 words
A method according to claim 6 wherein said branch instruction is executed by a processor, and said processor has a plurality of internal registers, and has a data path for accessing said internal registers under control of instructions, and wherein said register is accessible by said data path of said processor.
Claim 10
Independent Claim
231 words
A method of operating a computer, comprising the steps of: a) fetching a sequence of instructions using a sequence of addresses, wherein said instructions may include conditional branch instructions; b) detecting a conditional branch instruction in said sequence, and, when a conditional branch instruction is detected, selecting an entry in a branch history table in response to the address of said branch instruction in said sequence, the branch history table containing a plurality of the entries, each entry containing a plurality of indicators of taken or not taken, each indicator being the result of one of a plurality of occurrences of each branch instruction at a given memory address; c) in response to said plurality of indicators in said branch history table, predicting whether or not a branch will be taken when said conditional branch instruction is executed, and, if it is predicted that the branch will be taken, fetching instructions of a sequence different from said sequence, said predicting being by selecting from a multi-bit programmable prediction value using said plurality of indicators as an index for selecting within said multi-bit prediction value; said prediction value being in an internal location in said computer writable by said computer for dynamically changing said multi-bit prediction; d) executing said conditional branch instruction in a processing unit and updating said branch history table to indicate whether or not said branch was actually taken.
Claim 11
Independent Claim
231 words
A method of operating a computer, comprising the steps of: a) fetching a sequence of instructions using a sequence of addresses, wherein said instructions may include conditional branch instructions; b) detecting a conditional branch instruction in said sequence, and, when a conditional branch instruction is detected, selecting an entry in a branch history table in response to the address of said branch instruction in said sequence, the branch history table containing a plurality of the entries, each entry containing a plurality of indicators of taken or not taken, each indicator being the result of one of a plurality of occurrences of each branch instruction at a given memory address; c) in response to said plurality of indicators in said branch history table, predicting whether or not a branch will be taken when said conditional branch instruction is executed, and, if it is predicted that the branch will be taken, fetching instructions of a sequence different from said sequence, said predicting being by selecting from a multi-bit programmable prediction value using said plurality of indicators as an index for selecting within said multi-bit prediction value; said prediction value being in an internal location in said computer writable by said computer for dynamically changing said multi-bit prediction; d) executing said conditional branch instruction in a processing unit and updating said branch history table to indicate whether or not said branch was actually taken.
Claim 12
Dependent Claim
39 words
A method according to claim 8 wherein said branch history table includes an entry for each address in a range of addresses which is less than the addressing range for said instructions, each entry containing said plurality of indicators.
Claim 13
Dependent Claim
11 words
A method according to claim 9 wherein said range is 512.
Claim 14
Dependent Claim
43 words
A method according to claim 10 wherein each said entry contains four branch-history bits, each bit being one of said indicators of whether a branch was taken or not in a previous execution of a conditional branch at an address in said range.
Claim 15
Dependent Claim
38 words
A method according to claim 9 wherein said step of updating includes shifting the contents of a location in said branch history table and adding a value according to the predicted value of branch taken or not taken.
Claim 16
Independent Claim
281 words
A method of operating a computer, comprising the steps of: a) fetching a sequence of instructions using a sequence of addresses, wherein said instructions may include conditional branch instructions; b) detecting a conditional branch instruction in said sequence, and, when a conditional branch instruction is detected, selecting an entry in a branch history table in response to the address of said branch instruction in said sequence, the branch history table containing a plurality of indicators of taken or not taken, each indicator being the result of one of a plurality of occurrences of each branch instruction; wherein said branch history table includes an entry for each address in a range of addresses which is less than the addressing range for said instructions, each entry containing said plurality of indicators; wherein each said entry contains a plurality of branch-history bits, each bit being one of said indicators of whether a branch was taken or not in a previous execution of a conditional branch at an address in said range; c) in response to said plurality of indicators in said branch history table, predicting whether or not a branch will be taken when said conditional branch instruction is executed, and, if it is predicted that the branch will be taken, fetching instructions of a sequence different from said sequence, said predicting being based upon a programmable prediction algorithm using said plurality of indicators; wherein said step of predicting includes selecting a value from a register using bits from said history table as an index to said register; d) executing said conditional branch instruction in a processing unit and updating said branch history table to indicate whether or not said branch was actually taken.
Claim 17
Independent Claim
281 words
A method of operating a computer, comprising the steps of: a) fetching a sequence of instructions using a sequence of addresses, wherein said instructions may include conditional branch instructions; b) detecting a conditional branch instruction in said sequence, and, when a conditional branch instruction is detected, selecting an entry in a branch history table in response to the address of said branch instruction in said sequence, the branch history table containing a plurality of indicators of taken or not taken, each indicator being the result of one of a plurality of occurrences of each branch instruction; wherein said branch history table includes an entry for each address in a range of addresses which is less than the addressing range for said instructions, each entry containing said plurality of indicators; wherein each said entry contains a plurality of branch-history bits, each bit being one of said indicators of whether a branch was taken or not in a previous execution of a conditional branch at an address in said range; c) in response to said plurality of indicators in said branch history table, predicting whether or not a branch will be taken when said conditional branch instruction is executed, and, if it is predicted that the branch will be taken, fetching instructions of a sequence different from said sequence, said predicting being based upon a programmable prediction algorithm using said plurality of indicators; wherein said step of predicting includes selecting a value from a register using bits from said history table as an index to said register; d) executing said conditional branch instruction in a processing unit and updating said branch history table to indicate whether or not said branch was actually taken.
Claim 18
Dependent Claim
44 words
A method according to claim 13 wherein said computer includes a plurality of internal registers, said internal registers being accessible via a datapath upon execution of instructions of said sequence of instructions, and wherein said register is accessible by said datapath of said computer.
Claim 19
Dependent Claim
245 words
A processor, said processor fetching and executing a sequence of instructions, wherein said instructions may include conditional branch instructions, said processor having a branch predictor comprising: a) a branch history table storing a plurality entries, each entry containing a plurality of indicators of whether a branch was taken or not taken for each of said conditional branch instructions in a range of addresses for said instructions; b) a detector detecting a conditional branch instruction in said sequence, and, when a conditional branch in instruction is detected, selecting one of said entries in said branch history table in response to the address of said branch instruction in said sequence; c) a predictor generating an output indicating a programmable empirically-based prediction of whether or not a branch will be taken when said conditional branch instruction is executed, said prediction being responsive to said plurality of indicators of an entry, and, if it is predicted that the branch will be taken, generating a new address sequence for fetching instructions differing from said sequence; wherein said predictor includes a register containing a plurality of bits, said register being addressed by said indicators for said selected one of said entries, each bit of said register being said prediction for a pattern of said indicators as recorded in one of said entries in said history table; d) a processing unit executing said conditional branch instruction and updating said branch history table to indicate whether or not said branch was actually taken.
Claim 20
Dependent Claim
245 words
A processor, said processor fetching and executing a sequence of instructions, wherein said instructions may include conditional branch instructions, said processor having a branch predictor comprising: a) a branch history table storing a plurality entries, each entry containing a plurality of indicators of whether a branch was taken or not taken for each of said conditional branch instructions in a range of addresses for said instructions; b) a detector detecting a conditional branch instruction in said sequence, and, when a conditional branch in instruction is detected, selecting one of said entries in said branch history table in response to the address of said branch instruction in said sequence; c) a predictor generating an output indicating a programmable empirically-based prediction of whether or not a branch will be taken when said conditional branch instruction is executed, said prediction being responsive to said plurality of indicators of an entry, and, if it is predicted that the branch will be taken, generating a new address sequence for fetching instructions differing from said sequence; wherein said predictor includes a register containing a plurality of bits, said register being addressed by said indicators for said selected one of said entries, each bit of said register being said prediction for a pattern of said indicators as recorded in one of said entries in said history table; d) a processing unit executing said conditional branch instruction and updating said branch history table to indicate whether or not said branch was actually taken.
Claim 21
Dependent Claim
15 words
A processor according to claim 15 wherein said plurality of occurrences is at least four.
Claim 22
Dependent Claim
33 words
A processor according to claim 15 wherein said processor contains a plurality in internal registers accessible via a datapath, and wherein said register is accessible for writing by said datapath of said processor.
Claim 23
Dependent Claim
175 words
A processor for executing instructions including conditional branch instructions, having a branch prediction comprising: a) means for storing a record of entries containing indicators of whether a conditional branch is taken or not taken for each conditional branch instruction executed by said processor, said record including a plurality of entries, each said entry containing a plurality of said indicators for a plurality of occurrences of each conditional branch instruction at each memory address; b) means responsive to a conditional branch instruction being executed, for predicting whether or not the branch will be taken responsive to one of said entries of said record and based upon a stored programmable prediction pattern; said prediction pattern being a multi-bit value addressed by said one of said entries and selection from said multi-bit value being in response to the value of said one of said entries, said multi-bit value being in a location in said processor writable by an instruction executed by said processor; c) and means for fetching instructions in an instruction stream in response to said prediction.
Claim 24
Dependent Claim
175 words
A processor for executing instructions including conditional branch instructions, having a branch prediction comprising: a) means for storing a record of entries containing indicators of whether a conditional branch is taken or not taken for each conditional branch instruction executed by said processor, said record including a plurality of entries, each said entry containing a plurality of said indicators for a plurality of occurrences of each conditional branch instruction at each memory address; b) means responsive to a conditional branch instruction being executed, for predicting whether or not the branch will be taken responsive to one of said entries of said record and based upon a stored programmable prediction pattern; said prediction pattern being a multi-bit value addressed by said one of said entries and selection from said multi-bit value being in response to the value of said one of said entries, said multi-bit value being in a location in said processor writable by an instruction executed by said processor; c) and means for fetching instructions in an instruction stream in response to said prediction.
Claim 25
Dependent Claim
20 words
A processor according to claim 18 wherein each said entry of said record includes at least four of said indicators.
Claim 26
Dependent Claim
21 words
A processor according to claim 18 wherein said record is a table indexed by instruction address in a range of addresses.
Claim 27
Dependent Claim
38 words
A processor according to claim 18 wherein each said entry of said record is a plurality of bits, each bit being one of said indicators indicating taken or not taken for a branch instruction at an instruction address.
Claim 28
Dependent Claim
31 words
A processor according to claim 18 including means for entering into said record the correct indication of taken or not taken for each branch instruction after each branch instruction is executed.
Claim 29
Dependent Claim
172 words
A processor for executing instructions including conditional branch instructions, having a branch prediction comprising: a) means for storing a record of entries containing indicators of whether a conditional branch is taken or not taken for each conditional branch instruction executed by said processor, said record including an entry containing a plurality of said indicators for a plurality of occurrences of each conditional branch instruction at each memory address; wherein each said entry of said record is a plurality of bits, each bit being one of said indicators indicating taken or not taken for a branch instruction at an instruction address b) means responsive to a conditional branch instruction being executed, for predicting whether or not the branch will be taken responsive to one of said entries of said record and based upon a stored programmable prediction pattern; wherein a selected one of said entries of said record is used to address a register containing said prediction pattern; c) and means for fetching instructions in an instruction stream in response to said prediction.
Claim 30
Dependent Claim
172 words
A processor for executing instructions including conditional branch instructions, having a branch prediction comprising: a) means for storing a record of entries containing indicators of whether a conditional branch is taken or not taken for each conditional branch instruction executed by said processor, said record including an entry containing a plurality of said indicators for a plurality of occurrences of each conditional branch instruction at each memory address; wherein each said entry of said record is a plurality of bits, each bit being one of said indicators indicating taken or not taken for a branch instruction at an instruction address b) means responsive to a conditional branch instruction being executed, for predicting whether or not the branch will be taken responsive to one of said entries of said record and based upon a stored programmable prediction pattern; wherein a selected one of said entries of said record is used to address a register containing said prediction pattern; c) and means for fetching instructions in an instruction stream in response to said prediction.
Claim 31
Dependent Claim
42 words
A processor according to claim 23 wherein said processor includes a plurality of internal registers, said internal registers being accessible via a data path upon execution of said instructions, and wherein said register is accessible by said data paths of said processor.
References Cited (Backward Citations)
US4477872A
Cited
US4984154A
Cited
US4760519A
Cited
US4777594A
Cited
US4679141A
Cited
US5228131A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-02-27 | 1998-08-29 | 1999-02-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-02-27 | 2002-08-29 | 2003-02-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-02-27 | 2006-08-29 | 2007-02-28 | $7700.00 | Window Closed / Lapsed |