2024 · 22 citations · 6 references
ComputingComputer EngineeringComputer ScienceComputational GeometryParallel AlgorithmsParallel ComputingData ParallelismData PartitioningGraph AlgorithmsGraphics Processing Unit ArchitectureGraphics Processing Unit ComputingGraphics Processing UnitsGpgpu ComputingGpu Parallel AlgorithmsGraph PartitioningGraph ProcessingParallel PartitioningParallel Partitioning StrategiesParallel Speedup AnalysisPartitioning
Graph partitioning is important for the design of many CAD algorithms. However, as the graph size continues to grow, graph partitioning becomes increasingly time-consuming. To overcome these challenges, we propose G-kway, an efficient multilevel GPU-accelerated k-way graph partitioner. G-kway introduces an effective union find-based coarsening and a novel independent set-based refinement algorithm to significantly accelerate both the coarsening and uncoarsening stages. Experimental results have shown that G-kway outperforms both the state-of-the-art CPU-based and GPU-based parallel partitioners with an average speedup of 8.6× and 3.8×, respectively, while achieving comparable partitioning quality.
6
Multi-threaded Graph Partitioning
Dominique LaSalle, George Karypis · 2013 · 152 citations
Scalable SIMD-Efficient Graph Processing on GPUs
Farzad Khorasani, Rajiv Gupta, Laxmi N. Bhuyan · 2015 · 130 citations