high performance computing on graphics processing units: hgpu.org

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), 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.