Instruction dependency chain indentifier

Claim 2

Apparatus for identifying instruction dependencies comprising: a bit array of i lines, where i is an integer, each line representing an instruction in a sequence of instructions and comprising a string of bits in which a bit position is set corresponding to a preceding instruction on which the instruction is dependent, and wherein the bit array is triangular with a first line having a single bit position in the ith line having l bit positions; logic means coupled to the bit array for generating the string of bits for a next instruction stored in the ith line of the bit array, the logic means shifting the string of bits in each line of the bit array by one line and by one bit position, and generating the string of bits for the next instruction by setting bit positions which correspond to directly dependent instructions as well as additional bit positions corresponding to indirectly dependent instructions, the logic means including means for performing a logical bitwise OR operation between the string of bits of the lines corresponding to the directly dependent instructions, a result of the logical bitwise OR operation being written to corresponding bit positions of the ith line.

Claim 3

The apparatus of claim 1 wherein the means for performing the logical bitwise OR operation comprises an AND/OR logic structure.

Claim 4

In an out-of-order computing system, a method of operation comprising the steps of: (a) decoding an in-order sequence of instructions; (b) checking data dependencies for each instruction of the in-order sequence; (c) generating an instruction dependency matrix which identifies both direct and indirect dependencies for a set of instructions of the in-order sequence, the set of instructions including l instructions and where the matrix includes a triangular storage structure having l lines, an ith line corresponding to an ith instruction of the in-order sequence, the ith line having l bit positions in which a jth bit position is set corresponding to the jth instruction on which the ith instruction is dependent, where l and j are integers, for an ith instruction of the in-order sequence, the generating step further including the steps of: shifting the bit positions in each line of the matrix up by one line, and to the left by one bit position, thereby vacating the ith line; setting, in the ith line, bit positions corresponding to instructions on which the ith instruction is directly dependent, thereby producing a first string of bits for the ith line; performing a logical bitwise OR operation on the lines that correspond to the directly dependent instructions to produce a second string of bits; performing a logical bitwise OR operation on the first and second string of bits, the results for each bit position being stored in the corresponding bit position of the ith line; (d) scheduling execution of each instruction of the sequence in an optimum order based, at least in part, on the instruction dependency matrix wherein the optimum order differs from the in-order sequence.

Claim 5

In an out-of-order computing system, a method of operation comprising the steps of: (a) decoding an in-order sequence of instructions; (b) checking data dependencies for each instruction of the in-order sequence; (c) generating an instruction dependency matrix which identifies both direct and indirect dependencies for a set of instructions of the in-order sequence, the set of instructions including l instructions and where the matrix includes a triangular storage structure having l lines, an ith line corresponding to an ith instruction of the in-order sequence, the ith line having l bit positions in which a jth bit position is set corresponding to the jth instruction on which the ith instruction is dependent, where l and j are integers, for an ith instruction of the in-order sequence, the generating step further including the steps of: shifting the bit positions in each line of the matrix up by one line, and to the left by one bit position, thereby vacating the ith line; setting, in the ith line, bit positions corresponding to instructions on which the ith instruction is directly dependent, thereby producing a first string of bits for the ith line; performing a logical bitwise OR operation on the lines that correspond to the directly dependent instructions to produce a second string of bits; performing a logical bitwise OR operation on the first and second string of bits, the results for each bit position being stored in the corresponding bit position of the ith line; (d) scheduling execution of each instruction of the sequence in an optimum order based, at least in part, on the instruction dependency matrix wherein the optimum order differs from the in-order sequence.

Claim 6

The method of claim 3 wherein the set of instructions includes all instructions in the in-order sequence.

Claim 7

The method of claim 3 wherein the set of instructions comprises a subset of the in-order sequence.

Claim 10

The method of claim 6 wherein the storage structure has i lines, a kth line having k bit positions where k is an integer ranging from 1 to i.

Claim 11

The method of claim 7 wherein the ith line is at the bottom of the storage structure and the jth bit in the ith line corresponds to the (j-1)th instruction.