{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T14:04:26Z","timestamp":1766066666650,"version":"3.45.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,12,26]],"date-time":"2017-12-26T00:00:00Z","timestamp":1514246400000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"HUJI Cyber Security Research Center in conjunction with the Israel National Cyber Bureau in the Prime Minister's Office"},{"name":"Sandia National Laboratories Truman Fellowship"},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Security Science and Engineering"},{"DOI":"10.13039\/501100011101","name":"Intel Collaborative Research Institute for Computational Intelligence","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100011101","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Operator of Sandia National Laboratories"},{"DOI":"10.13039\/501100006245","name":"Ministry of Science and Technology, Israel","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006245","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Einstein Foundation and the Minerva Foundation"},{"name":"Sandia Corporation"},{"DOI":"10.13039\/501100003973","name":"Israel Academy of Sciences and Humanities","doi-asserted-by":"crossref","award":["3-10891"],"award-info":[{"award-number":["3-10891"]}],"id":[{"id":"10.13039\/501100003973","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"crossref","award":["DE-AC04-94AL85000, 1878\/14 and 1901\/14"],"award-info":[{"award-number":["DE-AC04-94AL85000, 1878\/14 and 1901\/14"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"PetaCloud industry-academia consortium"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2016,12,26]]},"abstract":"<jats:p>We propose a fine-grained hypergraph model for sparse matrix-matrix multiplication (SpGEMM), a key computational kernel in scientific computing and data analysis whose performance is often communication bound. This model correctly describes both the interprocessor communication volume along a critical path in a parallel computation and also the volume of data moving through the memory hierarchy in a sequential computation. We show that identifying a communication-optimal algorithm for particular input matrices is equivalent to solving a hypergraph partitioning problem. Our approach is nonzero structure dependent, meaning that we seek the best algorithm for the given input matrices.<\/jats:p>\n                  <jats:p>In addition to our three-dimensional fine-grained model, we also propose coarse-grained one-dimensional and two-dimensional models that correspond to simpler SpGEMM algorithms. We explore the relations between our models theoretically, and we study their performance experimentally in the context of three applications that use SpGEMM as a key computation. For each application, we find that at least one coarse-grained model is as communication efficient as the fine-grained model. We also observe that different applications have affinities for different algorithms.<\/jats:p>\n                  <jats:p>Our results demonstrate that hypergraphs are an accurate model for reasoning about the communication costs of SpGEMM as well as a practical tool for exploring the SpGEMM algorithm design space.<\/jats:p>","DOI":"10.1145\/3015144","type":"journal-article","created":{"date-parts":[[2016,12,27]],"date-time":"2016-12-27T08:51:31Z","timestamp":1482828691000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":36,"title":["Hypergraph Partitioning for Sparse Matrix-Matrix Multiplication"],"prefix":"10.1145","volume":"3","author":[{"given":"Grey","family":"Ballard","sequence":"first","affiliation":[{"name":"Sandia National Laboratories"}]},{"given":"Alex","family":"Druinsky","sequence":"additional","affiliation":[{"name":"Lawrence Berkeley National Laboratory, Berkeley, CA"}]},{"given":"Nicholas","family":"Knight","sequence":"additional","affiliation":[{"name":"New York University, New York, NY"}]},{"given":"Oded","family":"Schwartz","sequence":"additional","affiliation":[{"name":"Hebrew University, Jerusalem, Israel"}]}],"member":"320","published-online":{"date-parts":[[2016,12,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/13092589X"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/100813956"},{"key":"e_1_2_1_3_1","volume-title":"Technical Report 1510.00844. arXiv.","author":"Azad A.","year":"2015","unstructured":"A. Azad, G. Ballard, A. Buluc, J. Demmel, L. Grigori, O. Schwartz, S. Toledo, and S. Williams. 2015a. Exploiting Multiple Levels of Parallelism in Sparse Matrix-matrix Multiplication. Technical Report 1510.00844. arXiv. Retrieved from http:\/\/arxiv.org\/abs\/1510.00844."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2015.75"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486196"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","unstructured":"G. Ballard E. Carson J. Demmel M. Hoemmen N. Knight and O. Schwartz. 2014. Communication lower bounds and optimal algorithms for numerical linear algebra. Acta Numer. 23 (May 2014) 1--155. DOI:http:\/\/dx.doi.org\/10.1017\/S0962492914000038 10.1017\/S0962492914000038","DOI":"10.1017\/S0962492914000038"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312021"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/090769156"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755613"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.2172\/1504845"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.2118\/173277-MS"},{"key":"e_1_2_1_12_1","volume-title":"Technical Report SAND2007-4748W. Sandia National Laboratories.","author":"Boman E.","year":"2007","unstructured":"E. Boman, K. Devine, L. Fisk, R. Heaphy, B. Hendrickson, C. Vaughan, \u00dc. \u00c7ataly\u00fcrek, D. Bozdag, W. Mitchell, and J. Teresco. 2007. Zoltan 3.0: Parallel Partitioning, Load Balancing, and Data-Management Services; User\u2019s Guide. Technical Report SAND2007-4748W. Sandia National Laboratories. Retrieved from http:\/\/www.cs.sandia.gov\/Zoltan\/ug_html\/ug.html."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2503210.2503293"},{"key":"e_1_2_1_14_1","volume-title":"Technical Report SAND2004-6440","author":"Boman E.","year":"2004","unstructured":"E. Boman, O. Parekh, and C. Phillips. 2005. LDRD Final Report on Massively-parallel Linear Programming: The parPCx System. Technical Report SAND2004-6440. Sandia National Laboratories. Retrieved from http:\/\/prod.sandia.gov\/techlib\/access-control.cgi\/2004\/046440.pdf."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2014.03.012"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29843-1_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2008.4536313"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/110848244"},{"key":"e_1_2_1_19_1","unstructured":"\u00dc. \u00c7ataly\u00fcrek and C. Aykanat. 1999. PaToH: Partitioning Tool for Hypergraphs. Technical Report. (Revised March 2011). Retrieved from http:\/\/bmi.osu.edu\/umit\/PaToH\/manual.pdf."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2001.925093"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/080737770"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.780863"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.2118\/173257-MS"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.2118\/72469-PA"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1023\/a:1009716300509"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718881"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2014.7004369"},{"volume-title":"Sparse Matrix Computations and Their I\/O Complexity. Dissertation. Technische Universit\u00e4t M\u00fcnchen","author":"Greiner G.","key":"e_1_2_1_29_1","unstructured":"G. Greiner. 2012. Sparse Matrix Computations and Their I\/O Complexity. Dissertation. Technische Universit\u00e4t M\u00fcnchen, M\u00fcnchen."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/355791.355796"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802486"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2004.03.021"},{"volume-title":"Adaptive Algebraic Multigrid for Finite Element Elliptic Equations with Random Coefficients. Master\u2019s thesis","author":"Kalchev D.","key":"e_1_2_1_33_1","unstructured":"D. Kalchev. 2012. Adaptive Algebraic Multigrid for Finite Element Elliptic Equations with Random Coefficients. Master\u2019s thesis. Sofia University."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/120895366"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2006.36"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/HiPC.2014.7116888"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","unstructured":"R. Pagh and M. St\u00f6ckel. 2014. The input\/output somplexity of sparse matrix multiplication. In Algorithms - ESA 2014 A. Schulz and D. Wagner (Eds.). Lecture Notes in Computer Science Vol.&nbsp;8737. Springer Berlin 750--761. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-662-44777-2_62 10.1007\/978-3-662-44777-2_62","DOI":"10.1007\/978-3-662-44777-2_62"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2807591.2807603"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90005-9"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557101"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1177\/1094342005051521"},{"key":"e_1_2_1_42_1","unstructured":"S. van Dongen. 2000. Graph Clustering by Flow Simulation. Ph.D. Dissertation. University of Utrecht."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144502409019"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19328-6_38"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3015144","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3015144","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3015144","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:48:01Z","timestamp":1763459281000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3015144"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,26]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,12,26]]}},"alternative-id":["10.1145\/3015144"],"URL":"https:\/\/doi.org\/10.1145\/3015144","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2016,12,26]]},"assertion":[{"value":"2016-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-10-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-12-26","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}