Optimal automatic multi-pass shader partitioning by dynamic programming

Alan Heirich
Sony Computer Entertainment America, Foster City, California
SIGGRAPH/EUROGRAPHICS Conference On Graphics Hardware: Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware; 30-31 July 2005. 2005


   title={Optimal automatic multi-pass shader partitioning by dynamic programming},

   author={Heirich, A.},

   booktitle={Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware},






Download Download (PDF)   View View   Source Source   



Complex shaders must be partitioned into multiple passes to execute on GPUs with limited hardware resources. Automatic partitioning gives rise to an NP-hard scheduling problem that can be solved by any number of established techniques. One such technique, Dynamic Programming (DP), is commonly used for instruction scheduling and register allocation in the code generation phase of compilers. Since automatic partitioning occurs during the shader compilation process it is natural to ask whether DP is useful for shader partitioning as well as for code generation. This paper demonstrates that these problems are Markovian and can be solved by DP techniques. It presents a DP algorithm for shader partitioning that can be adapted for use with any GPU architecture. Unlike solutions produced by other techniques DP solutions are globally optimal. Experimental results on a set of test cases with a commercial prerelease compiler for a popular high level shading language showed a DP algorithm had an average runtime cost of O(n1.14966) which is less than O(n log n) on the region of interest in n. This demonstrates that efficient and optimal automatic shader partitioning can be an emergent byproduct of a DP-based code generator for a very high performance GPU.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: