{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,24]],"date-time":"2026-09-24T06:43:15Z","timestamp":1790232195070,"version":"4.1.0"},"reference-count":73,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2013,12,1]],"date-time":"2013-12-01T00:00:00Z","timestamp":1385856000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004901","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado de Minas Gerais","doi-asserted-by":"publisher","award":["2010\/2"],"award-info":[{"award-number":["2010\/2"]}],"id":[{"id":"10.13039\/501100004901","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Web during his stay in Brazil"},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:p>Growing interest in graphics processing units has brought renewed attention to the Single Instruction Multiple Data (SIMD) execution model. SIMD machines give application developers tremendous computational power; however, programming them is still challenging. In particular, developers must deal with memory and control-flow divergences. These phenomena stem from a condition that we call data divergence, which occurs whenever two processing elements (PEs) see the same variable name holding different values. This article introduces divergence analysis, a static analysis that discovers data divergences. This analysis, currently deployed in an industrial quality compiler, is useful in several ways: it improves the translation of SIMD code to non-SIMD CPUs, it helps developers to manually improve their SIMD applications, and it also guides the automatic optimization of SIMD programs. We demonstrate this last point by introducing the notion of a divergence-aware register spiller. This spiller uses information from our analysis to either rematerialize or share common data between PEs. As a testimony of its effectiveness, we have tested it on a suite of 395 CUDA kernels from well-known benchmarks. The divergence-aware spiller produces GPU code that is 26.21% faster than the code produced by the register allocator used in the baseline compiler.<\/jats:p>","DOI":"10.1145\/2523815","type":"journal-article","created":{"date-parts":[[2014,1,2]],"date-time":"2014-01-02T13:09:43Z","timestamp":1388668183000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Divergence analysis"],"prefix":"10.1145","volume":"35","author":[{"given":"Diogo","family":"Sampaio","sequence":"first","affiliation":[{"name":"Universidade Federal de Minas Gerais, Belo Horizonte, Brazil"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rafael Martins de","family":"Souza","sequence":"additional","affiliation":[{"name":"Universidade Federal de Minas Gerais, Belo Horizonte, Brazil"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Caroline","family":"Collange","sequence":"additional","affiliation":[{"name":"INRIA, Rennes Cedex, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fernando Magno Quint\u00e3o","family":"Pereira","sequence":"additional","affiliation":[{"name":"Universidade Federal de Minas Gerais, Belo Horizonte, Brazil"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,1,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1476793.1476814"},{"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\/268946.268974"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/278283.278285"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1693453.1693470"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.52.0078"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of FMPC. ACM, 471--480","author":"Blelloch G.","unstructured":"Blelloch, G. and Chatterjee, S. 1990. Vcode: A data-parallel intermediate language. In Proceedings of FMPC. ACM, 471--480."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the AMD Fusion Developer Summit. AMD.","author":"Boudier P.","unstructured":"Boudier, P. and Sellers, G. 2011. Memory system on Fusion APUs. In Proceedings of the AMD Fusion Developer Summit. AMD."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-739X(92)90069-N"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1972.8647"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/143095.143143"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","unstructured":"Brockmann K. and Wanka R. 1997. Efficient oblivious parallel sorting on the MasPar MP-1. Vol. ICSS. 1 200.","DOI":"10.5555\/938433.938539"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/512529.512534"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1531743.1531766"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1498698.1564500"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2009.5306797"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/99583.99594"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1884795.1884804"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/512760.512770"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2011.63"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.2853"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2212736.2212744"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/115372.115320"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(88)90094-4"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1854273.1854318"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254066"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00113-2"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/24039.24041"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1972.5009071"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2007.12"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1839676.1839694"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-012-0201-1"},{"key":"e_1_2_1_33_1","volume-title":"Filed","author":"Grover V.","year":"2009","unstructured":"Grover, V., Joannes, B., Aarts, M., and Murphy, M. 2009. Variance analysis for translating CUDA code for execution by a general purpose processor. U.S. Patent 2009\/0259997, Filed March 31, 2009, and issued October 15, 2009."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.01.008"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1964179.1964184"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of PLDI. ACM.","author":"Jang B.","unstructured":"Jang, B., Schaa, D., Mistry, P., and Kaeli, D. 2010. Static memory access pattern analysis on a massively parallel GPU. In Proceedings of PLDI. ACM."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2190025.2190061"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28652-0_1"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-25209-3_7"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1982.1675922"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 9th Workshop on Duplicating, Deconstructing, and Debunking (WDDD). IEEE, 75--81","author":"Lashgar A.","unstructured":"Lashgar, A. and Baniasadi, A. 2011. Performance in GPU architectures: Potentials and distances. In Proceedings of the 9th Workshop on Duplicating, Deconstructing, and Debunking (WDDD). IEEE, 75--81."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/360680.360687"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1504176.1504194"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000064.2000080"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2013.6494995"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2145816.2145825"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1815961.1815992"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10990-006-8609-1"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/1870926.1870950"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2010.41"},{"key":"e_1_2_1_51_1","unstructured":"Nickolls J. and Kirk D. 2009. Graphics and Computing GPUs. Computer Organization and Design (Patterson and Hennessy) 4th Ed. Elsevier Chapter A A.1--A.77."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","unstructured":"Nielson F. Nielson H. R. and Hankin C. 2005. Principles of Program Analysis. Springer.","DOI":"10.5555\/1965094"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/93542.93578"},{"key":"e_1_2_1_54_1","unstructured":"Pereira F. M. Q. 2011. Dirmap's Blog. http:\/\/divmap.wordpress.com\/."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/357073.357075"},{"key":"e_1_2_1_56_1","volume-title":"Proceedings of Innorative Parallel Computing (InPar).","author":"Pharr M.","unstructured":"Pharr, M. and Mark, W. R. 2012. ISPC: A SPMD compiler for high-performance CPU programming. In Proceedings of Innorative Parallel Computing (InPar)."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/330249.330250"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926445"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/1345206.1345220"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542476.1542525"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254067"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/SBAC-PAD.2012.22"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33182-4_3"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/1693453.1693473"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","unstructured":"Scholz B. Zhang C. and Cifuentes C. 2008. User-input dependence analysis via graph reachability. Tech. rep. Sun Inc.","DOI":"10.5555\/1698206"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772954.1772971"},{"key":"e_1_2_1_67_1","volume-title":"The parboil report. Tech. rep","author":"Stratton J. A.","unstructured":"Stratton, J. A., Rodrigues, C., Sun, I.-J., Obeid, N., Chang, L.-W., Anssari, N., Liu, G. D., and mei W. Hwu, W. 2012. The parboil report. Tech. rep., University of Illinois at Urbana-Champaign."},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/207110.207115"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.5555\/800078.802557"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806596.1806606"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810085.1810104"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/1950365.1950408"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.5555\/2014698.2014875"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2523815","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2523815","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:10:10Z","timestamp":1750234210000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2523815"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12]]},"references-count":73,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,12]]}},"alternative-id":["10.1145\/2523815"],"URL":"https:\/\/doi.org\/10.1145\/2523815","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"value":"0164-0925","type":"print"},{"value":"1558-4593","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,12]]},"assertion":[{"value":"2012-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-01-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}