DisGCo
- 30 September 2020
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Architecture and Code Optimization
- Vol. 17 (4), 1-26
- https://doi.org/10.1145/3414469
Abstract
Graph algorithms are widely used in various applications. Their programmability and performance have garnered a lot of interest among the researchers. Being able to run these graph analytics programs on distributed systems is an important requirement. Green-Marl is a popular Domain Specific Language (DSL) for coding graph algorithms and is known for its simplicity. However, the existing Green-Marl compiler for distributed systems (Green-Marl to Pregel) can only compile limited types of Green-Marl programs (in Pregel canonical form). This severely restricts the types of parallel Green-Marl programs that can be executed on distributed systems. We present DisGCo, the first compiler to translate any general Green-Marl program to equivalent MPI program that can run on distributed systems. Translating Green-Marl programs to MPI (SPMD/MPMD style of computation, distributed memory) presents many other exciting challenges, besides the issues related to differences in syntax, as Green-Marl gives the programmer a unified view of the whole memory and allows the parallel and serial code to be inter-mixed. We first present the set of challenges involved in translating Green-Marl programs to MPI and then present a systematic approach to do the translation. We also present a few optimization techniques to improve the performance of our generated programs. DisGCo is the first graph DSL compiler that can handle all syntactic capabilities of a practical graph DSL like Green-Marl and generate code that can run on distributed systems. Our preliminary evaluation of DisGCo shows that our generated programs are scalable. Further, compared to the state-of-the-art DH-Falcon compiler that translates a subset of Falcon programs to MPI, our generated codes exhibit a geomean speedup of 17.32×.Keywords
Funding Information
- SERB CRG (CRG/2018/002488)
- NSM research (MeitY/R8D/HPC/2(1)/2014)
This publication has 19 references indexed in Scilit:
- A compiler for throughput optimization of graph algorithms on GPUsPublished by Association for Computing Machinery (ACM) ,2016
- An implementation and evaluation of the MPI 3.0 one‐sided communication interfaceConcurrency and Computation: Practice and Experience, 2016
- FENNELPublished by Association for Computing Machinery (ACM) ,2014
- A lightweight infrastructure for graph analyticsPublished by Association for Computing Machinery (ACM) ,2013
- Distributed socialiteProceedings of the VLDB Endowment, 2013
- LigraACM SIGPLAN Notices, 2013
- Distributed GraphLabProceedings of the VLDB Endowment, 2012
- Balanced Graph PartitioningTheory of Computing Systems, 2006
- CGMgraph/CGMlib: Implementing and Testing CGM Graph Algorithms on PC ClustersLecture Notes in Computer Science, 2003
- The Bulk-Synchronous Parallel ModelPublished by Springer Science and Business Media LLC ,2000