Patent US5317701A successfully refreshed from Google Patents.
US5317701A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for refilling instruction queue by reading predetermined number of instruction words comprising one or more instructions and determining the actual number of instruction words used
Assignee: Robert Bosch GmbH
•
Filing: 1993-01-19
•
Granted: 1994-05-31
•
Expires: 2013-01-19
Abstract
Abstract A sequential prefetch method is provided for a pipelined data processor having a sequential instruction prefetch unit (IPU). An instruction queue in the IPU is coupled to a pipelined instruction unit and an instruction cache of the data processor. A prefetch controller in the IPU keeps the instruction stream prefetched so that the instruction queue may load any combination of one, two, or three word instructions into the pipelined instruction unit every clock cycle. The pipelined instruction unit receives instruction words from the instruction queue, and decodes the instruction for execution operations, and for the instruction length/pipeline movement. A queue filling method is provided for maintaining the requisite number of instruction words in the instruction queue to avoid pipeline stalls. The queue filling method is based upon the movement of the instruction pipeline attributable to the usage by an instruction sequencer of the instruction words received from the instruction queue.
Inventors
- 👤 Russell Reininger
- 👤 William B. Ledbetter, Jr.
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 12:58
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3802; G06F9/3814; A; A47; A47L; A47L11/00; G06F9/30145; G06F9/30149; G06F9/3816
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
460 words
In a data processor having a prefetch controller for prefetching a sequence of instructions from a memory, where each instruction in said sequence of instructions is comprised of a variable number of instruction words, said prefetch controller being coupled to said memory for loading a predetermined number of instruction words from said sequence of instructions into an instruction queue, said instruction queue having a predetermined number of buffers, each buffer having a predetermined n-word instruction boundary for storing a set of n instruction words retrieved from said memory, where n is an integer, a method for filling said instruction queue based upon movement of said predetermined number of instruction words within a pipelined instruction unit, said method comprising the steps of: loading said pipelined instruction unit, with a first set of instruction words comprising one or more instructions from a first sequence of instructions, said first set of instruction words being selected from said instruction queue, in response to a first control signal provided to said instruction queue by a queue pointer in said prefetch controller, during a first part of a machine cycle; decoding, via said pipelined instruction unit, said first set of instruction words to determine a word length of a first instruction in said first set of instruction words, said word length corresponding in value to an amount of movement of said pipelined instruction unit occurring as a result of loading said first set of instruction words; providing, via said pipelined instruction unit, a second control signal to said prefetch controller, during a second part of said machine cycle, said second control signal indicating said word length of said first instruction; incrementing a current value of said queue pointer by an amount corresponding in value to said amount of movement of said pipelined instruction unit, in response to said prefetch controller receiving said second control signal, said queue pointer thereafter pointing to a second set of instruction words comprising one or more instructions stored in said instruction queue, to be subsequently loaded into said pipelined instruction unit; and retrieving a next sequence of instructions from said memory to refill said instruction queue, if any one of the following conditions are met: the current value of the queue pointer combined with the amount of movement of said pipelined instruction unit occurring as the result of loading said first set of instruction words points to a last instruction word in one of said predetermined number of buffers, in said instruction queue; or the current value of the queue pointer combined with the amount of movement of said pipelined instruction unit occurring as the result of loading said first set of instruction words crosses said n-word instruction boundary of one of said predetermined number of buffers in said instruction queue.
Claim 2
Dependent Claim
460 words
In a data processor having a prefetch controller for prefetching a sequence of instructions from a memory, where each instruction in said sequence of instructions is comprised of a variable number of instruction words, said prefetch controller being coupled to said memory for loading a predetermined number of instruction words from said sequence of instructions into an instruction queue, said instruction queue having a predetermined number of buffers, each buffer having a predetermined n-word instruction boundary for storing a set of n instruction words retrieved from said memory, where n is an integer, a method for filling said instruction queue based upon movement of said predetermined number of instruction words within a pipelined instruction unit, said method comprising the steps of: loading said pipelined instruction unit, with a first set of instruction words comprising one or more instructions from a first sequence of instructions, said first set of instruction words being selected from said instruction queue, in response to a first control signal provided to said instruction queue by a queue pointer in said prefetch controller, during a first part of a machine cycle; decoding, via said pipelined instruction unit, said first set of instruction words to determine a word length of a first instruction in said first set of instruction words, said word length corresponding in value to an amount of movement of said pipelined instruction unit occurring as a result of loading said first set of instruction words; providing, via said pipelined instruction unit, a second control signal to said prefetch controller, during a second part of said machine cycle, said second control signal indicating said word length of said first instruction; incrementing a current value of said queue pointer by an amount corresponding in value to said amount of movement of said pipelined instruction unit, in response to said prefetch controller receiving said second control signal, said queue pointer thereafter pointing to a second set of instruction words comprising one or more instructions stored in said instruction queue, to be subsequently loaded into said pipelined instruction unit; and retrieving a next sequence of instructions from said memory to refill said instruction queue, if any one of the following conditions are met: the current value of the queue pointer combined with the amount of movement of said pipelined instruction unit occurring as the result of loading said first set of instruction words points to a last instruction word in one of said predetermined number of buffers, in said instruction queue; or the current value of the queue pointer combined with the amount of movement of said pipelined instruction unit occurring as the result of loading said first set of instruction words crosses said n-word instruction boundary of one of said predetermined number of buffers in said instruction queue.
Claim 3
Dependent Claim
41 words
The queue filling method according to claim 1 further comprising the step of transferring said second set of instruction words in said instruction queue to said pipelined instruction unit, after incrementing said current value of queue pointer in said prefetch controller.
Claim 4
Dependent Claim
83 words
The queue filling method according to claim 2 further comprising the step of providing, via said pipelined instruction unit, a third control signal to said prefetch controller, after decoding said first set of instruction words, said third control being provided to said prefetch controller if said first instruction in said first set of instructions words is a change of flow instruction, said prefetch controller initiating a required number of instruction prefetch cycles, in response thereto, as part of said change of flow instruction.
Claim 5
Dependent Claim
368 words
In a data processor having a prefetch controller for prefetching a plurality of instruction words from a memory, for storage in an instruction queue, said instruction queue having a predetermined number of buffers, each buffer having a predetermined n-word instruction boundary for storing a set of n instruction words retrieved from said memory, where n is an integer, and for providing a predetermined number of instruction words comprising one or more instructions from said instruction queue to a pipelined instruction unit, a method for filling the instruction queue, based upon an amount of movement of said pipelined instruction unit occurring as a result of loading said predetermined number of instruction words, the method comprising the steps of: decoding, via said pipelined instruction unit, a first sequence of said predetermined number of instruction words resident in said pipelined instruction unit to determine the amount of movement of said pipelined instruction unit, said amount of movement corresponding in value to a number of said first sequence of instruction words used by said pipelined instruction unit during a first part of a machine cycle; incrementing a current value of a queue pointer in said prefetch controller, by an amount corresponding in value to the amount of movement of said pipelined instruction unit, in response to said prefetch controller receiving a first control signal from said pipelined instruction unit during a second part of said machine cycle, said first control signal indicating the amount of movement of said pipelined instruction unit; and retrieving a next sequence of instruction words from said memory to refill said instruction queue, if any one of the following conditions are met: the current value of the queue pointer combined with the amount of movement of said pipelined instruction unit occurring as the result of loading said first sequence of instruction words points to a last instruction word in one of said predetermined number of buffers in said instruction queue; or the current value of the queue pointer combined with the amount of movement of said pipelined instruction unit occurring as the result of loading said first sequence of instruction words crosses the n-word instruction boundary of one of said predetermined number of buffers in said instruction queue.
Claim 6
Dependent Claim
368 words
In a data processor having a prefetch controller for prefetching a plurality of instruction words from a memory, for storage in an instruction queue, said instruction queue having a predetermined number of buffers, each buffer having a predetermined n-word instruction boundary for storing a set of n instruction words retrieved from said memory, where n is an integer, and for providing a predetermined number of instruction words comprising one or more instructions from said instruction queue to a pipelined instruction unit, a method for filling the instruction queue, based upon an amount of movement of said pipelined instruction unit occurring as a result of loading said predetermined number of instruction words, the method comprising the steps of: decoding, via said pipelined instruction unit, a first sequence of said predetermined number of instruction words resident in said pipelined instruction unit to determine the amount of movement of said pipelined instruction unit, said amount of movement corresponding in value to a number of said first sequence of instruction words used by said pipelined instruction unit during a first part of a machine cycle; incrementing a current value of a queue pointer in said prefetch controller, by an amount corresponding in value to the amount of movement of said pipelined instruction unit, in response to said prefetch controller receiving a first control signal from said pipelined instruction unit during a second part of said machine cycle, said first control signal indicating the amount of movement of said pipelined instruction unit; and retrieving a next sequence of instruction words from said memory to refill said instruction queue, if any one of the following conditions are met: the current value of the queue pointer combined with the amount of movement of said pipelined instruction unit occurring as the result of loading said first sequence of instruction words points to a last instruction word in one of said predetermined number of buffers in said instruction queue; or the current value of the queue pointer combined with the amount of movement of said pipelined instruction unit occurring as the result of loading said first sequence of instruction words crosses the n-word instruction boundary of one of said predetermined number of buffers in said instruction queue.
Claim 7
Dependent Claim
92 words
The method for filling an instruction queue according to claim 4 further comprising the step of providing, via said pipelined instruction unit, a second control signal to said prefetch controller, after decoding said first sequence instructions words resident in said pipelined instruction unit, said second control signal being provided to said prefetch controller if a first instruction in said first sequence of instructions words is a change of flow instruction, said prefetch controller initiating a required number of instruction prefetch cycles, in response thereto, as part of said change of flow instruction.
Claim 8
Dependent Claim
409 words
In a data processor having a prefetch controller for prefetching a sequence of instructions of a variable word length from a memory, and for providing a predetermined number of instructions instruction words comprising one or more instructions from said sequence of instructions to an instruction queue, said instruction queue having a predetermined number of buffers having an n-word instruction boundary for storing a set of n instruction words retrieved from memory, where n is an integer, a method for filling said instruction queue based upon an amount of movement of instructions within a pipelined instruction unit in response to usage by said pipelined instruction unit of said predetermined number of instruction words, the method comprising the steps of: decoding said predetermined number of instruction words resident in said pipelined instruction unit, during a first part of a machine cycle, to determine the following: the word length of a current instruction; and the movement of said pipelined instruction unit occurring as a result of execution by said pipelined instruction unit of said current instruction resident in said pipelined instruction unit; providing, via said pipelined instruction unit, a first control signal to said prefetch controller indicating the amount of movement of said pipelined instruction unit occurring as the result of executing said current instruction, said amount of movement corresponding in value to the word length of said current instruction resident in said pipelined instruction unit; advancing a current value of a queue pointer in said prefetch controller to point to a next predetermined number of instruction words from said instruction queue, based upon the amount of movement of said pipelined instruction unit corresponding in value to the word length of said current instruction resident in said pipelined instruction unit, during a second part of said machine cycle; and retrieving a next sequence of instructions from said memory to refill said instruction queue if any one of the following conditions are met: the current value of the queue pointer combined with the amount of movement of said pipelined instruction unit occurring as the result of executing said current instruction points to a last instruction word in one of said predetermined number of buffers in said instruction queue; or the current value of the queue pointer combined with the amount of movement of said pipelined instruction unit occurring as the result of executing said current instruction crosses said n-word instruction boundary of one of said predetermined number of buffers in said instruction queue.
Claim 9
Dependent Claim
409 words
In a data processor having a prefetch controller for prefetching a sequence of instructions of a variable word length from a memory, and for providing a predetermined number of instructions instruction words comprising one or more instructions from said sequence of instructions to an instruction queue, said instruction queue having a predetermined number of buffers having an n-word instruction boundary for storing a set of n instruction words retrieved from memory, where n is an integer, a method for filling said instruction queue based upon an amount of movement of instructions within a pipelined instruction unit in response to usage by said pipelined instruction unit of said predetermined number of instruction words, the method comprising the steps of: decoding said predetermined number of instruction words resident in said pipelined instruction unit, during a first part of a machine cycle, to determine the following: the word length of a current instruction; and the movement of said pipelined instruction unit occurring as a result of execution by said pipelined instruction unit of said current instruction resident in said pipelined instruction unit; providing, via said pipelined instruction unit, a first control signal to said prefetch controller indicating the amount of movement of said pipelined instruction unit occurring as the result of executing said current instruction, said amount of movement corresponding in value to the word length of said current instruction resident in said pipelined instruction unit; advancing a current value of a queue pointer in said prefetch controller to point to a next predetermined number of instruction words from said instruction queue, based upon the amount of movement of said pipelined instruction unit corresponding in value to the word length of said current instruction resident in said pipelined instruction unit, during a second part of said machine cycle; and retrieving a next sequence of instructions from said memory to refill said instruction queue if any one of the following conditions are met: the current value of the queue pointer combined with the amount of movement of said pipelined instruction unit occurring as the result of executing said current instruction points to a last instruction word in one of said predetermined number of buffers in said instruction queue; or the current value of the queue pointer combined with the amount of movement of said pipelined instruction unit occurring as the result of executing said current instruction crosses said n-word instruction boundary of one of said predetermined number of buffers in said instruction queue.
Claim 10
Dependent Claim
42 words
The queue filling method according to claim 6 further comprising the step of loading said next predetermined number of instruction from said instruction queue into said pipelined instruction unit, after advancing said current value of the queue pointer in said prefetch controller.
Claim 11
Dependent Claim
80 words
The queue filling method according to claim 6 further comprising the step of providing, via said pipelined instruction unit, a second control signal to said prefetch controller, after decoding said current instruction resident in said pipelined instruction unit, said second control signal being provided to said prefetch controller if said current instruction is a change of flow instruction, said prefetch controller initiating a required number of instruction prefetch cycles, in response thereto, as part of said change of flow instruction.
Claim 12
Dependent Claim
356 words
In a data processor having a prefetch controller for prefetching a plurality of instruction words from a memory, for storage in an instruction queue, said instruction queue having a predetermined number of buffers, each buffer having a predetermined n-word instruction boundary for storing a set of n instruction words retrieved from said memory, where n is an integer, and for providing a predetermined number of instruction words comprising one or more instructions from said instruction queue to a pipelined instruction unit, a method for filling the instruction queue, based upon an amount of movement of said pipelined instruction unit occurring as a result of loading said predetermined number of instruction words, the method comprising the steps of: decoding, via said pipelined instruction unit, a first set of said predetermined number of instruction words resident in said pipelined instruction unit to determine the amount of movement of said pipelined instruction unit, said amount of movement corresponding in value to a number of words in a first instruction used by said pipelined instruction unit during a first part of a machine cycle; incrementing a current value of a queue pointer in said prefetch controller, by an amount corresponding in value to the amount of movement of said pipelined instruction unit, in response to said prefetch controller receiving a first control signal from said pipelined instruction unit during a second part of said machine cycle, said first control signal indicating the amount of movement of said pipelined instruction unit; selecting, from said instruction queue, a next set of said predetermined number of instruction words for loading into said pipelined instruction unit, during a subsequent clock cycle, based upon said incremented value of said queue pointer; and re-filling said instruction queue with a sequence of instruction words retrieved from said memory, if any one of the following conditions are met: the incremented value of the queue pointer points to a last instruction word in one of said predetermined number of buffers in said instruction queue; or the incremented value of the queue pointer crosses the n-word instruction boundary of one of said predetermined number of buffers in said instruction queue.
Claim 13
Dependent Claim
356 words
In a data processor having a prefetch controller for prefetching a plurality of instruction words from a memory, for storage in an instruction queue, said instruction queue having a predetermined number of buffers, each buffer having a predetermined n-word instruction boundary for storing a set of n instruction words retrieved from said memory, where n is an integer, and for providing a predetermined number of instruction words comprising one or more instructions from said instruction queue to a pipelined instruction unit, a method for filling the instruction queue, based upon an amount of movement of said pipelined instruction unit occurring as a result of loading said predetermined number of instruction words, the method comprising the steps of: decoding, via said pipelined instruction unit, a first set of said predetermined number of instruction words resident in said pipelined instruction unit to determine the amount of movement of said pipelined instruction unit, said amount of movement corresponding in value to a number of words in a first instruction used by said pipelined instruction unit during a first part of a machine cycle; incrementing a current value of a queue pointer in said prefetch controller, by an amount corresponding in value to the amount of movement of said pipelined instruction unit, in response to said prefetch controller receiving a first control signal from said pipelined instruction unit during a second part of said machine cycle, said first control signal indicating the amount of movement of said pipelined instruction unit; selecting, from said instruction queue, a next set of said predetermined number of instruction words for loading into said pipelined instruction unit, during a subsequent clock cycle, based upon said incremented value of said queue pointer; and re-filling said instruction queue with a sequence of instruction words retrieved from said memory, if any one of the following conditions are met: the incremented value of the queue pointer points to a last instruction word in one of said predetermined number of buffers in said instruction queue; or the incremented value of the queue pointer crosses the n-word instruction boundary of one of said predetermined number of buffers in said instruction queue.
Claim 14
Dependent Claim
65 words
The method for filling an instruction queue according to claim 9 further comprising the step of loading said pipelined instruction unit with said first set of said predetermined number of instruction words selected from said instruction queue, in response to said first control signal provided to said instruction queue by a queue pointer in said prefetch controller, during said first part of a machine cycle.
Claim 15
Dependent Claim
91 words
The method for filling an instruction queue according to claim 10 further comprising the step of providing, via said pipelined instruction unit, a second control signal to said prefetch controller, after decoding said first set of said predetermined number of instructions words resident in said pipelined instruction unit, said second control signal being provided to said prefetch controller if said first instruction is for a change of flow instruction, said prefetch controller initiating a required number of instruction prefetch cycles, in response thereto, as part of said change of flow instruction.
References Cited (Backward Citations)
US4200927A
Cited
US4516199A
Cited
US4747045A
Cited
US4847759A
Cited
US4714994A
Cited
US4791557A
Cited
US4796175A
Cited
US4912634A
Cited
US5113515A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-05-30 | 1997-11-29 | 1998-05-31 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-05-30 | 2001-11-29 | 2002-05-31 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-05-30 | 2005-11-29 | 2006-05-31 | $7700.00 | Window Closed / Lapsed |