Optimal Automatic Multi-pass Shader Partitioning by Dynamic Programming

Simple item page
dc.contributor.authorHeirich, Alanen_US
dc.contributor.editorMichael Meissner and Bengt-Olaf Schneideren_US
dc.date.accessioned2013-10-28T10:03:38Z
dc.date.available2013-10-28T10:03:38Z
dc.date.issued2005en_US
dc.description.abstractComplex 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(nlogn) 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.en_US
dc.description.seriesinformationGraphics Hardwareen_US
dc.identifier.isbn1-59593-086-8en_US
dc.identifier.issn1727-3471en_US
dc.identifier.urihttps://doi.org/10.2312/EGGH/EGGH05/091-098en_US
dc.publisherThe Eurographics Associationen_US
dc.subjectCategories and Subject Descriptors (according to ACM CCS): I.3.1 [Computer Graphics]: Hardware Architecture I.3.3 [Computer Graphics]: Picture/Image Generation I.3.6 [Computer Graphics]: Methodology and Techniqueen_US
dc.titleOptimal Automatic Multi-pass Shader Partitioning by Dynamic Programmingen_US
Files
Collections
EGGH05: SIGGRAPH/Eurographics Workshop on Graphics Hardware 2005