US6003128A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Number of pipeline stages and loop length related counter differential based end-loop prediction
Assignee: Advanced Micro Devices Inc
•
Filing: 1997-05-01
•
Granted: 1999-12-14
•
Expires: 2017-05-01
Abstract
Abstract An apparatus for prediction of loop instructions. Loop instructions decrement the value in a counter register and branch to a target address (specified by an instruction operand) if the decremented value of the counter register is greater than zero. The apparatus comprises a loop detection unit that detects the presence of a loop instruction in the instruction stream. An indication of the loop instruction is conveyed to a reorder buffer which stores speculative register values. If the apparatus is not currently processing the loop instruction, a compare value corresponding to the counter register prior to execution of the loop instruction is conveyed to a loop prediction unit. The loop prediction unit also increments a counter value upon receiving each indication of the loop instruction. This counter value is then compared to the compare value conveyed from the reorder buffer. If the counter value is one less than the compare value, a signal is asserted that indicates that the loop instruction should be predicted not-taken upon a next iteration of the loop. In this manner, loop prediction accuracy may be increased by correctly predicting the loop instruction not-taken. Because loops are commonly found in a variety of applications, increasing the accuracy of loop prediction, even slightly, may have a beneficial effect on performance. The loop operation is particularly important in scientific applications where it may be used to perform various digital signal processing routines and to traverse arrays.
Inventors
- 👤 Thang M. Tran
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 17:01
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/32; G06F9/322; G06F9/325; G06F9/38; G06F9/3836; G06F9/3842; G06F9/3844
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
228 words
A method for predicting a loop instruction, comprising: detecting said loop instruction during each of an initial and subsequent iterations of a loop defined by said loop instruction; conveying an initial and subsequent indications of the detected loop instruction to a loop prediction circuit; conveying an initial loop count to the loop prediction circuit in response to the loop prediction circuit receiving the initial indication, wherein said initial loop count comprises a value stored in a specified register prior to any iteration of the loop containing the detected loop instruction, and wherein an execution of said detected loop instruction decrements a value stored in said specified register at the time the detected loop instruction is executed, and wherein the execution of the detected loop instruction causes a branch unless said decremented value is equal to zero; incrementing a counter value in response to the loop prediction circuit receiving said initial and subsequent indications; determining whether a difference between said incremented counter and said initial loop count is a given value, wherein said given value is determined as a function of a number of instructions in the loop and a number of pipeline stages prior to said loop prediction unit; predicting a not-taken outcome for said detected loop instruction in response to determining that the difference between said incremented counter and said initial loop count is the given value.
Claim 2
Independent Claim
228 words
A method for predicting a loop instruction, comprising: detecting said loop instruction during each of an initial and subsequent iterations of a loop defined by said loop instruction; conveying an initial and subsequent indications of the detected loop instruction to a loop prediction circuit; conveying an initial loop count to the loop prediction circuit in response to the loop prediction circuit receiving the initial indication, wherein said initial loop count comprises a value stored in a specified register prior to any iteration of the loop containing the detected loop instruction, and wherein an execution of said detected loop instruction decrements a value stored in said specified register at the time the detected loop instruction is executed, and wherein the execution of the detected loop instruction causes a branch unless said decremented value is equal to zero; incrementing a counter value in response to the loop prediction circuit receiving said initial and subsequent indications; determining whether a difference between said incremented counter and said initial loop count is a given value, wherein said given value is determined as a function of a number of instructions in the loop and a number of pipeline stages prior to said loop prediction unit; predicting a not-taken outcome for said detected loop instruction in response to determining that the difference between said incremented counter and said initial loop count is the given value.
Claim 3
Dependent Claim
18 words
The method for predicting a loop instruction as recited in claim 1 wherein said given value is one.
Claim 4
Dependent Claim
34 words
The method for predicting a loop instruction as recited in claim 1 further comprising disabling updates to said initial loop count subsequent to said conveying said initial loop count to said loop prediction unit.
Claim 5
Dependent Claim
40 words
The method for predicting a loop instruction as recited in claim 3 further comprising enabling updates to said initial loop count in response to a subsequent indication received during a last of said one or more iterations of said loop.
Claim 6
Dependent Claim
36 words
The method for predicting a loop instruction as recited in claim 3 further comprising resetting said counter value in response to a subsequent indication received during a last of one or more iterations of said loop.
Claim 7
Dependent Claim
46 words
The method for predicting a loop instruction as recited in claim 1 wherein said initial loop count is stored in a reorder buffer coupled to the loop prediction circuit, and wherein the initial loop count is conveyed from the reorder buffer to the loop prediction circuit.
Claim 8
Dependent Claim
52 words
The method for predicting a loop instruction as recited in claim 1 wherein said initial loop count is conveyed from a loop count cache coupled to the loop prediction circuit, wherein said loop count cache includes a copy of a value stored in said specified register prior to detecting said loop instruction.
Claim 9
Independent Claim
304 words
An apparatus for predicting a loop instruction, comprising: a loop detection circuit configured to detect said loop instruction during each of an initial and subsequent iterations of a loop defined by said loop instruction, wherein the loop detection circuit is configured to convey initial and subsequent indications of the detected loop instruction to a loop prediction circuit in response to detecting said loop instruction during each of the initial and subsequent iterations of the loop, wherein an execution of said loop instruction decrements a value stored in a specified register at the time the detected loop instruction is executed, and wherein the execution of the detected loop instruction causes a branch unless said decremented value is equal to zero; a reorder buffer configured to convey an initial loop count in response to said initial indication, wherein said initial loop count is defined by a value stored in the specified register prior to execution of any loop containing the detected loop instruction; the loop prediction circuit coupled to receive said initial and subsequent indications from said loop detection circuit and said initial loop count from said reorder buffer, and wherein said loop prediction circuit is configured to increment a counter value and compare said counter value to said initial loop count upon receiving said initial and subsequent indications to determine whether a difference between the incremented counter value and the initial loop count is a given value, wherein said given value is determined as a function of a number of instructions in the loop and a number of pipeline stages prior to said loop prediction unit, and wherein said loop prediction circuit is further configured to signal a not-taken prediction for said detected loop instruction in response to determining the difference between said incremented counter value and said initial loop count is the given value.
Claim 10
Independent Claim
304 words
An apparatus for predicting a loop instruction, comprising: a loop detection circuit configured to detect said loop instruction during each of an initial and subsequent iterations of a loop defined by said loop instruction, wherein the loop detection circuit is configured to convey initial and subsequent indications of the detected loop instruction to a loop prediction circuit in response to detecting said loop instruction during each of the initial and subsequent iterations of the loop, wherein an execution of said loop instruction decrements a value stored in a specified register at the time the detected loop instruction is executed, and wherein the execution of the detected loop instruction causes a branch unless said decremented value is equal to zero; a reorder buffer configured to convey an initial loop count in response to said initial indication, wherein said initial loop count is defined by a value stored in the specified register prior to execution of any loop containing the detected loop instruction; the loop prediction circuit coupled to receive said initial and subsequent indications from said loop detection circuit and said initial loop count from said reorder buffer, and wherein said loop prediction circuit is configured to increment a counter value and compare said counter value to said initial loop count upon receiving said initial and subsequent indications to determine whether a difference between the incremented counter value and the initial loop count is a given value, wherein said given value is determined as a function of a number of instructions in the loop and a number of pipeline stages prior to said loop prediction unit, and wherein said loop prediction circuit is further configured to signal a not-taken prediction for said detected loop instruction in response to determining the difference between said incremented counter value and said initial loop count is the given value.
Claim 11
Dependent Claim
18 words
The apparatus for predicting a loop instruction as recited in claim 8, wherein said given value is one.
Claim 12
Dependent Claim
39 words
The apparatus for predicting a loop instruction as recited in claim 8, wherein said loop detection circuit is located within a decode unit, and wherein said detecting said loop instruction is performed by a decode of said loop instruction.
Claim 13
Dependent Claim
44 words
The apparatus for predicting a loop instruction as recited in claim 8 wherein said loop prediction unit is further configured to reset said counter value in response to a subsequent indication received during a last of said one or more iterations of said loop.
Claim 14
Dependent Claim
43 words
The apparatus for predicting a loop instruction as recited in claim 8 wherein said initial loop count is stored on an initial loop count stack, wherein said initial loop count stack includes initial loop counts corresponding to other loops which are in execution.
Claim 15
Dependent Claim
39 words
The apparatus for predicting a loop instruction as recited in claim 12 wherein said counter value is stored on a counter value stack, wherein said counter value stack includes counter values corresponding to other loops which are in execution.
Claim 16
Dependent Claim
210 words
A superscalar microprocessor, comprising: a branch prediction unit configured to predict a loop instruction; a loop detection circuit coupled to receive said loop instruction from an instruction cache and configured to convey an indication thereof; a reorder buffer configured to convey an initial loop count in response to receiving said initial indication conveyed by said loop detection circuit, wherein said initial loop count comprises a value stored in a specified register prior to any iteration of a loop containing the detected loop instruction; a loop prediction circuit coupled to receive said initial loop count from said reorder buffer and said initial and subsequent indications from said loop detection circuit, wherein said loop prediction circuit is configured to increment a counter value and compare said counter value to said initial loop count each time the initial or subsequent indication is received, and wherein said loop prediction unit is further configured to convey a not-taken indication to said branch prediction unit for said detected loop instruction in response to said counter value being less than said initial loop count by a given value, wherein said given value is determined as a function of a number of instructions in the loop and a number of pipeline stages prior to said loop prediction unit.
Claim 17
Dependent Claim
210 words
A superscalar microprocessor, comprising: a branch prediction unit configured to predict a loop instruction; a loop detection circuit coupled to receive said loop instruction from an instruction cache and configured to convey an indication thereof; a reorder buffer configured to convey an initial loop count in response to receiving said initial indication conveyed by said loop detection circuit, wherein said initial loop count comprises a value stored in a specified register prior to any iteration of a loop containing the detected loop instruction; a loop prediction circuit coupled to receive said initial loop count from said reorder buffer and said initial and subsequent indications from said loop detection circuit, wherein said loop prediction circuit is configured to increment a counter value and compare said counter value to said initial loop count each time the initial or subsequent indication is received, and wherein said loop prediction unit is further configured to convey a not-taken indication to said branch prediction unit for said detected loop instruction in response to said counter value being less than said initial loop count by a given value, wherein said given value is determined as a function of a number of instructions in the loop and a number of pipeline stages prior to said loop prediction unit.
Claim 18
Dependent Claim
14 words
A superscalar microprocessor as recited in claim 14 wherein said given value is one.
Claim 19
Dependent Claim
36 words
The superscalar microprocessor as recited in claim 14, wherein said loop detection unit is located within a decode unit, and wherein said detecting said loop instruction is performed by a decode of said detected loop instruction.
Claim 20
Dependent Claim
32 words
The superscalar microprocessor as recited in claim 14 wherein branch prediction unit predicts a taken outcome for said detected loop instruction unless said not-taken indication is conveyed from said loop prediction circuit.
Claim 21
Dependent Claim
35 words
The superscalar microprocessor as recited in claim 14 wherein said compare value is stored on a compare value stack, wherein said compare value stack includes compare values corresponding to other loops which are in execution.
Claim 22
Dependent Claim
35 words
The superscalar microprocessor as recited in claim 18 wherein said counter value is stored on a counter value stack, wherein said counter value stack includes counter values corresponding to other loops which are in execution.
References Cited (Backward Citations)
US4044338A
Cited
US4453212A
Cited
US4928223A
Cited
US4807115A
Cited
US4764861A
Cited
US4858105A
Cited
EP0259095A2
Cited
EP0381471A2
Cited
US5101484A
Cited
US5226126A
Cited
US5129067A
Cited
US5136697A
Cited
US5226130A
Cited
US5058048A
Cited
US5053631A
Cited
EP0459232A2
Cited
US5303355A
Cited
GB2263987A
Cited
GB2263985A
Cited
US5421020A
Cited
GB2281422A
Cited
US5404473A
Cited
US5764970A
Cited
US5646974A
Cited
US5909573A
Cited
US5752015A
Cited
US5774711A
Cited
US5784607A
Cited
US5740419A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-12-13 | 2003-06-14 | 2003-12-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-12-13 | 2007-06-14 | 2007-12-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-12-13 | 2011-06-14 | 2011-12-14 | $7700.00 | Window Closed / Lapsed |