| Title | : | StarPlat: A Versatile DSL for Graph Analytics |
| Speaker | : | Nibedita Behera (IITM) |
| Details | : | Tue, 11 Apr, 2023 11:00 AM @ MR-I (SSB 233) |
| Abstract: | : | With the growth of unstructured and semi-structured data, parallelization of graph algorithms is inevitable. Unfortunately, due to inherent irregularity of computation, memory access, and communication, graph algorithms are traditionally challenging to parallelize. To tame this challenge, several libraries, frameworks, and domain-specific languages (DSLs) have been proposed to reduce the parallel programming burden of the users, who are often domain experts. A range of such frameworks exists today that partially or fully hide the parallelism intricacies, provide mnemonics for scheduling strategies, and perform program analysis to identify races to generate synchronization code. Existing frameworks are limited by their support in the form of abstractions and memory representation for static graphs only and typically target single architectures. Most real world graphs are dynamic in nature, their structures change with time. Hence, we require the frameworks, libraries to extend their functionality to support fast analysis of network properties for a dynamic~graph.
We present a graph DSL, named StarPlat, that allows programmers to specify graph algorithms in a high-level format, but generates code for three different backends from the same algorithmic specification. In particular, the DSL compiler generates OpenMP for multi-core systems, MPI for distributed systems, and CUDA for many-core GPUs. Since these three are completely different parallel programming paradigms, binding them together under the same language is challenging. We share our experience with the language design. Central to our compiler is an intermediate representation which allows a common representation of the high-level program, from which individual backend code generations begin. In this work, we present an abstraction scheme and memory representation for algorithmic processing of dynamic graphs. We design the generation scheme for multicore-backend that uses either the high level information embedded in constructs or extracts this information by analyzing the intermediate representation to generate parallel code with OpenMP support. We demonstrate the expressiveness of StarPlat by implementing popular algorithms. In particular, we implement and optimize static and dynamic versions of Betweenness Centrality, Single Source Shortest Path, PageRank and Triangle Counting. We illustrate the effectiveness of our approach by comparing the performance of the OpenMP generated codes with that obtained from the existing state of the art solutions. |
