Instruction dependency chain indentifier

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.