Instruction execution based on outstanding load operations

Abstract

One embodiment of the present invention sets forth a technique for scheduling thread execution in a multi-threaded processing environment. A two-level scheduler maintains a small set of active threads called strands to hide function unit pipeline latency and local memory access latency. The strands are a sub-set of a larger set of pending threads that is also maintained by the two-leveler scheduler. Pending threads are promoted to strands and strands are demoted to pending threads based on latency characteristics, such as whether outstanding load operations have been executed. The longer latency of the pending threads is hidden by selecting strands for execution. When the latency for a pending thread is expired, the pending thread may be promoted to a strand and begin (or resume) execution. When a strand encounters a latency event, the strand may be demoted to a pending thread while the latency is incurred.

1 . A method for executing dependent program instructions, the method comprising:
 receiving a first instruction for execution by a processing thread;   determining that the first instruction is a load instruction;   updating an outstanding load count for the processing thread to indicate that at least one load operation has not completed execution;   storing the outstanding load count as state associated with the processing thread; and   after first data is retrieved to complete execution of the first instruction, updating the outstanding load count for the processing thread to indicate that the first instruction has completed execution.   
     
     
         2 . The method of  claim 1 , further comprising receiving a second instruction for execution by the processing thread, wherein the second instruction includes a wait on outstanding load bit that indicates whether a third instruction that follows the second instruction is dependent on execution of the first instruction. 
     
     
         3 . The method of  claim 2 , further comprising:
 receiving the third instruction for execution by the processing thread; and   executing the third instruction when the wait on outstanding load bit indicates that the third instruction is not dependent on execution of the first instruction.   
     
     
         4 . The method of  claim 2 , further comprising:
 receiving the third instruction;   determining that the wait on outstanding load bit indicates that the third instruction is dependent on execution of the first instruction; and   executing the third instruction when the outstanding load count indicates that all load operations for the processing thread have completed execution.   
     
     
         5 . The method of  claim 2 , wherein a compiler encodes the wait on outstanding load bit into the second instruction. 
     
     
         6 . The method of  claim 1 , wherein the first instruction includes a wait on outstanding load bit indicates whether a second instruction that follows the first instruction is dependent on execution of the first instruction. 
     
     
         7 . The method of  claim 1 , wherein the first data is retrieved from a global memory. 
     
     
         8 . The method of  claim 1 , wherein the outstanding load count for the processing thread is updated when a cache miss occurs. 
     
     
         9 . The method of  claim 1 , wherein the outstanding load count for the processing thread is updated when a cache hit occurs. 
     
     
         10 . The method of  claim 1 , further comprising:
 receiving a second instruction for execution by the processing thread;   determining that the second instruction is a load instruction that accesses a shared memory;   updating an shared-memory load counter for the processing thread to indicate that at least one load operation that accesses the shared memory has not completed execution; and   after second data is retrieved from the shared memory to complete execution of the second instruction, updating the shared-memory load counter for the processing thread to indicate that the second instruction has completed execution.   
     
     
         11 . A non-transitory computer-readable storage medium storing instructions that, when executed by a processor, cause the processor to execute dependent program instructions, by performing the steps of:
 receiving a first instruction for execution by a processing thread;   determining that the first instruction is a load instruction;   updating an outstanding load count for the processing thread to indicate that at least one load operation has not completed execution;   storing the outstanding load count as state associated with the processing thread; and   after first data is retrieved to complete execution of the first instruction, updating the outstanding load count for the processing thread to indicate that the first instruction has completed execution.   
     
     
         12 . A system for executing dependent program instructions, the system comprising:
 an instruction memory that is configured to store instructions for a program; and   a scheduler that is coupled to the instruction memory and configured to:
 receive a first instruction for execution by a processing thread; 
 determine that the first instruction is a load instruction; 
 update an outstanding load count for the processing thread to indicate that at least one load operation has not completed execution; 
 store the outstanding load count as state associated with the processing thread; and 
 after first data is retrieved to complete execution of the first instruction, update the outstanding load count for the processing thread to indicate that the first instruction has completed execution. 
   
     
     
         13 . The system of  claim 12 , further comprising receiving a second instruction for execution by the processing thread, wherein the second instruction includes a wait on outstanding load bit indicates whether a third instruction that follows the second instruction is dependent on execution of the first instruction. 
     
     
         14 . The system of  claim 13 , wherein the scheduler is further configured to:
 receive the third instruction for execution by the processing thread; and   execute the third instruction when the wait on outstanding load bit indicates that the third instruction is not dependent on execution of the first instruction.   
     
     
         15 . The system of  claim 13 , wherein the scheduler is further configured to:
 receive the third instruction;   determine that the wait on outstanding load bit indicates that the third instruction is dependent on execution of the first instruction; and   execute the third instruction when the outstanding load count indicates that all load operations for the processing thread have completed execution.   
     
     
         16 . The system of  claim 13 , wherein a compiler encodes the wait on outstanding load bit into the second instruction. 
     
     
         17 . The system of  claim 12 , wherein the first instruction includes a wait on outstanding load bit indicates whether a second instruction that follows the first instruction is dependent on execution of the first instruction. 
     
     
         18 . The system of  claim 12 , wherein the outstanding load count for the processing thread is updated when a cache miss occurs. 
     
     
         19 . The system of  claim 12 , wherein the outstanding load count for the processing thread is updated when a cache hit occurs. 
     
     
         20 . The system of  claim 12 , wherein the scheduler is further configured to:
 receive a second instruction for execution by the processing thread;   determine that the second instruction is a load instruction that accesses a shared memory;   update an shared-memory load counter for the processing thread to indicate that at least one load operation that accesses the shared memory has not completed execution; and   after second data is retrieved from the shared memory to complete execution of the second instruction, update the shared-memory load counter for the processing thread to indicate that the second instruction has completed execution.