{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,21]],"date-time":"2025-11-21T17:55:55Z","timestamp":1763747755027,"version":"3.41.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,6,13]],"date-time":"2017-06-13T00:00:00Z","timestamp":1497312000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["1421505","1628401"],"award-info":[{"award-number":["1421505","1628401"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2017,6,13]]},"abstract":"<jats:p>\n            Graph\n            <jats:bold>edge<\/jats:bold>\n            partition models have recently become an appealing alternative to graph\n            <jats:bold>vertex<\/jats:bold>\n            partition models for distributed computing due to their flexibility in balancing loads and their performance in reducing communication cost [6, 16]. In this paper, we propose a simple yet effective graph edge partitioning algorithm. In practice, our algorithm provides good partition quality (and better than similar state-of-the-art edge partition approaches, at least for power-law graphs) while maintaining low partition overhead. In theory, previous work [6] showed that an approximation guarantee of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>\n              d\n              <jats:sub>max<\/jats:sub>\n            <\/jats:italic>\n            \u221a log\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>k<\/jats:italic>\n            ) apply to the graphs with\n            <jats:italic>m<\/jats:italic>\n            =\u03a9(\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) edges (\n            <jats:italic>k<\/jats:italic>\n            is the number of partitions). We further rigorously proved that this approximation guarantee hold for all graphs.\n          <\/jats:p>\n          <jats:p>We show how our edge partition model can be applied to parallel computing. We draw our example from GPU program locality enhancement and demonstrate that the graph edge partition model does not only apply to distributed computing with many computer nodes, but also to parallel computing in a single computer node with a many-core processor.<\/jats:p>","DOI":"10.1145\/3084451","type":"journal-article","created":{"date-parts":[[2018,3,23]],"date-time":"2018-03-23T18:28:08Z","timestamp":1521829688000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["A Simple Yet Effective Balanced Edge Partition Model for Parallel Computing"],"prefix":"10.1145","volume":"1","author":[{"given":"Lingda","family":"Li","sequence":"first","affiliation":[{"name":"Brookhaven National Laboratory, Upton, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robel","family":"Geda","sequence":"additional","affiliation":[{"name":"Rutgers University, New Brunswick, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ari B.","family":"Hayes","sequence":"additional","affiliation":[{"name":"Rutgers University, New Brunswick, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yanhao","family":"Chen","sequence":"additional","affiliation":[{"name":"Rutgers University, New Brunswick, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pranav","family":"Chaudhari","sequence":"additional","affiliation":[{"name":"Rutgers University, New Brunswick, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eddy Z.","family":"Zhang","sequence":"additional","affiliation":[{"name":"Rutgers University, new Brunswick, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mario","family":"Szegedy","sequence":"additional","affiliation":[{"name":"Rutgers University, New Brunswick, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,6,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2967938.2967945"},{"key":"e_1_2_1_2_1","volume-title":"Emergence of scaling in random networks. science, 286(5439):509--512","author":"Barab\u00e1si A.-L.","year":"1999","unstructured":"A.-L. Barab\u00e1si and R. Albert . Emergence of scaling in random networks. science, 286(5439):509--512 , 1999 . A.-L. Barab\u00e1si and R. Albert. Emergence of scaling in random networks. science, 286(5439):509--512, 1999."},{"key":"e_1_2_1_4_1","first-page":"125","volume-title":"Quality of Numerical Software","author":"Boisvert R. F.","year":"1996","unstructured":"R. F. Boisvert , R. Pozo , K. A. Remington , R. F. Barrett , and J. Dongarra . Matrix market: a web resource for test matrix collections . In Quality of Numerical Software , pages 125 -- 137 , 1996 . R. F. Boisvert, R. Pozo, K. A. Remington, R. F. Barrett, and J. Dongarra. Matrix market: a web resource for test matrix collections. In Quality of Numerical Software, pages 125--137, 1996."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375595"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623660"},{"key":"e_1_2_1_7_1","volume-title":"PaToH: a multilevel hypergraph partitioning tool, version 3.0","author":"Cataly\u00fcrek U. V.","year":"1999","unstructured":"U. V. Cataly\u00fcrek and C. Aykanat . PaToH: a multilevel hypergraph partitioning tool, version 3.0 . Bilkent University , Department of Computer Engineering, Ankara, 6533, 1999 . U. V. Cataly\u00fcrek and C. Aykanat. PaToH: a multilevel hypergraph partitioning tool, version 3.0. Bilkent University, Department of Computer Engineering, Ankara, 6533, 1999."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2009.5306797"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.2514\/6.2009-4001"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/fld.2254"},{"key":"e_1_2_1_11_1","unstructured":"S. Dalton and N. Bell. CUSP: A C  S. Dalton and N. Bell. CUSP: A C"},{"key":"e_1_2_1_12_1","unstructured":"templated sparse matrix library 2014.  templated sparse matrix library 2014."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/301618.301670"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2003.09.005"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796308217"},{"key":"e_1_2_1_17_1","first-page":"2","volume-title":"OSDI","volume":"12","author":"Gonzalez J. E.","year":"2012","unstructured":"J. E. Gonzalez , Y. Low , H. Gu , D. Bickson , and C. Guestrin . Powergraph: Distributed graph-parallel computation on natural graphs . In OSDI , volume 12 , page 2 , 2012 . J. E. Gonzalez, Y. Low, H. Gu, D. Bickson, and C. Guestrin. Powergraph: Distributed graph-parallel computation on natural graphs. In OSDI, volume 12, page 2, 2012."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(00)00048-X"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827598341475"},{"key":"e_1_2_1_20_1","volume-title":"Methods of conjugate gradients for solving linear systems","author":"Hestenes M. R.","year":"1952","unstructured":"M. R. Hestenes and E. Stiefel . Methods of conjugate gradients for solving linear systems . 1952 . M. R. Hestenes and E. Stiefel. Methods of conjugate gradients for solving linear systems. 1952."},{"key":"e_1_2_1_21_1","volume-title":"Metis-unstructured graph partitioning and sparse matrix ordering system, version 2.0","author":"Karypis G.","year":"1995","unstructured":"G. Karypis and V. Kumar . Metis-unstructured graph partitioning and sparse matrix ordering system, version 2.0 . 1995 . G. Karypis and V. Kumar. Metis-unstructured graph partitioning and sparse matrix ordering system, version 2.0. 1995."},{"key":"e_1_2_1_22_1","volume-title":"Department of Computer Science","author":"Karypis G.","year":"1998","unstructured":"G. Karypis and V. Kumar . hMETIS 1.5: A hypergraph partitioning package. Technical report , Department of Computer Science , University of Minnesota , 1998 . G. Karypis and V. Kumar. hMETIS 1.5: A hypergraph partitioning package. Technical report, Department of Computer Science, University of Minnesota, 1998."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496872"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_26_1","volume-title":"NVIDIA's Next Generation CUDA Compute Architecture: Kepler GK110","author":"NVIDIA.","year":"2012","unstructured":"NVIDIA. NVIDIA's Next Generation CUDA Compute Architecture: Kepler GK110 . 2012 . NVIDIA. NVIDIA's Next Generation CUDA Compute Architecture: Kepler GK110. 2012."},{"key":"e_1_2_1_27_1","volume-title":"cuSPARSE library","author":"NVIDIA.","year":"2014","unstructured":"NVIDIA. cuSPARSE library . 2014 . NVIDIA. cuSPARSE library. 2014."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556195.2556213"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442523"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1950365.1950408"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3084451","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3084451","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3084451","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:22Z","timestamp":1750217422000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3084451"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,13]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,6,13]]}},"alternative-id":["10.1145\/3084451"],"URL":"https:\/\/doi.org\/10.1145\/3084451","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2017,6,13]]},"assertion":[{"value":"2017-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}