{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:17:33Z","timestamp":1750306653362,"version":"3.41.0"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2014,6,1]],"date-time":"2014-06-01T00:00:00Z","timestamp":1401580800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2014,6]]},"abstract":"<jats:p>Fine-grained data parallelism is increasingly common in the form of longer vectors integrated with mainstream processors (SSE, AVX) and various GPU architectures. This article develops support for exploiting such data parallelism for a class of nonnumeric, nongraphic applications, which perform computations while traversing many independent, irregular data structures. We address this problem by developing several novel techniques. First, for code generation, we develop an intermediate language for specifying such traversals, followed by a runtime scheduler that maps traversals to various SIMD units. Second, we observe that good data locality is crucial to sustained performance from SIMD architectures, whereas many applications that operate on irregular data structures (e.g., trees and graphs) have poor data locality. To address this challenge, we develop a set of data layout optimizations that improve spatial locality for applications that traverse many irregular data structures. Unlike prior data layout optimizations, our approach incorporates a notion of both interthread and intrathread spatial reuse into data layout. Finally, we enable performance portability (i.e., the ability to automatically optimize applications for different architectures) by accurately modeling the impact of inter- and intrathread locality on program performance. As a consequence, our model can predict which data layout optimization to use on a wide variety of SIMD architectures.<\/jats:p>\n          <jats:p>To demonstrate the efficacy of our approach and optimizations, we first show how they enable up to a 12X speedup on one SIMD architecture for a set of real-world applications. To demonstrate that our approach enables performance portability, we show how our model predicts the optimal layout for applications across a diverse set of three real-world SIMD architectures, which offers as much as 45% speedup over a suboptimal solution.<\/jats:p>","DOI":"10.1145\/2632215","type":"journal-article","created":{"date-parts":[[2014,7,1]],"date-time":"2014-07-01T14:23:02Z","timestamp":1404224582000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["A Portable Optimization Engine for Accelerating Irregular Data-Traversal Applications on SIMD Architectures"],"prefix":"10.1145","volume":"11","author":[{"given":"Bin","family":"Ren","sequence":"first","affiliation":[{"name":"The Ohio State University, Columbus, OH"}]},{"given":"Todd","family":"Mytkowicz","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA"}]},{"given":"Gagan","family":"Agrawal","sequence":"additional","affiliation":[{"name":"The Ohio State University, Columbus, OH"}]}],"member":"320","published-online":{"date-parts":[[2014,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2010.46"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1994.1038"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1010933404324"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2012.6402918"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1880153.1880157"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/782814.782836"},{"volume-title":"Proceedings of the 1990 ACM\/IEEE Conference on Supercomputing (SC\u201990)","author":"Chatterjee S.","key":"e_1_2_1_7_1","unstructured":"S. Chatterjee , G. E. Blelloch , and M. Zagha . 1990. Scan primitives for vector computers . In Proceedings of the 1990 ACM\/IEEE Conference on Supercomputing (SC\u201990) . 666--675. S. Chatterjee, G. E. Blelloch, and M. Zagha. 1990. Scan primitives for vector computers. In Proceedings of the 1990 ACM\/IEEE Conference on Supercomputing (SC\u201990). 666--675."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063384.2063401"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/301618.301633"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"e_1_2_1_11_1","unstructured":"R. Cox. 2007. Regular Expression Matching Can Be Simple and Fast. Available at http:\/\/swtch.com\/&sim;rsc\/regexp\/regexp1.html.  R. Cox. 2007. Regular Expression Matching Can Be Simple and Fast. Available at http:\/\/swtch.com\/&sim;rsc\/regexp\/regexp1.html."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2011.89"},{"key":"e_1_2_1_13_1","unstructured":"H. G. Dietz and W. E. Cohen. 1992. A Massively Parallel MIMD Implemented by SIMD Hardware&excl; Technical Report. Purdue University.  H. G. Dietz and W. E. Cohen. 1992. A Massively Parallel MIMD Implemented by SIMD Hardware&excl; Technical Report. Purdue University."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1941553.1941568"},{"volume-title":"Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201902)","author":"Franchetti F.","key":"e_1_2_1_15_1","unstructured":"F. Franchetti and M. Puschel . 2002. A SIMD vectorizing compiler for digital signal processing algorithms . In Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201902) . IEEE, 20--26. F. Franchetti and M. Puschel. 2002. A SIMD vectorizing compiler for digital signal processing algorithms. In Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201902). IEEE, 20--26."},{"volume-title":"Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201903)","author":"Garca C.","key":"e_1_2_1_16_1","unstructured":"C. Garca , R. Lario , M. Prieto , L. Piuel , and F. Tirado . 2003. Vectorization of multigrid codes using SIMD ISA extensions . Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201903) . IEEE, 58.1. C. Garca, R. Lario, M. Prieto, L. Piuel, and F. Tirado. 2003. Vectorization of multigrid codes using SIMD ISA extensions. Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201903). IEEE, 58.1."},{"volume-title":"Proceedings of the 7th International Conference on Compiler Construction (CC\u201998)","author":"Ghiya R.","key":"e_1_2_1_17_1","unstructured":"R. Ghiya , L. J. Hendren , and Y. Zhu . 1998. Detecting parallelism in C programs with recursive data structures . In Proceedings of the 7th International Conference on Compiler Construction (CC\u201998) . Springer, 159--173. R. Ghiya, L. J. Hendren, and Y. Zhu. 1998. Detecting parallelism in C programs with recursive data structures. In Proceedings of the 7th International Conference on Compiler Construction (CC\u201998). Springer, 159--173."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-006-0059-1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/143095.143133"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 1st International Workshop on High-Level Programming Models and Supportive Environments (HIPS\u201996)","author":"Hardwick J. C.","year":"1996","unstructured":"J. C. Hardwick . 1996 . An efficient implementation of nested data parallelism for irregular divide-and-conquer algorithms . In Proceedings of the 1st International Workshop on High-Level Programming Models and Supportive Environments (HIPS\u201996) . 105--114. J. C. Hardwick. 1996. An efficient implementation of nested data parallelism for irregular divide-and-conquer algorithms. In Proceedings of the 1st International Workshop on High-Level Programming Models and Supportive Environments (HIPS\u201996). 105--114."},{"volume-title":"Proceedings of the 14th International Conference on High Performance Computing (HiPC\u201907)","author":"Harish P.","key":"e_1_2_1_21_1","unstructured":"P. Harish and P. Narayanan . 2007. Accelerating large graph algorithms on the GPU using CUDA . In Proceedings of the 14th International Conference on High Performance Computing (HiPC\u201907) . 197--208. P. Harish and P. Narayanan. 2007. Accelerating large graph algorithms on the GPU using CUDA. In Proceedings of the 14th International Conference on High Performance Computing (HiPC\u201907). 197--208."},{"key":"e_1_2_1_22_1","first-page":"851","article-title":"Parallel prefix sum (scan) with CUDA","volume":"3","author":"Harris M.","year":"2007","unstructured":"M. Harris , S. Sengupta , and J. D. Owens . 2007 . Parallel prefix sum (scan) with CUDA . GPU Gems 3 , 39, 851 -- 876 . M. Harris, S. Sengupta, and J. D. Owens. 2007. Parallel prefix sum (scan) with CUDA. GPU Gems 3, 39, 851--876.","journal-title":"GPU Gems"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(90)90230-X"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2011.14"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/4.848212"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2010.107"},{"volume-title":"Proceedings of the 22nd International Conference on Parallel Architectures and Compilation Techniques (PACT\u201913)","author":"Jo Y.","key":"e_1_2_1_27_1","unstructured":"Y. Jo , M. Goldfarb , and M. Kulkarni . 2013. Automatic vectorization of tree traversals . In Proceedings of the 22nd International Conference on Parallel Architectures and Compilation Techniques (PACT\u201913) . IEEE, 363--374. Y. Jo, M. Goldfarb, and M. Kulkarni. 2013. Automatic vectorization of tree traversals. In Proceedings of the 22nd International Conference on Parallel Architectures and Compilation Techniques (PACT\u201913). IEEE, 363--374."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2048066.2048104"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2384616.2384643"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807206"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2145816.2145824"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1504176.1504181"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1837274.1837289"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(90)90231-O"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.706049"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1693453.1693457"},{"volume-title":"Proceedings of the IEEE International Symposium on Parallel and Distributed Processing (IPDPS\u201910)","author":"Meng J.","key":"e_1_2_1_37_1","unstructured":"J. Meng , J. W. Sheaffer , and K. Skadron . 2010. Exploiting inter-thread temporal locality for chip multithreading . In Proceedings of the IEEE International Symposium on Parallel and Distributed Processing (IPDPS\u201910) . IEEE, 1--12. J. Meng, J. W. Sheaffer, and K. Skadron. 2010. Exploiting inter-thread temporal locality for chip multithreading. In Proceedings of the IEEE International Symposium on Parallel and Distributed Processing (IPDPS\u201910). IEEE, 1--12."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2145816.2145832"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/359842.359859"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956898"},{"volume-title":"Software Methods for Improvement of Cache Performance on Supercomputer Applications","author":"Porterfield A.","key":"e_1_2_1_41_1","unstructured":"A. Porterfield . 1989. Software Methods for Improvement of Cache Performance on Supercomputer Applications . Rice University , Department of Computer Science. A. Porterfield. 1989. Software Methods for Improvement of Cache Performance on Supercomputer Applications. Rice University, Department of Computer Science."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/155332.155345"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335449"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2013.6494989"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/1039834.1039864"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/16.8.699"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542275.1542284"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-8-474"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402719"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88693-8_44"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCC.2010.44"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363387"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2009.05.002"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28652-0_2"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04342-0_14"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920991"},{"volume-title":"Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM\u201902)","author":"Yan X.","key":"e_1_2_1_57_1","unstructured":"X. Yan and J. Han . 2002. gSpan: Graph-based substructure pattern mining . In Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM\u201902) . IEEE, 721--724. X. Yan and J. Han. 2002. gSpan: Graph-based substructure pattern mining. In Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM\u201902). IEEE, 721--724."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/1950365.1950408"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/1693453.1693482"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/996841.996872"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2009.40"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2145816.2145833"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2632215","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2632215","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:56:13Z","timestamp":1750229773000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2632215"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6]]},"references-count":62,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,6]]}},"alternative-id":["10.1145\/2632215"],"URL":"https:\/\/doi.org\/10.1145\/2632215","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2014,6]]},"assertion":[{"value":"2013-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}