| Title | : | GPU Code Generation for Dynamic Graph Algorithms |
| Speaker | : | Ashwina Kumar (IITM) |
| Details | : | Thu, 19 Dec, 2024 4:00 PM @ SSB 233 |
| Abstract: | : | Unlike static graph algorithms that assume a fixed graph structure, dynamic graph algorithms are specifically designed to handle graphs undergoing structural modifications, such as edge insertions, deletions, as well as node additions and deletions. These algorithms play a crucial role in the application domains where graphs continually evolve or need to be updated, such as social networks, recommendation systems, and other related areas. A major challenge in dynamic graph algorithms lies in efficiently maintaining and updating the graph properties under graph modifications. These algorithms reduce the computational overhead after modifications by employing techniques such as incremental updates, where changes are processed incrementally instead of recomputing the entire graph from scratch. Parallelization of static graph algorithms was traditionally viewed to be challenging due to irregular data access pattern, inherent sequential nature of some algorithms, memory access pattern, synchronization overhead, and data dependencies. The challenges exacerbate when structural modifications are permitted. Therefore, it is only in the recent past that the community has started looking for efficient parallel solutions for dynamic graph algorithms. Maintaining the graph attributes consistently under structural modifications happening simultaneously demands clever synchronization mechanisms, in the absence of which, the processing becomes slower. It would be ideal, of course, if the parallel code can be generated rather than written. This relieves the domain experts of the nitty-gritty details of the architectural and parallelism optimizations, allowing them to focus on the underlying domain problem. In this work, we address this concern. This work describes programming abstractions in StarPlat graph DSL and code generation for supporting dynamic graph algorithms for GPU. The programming constructs support incremental and decremental processing in a batch, with succinct dynamic processing logic. This makes it easy for programmers to generate efficient parallel codes for popular graph algorithms such as SSSP, PR, and TC. The performance of the generated codes is considerably better than rerunning the static algorithm upto a certain number of dynamic updates, as illustrated with a range of real-world and synthetic graphs in our experimental setup. We believe this work would pave way towards productive parallel graph processing. |
