2026-09-19T03:26:05Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/105715 2023-07-11 col_2142_8888 col_2142_5131 com_2142_8887 com_2142_234 com_2142_5130

Chen, Deming Kim, Dae Hee 2019-11-26T20:35:15Z 2019-11-26T20:35:15Z 2019-07-17 2019-08 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 application/pdf http://hdl.handle.net/2142/105715 en Copyright 2019 Dae Hee Kim Graph Partitioning, GPU, Cross-Decomposition Thanos: High-performance CPU-GPU based balanced graph partitioning using cross-decomposition text text Electrical & Computer Eng Electrical & Computer Engr University of Illinois at Urbana-Champaign Thesis M.S.