{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T15:47:03Z","timestamp":1775231223650,"version":"3.50.1"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,6,30]],"date-time":"2018-06-30T00:00:00Z","timestamp":1530316800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NVIDIA Corporation"},{"DOI":"10.13039\/100000001","name":"U.S. National Science Foundation","doi-asserted-by":"crossref","award":["1406304"],"award-info":[{"award-number":["1406304"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2018,6,30]]},"abstract":"<jats:p>Computing a maximal independent set is an important step in many parallel graph algorithms. This article introduces ECL-MIS, a maximal independent set implementation that works well on GPUs. It includes key optimizations to speed up computation, reduce the memory footprint, and increase the set size. Its CUDA implementation requires fewer than 30 kernel statements, runs asynchronously, and produces a deterministic result. It outperforms the maximal independent set implementations of Pannotia, CUSP, and IrGL on each of the 16 tested graphs of various types and sizes. On a Titan X GPU, ECL-MIS is between 3.9 and 100 times faster (11.5 times, on average). ECL-MIS running on the GPU is also faster than the parallel CPU codes Ligra, Ligra+, and PBBS running on 20 Xeon cores, which it outperforms by 4.1 times, on average. At the same time, ECL-MIS produces maximal independent sets that are up to 52% larger (over 10%, on average) compared to these preexisting CPU and GPU implementations. Whereas these codes produce maximal independent sets that are, on average, about 15% smaller than the largest possible such sets, ECL-MIS sets are less than 6% smaller than the maximum independent sets.<\/jats:p>","DOI":"10.1145\/3291525","type":"journal-article","created":{"date-parts":[[2018,12,10]],"date-time":"2018-12-10T13:09:16Z","timestamp":1544447356000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["A High-Quality and Fast Maximal Independent Set Implementation for GPUs"],"prefix":"10.1145","volume":"5","author":[{"given":"Martin","family":"Burtscher","sequence":"first","affiliation":[{"name":"Department of Computer Science, Texas State University, San Marcos, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sindhu","family":"Devale","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Texas State University, San Marcos, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sahar","family":"Azimi","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Texas State University, San Marcos, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jayadharini","family":"Jaiganesh","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Texas State University, San Marcos, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Evan","family":"Powers","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Texas State University, San Marcos, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,12,8]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 5th Copper Mountain Conference on Iterative Methods. http:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi&equals;10","author":"Adams Mark F.","year":"1998","unstructured":"Mark F. Adams . 1998 . A parallel maximal independent set algorithm . In Proceedings of the 5th Copper Mountain Conference on Iterative Methods. http:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi&equals;10 .1.1.40.8968. Mark F. Adams. 1998. A parallel maximal independent set algorithm. In Proceedings of the 5th Copper Mountain Conference on Iterative Methods. http:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi&equals;10.1.1.40.8968."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.09.023"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312058"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035939"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2013.6704684"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718133.ch10"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-38851-9_9"},{"key":"e_1_2_1_8_1","volume-title":"CUSP: Generic parallel algorithms for sparse matrix and graph computations. Version 0.5.0","author":"Dalton Steven","year":"2014","unstructured":"Steven Dalton , Nathan Bell , Luke Olson , and Michael Garland . 2014 . CUSP: Generic parallel algorithms for sparse matrix and graph computations. Version 0.5.0 . http:\/\/cusplibrary.github.io\/. Steven Dalton, Nathan Bell, Luke Olson, and Michael Garland. 2014. CUSP: Generic parallel algorithms for sparse matrix and graph computations. Version 0.5.0. http:\/\/cusplibrary.github.io\/."},{"key":"e_1_2_1_9_1","unstructured":"Camil Demetrescu. 2010. DIMACS9 (June 2010). Retrieved June 6 2017 from http:\/\/www.dis.uniroma1.it\/challenge9\/download.shtml.  Camil Demetrescu. 2010. DIMACS9 (June 2010). Retrieved June 6 2017 from http:\/\/www.dis.uniroma1.it\/challenge9\/download.shtml."},{"key":"e_1_2_1_10_1","volume-title":"Walker","author":"Fox Geoffrey C.","year":"1988","unstructured":"Geoffrey C. Fox , Mark A. Johnson , Gregory A. Lyzenga , Steve W. Otto , John K. Salmon , and David W . Walker . 1988 . Solving Problems on Concurrent Processors, General Techniques and Regular Problems, Vol. 1 . Prentice-Hall , Inc., Upper Saddle, NJ. Geoffrey C. Fox, Mark A. Johnson, Gregory A. Lyzenga, Steve W. Otto, John K. Salmon, and David W. Walker. 1988. Solving Problems on Concurrent Processors, General Techniques and Regular Problems, Vol. 1. Prentice-Hall, Inc., Upper Saddle, NJ."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884455"},{"key":"e_1_2_1_12_1","volume-title":"Retrieved","author":"Hub Git","year":"2016","unstructured":"Git Hub . 2016 . Ligra . Retrieved November 15, 2018 from https:\/\/github.com\/jshun\/ligra. Git Hub. 2016. Ligra. Retrieved November 15, 2018 from https:\/\/github.com\/jshun\/ligra."},{"key":"e_1_2_1_13_1","volume-title":"Retrieved","author":"Hub Git","year":"2017","unstructured":"Git Hub . 2017 . Pannotia . Retrieved November 15, 2018 from https:\/\/github.com\/pannotia\/pannotia. Git Hub. 2017. Pannotia. Retrieved November 15, 2018 from https:\/\/github.com\/pannotia\/pannotia."},{"key":"e_1_2_1_14_1","volume-title":"Owens","author":"Gupta Kshitij","year":"2012","unstructured":"Kshitij Gupta , Jeff A. Stuart , and John D . Owens . 2012 . A study of persistent threads style GPU programming for GPGPU workloads. In Innovative Parallel Computing (InPar\u201912). San Jose, CA , 1--14. Kshitij Gupta, Jeff A. Stuart, and John D. Owens. 2012. A study of persistent threads style GPU programming for GPGPU workloads. In Innovative Parallel Computing (InPar\u201912). San Jose, CA, 1--14."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612697"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248435"},{"key":"e_1_2_1_17_1","volume-title":"Retrieved","author":"ISS.","year":"2014","unstructured":"ISS. 2014 . Galois . Retrieved November 15, 2018 from http:\/\/iss.ices.utexas.edu\/?p=projects\/galois\/download. ISS. 2014. Galois. Retrieved November 15, 2018 from http:\/\/iss.ices.utexas.edu\/?p=projects\/galois\/download."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.engappai.2014.08.007"},{"key":"e_1_2_1_19_1","unstructured":"KaMIS. 2017. Retrieved November 15 2018 from http:\/\/algo2.iti.kit.edu\/kamis\/.  KaMIS. 2017. Retrieved November 15 2018 from http:\/\/algo2.iti.kit.edu\/kamis\/."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808690"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-017-9337-x"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/22145.22146"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1693453.1693457"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2458523.2458533"},{"key":"e_1_2_1_26_1","unstructured":"NearLinear. Retrieved November 15 2018 from https:\/\/github.com\/LijunChang\/Near-Maximum-Independent-Set.  NearLinear. Retrieved November 15 2018 from https:\/\/github.com\/LijunChang\/Near-Maximum-Independent-Set."},{"key":"e_1_2_1_27_1","volume-title":"Retrieved","author":"NVIDIA.","year":"2017","unstructured":"NVIDIA. 2017 . CUSP . Retrieved November 15, 2018 from https:\/\/developer.nvidia.com\/cusp. NVIDIA. 2017. CUSP. Retrieved November 15, 2018 from https:\/\/developer.nvidia.com\/cusp."},{"key":"e_1_2_1_28_1","volume-title":"Retrieved","author":"NVIDIA.","year":"2017","unstructured":"NVIDIA. 2017 . THRUST . Retrieved November 15, 2018 from https:\/\/developer.nvidia.com\/thrust. NVIDIA. 2017. THRUST. Retrieved November 15, 2018 from https:\/\/developer.nvidia.com\/thrust."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3022671.2984015"},{"key":"e_1_2_1_30_1","unstructured":"PBBS. 2014. Retrieved November 15 2018 from http:\/\/www.cs.cmu.edu\/\u223cpbbs\/.  PBBS. 2014. Retrieved November 15 2018 from http:\/\/www.cs.cmu.edu\/\u223cpbbs\/."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00047-5"},{"key":"e_1_2_1_32_1","unstructured":"SNAP. Retrieved November 15 2018 from https:\/\/snap.stanford.edu\/data\/.  SNAP. Retrieved November 15 2018 from https:\/\/snap.stanford.edu\/data\/."},{"key":"e_1_2_1_33_1","unstructured":"Sparse Matrix Collection. Retrieved November 15 2018 from https:\/\/www.cise.ufl.edu\/research\/sparse\/matrices\/.  Sparse Matrix Collection. Retrieved November 15 2018 from https:\/\/www.cise.ufl.edu\/research\/sparse\/matrices\/."},{"key":"e_1_2_1_34_1","unstructured":"TEPS. Retrieved November 15 2018 from http:\/\/www.graph500.org\/specifications#sec-8_2.  TEPS. Retrieved November 15 2018 from http:\/\/www.graph500.org\/specifications#sec-8_2."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 7th IBM Symposium on Mathematical Foundations of Computer Science. 171--189","author":"Valiant Leslie G.","year":"1982","unstructured":"Leslie G. Valiant . 1982 . Parallel computation . In Proceedings of the 7th IBM Symposium on Mathematical Foundations of Computer Science. 171--189 . Leslie G. Valiant. 1982. Parallel computation. In Proceedings of the 7th IBM Symposium on Mathematical Foundations of Computer Science. 171--189."}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3291525","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3291525","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:33Z","timestamp":1750204473000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3291525"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,30]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,6,30]]}},"alternative-id":["10.1145\/3291525"],"URL":"https:\/\/doi.org\/10.1145\/3291525","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6,30]]},"assertion":[{"value":"2017-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}