{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T04:32:32Z","timestamp":1767846752751,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":52,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,2,22]],"date-time":"2020-02-22T00:00:00Z","timestamp":1582329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["#CCF-1845763"],"award-info":[{"award-number":["#CCF-1845763"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["#DE-SC0008923, #DE-SC0018947"],"award-info":[{"award-number":["#DE-SC0008923, #DE-SC0018947"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Applications Driving Architectures (ADA) Research Center"},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["#HR0011-18-3-0007, #FA8750-17-2-0126"],"award-info":[{"award-number":["#HR0011-18-3-0007, #FA8750-17-2-0126"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Toyota Research Institute"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,2,22]]},"DOI":"10.1145\/3368826.3377909","type":"proceedings-article","created":{"date-parts":[[2020,2,21]],"date-time":"2020-02-21T21:49:28Z","timestamp":1582321768000},"page":"158-170","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":32,"title":["Optimizing ordered graph algorithms with GraphIt"],"prefix":"10.1145","author":[{"given":"Yunming","family":"Zhang","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}]},{"given":"Ajay","family":"Brahmakshatriya","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}]},{"given":"Xinyi","family":"Chen","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}]},{"given":"Laxman","family":"Dhulipala","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}]},{"given":"Shoaib","family":"Kamil","sequence":"additional","affiliation":[{"name":"Adobe Research, USA"}]},{"given":"Saman","family":"Amarasinghe","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}]},{"given":"Julian","family":"Shun","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}]}],"member":"320","published-online":{"date-parts":[[2020,2,22]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"2019. OpenStreetMap \u00a9OpenStreetMap contributors. https:\/\/www.openstreetmap.org\/."},{"key":"e_1_3_2_1_2_1","volume-title":"Chronos: Efficient Speculative Parallelism for Accelerators. In International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS).","author":"Abeydeera Maleen","year":"2020","unstructured":"Maleen Abeydeera and Daniel Sanchez. 2020. Chronos: Efficient Speculative Parallelism for Accelerators. In International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS)."},{"key":"e_1_3_2_1_3_1","volume-title":"Distributionally Linearizable Data Structures. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 133\u2013142","author":"Alistarh Dan","year":"2018","unstructured":"Dan Alistarh, Trevor Brown, Justin Kopinsky, Jerry Zheng Li, and Giorgi Nadiradze. 2018. Distributionally Linearizable Data Structures. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 133\u2013142."},{"key":"e_1_3_2_1_4_1","volume-title":"The SprayList: A Scalable Relaxed Priority Queue. In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP). 11\u201320","author":"Alistarh Dan","year":"2015","unstructured":"Dan Alistarh, Justin Kopinsky, Jerry Li, and Nir Shavit. 2015. The SprayList: A Scalable Relaxed Priority Queue. In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP). 11\u201320."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2628071.2628092"},{"key":"e_1_3_2_1_6_1","volume-title":"Tiramisu: A Polyhedral Compiler for Expressing Fast and Portable Code. In IEEE\/ACM International Symposium on Code Generation and Optimization (CGO). 193\u2013205","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. In IEEE\/ACM International Symposium on Code Generation and Optimization (CGO). 193\u2013205."},{"key":"e_1_3_2_1_7_1","volume-title":"Patterson","author":"Beamer Scott","year":"2015","unstructured":"Scott Beamer, Krste Asanovic, and David A. Patterson. 2015. The GAP Benchmark Suite. CoRR abs\/1508.03619 (2015). http:\/\/arxiv.org\/abs\/ 1508.03619"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1090\/qam\/102435"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018743.3018756"},{"key":"e_1_3_2_1_10_1","volume-title":"Linearwork Greedy Parallel Approximate Set Cover and Variants. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Blelloch Guy E.","year":"2011","unstructured":"Guy E. Blelloch, Richard Peng, and Kanat Tangwongsan. 2011. Linearwork Greedy Parallel Approximate Set Cover and Variants. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312024"},{"key":"e_1_3_2_1_12_1","volume-title":"Gluon: A Communication-optimizing Substrate for Distributed Heterogeneous Graph Analytics. In ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 752\u2013768","author":"Dathathri Roshan","year":"2018","unstructured":"Roshan Dathathri, Gurbinder Gill, Loc Hoang, Hoang-Vu Dang, Alex Brooks, Nikoli Dryden, Marc Snir, and Keshav Pingali. 2018. Gluon: A Communication-optimizing Substrate for Distributed Heterogeneous Graph Analytics. In ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 752\u2013768."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304056"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_3_2_1_15_1","volume-title":"9th DIMACS implementation challenge -shortest paths","author":"Demetrescu Camil","unstructured":"Camil Demetrescu, Andrew Goldberg, and David Johnson. 2019. 9th DIMACS implementation challenge -shortest paths. http:\/\/www.dis.uniroma1.it\/challenge9\/."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087580"},{"key":"e_1_3_2_1_17_1","volume-title":"Lowlatency Graph Streaming Using Compressed Purely-functional Trees. In ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 918\u2013934","author":"Dhulipala Laxman","year":"2019","unstructured":"Laxman Dhulipala, Guy E. Blelloch, and Julian Shun. 2019. Lowlatency Graph Streaming Using Compressed Purely-functional Trees. In ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 918\u2013934."},{"key":"e_1_3_2_1_18_1","volume-title":"Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201912)","author":"Gonzalez Joseph E.","year":"2012","unstructured":"Joseph E. Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin. 2012. PowerGraph: Distributed Graph-parallel Computation on Natural Graphs. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201912). 17\u201330."},{"key":"e_1_3_2_1_19_1","volume-title":"Making Pull-based Graph Processing Performant. In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP). 246\u2013260","author":"Grossman Samuel","year":"2018","unstructured":"Samuel Grossman, Heiner Litz, and Christos Kozyrakis. 2018. Making Pull-based Graph Processing Performant. In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP). 246\u2013260."},{"key":"e_1_3_2_1_20_1","volume-title":"Graphicionado: A High-performance and Energy-efficient Accelerator for Graph Analytics. In Annual IEEE\/ACM International Symposium on Microarchitecture (MICRO). 56:1\u201356:13","author":"Ham Tae Jun","year":"2016","unstructured":"Tae Jun Ham, Lisa Wu, Narayanan Sundaram, Nadathur Satish, and Margaret Martonosi. 2016. Graphicionado: A High-performance and Energy-efficient Accelerator for Graph Analytics. In Annual IEEE\/ACM International Symposium on Microarchitecture (MICRO). 56:1\u201356:13."},{"key":"e_1_3_2_1_21_1","volume-title":"KLA: A New Algorithmic Paradigm for Parallel Graph Computations. In International Conference on Parallel Architectures and Compilation (PACT). 27\u201338","author":"Fidel Adam","year":"2014","unstructured":"Harshvardhan, Adam Fidel, Nancy M. Amato, and Lawrence Rauchwerger. 2014. KLA: A New Algorithmic Paradigm for Parallel Graph Computations. In International Conference on Parallel Architectures and Compilation (PACT). 27\u201338."},{"key":"e_1_3_2_1_22_1","volume-title":"Unordered: A Comparison of Parallelism and Workefficiency in Irregular Algorithms. In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP). 3\u201312","author":"Hassaan Muhammad Amber","year":"2011","unstructured":"Muhammad Amber Hassaan, Martin Burtscher, and Keshav Pingali. 2011. Ordered vs. Unordered: A Comparison of Parallelism and Workefficiency in Irregular Algorithms. In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP). 3\u201312."},{"key":"e_1_3_2_1_23_1","volume-title":"Kinetic Dependence Graphs. In International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS). 457\u2013471","author":"Hassaan Muhammad Amber","unstructured":"Muhammad Amber Hassaan, Donald D. Nguyen, and Keshav K. Pingali. 2015. Kinetic Dependence Graphs. In International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS). 457\u2013471."},{"key":"e_1_3_2_1_24_1","volume-title":"Annual IEEE\/ACM International Symposium on Microarchitecture (MICRO). 1\u201313","author":"Jeffrey M. C.","unstructured":"M. C. Jeffrey, S. Subramanian, M. Abeydeera, J. Emer, and D. Sanchez. 2016. Data-centric execution of speculative parallel programs. In Annual IEEE\/ACM International Symposium on Microarchitecture (MICRO). 1\u201313."},{"key":"e_1_3_2_1_25_1","volume-title":"Annual IEEE\/ACM International Symposium on Microarchitecture (MICRO). 228\u2013241","author":"Jeffrey M. C.","unstructured":"M. C. Jeffrey, S. Subramanian, C. Yan, J. Emer, and D. Sanchez. 2015. A scalable architecture for ordered parallelism. In Annual IEEE\/ACM International Symposium on Microarchitecture (MICRO). 228\u2013241."},{"key":"e_1_3_2_1_26_1","volume-title":"Harmonizing Speculative and Non-Speculative Execution in Architectures for Ordered Parallelism. In Annual IEEE\/ACM International Symposium on Microarchitecture (MICRO). 217\u2013230","author":"Jeffrey M. C.","unstructured":"M. C. Jeffrey, V. A. Ying, S. Subramanian, H. R. Lee, J. Emer, and D. Sanchez. 2018. Harmonizing Speculative and Non-Speculative Execution in Architectures for Ordered Parallelism. In Annual IEEE\/ACM International Symposium on Microarchitecture (MICRO). 217\u2013230."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_3_2_1_28_1","volume-title":"USENIX Conference on Operating Systems Design and Implementation (OSDI). 31\u201346","author":"Kyrola Aapo","year":"2012","unstructured":"Aapo Kyrola, Guy Blelloch, and Carlos Guestrin. 2012. GraphChi: Large-scale Graph Computation on Just a PC. In USENIX Conference on Operating Systems Design and Implementation (OSDI). 31\u201346."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"e_1_3_2_1_30_1","volume-title":"ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP). 201\u2013213","author":"Meng Ke","year":"2019","unstructured":"Ke Meng, Jiajia Li, Guangming Tan, and Ninghui Sun. 2019. A Pattern Based Algorithmic Autotuner for Graph Processing on GP Us. In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP). 201\u2013213."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00076-2"},{"key":"e_1_3_2_1_32_1","volume-title":"Annual IEEE\/ACM International Symposium on Microarchitecture (MICRO). 1\u201314","author":"Mukkara A.","unstructured":"A. Mukkara, N. Beckmann, M. Abeydeera, X. Ma, and D. Sanchez. 2018. Exploiting Locality in Graph Analytics through Hardware-Accelerated Traversal Scheduling. In Annual IEEE\/ACM International Symposium on Microarchitecture (MICRO). 1\u201314."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3352460.3358254"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522739"},{"key":"e_1_3_2_1_35_1","volume-title":"ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA). 1\u201319","author":"Pai Sreepathi","year":"2016","unstructured":"Sreepathi Pai and Keshav Pingali. 2016. A Compiler for Throughput Optimization of Graph Algorithms on GP Us. In ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA). 1\u201319."},{"key":"e_1_3_2_1_36_1","volume-title":"Managing Large Graphs on Multi-cores with Graph Awareness. In USENIX Conference on Annual Technical Conference (ATC).","author":"Prabhakaran Vijayan","year":"2012","unstructured":"Vijayan Prabhakaran, Ming Wu, Xuetian Weng, Frank McSherry, Lidong Zhou, and Maya Haridasan. 2012. Managing Large Graphs on Multi-cores with Graph Awareness. In USENIX Conference on Annual Technical Conference (ATC)."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3150211"},{"key":"e_1_3_2_1_38_1","volume-title":"Ibrahim Abdelaziz, and Zuhair Khayyat.","author":"Sakr Sherif","year":"2017","unstructured":"Sherif Sakr, Faisal Moeen Orakzai, Ibrahim Abdelaziz, and Zuhair Khayyat. 2017. Large-Scale Graph Processing Using Apache Giraph (1st ed.). Springer Publishing Company, Incorporated."},{"key":"e_1_3_2_1_39_1","volume-title":"Ligra: A Lightweight Graph Processing Framework for Shared Memory. In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP). 135\u2013146","author":"Shun Julian","unstructured":"Julian Shun and Guy E. Blelloch. 2013. Ligra: A Lightweight Graph Processing Framework for Shared Memory. In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP). 135\u2013146."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3282495.3282501"},{"key":"e_1_3_2_1_41_1","volume-title":"ACM\/IEEE Annual International Symposium on Computer Architecture (ISCA). 587\u2013599","author":"Subramanian S.","unstructured":"S. Subramanian, M. C. Jeffrey, M. Abeydeera, H. R. Lee, V. A. Ying, J. Emer, and D. Sanchez. 2017. Fractal: An execution model for finegrain nested speculative parallelism. In ACM\/IEEE Annual International Symposium on Computer Architecture (ISCA). 587\u2013599."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809983"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3037697.3037748"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660193.2660227"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178487.3178508"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3108140"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304012"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0693-z"},{"key":"e_1_3_2_1_49_1","volume-title":"Wonderland: A Novel Abstraction-Based Out-Of-Core Graph Processing System. In International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS). 608\u2013621","author":"Zhang Mingxing","year":"2018","unstructured":"Mingxing Zhang, Yongwei Wu, Youwei Zhuo, Xuehai Qian, Chengying Huan, and Kang Chen. 2018. Wonderland: A Novel Abstraction-Based Out-Of-Core Graph Processing System. In International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS). 608\u2013621."},{"key":"e_1_3_2_1_50_1","volume-title":"Making Caches Work for Graph Analytics. In IEEE International Conference on Big Data (Big Data). 293\u2013302","author":"Zhang Yunming","year":"2017","unstructured":"Yunming Zhang, Vladimir Kiriansky, Charith Mendis, Saman Amarasinghe, and Matei Zaharia. 2017. Making Caches Work for Graph Analytics. In IEEE International Conference on Big Data (Big Data). 293\u2013302."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276491"},{"key":"e_1_3_2_1_52_1","volume-title":"Gemini: A Computation-Centric Distributed Graph Processing System. In USENIX Symposium on Operating Systems Design and Implementation (OSDI). 301\u2013316","author":"Zhu Xiaowei","year":"2016","unstructured":"Xiaowei Zhu, Wenguang Chen, Weimin Zheng, and Xiaosong Ma. 2016. Gemini: A Computation-Centric Distributed Graph Processing System. In USENIX Symposium on Operating Systems Design and Implementation (OSDI). 301\u2013316."}],"event":{"name":"CGO '20: 18th ACM\/IEEE International Symposium on Code Generation and Optimization","location":"San Diego CA USA","acronym":"CGO '20","sponsor":["SIGPLAN ACM Special Interest Group on Programming Languages","SIGMICRO ACM Special Interest Group on Microarchitectural Research and Processing","IEEE-CS Computer Society"]},"container-title":["Proceedings of the 18th ACM\/IEEE International Symposium on Code Generation and Optimization"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3368826.3377909","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3368826.3377909","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3368826.3377909","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:28Z","timestamp":1750202608000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3368826.3377909"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,22]]},"references-count":52,"alternative-id":["10.1145\/3368826.3377909","10.1145\/3368826"],"URL":"https:\/\/doi.org\/10.1145\/3368826.3377909","relation":{},"subject":[],"published":{"date-parts":[[2020,2,22]]},"assertion":[{"value":"2020-02-22","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}