Software Engineering Institute

Graph analytics and other data-intensive applications are characterized by unpredictable memory access and low computation intensity. Called irregular algorithms, these applications are difficult to implement efficiently, but they are required by increasingly complex systems.

The goal of this work is to automate code generation of high-performance libraries of graph algorithms, tuned for at least two different hardware architectures—multi-core CPU and SIMD (Single Instruction, Multiple Data) GPU—to establish a foundation for the infrastructure of a wider range of systems. This work advances the state-of-the-art in code generation by introducing concepts needed to capture graph algorithm primitives, including a parameterization of the structure of sparse data to produce highly tuned codes for irregular algorithms.