{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T01:22:59Z","timestamp":1767835379664,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":60,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,17]],"date-time":"2023-06-17T00:00:00Z","timestamp":1686960000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100008902","name":"Los Alamos National Laboratory","doi-asserted-by":"publisher","award":["89233218CNA000001, 20230692ER"],"award-info":[{"award-number":["89233218CNA000001, 20230692ER"]}],"id":[{"id":"10.13039\/100008902","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011039","name":"Intelligence Advanced Research Projects Activity","doi-asserted-by":"publisher","award":["W911NF22C0081"],"award-info":[{"award-number":["W911NF22C0081"]}],"id":[{"id":"10.13039\/100011039","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,17]]},"DOI":"10.1145\/3558481.3591073","type":"proceedings-article","created":{"date-parts":[[2023,5,31]],"date-time":"2023-05-31T22:22:03Z","timestamp":1685571723000},"page":"165-176","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["In-network Allreduce with Multiple Spanning Trees on PolarFly"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9414-8481","authenticated-orcid":false,"given":"Kartik","family":"Lakhotia","sequence":"first","affiliation":[{"name":"Intel Labs, Santa Clara, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7979-0516","authenticated-orcid":false,"given":"Kelly","family":"Isham","sequence":"additional","affiliation":[{"name":"Colgate University, Hamilton, OH, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7175-0103","authenticated-orcid":false,"given":"Laura","family":"Monroe","sequence":"additional","affiliation":[{"name":"Los Alamos National Laboratory, Los Alamos, NM, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6550-7916","authenticated-orcid":false,"given":"Maciej","family":"Besta","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1333-9797","authenticated-orcid":false,"given":"Torsten","family":"Hoefler","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4977-7107","authenticated-orcid":false,"given":"Fabrizio","family":"Petrini","sequence":"additional","affiliation":[{"name":"Intel Labs, Santa Clara, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,17]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Stijn Eyerman, Joshua B Fryman, Ivan Ganev, Wim Heirman, et al.","author":"Aananthakrishnan Sriram","year":"2020","unstructured":"Sriram Aananthakrishnan, Nesreen K Ahmed, Vincent Cave, Marcelo Cintra, Yigit Demir, Kristof Du Bois, Stijn Eyerman, Joshua B Fryman, Ivan Ganev, Wim Heirman, et al. 2020. PIUMA: programmable integrated unified memory architecture."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/HOTI.2010.16"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.26493\/1855-3974.527.74e"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1953-0054978-4"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2014.34"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/HiPC.2013.6799144"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/3495724.3495883"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1966-036-2"},{"key":"e_1_3_2_1_10_1","first-page":"241","article-title":"Blueconnect: Decomposing all-reduce for deep learning on heterogeneous network hierarchy","volume":"1","author":"Cho Minsik","year":"2019","unstructured":"Minsik Cho, Ulrich Finkler, David Kung, and Hillery Hunter. 2019. Blueconnect: Decomposing all-reduce for deep learning on heterogeneous network hierarchy. Proceedings of Machine Learning and Systems 1 (2019), 241--251.","journal-title":"Proceedings of Machine Learning and Systems"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3458817.3476178"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/3014904.3014928"},{"key":"e_1_3_2_1_13_1","volume-title":"On a problem in the theory of graphs. Publ. Math. Inst. Hungar. Acad. Sci. 7A","author":"Erd's Paul","year":"1962","unstructured":"Paul Erd's and Alfred R\u00e9nyi. 1962. On a problem in the theory of graphs. Publ. Math. Inst. Hungar. Acad. Sci. 7A (1962), 623--641."},{"key":"e_1_3_2_1_14_1","first-page":"48","article-title":"Graphs derived from perfect difference sets","volume":"80","author":"Erskine Grahame","year":"2021","unstructured":"Grahame Erskine, Peter Fratri\u010d, and Jozef ?ir\u00e1\u0148. 2021. Graphs derived from perfect difference sets. Australas. J Comb. 80 (2021), 48--56.","journal-title":"Australas. J Comb."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542275.1542344"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1183401.1183431"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316339831"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30218-6_19"},{"key":"e_1_3_2_1_19_1","volume-title":"Proceedings of Machine Learning and Systems 3","author":"Gebara Nadeen","year":"2021","unstructured":"Nadeen Gebara, Manya Ghobadi, and Costa Paolo. 2021. In-network Aggregation for Shared Machine Learning Clusters. Proceedings of Machine Learning and Systems 3 (2021)."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/COMHPC.2016.006"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-50743-5_3"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45825-5_5"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2015.42"},{"key":"e_1_3_2_1_24_1","volume-title":"Targeted Branching for the Maximum Independent Set Problem. In 19th International Symposium on Experimental Algorithms (SEA","author":"Hespe Demian","year":"2021","unstructured":"Demian Hespe, Sebastian Lamm, and Christian Schorr. 2021. Targeted Branching for the Maximum Independent Set Problem. In 19th International Symposium on Experimental Algorithms (SEA 2021). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC41404.2022.00016"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2007.06.006"},{"key":"e_1_3_2_1_27_1","volume-title":"Energy, memory, and runtime tradeoffs for implementing collective communication operations. Supercomputing frontiers and innovations 1, 2","author":"Hoefler Torsten","year":"2014","unstructured":"Torsten Hoefler and Dmitry Moor. 2014. Energy, memory, and runtime tradeoffs for implementing collective communication operations. Supercomputing frontiers and innovations 1, 2 (2014), 58--75."},{"key":"e_1_3_2_1_28_1","volume-title":"Galois: A performant NumPy extension for Galois fields. https:\/\/github.com\/mhostetter\/galois","author":"Hostetter Matt","year":"2020","unstructured":"Matt Hostetter. 2020. Galois: A performant NumPy extension for Galois fields. https:\/\/github.com\/mhostetter\/galois"},{"key":"e_1_3_2_1_29_1","volume-title":"The On-Line Encyclopedia of Integer Sequences: Sequence A333852. https:\/\/oeis.org\/A333852","author":"OEIS Foundation Inc. 2023.","unstructured":"OEIS Foundation Inc. 2023. The On-Line Encyclopedia of Integer Sequences: Sequence A333852. https:\/\/oeis.org\/A333852."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810085.1810093"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/MLHPC.2016.006"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA45697.2020.00085"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1177\/1094342014552086"},{"key":"e_1_3_2_1_34_1","volume-title":"BoomGate: Deadlock Avoidance in Non-Minimal Routing for High-Radix Networks. In 2021 IEEE International Symposium on High-Performance Computer Architecture (HPCA). IEEE, 696--708","author":"Kwauk Gyuyoung","year":"2021","unstructured":"Gyuyoung Kwauk, Seungkwan Kang, Hans Kasan, Hyojun Son, and John Kim. 2021. BoomGate: Deadlock Avoidance in Non-Minimal Routing for High-Radix Networks. In 2021 IEEE International Symposium on High-Performance Computer Architecture (HPCA). IEEE, 696--708."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC41404.2022.00017"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2021.3139092"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/HOTI52880.2021.00015"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/HiPC56025.2022.00020"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3392717.3392747"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3307650.3322259"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0898-1221(97)84597-X"},{"key":"e_1_3_2_1_42_1","volume-title":"Finite Fields for Computer Scientists and Engineers","author":"McEliece Robert J.","unstructured":"Robert J. McEliece. 1987. Finite Fields for Computer Scientists and Engineers. Springer, Boston, MA."},{"key":"e_1_3_2_1_43_1","unstructured":"D.S. Mitrinovi\u0107 J. S\u00e1ndor and B. Crstici. 1995. Handbook of Number Theory. Kluwer Academic Publishers Dordrecht. 9 pages."},{"key":"e_1_3_2_1_44_1","volume-title":"Accurate runtime selection of optimal MPI collective algorithms using analytical performance modelling. arXiv preprint arXiv:2004.11062","author":"Nuriyev Emin","year":"2020","unstructured":"Emin Nuriyev and Alexey Lastovetsky. 2020. Accurate runtime selection of optimal MPI collective algorithms using analytical performance modelling. arXiv preprint arXiv:2004.11062 (2020)."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01836217"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2008.09.002"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10586-007-0012-0"},{"key":"e_1_3_2_1_48_1","volume-title":"European Conference on Parallel Processing. Springer, 107--117","author":"Pjeivac-Grbovi\u0107 Jelena","year":"2007","unstructured":"Jelena Pjeivac-Grbovi\u0107, George Bosilca, Graham E Fagg, Thara Angskun, and Jack J Dongarra. 2007. Decision trees and MPI collective algorithm selection problem. In European Conference on Parallel Processing. Springer, 107--117."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2016.05.014"},{"key":"e_1_3_2_1_50_1","volume-title":"42nd cug conference. 396--405.","author":"Rabenseifner Rolf","unstructured":"Rolf Rabenseifner. 2000. Automatic MPI counter profiling. In 42nd cug conference. 396--405."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24685-5_1"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2018.00064"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2686882"},{"key":"e_1_3_2_1_54_1","volume-title":"18th USENIX Symposium on Networked Systems Design and Implementation (NSDI 21)","author":"Sapio Amedeo","year":"2021","unstructured":"Amedeo Sapio, Marco Canini, Chen-Yu Ho, Jacob Nelson, Panos Kalnis, Changhoon Kim, Arvind Krishnamurthy, Masoud Moshref, Dan Ports, and Peter Richtarik. 2021. Scaling Distributed Machine Learning with {In-Network} Aggregation. In 18th USENIX Symposium on Networked Systems Design and Implementation (NSDI 21). 785--808."},{"key":"e_1_3_2_1_55_1","volume-title":"Horovod: fast and easy distributed deep learning in TensorFlow. CoRR abs\/1802.05799","author":"Sergeev Alexander","year":"2018","unstructured":"Alexander Sergeev and Mike Del Balso. 2018. Horovod: fast and easy distributed deep learning in TensorFlow. CoRR abs\/1802.05799 (2018). arXiv:1802.05799 http:\/\/arxiv.org\/abs\/1802.05799"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1938-1501951-4"},{"key":"e_1_3_2_1_57_1","volume-title":"Combinatorial Designs: Constructions and Analysis","author":"Stimson Douglas R.","year":"2004","unstructured":"Douglas R. Stimson. 2004. Combinatorial Designs: Constructions and Analysis. Springer, New York, NY. 52--54 pages."},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39924-7_38"},{"key":"e_1_3_2_1_59_1","volume-title":"The PARI Group","author":"The PARI Group 2022. PARI\/GP version 2.13.4.","unstructured":"The PARI Group 2022. PARI\/GP version 2.13.4. The PARI Group, Univ. Bordeaux. available from http:\/\/pari.math.u-bordeaux.fr\/."},{"key":"e_1_3_2_1_60_1","unstructured":"Udayanga Wickramasinghe and Andrew Lumsdaine. 2016. A survey of methods for collective communication optimization and tuning. arXiv preprint arXiv:1611.06334 (2016)"}],"event":{"name":"SPAA '23: 35th ACM Symposium on Parallelism in Algorithms and Architectures","location":"Orlando FL USA","acronym":"SPAA '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"]},"container-title":["Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3558481.3591073","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3558481.3591073","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3558481.3591073","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:33Z","timestamp":1750182573000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3558481.3591073"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,17]]},"references-count":60,"alternative-id":["10.1145\/3558481.3591073","10.1145\/3558481"],"URL":"https:\/\/doi.org\/10.1145\/3558481.3591073","relation":{},"subject":[],"published":{"date-parts":[[2023,6,17]]},"assertion":[{"value":"2023-06-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}