HyperG：多级 GPU 加速的 k 路超图分区器.pdf

1、HyperG:A Multilevel GPU-Accelerated k-way Hypergraph PartitionerWan Luan Lee,Dian-Lun Lin,Cheng-Hsiang Chiu,Ulf Schlichtmann,and Tsung-Wei HuangDepartment of Electrical and Computer EngineeringUniversity of Wisconsin at Madison,WI2Hypergraph Partitioning is Important in CAD Breaks down a large circu

2、it into manageable pieces Ex:divide&conquer Mainstream graph partitioning algorithms are multi-levelCoarseningUncoarseningLevel 0Level 1Level 2Initial Partitioningfinestcoarsest3However,Hypergraph Partitioning is Time-consuming Modern circuit complexity and size continue to increase Ex:Four minutes

3、for hmetis to partition a circuit with five million-gate Partitioning can be performed multiple times during a CAD algorithm CPU parallel hypergraph partitioners mitigate the runtime challenges Ex:Mt-KaHyPar Speedup plateaus at 816 CPU threads GPU non-hypergraph partitioners G-kway GKSG There is a n

4、eed for a GPU-accelerated hypergraph partitioning algorithm216mt-KaHyPar/hmetisspeedup#threads4GPU-accelerated Hypergraph Partitioner is NOT EASY Uses GPU non-hypergraph partitioning algorithm on hypergraph results in poor quality Extra cost of transforming hypergraph into non-hypergraph Transformed

5、 graph fails to accurately represent the original hypergraph Distinct performance characteristics of CPU and GPU require different data layout designs to maximize computing efficiency Ex:Mt-KaHyPars coarsening algorithm requires frequent synchronization,which is costly on GPUs5HyperG:A GPU-accelerat

6、ed Hypergraph Partitioner Among the earliest attempts to parallelize both coarsening and uncoarsening stages on a GPU Balanced group coarsening algorithm Groups many vertices into balanced subgroups Sequence-based refinement Simultaneously moves the best vertices to improve partitioning quality Mode