Method and apparatus for scheduling instructions in waves

An apparatus for scheduling instructions for dispatch to an execution unit, comprising:

• a waiting buffer adapted to receive a plurality of instructions;
• a dependency matrix adapted to receive a plurality of dependency vectors associated with the instructions received in said waiting buffer, wherein each dependency vector has a bit set that indicates each instruction on which the instruction is dependent;
• a zero detect circuit coupled to said dependency matrix and adapted to deliver a wave vector indicative of an absence of bits being set in each dependency vector, said wave vector being delivered to a clear input of said dependency matrix to clear the bits set in each of said dependency vectors indicating a dependency on the instructions identified in the wave vector;
• port assignment logic coupled to said zero detect circuit and adapted to receive said wave vector, determine the instructions identified in said wave vector that are currently executable, and provide a dispatch wave vector indicative of the instructions that are currently executable;
• and
• an incomplete wave detector coupled to said port assignment logic and adapted to compare said wave vector and said dispatch wave vector, controllably deliver the output of the zero detect circuit as the next wave vector in response to detecting a match, and deliver an incomplete wave vector as the next wave vector in response to the wave vector and dispatch wave vector not matching.

An apparatus for scheduling instructions for dispatch to an execution unit in waves, comprising:

• means for receiving a plurality of instructions;
• means for determining dependencies for received instructions by use of dependency vectors associated with the instructions, wherein each dependency vector has a bit set that indicates each instruction on which the instruction is dependent;
• means for generating a wave vector indicative of instructions ready for execution by identifying each instruction that has no bits set in its corresponding dependency vector;
• means for clearing the bits in each dependency vector that correspond to the instructions ready for execution;
• and
• means for scheduling and dispatching instructions in a series of waves in relation to the wave vector and not accepting a next wave of instructions until a previous group of instructions has been dispatched.

An apparatus for scheduling instructions for dispatch, comprising:

• a buffer to store a plurality of instructions;
• a dependency matrix to store a plurality of dependency vectors, each dependency vector to indicate dependencies of one instruction in the buffer, a component of the dependency vector being set to a first logic value to indicate a dependency on an instruction corresponding to the component;
• a zero detect circuit to generate a wave vector of ready instructions in response to finding one or more dependency vectors without components set to the first logic value, the dependency matrix to clear a particular component of the stored dependency vectors in response to the instruction corresponding to the particular component being dispatched for execution, and
• a port assignment unit coupled to said zero detect circuit to receive said wave vector and to provide a dispatch wave vector comprising a portion of the instructions from the wave vector to dispatch for execution.