Lightweight out of order scheduler for processing units

Abstract

A processing unit leverages a decode stage's pool of instructions, thereby expanding available instruction choices and eliminating the need for expensive OoO techniques to identify reordering opportunities. The processing unit introduces instruction reordering by presenting an alternative instruction to the warp scheduler through the existing interface rather than offering the oldest instruction in each warp. The result is a simple and efficient OoO engine that operates predominantly in the processing unit's front end.

What is claimed is: 
     
         1 . A processing unit, comprising:
 a front-end including:
 an issue buffer configured to receive instructions; 
 a dependence checker configured to receive instructions and detect any read-after-write (RAW), write-after-read (WAR), or write-after-write (WAW) hazards of each instruction; and 
 an out-of-order (OoO) scheduler operably coupled to the issue buffer and dependence checker, the OoO scheduler configured to select one or more instructions from the issue buffer for later stages. 
   
     
     
         2 . The processing unit of  claim 1 , wherein an instruction is removed from the issue buffer after it is issued. 
     
     
         3 . The processing unit of  claim 2 , wherein the issue buffer marks a space as empty after an instruction has been issued from the issue buffer. 
     
     
         4 . The processing unit of  claim 1 , wherein the dependence checker is further configured to mark and/or detect any read-after-write (RAW), write-after-read (WAR), or write-after-write (WAW) hazards of each instruction with instructions currently in the issue buffer. 
     
     
         5 . The processing unit of  claim 1 , wherein the processing unit is a graphics processing unit (GPU). 
     
     
         6 . The processing unit of  claim 1 , wherein the processing unit is configured to respect all register dependencies. 
     
     
         7 . The processing unit of  claim 1 , wherein the processing unit is configured to issue all memory instructions in order with respect to each other. 
     
     
         8 . The processing unit of  claim 1 , wherein the processing unit is configured to operate such that load instructions can be reordered against other load instructions but cannot be reordered against store instructions. 
     
     
         9 . The processing unit of  claim 1 , wherein the processing unit is configured to operate such that store instructions are not reordered against any load or store instruction. 
     
     
         10 . The processing unit of  claim 1 , wherein the processing unit is configured to check for idempotence in the dependence checker and does not issue non-idempotent instructions until a translation lookaside buffer hit or miss is determined for all prior load instructions. 
     
     
         11 . The processing unit of  claim 1 , wherein the processing unit is configured to consider structural hazards when selecting instructions for out-of-order issue. 
     
     
         12 . The processing unit of  claim 1 , wherein the front-end further comprises an instruction buffer, the instruction buffer is configured to:
 receive instructions and send the instructions to the dependence checker and the issue buffer when the issue buffer requests a new instruction.   
     
     
         13 . The processing unit of  claim 12 , wherein new instructions are fetched only when the instruction buffer is empty. 
     
     
         14 . The processing unit of  claim 1 , further comprising at least one warp scheduler configured to select at least one warp from its assigned warps and issuing one or more instructions from that warp. 
     
     
         15 . The processing unit of  claim 14 , wherein the processing unit utilizes an out-of-order scheduler and separate warp scheduler. 
     
     
         16 . The processing unit of  claim 15 , wherein the out-of-order scheduler looks at one or more warps in each cycle to select one or more instructions which are ready for out-of-order issue. 
     
     
         17 . The processing unit of  claim 16 , wherein the warp scheduler selects one or more of the ready instructions from one or more warps and issues the selected one or more ready instructions. 
     
     
         18 . The processing unit of  claim 1 , wherein the out-of-order scheduler knows the instruction has no dependencies by means of a scoreboard. 
     
     
         19 . The processing unit of  claim 1 , wherein the out-of-order scheduler knows the instruction has no dependencies by means of an instruction encoding. 
     
     
         20 . The processing unit of  claim 18 , wherein, after issuing an instruction, a single instruction, multiple threads (SIMT) stack and/or a scoreboard (SB) is/are updated. 
     
     
         21 . The processing unit of  claim 14 , wherein the warp scheduler is configured to use a scheduling policy that selects one or more instructions from one or more warps with no structural hazards. 
     
     
         22 . The processing unit of  claim 1 , wherein the processing unit is configured to select a warp for dependence checking if there was a writeback to the warp and/or the warp does not have any valid entries in an instruction table. 
     
     
         23 . The processing unit of  claim 1 , wherein the processing unit maintains a Warp-WriteBack (WWb) bit-vector and an ITabEmpty (ITE) bit vector where each bit corresponds to a warp. 
     
     
         24 . The processing unit of  claim 23 , wherein, when a warp has a write-back, the corresponding bit in the WWb is set. 
     
     
         25 . The processing unit of  claim 23 , wherein, when a warp does not have any entries in the ITE, the corresponding ITE bit is set to one. 
     
     
         26 . The processing unit of  claim 23 , wherein, in a cycle, the processing unit selects warps whose WWb bit is set over warps whose ITE bit is set. 
     
     
         27 . The processing unit of  claim 23 , wherein after dependence checking for a warp, the WWb bit corresponding to the warp is unset. 
     
     
         28 . The processing unit of  claim 23 , wherein when independent instructions are found and placed in the ITE, the ITE bit corresponding to the warp is unset. 
     
     
         29 . The processing unit of  claim 23 , wherein, when the ITE bit is set for a warp, the warp is skipped for consideration by a warp scheduler in that cycle.