Presentation
G-kway: Multilevel GPU-Accelerated k-way Graph Partitioner
DescriptionGraph partitioning is fundamental for many CAD algorithms because it divides a large circuit into smaller pieces with manageable complexity. As the size of the circuit graph continues to grow, graph partitioning becomes increasingly time-consuming. Recent research has introduced parallel graph partitioners using either multi-core CPUs or GPUs. However, their performance is limited to a few CPU cores and available GPU memory. As a result, we propose G-kway, an efficient multilevel GPU-accelerated k-way graph partitioner. 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.6x and 3.8x, respectively.
Event Type
Research Manuscript
TimeWednesday, June 264:00pm - 4:15pm PDT
Location3003, 3rd Floor
Design
SoC, Heterogeneous, and Reconfigurable Architectures