{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/105715"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/105715","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Thanos: High-performance CPU-GPU based balanced graph partitioning using cross-decomposition","abstract":"As graphs become larger and more complex, it is becoming nearly impossible to process them without graph partitioning. Graph partitioning creates many subgraphs which can be processed in parallel thus delivering high-speed computation results. However, graph partitioning is a difficult task. In this work, we introduce Thanos, a fast graph partitioning tool which uses the cross-decomposition algorithm that iteratively partitions a graph. It also produces balanced loads of partitions. The algorithm is well suited for parallel GPU programming which leads to fast and high-quality graph partitioning solutions. Experimental results show that we have achieved a 30x speedup and 35% better edge cut reduction compared to the CPU version of METIS on average.","abstract_html":"As graphs become larger and more complex, it is becoming nearly impossible to process them without graph partitioning. Graph partitioning creates many subgraphs which can be processed in parallel thus delivering high-speed computation results. However, graph partitioning is a difficult task. In this work, we introduce Thanos, a fast graph partitioning tool which uses the cross-decomposition algorithm that iteratively partitions a graph. It also produces balanced loads of partitions. The algorithm is well suited for parallel GPU programming which leads to fast and high-quality graph partitioning solutions. Experimental results show that we have achieved a 30x speedup and 35% better edge cut reduction compared to the CPU version of METIS on average.","abstract_has_math":false,"creators":["Kim, Dae Hee"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Chen, Deming"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2019,"date_issued":"2019-11-26T20:35:15Z","date_published":"2019-11-26T20:35:15Z","updated_at":"2026-07-22T22:24:44Z","subjects":["Graph Partitioning, GPU, Cross-Decomposition"],"languages":["en"],"rights":["Copyright 2019 Dae Hee Kim"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/105715","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Chen, Deming"]},{"key":"dc:creator","label":"Author","values":["Kim, Dae Hee"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2019-11-26T20:35:15Z","2019-07-17","2019-08"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Graph Partitioning, GPU, Cross-Decomposition"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2019 Dae Hee Kim"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/105715"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["As graphs become larger and more complex, it is becoming nearly impossible to process them without graph partitioning. Graph partitioning creates many subgraphs which can be processed in parallel thus delivering high-speed computation results. However, graph partitioning is a difficult task. In this work, we introduce Thanos, a fast graph partitioning tool which uses the cross-decomposition algorithm that iteratively partitions a graph. It also produces balanced loads of partitions. The algorithm is well suited for parallel GPU programming which leads to fast and high-quality graph partitioning solutions. Experimental results show that we have achieved a 30x speedup and 35% better edge cut reduction compared to the CPU version of METIS on average.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2019-11-26 without embargo terms","The student, Dae Hee Kim, accepted the attached license on 2019-07-17 at 15:55.","The student, Dae Hee Kim, submitted this Thesis for approval on 2019-07-17 at 15:56.","This Thesis was approved for publication on 2019-07-17 at 16:12.","DSpace SAF Submission Ingestion Package generated from Vireo submission #14367 on 2019-11-26 at 12:54:14","Made available in DSpace on 2019-11-26T20:35:15Z (GMT). No. of bitstreams: 2 KIM-THESIS-2019.pdf: 448960 bytes, checksum: f3d823335c3e3ab0612327ab200632a9 (MD5) LICENSE.txt: 4208 bytes, checksum: 35fb331963c2dfd6f93a34cd9d4efde3 (MD5) Previous issue date: 2019-07-17"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Thanos: High-performance CPU-GPU based balanced graph partitioning using cross-decomposition"]}]}],"canonical_facts":{"dc:contributor":["Chen, Deming"],"dc:creator":["Kim, Dae Hee"],"dc:date":["2019-11-26T20:35:15Z","2019-07-17","2019-08"],"dc:description":["As graphs become larger and more complex, it is becoming nearly impossible to process them without graph partitioning. Graph partitioning creates many subgraphs which can be processed in parallel thus delivering high-speed computation results. However, graph partitioning is a difficult task. In this work, we introduce Thanos, a fast graph partitioning tool which uses the cross-decomposition algorithm that iteratively partitions a graph. It also produces balanced loads of partitions. The algorithm is well suited for parallel GPU programming which leads to fast and high-quality graph partitioning solutions. Experimental results show that we have achieved a 30x speedup and 35% better edge cut reduction compared to the CPU version of METIS on average.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2019-11-26 without embargo terms","The student, Dae Hee Kim, accepted the attached license on 2019-07-17 at 15:55.","The student, Dae Hee Kim, submitted this Thesis for approval on 2019-07-17 at 15:56.","This Thesis was approved for publication on 2019-07-17 at 16:12.","DSpace SAF Submission Ingestion Package generated from Vireo submission #14367 on 2019-11-26 at 12:54:14","Made available in DSpace on 2019-11-26T20:35:15Z (GMT). No. of bitstreams: 2 KIM-THESIS-2019.pdf: 448960 bytes, checksum: f3d823335c3e3ab0612327ab200632a9 (MD5) LICENSE.txt: 4208 bytes, checksum: 35fb331963c2dfd6f93a34cd9d4efde3 (MD5) Previous issue date: 2019-07-17"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/105715"],"dc:language":["en"],"dc:rights":["Copyright 2019 Dae Hee Kim"],"dc:subject":["Graph Partitioning, GPU, Cross-Decomposition"],"dc:title":["Thanos: High-performance CPU-GPU based balanced graph partitioning using cross-decomposition"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:44Z"}