Presentation
iG-kway: Incremental k-way Graph Partitioning on GPU
DescriptionRecently, researchers have leveraged GPU to accelerate graph partitioning to a new performance milestone. However, existing GPU-accelerated graph partitioners are limited to full graph partitioning and do not anticipate incremental update. Incremental partitioning is integral to many optimization-driven CAD applications, where a circuit graph is re-partitioned iteratively as it undergoes incremental modifications during the evaluation of optimization transforms. To unlock the full potential of GPU-accelerated graph partitioning, we introduce iG-kway, an incremental k-way graph partitioner on GPU. iG-kway introduces an incrementality-aware data structure to support graph modifications directly on GPU. Atop this data structure, iG-kway introduces an incremental refinement kernel that can efficiently refine affected vertices after the graph is incrementally modified, with minimal impact on partitioning quality. Experimental results show that iG-kway achieves an average speedup of 84x over the state-of-the-art G-kway, with comparable cut sizes.
Event Type
Research Manuscript
TimeWednesday, June 253:30pm - 3:45pm PDT
Location3002, Level 3