{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T20:14:57Z","timestamp":1762460097962,"version":"3.37.3"},"reference-count":81,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2022,11,7]],"date-time":"2022-11-07T00:00:00Z","timestamp":1667779200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,11,7]],"date-time":"2022-11-07T00:00:00Z","timestamp":1667779200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"PhD Award from the Foundation for Education and European Culture"},{"DOI":"10.13039\/501100018960","name":"National Technical University of Athens","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100018960","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"published-print":{"date-parts":[[2023,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Graph coloring is widely used to parallelize scientific applications by identifying subsets of independent tasks that can be executed simultaneously. Graph coloring assigns colors the vertices of a graph, such that no adjacent vertices have the same color. The number of colors used corresponds to the number of parallel steps in a real-world end-application. Therefore, the total runtime of the graph coloring kernel adds to the overall parallel overhead of the real-world end-application, whereas the number of the vertices of each color class determines the number of the independent concurrent tasks of each parallel step, thus affecting the amount of parallelism and hardware resource utilization in the execution of the real-world end-application. In this work, we propose a high-performance graph coloring algorithm, named ColorTM, that leverages Hardware Transactional Memory (HTM) to detect coloring inconsistencies between adjacent vertices. ColorTM detects and resolves coloring inconsistencies between adjacent vertices with an eager approach to minimize data access costs, and implements a speculative synchronization scheme to minimize synchronization costs and increase parallelism. We extend our proposed algorithmic design to propose a balanced graph coloring algorithm, named BalColorTM, with which all color classes include almost the same number of vertices to achieve high parallelism and resource utilization in the execution of the real-world end-applications. We evaluate ColorTM and BalColorTM using a wide variety of large real-world graphs with diverse characteristics. ColorTM and BalColorTM improve performance by 12.98<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\times$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mo>\u00d7<\/mml:mo>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and 1.78<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\times$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mo>\u00d7<\/mml:mo>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> on average using 56 parallel threads compared to prior state-of-the-art approaches. Moreover, we study the impact of our proposed graph coloring algorithmic designs on a popular end-application, i.e., Community Detection, and demonstrate the ColorTM and BalColorTM can provide high-performance improvements in real-world end-applications across various input data given.<\/jats:p>","DOI":"10.1007\/s11227-022-04894-6","type":"journal-article","created":{"date-parts":[[2022,11,7]],"date-time":"2022-11-07T20:03:03Z","timestamp":1667851383000},"page":"6373-6421","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["High-performance and balanced parallel graph coloring on multicore platforms"],"prefix":"10.1007","volume":"79","author":[{"given":"Christina","family":"Giannoula","sequence":"first","affiliation":[]},{"given":"Athanasios","family":"Peppas","sequence":"additional","affiliation":[]},{"given":"Georgios","family":"Goumas","sequence":"additional","affiliation":[]},{"given":"Nectarios","family":"Koziris","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,11,7]]},"reference":[{"issue":"1","key":"4894_CR1","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1093\/comjnl\/10.1.85","volume":"10","author":"DJA Welsh","year":"1967","unstructured":"Welsh DJA, Powell MB (1967) An upper bound for the chromatic number of a graph and its application to timetabling problems. Comput J 10(1):85\u201386","journal-title":"Comput J"},{"key":"4894_CR2","unstructured":"Marx D (2004) Graph coloring problems and their applications in scheduling. In: Proceedings of John Von Neumann PhD Students Conference, vol 48, pp 11\u201316"},{"issue":"1","key":"4894_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0166-218X(87)90037-0","volume":"18","author":"EM Arkin","year":"1987","unstructured":"Arkin EM, Silverberg EB (1987) Scheduling jobs with fixed start and end times. Discrete Appl Math 18(1):1\u20138","journal-title":"Discrete Appl Math"},{"key":"4894_CR4","first-page":"11","volume":"48","author":"D Marx","year":"2004","unstructured":"Marx D (2004) Graph colouring problems and their applications in scheduling. Period Polytech Electr Eng 48:11\u201316","journal-title":"Period Polytech Electr Eng"},{"key":"4894_CR5","doi-asserted-by":"crossref","unstructured":"Ramaswami R, Parhi KK (1989) Distributed scheduling of broadcasts in a radio network. In: IEEE INFOCOM, pp 497\u20135042","DOI":"10.1109\/INFCOM.1989.101493"},{"issue":"1","key":"4894_CR6","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0096-0551(81)90048-5","volume":"6","author":"GJ Chaitin","year":"1981","unstructured":"Chaitin GJ, Auslander MA, Chandra AK, Cocke J, Hopkins ME, Markstein PW (1981) Register allocation via coloring. Comput Lang 6(1):47\u201357","journal-title":"Comput Lang"},{"key":"4894_CR7","doi-asserted-by":"crossref","unstructured":"Chaitin GJ (1982) Register allocation and spilling via graph coloring. In: SIGPLAN Symposium on Compiler Construction. vol 17, pp 98\u2013101","DOI":"10.1145\/872726.806984"},{"issue":"3","key":"4894_CR8","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1145\/177492.177575","volume":"16","author":"P Briggs","year":"1994","unstructured":"Briggs P, Cooper KD, Torczon L (1994) Improvements to graph coloring register allocation. TOPLAS 16(3):428\u2013455","journal-title":"TOPLAS"},{"key":"4894_CR9","doi-asserted-by":"crossref","unstructured":"Chen W-Y, Lueh G-Y, Ashar P, Chen K, Cheng B (2018) Register allocation for intel processor graphics. In: CGO, pp 352\u2013364","DOI":"10.1145\/3168806"},{"key":"4894_CR10","doi-asserted-by":"crossref","unstructured":"Cohen A, Rohou E (2010) Processor virtualization and split compilation for heterogeneous multicore embedded systems. In: DAC, pp 102\u2013107","DOI":"10.1145\/1837274.1837303"},{"issue":"1","key":"4894_CR11","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1137\/0720013","volume":"20","author":"TF Coleman","year":"1983","unstructured":"Coleman TF, Mor\u00e9 JJ (1983) Estimation of sparse Jacobian matrices and graph coloring problems. SIAM J Numer Anal 20(1):187\u2013209","journal-title":"SIAM J Numer Anal"},{"key":"4894_CR12","unstructured":"Saad Y (1994) SPARSKIT: a basic tool kit for sparse matrix computations\u2014Version 2"},{"key":"4894_CR13","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/978-1-4613-8369-7_11","volume-title":"Graph theory and sparse matrix computation","author":"MT Jones","year":"1993","unstructured":"Jones MT, Plassmann PE (1993) The efficient parallel iterative solution of large sparse linear systems. In: George A, Gilbert JR, Liu JWH (eds) Graph theory and sparse matrix computation. Springer, New York, pp 229\u2013245"},{"issue":"4","key":"4894_CR14","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1137\/S0036144504444711","volume":"47","author":"AH Gebremedhin","year":"2005","unstructured":"Gebremedhin AH, Manne F, Pothen A (2005) What color is your Jacobian? Graph coloring for computing derivatives. SIAM Rev 47(4):629\u2013705","journal-title":"SIAM Rev"},{"key":"4894_CR15","doi-asserted-by":"crossref","unstructured":"Kaler T, Hasenplaugh W, Schardl TB, Leiserson CE (2016) Executing dynamic data-graph computations deterministically using chromatic scheduling. In: ACM TOPC vol 3(1)","DOI":"10.1145\/2896850"},{"key":"4894_CR16","doi-asserted-by":"crossref","unstructured":"Kaler T, Hasenplaugh W, Schardl TB, Leiserson CE (2014) Executing dynamic data-graph computations deterministically using chromatic scheduling. In: SPAA, pp 154\u2013165","DOI":"10.1145\/2612669.2612673"},{"key":"4894_CR17","doi-asserted-by":"crossref","unstructured":"Strati F, Giannoula C, Siakavaras D, Goumas G, Koziris N (2019) An adaptive concurrent priority queue for NUMA architectures. In: CF, pp 135\u2013144","DOI":"10.1145\/3310273.3323164"},{"key":"4894_CR18","doi-asserted-by":"crossref","unstructured":"Giannoula C, Vijaykumar N, Papadopoulou N, Karakostas V, Fernandez I, G\u00f3mez-Luna J, Orosa L, Koziris N, Goumas G, Mutlu O (2021) SynCron: efficient synchronization support for near-data-processing architectures. In: HPCA, pp 263\u2013276","DOI":"10.1109\/HPCA51647.2021.00031"},{"key":"4894_CR19","doi-asserted-by":"crossref","unstructured":"Garey MR, Johnson DS, Stockmeyer L (1974) Some simplified NP-complete problems. In: STOC, pp 47\u201363","DOI":"10.1145\/800119.803884"},{"key":"4894_CR20","doi-asserted-by":"crossref","unstructured":"Besta M, Carigiet A, Janda K, Vonarburg-Shmaria Z, Gianinazzi L, Hoefler T (2020) High-performance parallel graph coloring with strong guarantees on work, depth, and quality. In: SC, pp 1\u201317","DOI":"10.1109\/SC41405.2020.00103"},{"key":"4894_CR21","doi-asserted-by":"crossref","unstructured":"Hasenplaugh W, Kaler T, Schardl TB, Leiserson CE (2014) Ordering heuristics for parallel graph coloring. In: SPAA, pp 166\u2013177","DOI":"10.1145\/2612669.2612697"},{"issue":"4","key":"4894_CR22","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1145\/359094.359101","volume":"22","author":"D Br\u00e9laz","year":"1979","unstructured":"Br\u00e9laz D (1979) New methods to color the vertices of a graph. Commun ACM 22(4):251\u2013256","journal-title":"Commun ACM"},{"issue":"3","key":"4894_CR23","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1145\/2402.322385","volume":"30","author":"DW Matula","year":"1983","unstructured":"Matula DW, Beck LL (1983) Smallest-last ordering and clustering and graph coloring algorithms. J ACM 30(3):417\u2013427","journal-title":"J ACM"},{"issue":"4","key":"4894_CR24","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1145\/4221.4226","volume":"32","author":"RM Karp","year":"1985","unstructured":"Karp RM, Wigderson A (1985) A fast parallel algorithm for the maximal independent set problem. J ACM 32(4):762\u2013773","journal-title":"J ACM"},{"key":"4894_CR25","doi-asserted-by":"crossref","unstructured":"Luby M (1985) A simple parallel algorithm for the maximal independent set problem. In: STOC, vol 7, pp 567\u2013583","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"4894_CR26","doi-asserted-by":"crossref","unstructured":"Goldberg M, Spencer T (1987) A new parallel algorithm for the maximal independent set problem. In: SFCS, pp 161\u2013165","DOI":"10.1109\/SFCS.1987.2"},{"issue":"10","key":"4894_CR27","doi-asserted-by":"publisher","first-page":"576","DOI":"10.1016\/j.parco.2012.07.001","volume":"38","author":"\u00dcV \u00c7ataly\u00fcrek","year":"2012","unstructured":"\u00c7ataly\u00fcrek \u00dcV, Feo J, Gebremedhin AH, Halappanavar M, Pothen A (2012) Graph coloring algorithms for muti-core and massively multithreaded architectures. Parallel Comput 38(10):576\u2013594","journal-title":"Parallel Comput"},{"issue":"12","key":"4894_CR28","doi-asserted-by":"publisher","first-page":"1131","DOI":"10.1002\/1096-9128(200010)12:12<1131::AID-CPE528>3.0.CO;2-2","volume":"12","author":"AH Gebremedhin","year":"2000","unstructured":"Gebremedhin AH, Manne F (2000) Scalable parallel graph coloring algorithms. Concurr Pract Exp 12(12):1131\u20131146","journal-title":"Concurr Pract Exp"},{"key":"4894_CR29","doi-asserted-by":"crossref","unstructured":"Rokos G, Gorman G, Kelly PHJ (2015) A fast and scalable graph coloring algorithm for multi-core and many-core architectures. Euro-Par-2015, pp 414\u2013425","DOI":"10.1007\/978-3-662-48096-0_32"},{"key":"4894_CR30","doi-asserted-by":"crossref","unstructured":"Boman EG, Bozda\u011f D, Catalyurek U, Gebremedhin AH, Manne F (2005) A scalable parallel graph coloring algorithm for distributed memory computers. EuroPar, pp 241\u2013251","DOI":"10.1007\/11549468_29"},{"key":"4894_CR31","doi-asserted-by":"crossref","unstructured":"Lu H, Halappanavar M, Chavarr\u00eda-Miranda D, Gebremedhin A, Kalyanaraman A: Balanced coloring for parallel computing applications. In: IEEE IPDPS, pp 7\u201316 (2015)","DOI":"10.1109\/IPDPS.2015.113"},{"key":"4894_CR32","unstructured":"Giannoula C (2022) ColorTM: a high-performance graph coloring algorithm. https:\/\/github.com\/cgiannoula\/ColorTM.git"},{"key":"4894_CR33","doi-asserted-by":"crossref","unstructured":"Giannoula C, Goumas G, Koziris N: Combining HTM with RCU to speed up graph coloring on multicore platforms. In: ISC HPC, pp 350\u2013369 (2018)","DOI":"10.1007\/978-3-319-92040-5_18"},{"issue":"3\u20135","key":"4894_CR34","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","volume":"486","author":"S Fortunato","year":"2010","unstructured":"Fortunato S (2010) Community detection in graphs. Phys Rep 486(3\u20135):75\u2013174","journal-title":"Phys Rep"},{"issue":"2","key":"4894_CR35","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1093\/comjnl\/19.2.182","volume":"19","author":"J Mitchem","year":"1976","unstructured":"Mitchem J (1976) On various algorithms for estimating the chromatic number of a graph. Comput J 19(2):182\u2013183","journal-title":"Comput J"},{"issue":"1","key":"4894_CR36","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/0012-365X(89)90096-4","volume":"75","author":"LM Lov\u00e1sz","year":"1989","unstructured":"Lov\u00e1sz LM, Saks ME, Trotter WT (1989) An on-line graph coloring algorithm with sublinear performance ratio. Discrete Math 75(1):319\u2013325","journal-title":"Discrete Math"},{"key":"4894_CR37","doi-asserted-by":"crossref","unstructured":"Herlihy M, Moss JEB (1993) Transactional memory: architectural support for lock-free data structures. In: ISCA, pp 289\u2013300","DOI":"10.1145\/173682.165164"},{"key":"4894_CR38","doi-asserted-by":"crossref","unstructured":"Yoo RM, Hughes CJ, Lai K, Rajwar R (2013) Performance Evaluation of Intel\u00aetransactional synchronization extensions for high-performance computing. In: SC","DOI":"10.1145\/2503210.2503232"},{"key":"4894_CR39","doi-asserted-by":"crossref","unstructured":"Cain HW, Michael MM, Frey B, May C, Williams D, Le H (2013) Robust architectural support for transactional memory in the power architecture. In: ISCA, pp 225\u2013236","DOI":"10.1145\/2508148.2485942"},{"key":"4894_CR40","doi-asserted-by":"crossref","unstructured":"Wang A, Gaudet M, Wu P, Amaral JN, Ohmacht M, Barton C, Silvera R, Michael M (2012) Evaluation of blue gene\/Q hardware support for transactional memories. In: PACT, pp 127\u2013136","DOI":"10.1145\/2370816.2370836"},{"key":"4894_CR41","doi-asserted-by":"crossref","unstructured":"Giannoula C, Fernandez I, G\u00f3mez-Luna J, Koziris N, Goumas G, Mutlu O (2022) Towards efficient sparse matrix vector multiplication on real processing-in-memory architectures. In: SIGMETRICS, pp 33\u201334","DOI":"10.1145\/3547353.3522661"},{"issue":"1","key":"4894_CR42","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3508041","volume":"6","author":"C Giannoula","year":"2022","unstructured":"Giannoula C, Fernandez I, Luna JG, Koziris N, Goumas G, Mutlu O (2022) SparseP: towards efficient sparse matrix vector multiplication on real processing-in-memory architectures. Proc ACM Meas Anal Comput Syst 6(1):1\u201349","journal-title":"Proc ACM Meas Anal Comput Syst"},{"key":"4894_CR43","doi-asserted-by":"crossref","unstructured":"Tang WT, Zhao R, Lu M, Liang Y, Huyng HP, Li X, Goh RSM (2015) Optimizing and auto-tuning scale-free sparse matrix-vector multiplication on Intel Xeon Phi. In: CGO, pp 136\u2013145","DOI":"10.1109\/CGO.2015.7054194"},{"key":"4894_CR44","doi-asserted-by":"crossref","unstructured":"Boldi P, Vigna S (2004) The WebGraph framework I: compression techniques. In: WWW 2004, pp 595\u2013602","DOI":"10.1145\/988672.988752"},{"key":"4894_CR45","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.parco.2015.03.003","volume":"47","author":"H Lu","year":"2015","unstructured":"Lu H, Halappanavar M, Kalyanaraman A (2015) Parallel heuristics for scalable community detection. Parallel Comput 47:19\u201337","journal-title":"Parallel Comput"},{"key":"4894_CR46","doi-asserted-by":"crossref","unstructured":"Chavarria-Miranda D, Halappanavar M, Kalyanaraman A (2014) Scaling graph community detection on the Tilera many-core architecture. In: HiPC, vol 47, pp 19\u201337","DOI":"10.1109\/HiPC.2014.7116708"},{"key":"4894_CR47","doi-asserted-by":"publisher","first-page":"10008","DOI":"10.1088\/1742-5468\/2008\/10\/P10008","volume":"10","author":"VD Blondel","year":"2008","unstructured":"Blondel VD, Guillaume J-L, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. JSTAT 10:10008","journal-title":"JSTAT"},{"key":"4894_CR48","unstructured":"ExaGraph (2020) Grappolo: parallel clustering using the louvain method as the serial template. https:\/\/github.com\/.Exa-Graph\/grappolo"},{"key":"4894_CR49","doi-asserted-by":"crossref","unstructured":"Ghosh S, Halappanavar M, Tumeo A, Kalyanaraman A, Lu H, Chavarri\u00e0-Miranda D, Khan A, Gebremedhin A (2018) Distributed Louvain algorithm for graph community detection. In: IPDPS, pp 885\u2013895","DOI":"10.1109\/IPDPS.2018.00098"},{"key":"4894_CR50","doi-asserted-by":"crossref","unstructured":"Naim M, Manne F, Halappanavar M, Tumeo A (2017) Community detection on the GPU. In: IPDPS, pp 625\u2013634","DOI":"10.1109\/IPDPS.2017.16"},{"key":"4894_CR51","doi-asserted-by":"crossref","unstructured":"Halappanavar M, Lu H, Kalyanaraman A, Tumeo A (2017) Scalable static and dynamic community detection using Grappolo. In: HPEC, pp 1\u20136","DOI":"10.1109\/HPEC.2017.8091047"},{"key":"4894_CR52","doi-asserted-by":"crossref","unstructured":"Tas MK., Kaya K, Saule E (2017) Greed is good: parallel algorithms for bipartite-graph partial coloring on multicore architectures. In: ICPP, pp 503\u2013512","DOI":"10.1109\/ICPP.2017.59"},{"issue":"3","key":"4894_CR53","doi-asserted-by":"publisher","first-page":"654","DOI":"10.1137\/0914041","volume":"14","author":"MT Jones","year":"1993","unstructured":"Jones MT, Plassmann PE (1993) A parallel graph coloring heuristic. SIAM J Sci Comput 14(3):654\u2013669","journal-title":"SIAM J Sci Comput"},{"key":"4894_CR54","doi-asserted-by":"crossref","unstructured":"Deveci M, Boman EG, Devine KD, Rajamanickam S (2016) Parallel graph coloring for manycore architectures. In: IPDPS, pp 892\u2013901","DOI":"10.1109\/IPDPS.2016.54"},{"key":"4894_CR55","doi-asserted-by":"crossref","unstructured":"Grosset AVP, Zhu P, Liu S, Venkatasubramanian S, Hall M (2011) Evaluating graph coloring on GPUs. In: PPoPP, pp 297\u2013298","DOI":"10.1145\/2038037.1941597"},{"key":"4894_CR56","doi-asserted-by":"crossref","unstructured":"Osama M, Truong M, Yang C, Bulu\u00e7 A, Owens J (2019) Graph coloring on the GPU. In: IPDPSW, pp 231\u2013240","DOI":"10.1109\/IPDPSW.2019.00046"},{"issue":"10","key":"4894_CR57","doi-asserted-by":"publisher","first-page":"4064","DOI":"10.1002\/cpe.4064","volume":"29","author":"X Chen","year":"2017","unstructured":"Chen X, Li P, Fang J, Tang T, Wang Z, Yang C (2017) Efficient and high-quality sparse graph coloring on GPUS. Concurr Comput Pract Exp 29(10):4064","journal-title":"Concurr Comput Pract Exp"},{"key":"4894_CR58","doi-asserted-by":"crossref","unstructured":"Che S, Rodgers G, Beckmann B, Reinhardt S (2015) Graph coloring on the GPU and some techniques to improve load imbalance. In: IPDPS, pp 610\u2013617","DOI":"10.1109\/IPDPSW.2015.74"},{"key":"4894_CR59","doi-asserted-by":"crossref","unstructured":"Fernandez I, Quislant R, Guti\u00e9rrez E, Plata O, Giannoula C, Alser M, G\u00f3mez-Luna J, Mutlu O (2020) NATSA: a near-data processing accelerator for time series analysis. In: ICCD, pp 120\u2013129","DOI":"10.1109\/ICCD50377.2020.00035"},{"key":"4894_CR60","doi-asserted-by":"crossref","unstructured":"G\u00f3mez-Luna J, El\u00a0Hajj I, Fernandez I, Giannoula C, Oliveira GF, Mutlu O (2021) Benchmarking memory-centric computing systems: analysis of real processing-in-memory hardware. In: IGSC, pp 1\u20137","DOI":"10.1109\/IGSC54211.2021.9651614"},{"key":"4894_CR61","doi-asserted-by":"crossref","unstructured":"G\u00f3mez-Luna J, El\u00a0Hajj I, Fernandez I, Giannoula C, Oliveira GF, Mutlu O (2022) Benchmarking a new paradigm: experimental analysis and characterization of a real processing-in-memory system. In: IEEE Access, vol 10, pp 52565\u201352608","DOI":"10.1109\/ACCESS.2022.3174101"},{"key":"4894_CR62","doi-asserted-by":"crossref","unstructured":"Gao M, Ayers G, Kozyrakis C (2015) Practical near-data processing for in-memory analytics frameworks. In: PACT, pp 113\u2013124","DOI":"10.1109\/PACT.2015.22"},{"key":"4894_CR63","doi-asserted-by":"crossref","unstructured":"Ahn J, Hong S, Yoo S, Mutlu O (2015) A scalable processing-in-memory accelerator for parallel graph processing. In: ISCA, pp 105\u2013117","DOI":"10.1145\/2872887.2750386"},{"key":"4894_CR64","doi-asserted-by":"crossref","unstructured":"Nai L, Hadidi R, Sim J, Kim H, Kumar P, Kim H (2017) GraphPIM: enabling instruction-level PIM offloading in graph computing frameworks. In: HPCA, pp 457\u2013468","DOI":"10.1109\/HPCA.2017.54"},{"key":"4894_CR65","doi-asserted-by":"crossref","unstructured":"Zhuo Y, Wang C, Zhang M, Wang R, Niu D, Wang Y, Qian X (2019) GraphQ: scalable PIM-based graph processing. In: MICRO, pp 712\u2013725","DOI":"10.1145\/3352460.3358256"},{"key":"4894_CR66","doi-asserted-by":"crossref","unstructured":"Alabandi G, Powers E, Burtscher M (2020) Increasing the parallelism of graph coloring via shortcutting. In: PpopP, pp 262\u2013275","DOI":"10.1145\/3332466.3374519"},{"issue":"4","key":"4894_CR67","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer I (1981) The NP-completeness of edge-coloring. SIAM J Comput 10(4):718\u2013720","journal-title":"SIAM J Comput"},{"key":"4894_CR68","doi-asserted-by":"crossref","unstructured":"Sallinen S, Iwabuchi K, Poudel S, Gokhale M, Ripeanu M, Pearce R (2016) Graph colouring as a challenge problem for dynamic graph processing on distributed systems. In: SC, pp 347\u2013358","DOI":"10.1109\/SC.2016.29"},{"issue":"3","key":"4894_CR69","first-page":"338","volume":"11","author":"L Yuan","year":"2017","unstructured":"Yuan L, Qin L, Lin X, Chang L, Zhang W (2017) Effective and efficient dynamic graph coloring. VLDB 11(3):338\u2013351","journal-title":"VLDB"},{"key":"4894_CR70","doi-asserted-by":"crossref","unstructured":"Bossek J, Neumann F, Peng P, Sudholt D (2019) Runtime analysis of randomized search heuristics for dynamic graph coloring. In: GECCO, pp 1443\u20131451","DOI":"10.1145\/3321707.3321792"},{"key":"4894_CR71","doi-asserted-by":"crossref","unstructured":"Barba L, Cardinal J, Korman M, Langerman S, Renssen A, Roeloffzen M, Verdonschot S (2017) Dynamic graph coloring. In: Workshop on algorithms and data structures, pp 97\u2013108","DOI":"10.1007\/978-3-319-62127-2_9"},{"key":"4894_CR72","doi-asserted-by":"crossref","unstructured":"Bhattacharya S, Chakrabarty D, Henzinger M, Nanongkai D (2018) Dynamic algorithms for graph coloring. In: ACM SIAM, pp 1\u201320","DOI":"10.1137\/1.9781611975031.1"},{"issue":"3","key":"4894_CR73","first-page":"1","volume":"16","author":"S Solomon","year":"2020","unstructured":"Solomon S, Wein N (2020) Improved dynamic graph coloring. TALG 16(3):1\u201324","journal-title":"Improved dynamic graph coloring. TALG"},{"key":"4894_CR74","unstructured":"Chakrabarti A, Ghosh P, Stoeckl M (2021) Adversarially robust coloring for graph streams. arXiv preprint arXiv:2109.11130"},{"issue":"4","key":"4894_CR75","doi-asserted-by":"publisher","first-page":"2418","DOI":"10.1137\/080732158","volume":"32","author":"D Bozda\u011f","year":"2010","unstructured":"Bozda\u011f D, \u00c7ataly\u00fcrek UV, Gebremedhin AH, Manne F, Boman EG, \u00d6zg\u00fcner F (2010) Distributed-memory parallel algorithms for distance-2 coloring and related problems in derivative computation. SIAM J Sci Comput 32(4):2418\u20132446","journal-title":"SIAM J Sci Comput"},{"key":"4894_CR76","doi-asserted-by":"crossref","unstructured":"Bozdag D, \u00c7ataly\u00fcrek \u00dcV, Gebremedhin AH, Manne F, Boman EG, \u00d6zg\u00fcner F (2005) A parallel distance-2 graph coloring algorithm for distributed memory computers. In: HPCC, pp 796\u2013806","DOI":"10.1007\/11557654_90"},{"key":"4894_CR77","doi-asserted-by":"crossref","unstructured":"Lin J, Cai S, Luo C, Su K (2017) A reduction based method for coloring very large graphs. In: IJCAI pp 517\u2013523","DOI":"10.24963\/ijcai.2017\/73"},{"issue":"1","key":"4894_CR78","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1287\/ijoc.2014.0618","volume":"27","author":"A Verma","year":"2015","unstructured":"Verma A, Buchanan A, Butenko S (2015) Solving the maximum clique and vertex coloring problems on very large sparse networks. INFORMS J Comput 27(1):164\u2013177","journal-title":"INFORMS J Comput"},{"key":"4894_CR79","doi-asserted-by":"crossref","unstructured":"Hebrard E, Katsirelos G (2019) A hybrid approach for exact coloring of massive graphs. In: CPAIOR, pp 374\u2013390","DOI":"10.1007\/978-3-030-19212-9_25"},{"key":"4894_CR80","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1016\/j.asoc.2018.01.027","volume":"65","author":"Y Zhou","year":"2018","unstructured":"Zhou Y, Duval B, Hao J-K (2018) Improving probability learning based local search for graph coloring. Appl Soft Comput 65:542\u2013553","journal-title":"Appl Soft Comput"},{"key":"4894_CR81","doi-asserted-by":"crossref","unstructured":"Brown T, Kogan A, Lev Y, Luchangco V (2016) Investigating the performance of hardware transactions on a multi-socket machine. In: SPAA, pp 121\u2013132","DOI":"10.1145\/2935764.2935796"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-022-04894-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11227-022-04894-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-022-04894-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,2]],"date-time":"2023-03-02T19:16:30Z","timestamp":1677784590000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11227-022-04894-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,7]]},"references-count":81,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,4]]}},"alternative-id":["4894"],"URL":"https:\/\/doi.org\/10.1007\/s11227-022-04894-6","relation":{},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"type":"print","value":"0920-8542"},{"type":"electronic","value":"1573-0484"}],"subject":[],"published":{"date-parts":[[2022,11,7]]},"assertion":[{"value":"15 October 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 November 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}}]}}