System and method for scheduling instructions in a multithread SIMD architecture with a fixed number of registers

Abstract

A method and apparatus for scheduling instructions of a shader program for a graphics processing unit (GPU) with a fixed number of registers. The method and apparatus include computing, via a processing unit (PU), a liveness-based register usage across all basic blocks in the shader program, computing, via the PU, the range of numbers of waves of a plurality of registers for the shader program, assessing the impact of available post-register allocation optimizations, computing, via the PU, the scoring data based on number of waves of the plurality of registers, and computing, via the PU, the number of waves for execution for the plurality of registers.

What is claimed is: 
     
       1. A method for scheduling instructions of a shader program for a graphics processing unit (GPU) with a fixed number of registers, the method comprising:
 computing, via a processing unit (PU), a live variable analysis of the registers used by a shader program; 
 computing, via the PU, a range of waves of the analyzed registers based on the live variable analysis of the registers; 
 assessing, via the PU, an impact of the computed range of waves based on the computed range of wave of the analyzed registers; 
 computing, via the PU, a score for the assessed impact of the computed range of waves; and 
 computing, via the PU, the number of waves to execute for the registers used by the shader program based on the computed score, 
 wherein the computed number of waves to execute enables the GPU to process the computed number of waves to avoid reducing performance. 
 
     
     
       2. The method of  claim 1 , wherein the live variable analysis of the registers used by a shader program includes a liveness-based register usage across all basic blocks in the shader program. 
     
     
       3. The method of  claim 2 , wherein the computing a liveness-based register usage across all basic blocks in the shader program includes computing a minimum and maximum number of registers of the plurality of registers estimated for the shader program. 
     
     
       4. The method of  claim 1 , wherein the range of waves of the analyzed registers includes a range of numbers of waves of a plurality of registers for the shader program based on the live variable analysis of the registers used by a shader program. 
     
     
       5. The method of  claim 4 , wherein the computing the range of numbers of waves of the plurality of registers for the shader program includes computing a minimum number of waves of the plurality of registers and a maximum numbers of waves of the plurality of registers for the shader program. 
     
     
       6. The method of  claim 1 , wherein the impact of the computed range of waves includes an impact of available post-register allocation optimizations based on the range of waves of the analyzed registers. 
     
     
       7. The method of  claim 6 , wherein the assessing the impact of available post-register allocation optimizations includes computing a minimum number of waves of the plurality of registers for the shader program from the computed maximum number of registers of the plurality of registers. 
     
     
       8. The method of  claim 1 , wherein the score for the assessed impact of the computed range of waves includes a scoring data based on the assessed impact of available post-register allocation optimizations. 
     
     
       9. The method of  claim 8 , wherein the computing the scoring data based on number of waves of the plurality of registers includes choosing a best scheduling algorithm based on the scores including post-register allocation optimization and accumulate the information with the information for the number of waves of the plurality of registers for all blocks in the shader program. 
     
     
       10. The method of  claim 1 , wherein the number of waves to execute for the registers used by the shader program based on the computed score includes a number of waves for the plurality of registers based on the computed scoring data. 
     
     
       11. The method of  claim 10 , wherein the computing the number of waves of the plurality of registers includes choosing the number of waves, based on a best score for the accumulated data for the number of waves, and the best score for the accumulated data with post-register allocation optimizations, and choosing the number of registers of the plurality of registers used by the shader program based on the number of waves chosen. 
     
     
       12. The method of  claim 1 , wherein the PU is one of a central processing unit (CPU) and a GPU. 
     
     
       13. A graphics processor with optimized scheduling of instructions of a shader program, the scheduling of instructions optimized by:
 computing, via a processing unit (PU), a live variable analysis of the registers used by a shader program; 
 computing, via the PU, a range of waves of the analyzed registers based on the computed live variable analysis; 
 assessing, via the PU, an impact of the computed range of waves based on the computed range of numbers of waves of the plurality of registers; 
 computing, via the PU, a score for the assessed impact of the computed range of waves; and 
 computing, via the PU, the number of waves to execute for the registers used by the shader program based on the computed score, 
 wherein the computed number of waves to execute enables the GPU to process the computed number of waves to avoid reducing performance. 
 
     
     
       14. The graphics processor of  claim 13 , wherein the computing a live variable analysis of the registers used by a shader program includes computing a minimum and maximum number of registers of the plurality of registers estimated for the shader program. 
     
     
       15. The graphics processor of  claim 13 , wherein the a range of waves of the analyzed registers includes computing a minimum number of waves of the plurality of registers and a maximum numbers of waves of the plurality of registers for the shader program. 
     
     
       16. The graphics processor of  claim 13 , wherein the assessing the impact of the computed range of waves includes computing a minimum number of waves of the plurality of registers for the shader program from the computed maximum number of registers of the plurality of registers. 
     
     
       17. The graphics processor of  claim 13 , wherein the computing a score for the assessed impact of the computed range of waves includes choosing a best scheduling algorithm based on the scores including post-register allocation optimization and accumulate the information with the information for the number of waves of the plurality of registers for all basic blocks in the shader program. 
     
     
       18. The graphics processor of  claim 13 , wherein the computing the number of waves to execute for the registers used by the shader program based on the computed score includes choosing the number of waves, based on a best score for the accumulated data for the number of waves, and the best score for the accumulated data with post-register allocation optimizations, and choosing the number of registers of the plurality of registers used by the shader program based on the number of waves chosen. 
     
     
       19. The graphics processor of  claim 13 , wherein the PU is one of a central processing unit (CPU) and a GPU.