{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T01:55:51Z","timestamp":1775786151313,"version":"3.50.1"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2019,11,8]],"date-time":"2019-11-08T00:00:00Z","timestamp":1573171200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF\/Intel Partnership on Computer Assisted Programming for Heterogeneous Architectures","award":["CCF-1723445"],"award-info":[{"award-number":["CCF-1723445"]}]},{"DOI":"10.13039\/100015599","name":"Toyota Research Institute","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100015599","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2019,12,31]]},"abstract":"<jats:p>\n            3D visual computing data are often spatially sparse. To exploit such sparsity, people have developed hierarchical sparse data structures, such as multi-level sparse voxel grids, particles, and 3D hash tables. However, developing and using these high-performance sparse data structures is challenging, due to their intrinsic complexity and overhead. We propose\n            <jats:italic>Taichi<\/jats:italic>\n            , a new data-oriented programming language for efficiently authoring, accessing, and maintaining such data structures. The language offers a high-level, data structure-agnostic interface for writing computation code. The user independently specifies the data structure. We provide several elementary components with different sparsity properties that can be arbitrarily composed to create a wide range of multi-level sparse data structures. This\n            <jats:italic>decoupling<\/jats:italic>\n            of data structures from computation makes it easy to experiment with different data structures without changing computation code, and allows users to write computation as if they are working with a dense array. Our compiler then uses the semantics of the data structure and index analysis to automatically optimize for locality, remove redundant operations for coherent accesses, maintain sparsity and memory allocations, and generate efficient parallel and vectorized instructions for CPUs and GPUs.\n          <\/jats:p>\n          <jats:p>\n            Our approach yields competitive performance on common computational kernels such as stencil applications, neighbor lookups, and particle scattering. We demonstrate our language by implementing simulation, rendering, and vision tasks including a material point method simulation, finite element analysis, a multigrid Poisson solver for pressure projection, volumetric path tracing, and 3D convolution on sparse grids. Our computation-data structure decoupling allows us to quickly experiment with different data arrangements, and to develop high-performance data structures tailored for specific computational tasks. With\n            <jats:sub>1<\/jats:sub>\n            &lt;u&gt;\n            <jats:sup>1<\/jats:sup>\n            &lt;\/u&gt;\n            <jats:sub>0<\/jats:sub>\n            th as many lines of code, we achieve 4.55\u00d7 higher performance on average, compared to hand-optimized reference implementations.\n          <\/jats:p>","DOI":"10.1145\/3355089.3356506","type":"journal-article","created":{"date-parts":[[2019,11,8]],"date-time":"2019-11-08T20:27:58Z","timestamp":1573244878000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":217,"title":["Taichi"],"prefix":"10.1145","volume":"38","author":[{"given":"Yuanming","family":"Hu","sequence":"first","affiliation":[{"name":"MIT CSAIL"}]},{"given":"Tzu-Mao","family":"Li","sequence":"additional","affiliation":[{"name":"MIT CSAIL and UC Berkeley"}]},{"given":"Luke","family":"Anderson","sequence":"additional","affiliation":[{"name":"MIT CSAIL"}]},{"given":"Jonathan","family":"Ragan-Kelley","sequence":"additional","affiliation":[{"name":"UC Berkeley"}]},{"given":"Fr\u00e9do","family":"Durand","sequence":"additional","affiliation":[{"name":"MIT CSAIL"}]}],"member":"320","published-online":{"date-parts":[[2019,11,8]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"Mike Acton. 2014. Data-oriented design and C++. (2014). https:\/\/www.youtube.com\/watch?v=rX0ItVEVjHc"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276495"},{"key":"e_1_2_2_3_1","volume-title":"PENCIL: A platform-neutral compute intermediate language for accelerator programming. In Parallel Architecture and Compilation","author":"Baghdadi Riyadh","year":"2015","unstructured":"Riyadh Baghdadi, Ulysse Beaugnon, Albert Cohen, Tobias Grosser, Michael Kruse, Chandan Reddy, Sven Verdoolaege, Adam Betts, Alastair F Donaldson, Jeroen Ketema, et al. 2015. PENCIL: A platform-neutral compute intermediate language for accelerator programming. In Parallel Architecture and Compilation. IEEE, 138--149."},{"key":"e_1_2_2_4_1","volume-title":"Emanuele Del Sozzo, Abdurrahman Akkas, Yunming Zhang, Patricia Suriana, Shoaib Kamil, and Saman Amarasinghe.","author":"Baghdadi Riyadh","year":"2019","unstructured":"Riyadh Baghdadi, Jessica Ray, Malek Ben Romdhane, Emanuele Del Sozzo, Abdurrahman Akkas, Yunming Zhang, Patricia Suriana, Shoaib Kamil, and Saman Amarasinghe. 2019. Tiramisu: A polyhedral compiler for expressing fast and portable code. Code Generation and Optimization (2019), 193--205."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2504459.2504478"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2892632"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461940"},{"key":"e_1_2_2_9_1","first-page":"1","article-title":"Sympiler: Transforming sparse matrix codes by decoupling symbolic analysis. In International Conference for High Performance Computing","volume":"13","author":"Cheshmi Kazem","year":"2017","unstructured":"Kazem Cheshmi, Shoaib Kamil, Michelle Mills Strout, and Maryam Mehri Dehnavi. 2017. Sympiler: Transforming sparse matrix codes by decoupling symbolic analysis. In International Conference for High Performance Computing, Networking, Storage and Analysis. ACM, 13:1--13:13.","journal-title":"Networking, Storage and Analysis. ACM"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2018.00065"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276493"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(88)90094-4"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063384.2063396"},{"key":"e_1_2_2_14_1","first-page":"102","article-title":"GPU Optimization of Material Point Methods","volume":"32","author":"Gao Ming","year":"2018","unstructured":"Ming Gao, Xinlei Wang, Kui Wu, Andre Pradhana-Tampubolon, Eftychios Sifakis, Yuksel Cem, and Chenfanfu Jiang. 2018. GPU Optimization of Material Point Methods. ACM Trans. Graph. (Proc. SIGGRAPH Asia) 32, 4 (2018), 102.","journal-title":"ACM Trans. Graph. (Proc. SIGGRAPH Asia)"},{"key":"e_1_2_2_15_1","doi-asserted-by":"crossref","unstructured":"Benjamin Graham Martin Engelcke and Laurens van der Maaten. 2018. 3D semantic segmentation with submanifold sparse convolutional networks. In Computer Vision and Pattern Recognition. 9224--9232.","DOI":"10.1109\/CVPR.2018.00961"},{"key":"e_1_2_2_16_1","volume-title":"Proceedings of High Performance Graphics. Eurographics Association, 109--117","author":"Hoetzlein Rama Karl","year":"2016","unstructured":"Rama Karl Hoetzlein. 2016. GVDB: Raytracing sparse voxel database structures on the GPU. In Proceedings of High Performance Graphics. Eurographics Association, 109--117."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1122501.1122508"},{"key":"e_1_2_2_18_1","volume-title":"Taichi: An open-source computer graphics library. arXiv preprint arXiv:1804.09293","author":"Hu Yuanming","year":"2018","unstructured":"Yuanming Hu. 2018. Taichi: An open-source computer graphics library. arXiv preprint arXiv:1804.09293 (2018)."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201293"},{"key":"e_1_2_2_20_1","unstructured":"Wenzel Jakob. 2010. Mitsuba renderer. (2010). http:\/\/www.mitsuba-renderer.org."},{"key":"e_1_2_2_21_1","volume-title":"Eurographics Symposium on Geometry Processing","volume":"7","author":"Kazhdan Michael","year":"2006","unstructured":"Michael Kazhdan, Matthew Bolitho, and Hugues Hoppe. 2006. Poisson surface reconstruction. In Eurographics Symposium on Geometry Processing, Vol. 7."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133901"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2866569"},{"key":"e_1_2_2_24_1","volume-title":"LLVM: A compilation framework for lifelong program analysis & transformation. In Code Generation and Optimization.","author":"Lattner Chris","year":"2004","unstructured":"Chris Lattner and Vikram Adve. 2004. LLVM: A compilation framework for lifelong program analysis & transformation. In Code Generation and Optimization."},{"key":"e_1_2_2_25_1","doi-asserted-by":"crossref","unstructured":"Mark Lee Brian Green Feng Xie and Eric Tabellion. 2017. Vectorized Production Path Tracing. In High Performance Graphics.","DOI":"10.1145\/3105762.3105768"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2370036.2145825"},{"key":"e_1_2_2_27_1","article-title":"Narrow-band Topology Optimization on a Sparsely Populated Grid","volume":"37","author":"Liu Haixiang","year":"2018","unstructured":"Haixiang Liu, Yuanming Hu, Bo Zhu, Wojciech Matusik, and Eftychios Sifakis. 2018. Narrow-band Topology Optimization on a Sparsely Populated Grid. ACM Trans. Graph. (Proc. SIGGRAPH Asia) 37, 6 (2018), 251:1--251:14.","journal-title":"ACM Trans. Graph. (Proc. SIGGRAPH Asia)"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015745"},{"key":"e_1_2_2_29_1","volume-title":"Symposium on Computer Animation. ACM\/Eurographics Association, 65--74","author":"McAdams Aleka","year":"2010","unstructured":"Aleka McAdams, Eftychios Sifakis, and Joseph Teran. 2010. A parallel multigrid Poisson solver for fluids simulation on large grids. In Symposium on Computer Animation. ACM\/Eurographics Association, 65--74."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786763.2694364"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487228.2487235"},{"key":"e_1_2_2_32_1","doi-asserted-by":"crossref","unstructured":"Ken Museth. 2014. Hierarchical digital differential analyzer for efficient ray-marching in OpenVDB. (2014).","DOI":"10.1145\/2614106.2614136"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897839.2927399"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-005-9062-8"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(88)90002-2"},{"key":"e_1_2_2_36_1","doi-asserted-by":"crossref","unstructured":"Matt Pharr Craig Kolb Reid Gershbein and Pat Hanrahan. 1997. Rendering Complex Scenes with Memory-coherent Ray Tracing. In SIGGRAPH. ACM 101--108.","DOI":"10.1145\/258734.258791"},{"key":"e_1_2_2_37_1","doi-asserted-by":"crossref","unstructured":"Matt Pharr and William R Mark. 2012. ispc: A SPMD compiler for high-performance CPU programming. In Innovative Parallel Computing. 1--13.","DOI":"10.1109\/InPar.2012.6339601"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185528"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499370.2462176"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2017.701"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661269"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461948"},{"key":"e_1_2_2_43_1","volume-title":"OpenCL: A parallel programming standard for heterogeneous computing systems. Computing in science & engineering 12, 3","author":"Stone John E","year":"2010","unstructured":"John E Stone, David Gohara, and Guochun Shi. 2010. OpenCL: A parallel programming standard for heterogeneous computing systems. Computing in science & engineering 12, 3 (2010), 66--73."},{"key":"e_1_2_2_44_1","volume-title":"Application of a particlein-cell method to solid mechanics. Computer physics communications 87, 1--2","author":"Sulsky Deborah","year":"1995","unstructured":"Deborah Sulsky, Shi-Jian Zhou, and Howard L Schreyer. 1995. Application of a particlein-cell method to solid mechanics. Computer physics communications 87, 1--2 (1995), 236--252."},{"key":"e_1_2_2_45_1","volume-title":"Tensor comprehensions: Framework-agnostic high-performance machine learning abstractions. arXiv:1802.04730","author":"Vasilache Nicolas","year":"2018","unstructured":"Nicolas Vasilache, Oleksandr Zinenko, Theodoros Theodoridis, Priya Goyal, Zachary DeVito, William S Moses, Sven Verdoolaege, Andrew Adams, and Albert Cohen. 2018. Tensor comprehensions: Framework-agnostic high-performance machine learning abstractions. arXiv:1802.04730 (2018)."},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3073608"},{"key":"e_1_2_2_47_1","article-title":"Adaptive O-CNN: A patch-based deep representation of 3D shapes","volume":"37","author":"Wang Peng-Shuai","year":"2018","unstructured":"Peng-Shuai Wang, Chun-Yu Sun, Yang Liu, and Xin Tong. 2018. Adaptive O-CNN: A patch-based deep representation of 3D shapes. ACM Transactions on Graphics (SIGGRAPH Asia) 37, 6 (2018).","journal-title":"ACM Transactions on Graphics (SIGGRAPH Asia)"},{"key":"e_1_2_2_48_1","volume-title":"Owens","author":"Wang Yangzihao","year":"2016","unstructured":"Yangzihao Wang, Andrew Davidson, Yuechao Pan, Yuduo Wu, Andy Riffel, and John D. Owens. 2016. Gunrock: A high-performance graph processing library on the GPU. SIGPLAN Not. 51, 8 (2016), 11:1--11:12."},{"key":"e_1_2_2_49_1","volume-title":"Applications of Computing Methods to Reactor Problems","author":"Woodcock E","unstructured":"E Woodcock, T Murphy, P Hemmings, and S Longworth. 1965. Techniques used in the GEM code for Monte Carlo neutronics calculations in reactors and other systems of complex geometry. In Applications of Computing Methods to Reactor Problems, Vol. 557."},{"key":"e_1_2_2_50_1","volume-title":"Computer Graphics Forum (Proc. Eurographics)","author":"Wu Kui","unstructured":"Kui Wu, Nghia Truong, Cem Yuksel, and Rama Hoetzlein. 2018. Fast fluid simulations with sparse volumes on the GPU. In Computer Graphics Forum (Proc. Eurographics), Vol. 37. Wiley Online Library, 157--167."},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276491"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073298"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3355089.3356506","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3355089.3356506","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:41Z","timestamp":1750203881000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3355089.3356506"}},"subtitle":["a language for high-performance computation on spatially sparse data structures"],"short-title":[],"issued":{"date-parts":[[2019,11,8]]},"references-count":51,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,12,31]]}},"alternative-id":["10.1145\/3355089.3356506"],"URL":"https:\/\/doi.org\/10.1145\/3355089.3356506","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,8]]},"assertion":[{"value":"2019-11-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}