Decoupling Schedule, Topology Layout, and Algorithm to Easily Enlarge the Tuning Space of GPU Graph Processing

Abstract

© 2022 Association for Computing Machinery.Only with a right schedule and a right topology layout, a graph algorithm can be efciently processed on GPUs. Existing GPU graph processing frameworks try to fnd an optimal schedule and topology layout for an algorithm via iterative search, but they fail to fnd the optimal confguration because their schedules and topology layouts are tightly coupled in their processing models. Moreover, their tightly coupled schedules and topology layouts make it diffcult for developers to extend the tuning space. To easily enlarge the tuning space of GPU graph processing, this work proposes a new GPU graph processing abstraction scheme that fully decouples schedules, topology layouts, and algorithms from each other with abstraction interfaces. Moreover, this work proposes GRAssembler, a new GPU graph processing framework that efciently integrates the decoupled schedule, topology layout, and algorithm without abstraction overhead. Thanks to the efcient decoupling and integration, GRAssembler increases the tuning space from 336 to 4,480 and achieves 30.4% higher performance on geomean average, compared to the state-of-the-art GPU graph processing framework.