Faclon: A Graph Manipulation Language for Heterogeneous Systems
Unnikrishnan.C, Y.N.Srikant & Rupesh Nasre
Graph algorithms are used in several domains such as social networking, biological
sciences, computational geometry, and compilers, to name a few.
It has been shown that they possess enough parallelism to keep several computing
resources busy -- even hundreds of cores on a GPU.
Unfortunately, tuning their implementation for efficient execution on a particular
hardware architecture is challenging, time-consuming, and error-prone.
Further, efficient execution on different kinds of hardware such as multi-core CPUs,
GPUs, heterogeneous systems, etc. requires modifying
the low-level code(s) separately for each platform. To address these issues, we
propose a Domain Specific Language (DSL), {\tt Falcon}, for implementing graph
algorithms
that (i) abstracts the hardware, (ii) provides constructs to write explicitly
parallel programs at a higher level, and (iii) can work with general algorithms that
may change the graph structure (morph algorithms).
We illustrate the usage of our DSL to implement local computation algorithms (that
do not change the graph structure) and morph algorithms such as Delaunay mesh
refinement, survey propagation and dynamic SSSP
on GPU and multi-core CPU.
Using a set of benchmark graphs, we illustrate that the generated code performs
close to the state-of-the-art hand-tuned implementations.
pdf