Rescheduling conflicting issued instructions by delaying one conflicting instruction into the same pipeline stage as a third non-conflicting instruction

Claim 1

A pipeline controller for a computer system having an instruction pipeline containing a plurality of types of multiple stage issued instructions, having variable execution latencies, and requiring particular computer resources at different stages of execution, the controller comprising: pipeline monitoring means coupled to the instruction pipeline for detecting the types and stages of execution of issued instructions in the pipeline; conflict detector means coupled to the pipeline monitoring means for detecting when two issued instructions in the pipeline will require a given computer resource in a same stage at some future time; and rescheduler means coupled to both the conflict detector means and to the instruction pipeline for rescheduling one of said two issued instructions which will be in the same stage at some future time, said rescheduler means including means for detecting when a third issued instruction will not require said given computer resource in said same stage at some other future time, and means for enabling the rescheduled one of said two issued instructions and said third issued instruction to continue execution such that the rescheduled one of said two issued instructions has exclusive access to said computer resource at said other future time when both said third issued instruction and the rescheduled one of said two issued instructions are in the same stage of execution in the instruction pipeline.

Claim 6

A method for controlling execution of issued instructions in a computer, having an instruction pipeline for receiving a plurality of multi-stage instructions, having variable execution latencies, and a plurality of computer resources, the method comprising the steps of; (a) monitoring each issued instruction in the instruction pipeline; (b) determining what computer resources are needed for each issued instruction and the stages at which the needed resources will be required by each instruction; (c) detecting when two different issued instructions will require one identical resource at a same time; (d) rescheduling one of the two issued instructions so that the identical resource will no longer be required at the same time by the two issued instructions; (e) detecting when a third issued instruction will not require said identical resource during a given stage of said third issued instruction; and (f) enabling the rescheduled one of said two issued instructions and said third issued instruction to continue execution such that the rescheduled one of said two issued instructions has exclusive access to said computer resource at said other future time when both said third issued instruction and the rescheduled one of said two issued instructions are in the same stage of execution in the instruction pipeline.

Claim 7

A method for controlling execution of issued instructions in a computer, having an instruction pipeline for receiving a plurality of multi-stage instructions, having variable execution latencies, and a plurality of computer resources, the method comprising the steps of; (a) monitoring each issued instruction in the instruction pipeline; (b) determining what computer resources are needed for each issued instruction and the stages at which the needed resources will be required by each instruction; (c) detecting when two different issued instructions will require one identical resource at a same time; (d) rescheduling one of the two issued instructions so that the identical resource will no longer be required at the same time by the two issued instructions; (e) detecting when a third issued instruction will not require said identical resource during a given stage of said third issued instruction; and (f) enabling the rescheduled one of said two issued instructions and said third issued instruction to continue execution such that the rescheduled one of said two issued instructions has exclusive access to said computer resource at said other future time when both said third issued instruction and the rescheduled one of said two issued instructions are in the same stage of execution in the instruction pipeline.

Claim 10

A method for optimizing the operation of a multi-stage instruction pipeline for receiving multi-stage instructions in a computer having a processor with an internal data path and a memory bus, the instructions in the pipeline requiring different amounts of data, the processor data path having a first data width, and the memory bus having a second, smaller data width, the method comprising the steps of: monitoring the instructions in the pipeline and the processor; monitoring the amount of data required by each instruction; detecting whether the amount of data required by a given instruction can be accommodated by the memory bus in a preset amount of time; ordering the processor to read the data in successive stages of said pipeline over a total time equal to a multiple of the preset amount of time if the memory bus cannot accommodate all of the data required by a given instruction in said preset amount of time, and permitting said given instruction to proceed to a next stage in the instruction pipeline after the first read operation; and allowing a new instruction to enter said pipeline in the stage from which said given instruction proceeded.

Claim 11

A method for optimizing the operation of a multi-stage instruction pipeline for receiving multi-stage instructions in a computer having a processor with an internal data path and a memory bus, the instructions in the pipeline requiring different amounts of data, the processor data path having a first data width, and the memory bus having a second, smaller data width, the method comprising the steps of: monitoring the instructions in the pipeline and the processor; monitoring the amount of data required by each instruction; detecting whether the amount of data required by a given instruction can be accommodated by the memory bus in a preset amount of time; ordering the processor to read the data in successive stages of said pipeline over a total time equal to a multiple of the preset amount of time if the memory bus cannot accommodate all of the data required by a given instruction in said preset amount of time, and permitting said given instruction to proceed to a next stage in the instruction pipeline after the first read operation; and allowing a new instruction to enter said pipeline in the stage from which said given instruction proceeded.

Claim 17

A method of varying a progression of instructions through an instruction pipeline having a plurality of stages in a data processing system having a flow path having a plurality of stages, a register file, an input data bus and a plurality of bypass multiplexers interconnecting predetermined data stages in the data flow path and having a known processing cycle, said instructions including a first instruction type requiring operands having a first data width and a second instruction type requiring operands having a second data width wider than said first data width, said method comprising the steps of: A. introducing a first instruction into a given stage in the instruction pipeline; B. determining the type of instruction; C. for an instruction of the first type, proceeding by: (I) making at least one operand required by the instruction of the first type available; (II) determining whether each operand required by the instruction of the first type is available from said register file or from a subsequent stage of the pipeline via one of said plurality of bypass multiplexers; (a) if so, reading each operand required and permitting the instruction to proceed to a next stage in the instruction pipeline for further processing; (b) if not, holding the instruction in the given stage for at least one processing cycle and repeating steps (I) and (II); D. for an instruction of the second type, proceeding by: (III) making at least part of each operand required by the instruction of the second type available, each operand required by the second type of instruction having a first and a second half; (IV) determining whether the first and second halves of each operand are available from said register file or from a subsequent stage of the pipeline via one of said plurality of bypass multiplexers; (c) if so, reading each operand required and permitting the instruction to proceed to the next stage in the instruction pipeline for further processing; (d) if not, determining whether the first half of each operand required is available from said register file or from a subsequent stage of the pipeline via one of said plurality of bypass multiplexers: (i) if so, reading the first half of each operand required and permitting the instruction to proceed to the next stage in the instruction pipeline and proceeding to step (aa); (ii) if not, holding the instruction in the given stage for at least one processing cycle and repeating step (d); (aa) determining whether the second half of each operand required is available from said register file or from a subsequent stage of the pipeline via one of said plurality of bypass multiplexers; (x) if so, reading the second half of each operand required and permitting further processing of the instruction; (y) if not, holding the instruction in the next stage for at least one processing cycle and repeating step (aa).

Claim 18

A method of varying a progression of instructions through an instruction pipeline having a plurality of stages in a data processing system having a flow path having a plurality of stages, a register file, an input data bus and a plurality of bypass multiplexers interconnecting predetermined data stages in the data flow path and having a known processing cycle, said instructions including a first instruction type requiring operands having a first data width and a second instruction type requiring operands having a second data width wider than said first data width, said method comprising the steps of: A. introducing a first instruction into a given stage in the instruction pipeline; B. determining the type of instruction; C. for an instruction of the first type, proceeding by: (I) making at least one operand required by the instruction of the first type available; (II) determining whether each operand required by the instruction of the first type is available from said register file or from a subsequent stage of the pipeline via one of said plurality of bypass multiplexers; (a) if so, reading each operand required and permitting the instruction to proceed to a next stage in the instruction pipeline for further processing; (b) if not, holding the instruction in the given stage for at least one processing cycle and repeating steps (I) and (II); D. for an instruction of the second type, proceeding by: (III) making at least part of each operand required by the instruction of the second type available, each operand required by the second type of instruction having a first and a second half; (IV) determining whether the first and second halves of each operand are available from said register file or from a subsequent stage of the pipeline via one of said plurality of bypass multiplexers; (c) if so, reading each operand required and permitting the instruction to proceed to the next stage in the instruction pipeline for further processing; (d) if not, determining whether the first half of each operand required is available from said register file or from a subsequent stage of the pipeline via one of said plurality of bypass multiplexers: (i) if so, reading the first half of each operand required and permitting the instruction to proceed to the next stage in the instruction pipeline and proceeding to step (aa); (ii) if not, holding the instruction in the given stage for at least one processing cycle and repeating step (d); (aa) determining whether the second half of each operand required is available from said register file or from a subsequent stage of the pipeline via one of said plurality of bypass multiplexers; (x) if so, reading the second half of each operand required and permitting further processing of the instruction; (y) if not, holding the instruction in the next stage for at least one processing cycle and repeating step (aa).

Claim 21

A method for controlling execution of issued instructions, having variable execution latencies, in a data processing system having an instruction pipeline with a plurality of stages for temporarily holding issued instructions identifying data processing operations, said data processing system having at least one data processing element to which access is required by at least two of said issued instructions, said method comprising the steps of: (a) monitoring the issued instructions in various stages in the pipeline; (b) determining whether two issued instructions in the pipeline will require contemporaneous access to an identical data processing element when each issued instruction is in an identical later stage in the instruction pipeline; (c) temporarily holding one of said two issued instructions in a current stage in the instruction pipeline in response to the determining step (b); (d) detecting another issued instruction which will not require contemporaneous access to said identical data processing element when in said identical later stage in the instruction pipeline; and (e) permitting the held instruction and said other issued instruction to continue execution such that the held issued instruction has exclusive access to said computer resource at said other future time when both the held issued instruction and said other issued instruction are in the same stage of execution in the instruction pipeline to proceed to a next stage in the pipeline in response to the detecting step (d).

Claim 22

A method for controlling execution of issued instructions, having variable execution latencies, in a data processing system having an instruction pipeline with a plurality of stages for temporarily holding issued instructions identifying data processing operations, said data processing system having at least one data processing element to which access is required by at least two of said issued instructions, said method comprising the steps of: (a) monitoring the issued instructions in various stages in the pipeline; (b) determining whether two issued instructions in the pipeline will require contemporaneous access to an identical data processing element when each issued instruction is in an identical later stage in the instruction pipeline; (c) temporarily holding one of said two issued instructions in a current stage in the instruction pipeline in response to the determining step (b); (d) detecting another issued instruction which will not require contemporaneous access to said identical data processing element when in said identical later stage in the instruction pipeline; and (e) permitting the held instruction and said other issued instruction to continue execution such that the held issued instruction has exclusive access to said computer resource at said other future time when both the held issued instruction and said other issued instruction are in the same stage of execution in the instruction pipeline to proceed to a next stage in the pipeline in response to the detecting step (d).