US 5,317,701 AGranted

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

AssigneeMotorola, Inc.

InventorsRussell Reininger, William B. Ledbetter, Jr.

Life of this patent

Estimating the term…

Loading patent…

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.

Claims11

Dependent claims

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.

6 more elements

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.

5 more elements

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.

8 more elements

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.

6 more elements

Dependencies are inferred from the claim text.

Facts

Application: 08/005,924Filed 19 Jan 1993 · continuation
Priority: 2 Jan 1990
Granted: 31 May 1994
Term ends: Not estimatedThe source records don’t support an estimate.

Classification5 codes

G06F 9/3814
Instruction prefetching: implementation provisions of instruction buffers, e.g. prefetch buffer; banks
G06F 9/30149
Instruction analysis, e.g. decoding, instruction word fields: of variable length instructions
G06F 9/3802
Concurrent instruction execution, e.g. pipeline or look ahead: instruction prefetching
G06F 9/3816
Instruction prefetching: instruction alignment, e.g. cache line crossing