{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T18:54:03Z","timestamp":1791312843619,"version":"4.3.1"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2009,6,1]],"date-time":"2009-06-01T00:00:00Z","timestamp":1243814400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2009,6]]},"abstract":"<jats:p>Recent advances in graphics processing units (GPUs) have resulted in massively parallel hardware that is easily programmable and widely available in today's desktop and notebook computer systems. GPUs typically use single-instruction, multiple-data (SIMD) pipelines to achieve high performance with minimal overhead for control hardware. Scalar threads running the same computing kernel are grouped together into SIMD batches, sometimes referred to as warps. While SIMD is ideally suited for simple programs, recent GPUs include control flow instructions in the GPU instruction set architecture and programs using these instructions may experience reduced performance due to the way branch execution is supported in hardware. One solution is to add a stack to allow different SIMD processing elements to execute distinct program paths after a branch instruction. The occurrence of diverging branch outcomes for different processing elements significantly degrades performance using this approach. In this article, we propose dynamic warp formation and scheduling, a mechanism for more efficient SIMD branch execution on GPUs. It dynamically regroups threads into new warps on the fly following the occurrence of diverging branch outcomes. We show that a realistic hardware implementation of this mechanism improves performance by 13%, on average, with 256 threads per core, 24% with 512 threads, and 47% with 768 threads for an estimated area increase of 8%.<\/jats:p>","DOI":"10.1145\/1543753.1543756","type":"journal-article","created":{"date-parts":[[2009,7,8]],"date-time":"2009-07-08T17:28:33Z","timestamp":1247074113000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":54,"title":["Dynamic warp formation"],"prefix":"10.1145","volume":"6","author":[{"given":"Wilson W. L.","family":"Fung","sequence":"first","affiliation":[{"name":"University of British Columbia, Vancouver, B.C., Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ivan","family":"Sham","sequence":"additional","affiliation":[{"name":"University of British Columbia, Vancouver, B.C., Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"George","family":"Yuan","sequence":"additional","affiliation":[{"name":"University of British Columbia, Vancouver, B.C., Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tor M.","family":"Aamodt","sequence":"additional","affiliation":[{"name":"University of British Columbia, Vancouver, B.C., Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2009,7,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/339647.339691"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1177220"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/567067.567085"},{"key":"e_1_2_1_4_1","unstructured":"]]AMD Inc. 2006. ATI CTM Guide 1.01 ed. AMD Inc.  ]]AMD Inc. 2006. ATI CTM Guide 1.01 ed. AMD Inc."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1331699.1331736"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/965139.507101"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1972.8647"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1080\/17445760802337010"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186562.1015800"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/268806.268810"},{"key":"e_1_2_1_11_1","unstructured":"]]Cervini S. 2005. European Patent EP 1531391 A2: System and method for efficiently executing single program multiple data (SPMD) programs.  ]]Cervini S. 2005. European Patent EP 1531391 A2: System and method for efficiently executing single program multiple data (SPMD) programs."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2007.346199"},{"key":"e_1_2_1_13_1","unstructured":"]]Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms 2nd Ed. MIT Press Cambridge MA.   ]]Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms 2nd Ed. MIT Press Cambridge MA."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/965141.563901"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1048935.1050187"},{"key":"e_1_2_1_16_1","unstructured":"]]Dally W. J. and Towles B. 2004. Interconnection Networks. Morgan Kaufmann San Francisco CA.  ]]Dally W. J. and Towles B. 2004. Interconnection Networks. Morgan Kaufmann San Francisco CA."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software. IEEE, 231--241","author":"del Barrio V.","unstructured":"]] del Barrio , V. , Gonzalez , C. , Roca , J. , Fernandez , A. , and Espasa , R . 2006. ATTILA: A cycle-level execution-driven simulator for modern GPU architectures . In Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software. IEEE, 231--241 . ]]del Barrio, V., Gonzalez, C., Roca, J., Fernandez, A., and Espasa, R. 2006. ATTILA: A cycle-level execution-driven simulator for modern GPU architectures. In Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software. IEEE, 231--241."},{"key":"e_1_2_1_18_1","volume-title":"Eds","author":"Fowler H.","year":"1995","unstructured":"]] Fowler , H. , Fowler , F. , and Thompson , D. , Eds . 1995 . The Concise Oxford Dictionary 9th Ed. Oxford University Press . ]]Fowler, H., Fowler, F., and Thompson, D., Eds. 1995. The Concise Oxford Dictionary 9th Ed. Oxford University Press."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2007.12"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/264107.264152"},{"key":"e_1_2_1_21_1","unstructured":"]]Harris M. 2007. Optimizing parallel reduction in cuda. http:\/\/developer.download.nvidia.com\/compute\/cuda\/1_1\/Website\/projects\/reduction\/doc\/reduction.pdf.  ]]Harris M. 2007. Optimizing parallel reduction in cuda. http:\/\/developer.download.nvidia.com\/compute\/cuda\/1_1\/Website\/projects\/reduction\/doc\/reduction.pdf."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"]]Hwu W.-M. Kirk D. Ryoo S. Rodrigues C. Stratton J. and Huang K. 2007. Performance insights on executing non-graphics applications on CUDA on the NVIDIA GeForce 8800 GTX. http:\/\/www.hotchips.org\/archives\/hc19\/2Mon\/HC19.02\/HC19.02.03.pdf.  ]]Hwu W.-M. Kirk D. Ryoo S. Rodrigues C. Stratton J. and Huang K. 2007. Performance insights on executing non-graphics applications on CUDA on the NVIDIA GeForce 8800 GTX. http:\/\/www.hotchips.org\/archives\/hc19\/2Mon\/HC19.02\/HC19.02.03.pdf.","DOI":"10.1109\/HOTCHIPS.2007.7482492"},{"key":"e_1_2_1_23_1","volume-title":"Intel 965 Express Chipset Family and Intel G35 Express Chipset Graphics Controller Programmer's Reference Manual","author":"]]Intel Corp. 2008.","unstructured":"]]Intel Corp. 2008. Intel 965 Express Chipset Family and Intel G35 Express Chipset Graphics Controller Programmer's Reference Manual . Intel Corporation . ]]Intel Corp. 2008. Intel 965 Express Chipset Family and Intel G35 Express Chipset Graphics Controller Programmer's Reference Manual. Intel Corporation."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2007.892882"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2004.10007"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/360128.360145"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 31st Annual International Symposium on Computer Architecture (ISCA'04)","author":"Krashinsky R.","unstructured":"]] Krashinsky , R. , Batten , C. , Hampton , M. , Gerding , S. , Pharris , B. , Casper , J. , and Asanovic , K . 2004. The vector-thread architecture . In Proceedings of the 31st Annual International Symposium on Computer Architecture (ISCA'04) . ACM, 52--63. ]]Krashinsky, R., Batten, C., Hampton, M., Gerding, S., Pharris, B., Casper, J., and Asanovic, K. 2004. The vector-thread architecture. In Proceedings of the 31st Annual International Symposium on Computer Architecture (ISCA'04). ACM, 52--63."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/800031.808581"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/383259.383274"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2008.31"},{"key":"e_1_2_1_31_1","unstructured":"]]Lorie R. A. and Strong H. R. 1984. US Patent 4 435 758: Method for conditional branch execution in SIMD vector processors.  ]]Lorie R. A. and Strong H. R. 1984. US Patent 4 435 758: Method for conditional branch execution in SIMD vector processors."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2007.59"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2005.37"},{"key":"e_1_2_1_34_1","unstructured":"]]Moy S. and Lindholm E. 2005. US Patent 6 947 047: Method and system for programmable pipelined graphics processing with branching instructions.  ]]Moy S. and Lindholm E. 2005. US Patent 6 947 047: Method and system for programmable pipelined graphics processing with branching instructions."},{"key":"e_1_2_1_35_1","unstructured":"]]Muchnick S. S. 1997. Advanced Compiler Design and Implementation. Morgan Kaufmanns.   ]]Muchnick S. S. 1997. Advanced Compiler Design and Implementation. Morgan Kaufmanns."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(70)90057-4"},{"key":"e_1_2_1_37_1","unstructured":"]]NVIDIA Corp. CUDA SDK code samples. http:\/\/www.nvidia.com\/object\/cudagetsamples.html.  ]]NVIDIA Corp. CUDA SDK code samples. http:\/\/www.nvidia.com\/object\/cudagetsamples.html."},{"key":"e_1_2_1_38_1","volume-title":"NVIDIA CUDA Programming Guide, 1.1 ed","author":"]]NVIDIA Corp. 2007a.","unstructured":"]]NVIDIA Corp. 2007a. NVIDIA CUDA Programming Guide, 1.1 ed . NVIDIA Corp . ]]NVIDIA Corp. 2007a. NVIDIA CUDA Programming Guide, 1.1 ed. NVIDIA Corp."},{"key":"e_1_2_1_39_1","volume-title":"PTX: Parallel Thread Execution ISA, 1.1 ed","author":"]]NVIDIA Corp.","year":"2007","unstructured":"]]NVIDIA Corp. 2007 b. PTX: Parallel Thread Execution ISA, 1.1 ed . NVIDIA Corp . ]]NVIDIA Corp. 2007b. PTX: Parallel Thread Execution ISA, 1.1 ed. NVIDIA Corp."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/566570.566640"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 31st International Symposium on Micro-architecture (MICRO'98)","author":"Rixner S.","unstructured":"]] Rixner , S. , Dally , W. J. , Kapasi , U. J. , Khailany , B. , L\u00f3pez-Lagunas , A. , Mattson , P. R. , and Owens , J. D . 1998. A bandwidth-efficient architecture for media processing . In Proceedings of the 31st International Symposium on Micro-architecture (MICRO'98) . ACM, 3--13. ]]Rixner, S., Dally, W. J., Kapasi, U. J., Khailany, B., L\u00f3pez-Lagunas, A., Mattson, P. R., and Owens, J. D. 1998. A bandwidth-efficient architecture for media processing. In Proceedings of the 31st International Symposium on Micro-architecture (MICRO'98). ACM, 3--13."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/339647.339668"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 5th International Symposium on High-Performance Computer Architecutre (HPCA'99)","author":"Rotenberg E.","unstructured":"]] Rotenberg , E. , Jacobson , Q. , and Smith , J. E . 1999. A study of control independence in super-scalar processors . In Proceedings of the 5th International Symposium on High-Performance Computer Architecutre (HPCA'99) . IEEE, 115--124. ]]Rotenberg, E., Jacobson, Q., and Smith, J. E. 1999. A study of control independence in super-scalar processors. In Proceedings of the 5th International Symposium on High-Performance Computer Architecutre (HPCA'99). IEEE, 115--124."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1058129.1058142"},{"key":"e_1_2_1_45_1","unstructured":"]]Shebanow M. 2007. ECE 498 AL: Programming massively parallel processors (lecture 12). http:\/\/courses.ece.uiuc.edu\/ece498\/al1\/Archive\/Spring2007.  ]]Shebanow M. 2007. ECE 498 AL: Programming massively parallel processors (lecture 12). http:\/\/courses.ece.uiuc.edu\/ece498\/al1\/Archive\/Spring2007."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/1299042.1299055"},{"key":"e_1_2_1_47_1","volume-title":"Performance Evaluation Corporation. SPEC CPU2006 benchmarks. http:\/\/www.spec.org\/cpu2006\/.","author":"Standard","unstructured":"]] Standard Performance Evaluation Corporation. SPEC CPU2006 benchmarks. http:\/\/www.spec.org\/cpu2006\/. ]]Standard Performance Evaluation Corporation. SPEC CPU2006 benchmarks. http:\/\/www.spec.org\/cpu2006\/."},{"key":"e_1_2_1_48_1","unstructured":"]]Tarjan D. Thoziyor S. and Jouppi N. P. 2006. CACTI 4.0. Tech. rep. HPL-2006-86 Hewlett Packard Laboratories Palo Alto CA.  ]]Tarjan D. Thoziyor S. and Jouppi N. P. 2006. CACTI 4.0. Tech. rep. HPL-2006-86 Hewlett Packard Laboratories Palo Alto CA."},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of Super-computing. IEEE, 35--41","author":"Thistle M. R.","unstructured":"]] Thistle , M. R. and Smith , B. J . 1988. A processor architecture for Horizon . In Proceedings of Super-computing. IEEE, 35--41 . ]]Thistle, M. R. and Smith, B. J. 1988. A processor architecture for Horizon. In Proceedings of Super-computing. IEEE, 35--41."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1464039.1464045"},{"key":"e_1_2_1_51_1","volume-title":"The RenderMan Companion: A Programmer's Guide to Realistic Computer Graphics","author":"Upstill S.","unstructured":"]] Upstill , S. 1990. The RenderMan Companion: A Programmer's Guide to Realistic Computer Graphics . Addison-Wesley , Reading, MA . ]]Upstill, S. 1990. The RenderMan Companion: A Programmer's Guide to Realistic Computer Graphics. Addison-Wesley, Reading, MA."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/223982.223990"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073211"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1543753.1543756","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1543753.1543756","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:30:20Z","timestamp":1750253420000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1543753.1543756"}},"subtitle":["Efficient MIMD control flow on SIMD graphics hardware"],"short-title":[],"issued":{"date-parts":[[2009,6]]},"references-count":53,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,6]]}},"alternative-id":["10.1145\/1543753.1543756"],"URL":"https:\/\/doi.org\/10.1145\/1543753.1543756","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,6]]},"assertion":[{"value":"2008-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-07-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}