Method and Apparatus for Scheduling of Instructions in a Multi-Strand Out-Of-Order Processor

Abstract

In accordance with embodiments disclosed herein, there are provided methods, systems, and apparatuses for scheduling instructions in a multi-strand out-of-order processor. For example, an apparatus for scheduling instructions in a multi-strand out-of-order processor includes an out-of-order instruction fetch unit to retrieve a plurality of interdependent instructions for execution from a multi-strand representation of a sequential program listing; an instruction scheduling unit to schedule the execution of the plurality of interdependent instructions based at least in part on operand synchronization bits encoded within each of the plurality of interdependent instructions; and a plurality of execution units to execute at least a subset of the plurality of interdependent instructions in parallel.

What is claimed is: 
     
         1 . A system comprising:
 a display;   a binary translator to generate a multi-strand representation of a sequential program listing, the generated multi-strand representation having a plurality of interdependent strands, each of the plurality of interdependent strands comprising operand synchronization bits;   an out-of-order instruction fetch unit to retrieve the plurality of interdependent strands for execution; and   an instruction scheduling unit to schedule the execution of the plurality of interdependent strands based at least in part on the operand synchronization bits.   
     
     
         2 . The system of  claim 1 , wherein each of the plurality of interdependent strands comprises an instruction format specifying at least:
 opcode;   an address for a first source operand;   a synchronization bit for the first source operand;   an address for a second source operand;   a synchronization bit for the second source operand;   an address for a destination operand; and   a synchronization bit for the destination operand.   
     
     
         3 . The system of  claim 1 , wherein the binary translator generates and encodes the synchronization bits into each of the plurality of interdependent strands at compile time. 
     
     
         4 . The system of  claim 1 , wherein one or more of the plurality of interdependent strands encodes a data anti-dependency between a first instruction using a value and a second instruction updating the value with a new value. 
     
     
         5 . The system of  claim 4 , wherein the value is stored by a register and wherein the new value is updated to the register. 
     
     
         6 . The system of  claim 4 , wherein the binary translator is to:
 set one of the operand synchronization bits in one of the plurality of interdependent strands to indicate a producer source operand represents a last use of a data item causing an anti-dependency;   set one of the operand synchronization bits in a second one of the plurality of interdependent strands to indicate a consumer destination operand must wait until all uses of the data item are completed; and   wherein the instruction scheduling unit to execute the consumer destination operand after the producer source operand based on the set operand synchronization bits.   
     
     
         7 . The system of  claim 1 , wherein the binary translator enforces a plurality of rules to guarantee correct scheduling of the plurality of interdependent strands via the instruction scheduling unit, the plurality of rules comprising:
 a first rule prohibiting race conditions among instructions belonging to different strands producing a same destination register;   a second rule prohibiting race conditions among instructions belonging to different strands reading a same source register with a synchronization bit; and   a third rule prohibiting any instruction from having a same source and destination operand addresses, each with a synchronization bit.