CSR: Small: High-Level Programming Languages and Environments for Scalable Graph Processing

Indiana University, Bloomington IN

Investigators

Abstract

Graphs and graph algorithms are fundamental to computer science. Although historically they have not played a major role in traditional scientific computing, their importance is rapidly increasing with the emergence of informatics and data-centric applications. Although many graph analysis tasks are performed sequentially today, problem sizes continue to grow, necessitating the increasing use of parallel computing. Parallel graph algorithms are already being written, but with great effort and limited code reuse. A major issue in current ways of implementing parallel graph algorithms is the lack of performance portability: not only is it often required to reimplement algorithms on different platforms for the best performance, it is frequently also necessary to completely redesign them. To avoid this rewriting and thus increase scientists' productivity, this project will study domain-specific programming languages allowing graph algorithms to be expressed portably, while using compilation techniques that allow the high-level expressions to achieve performance competitive with hand-written, low-level code for these algorithms. Domain-specific languages have already shown benefit in multiple application areas. This project will extend their benefits further in the graph domain, including to more platforms and data representations than in the past. In particular, the project goals include finding abstractions common to the expressions of graph applications on different platforms, as well as between different applications. To demonstrate the effectiveness of these abstractions, the project includes the creation of prototype implementations of graph algorithms for a variety of high-performance computing platforms and the evaluation of the high-level versions of algorithms against comparable low-level versions.