CAREER:High Performance Code Generation for Irregular Computation via a Graph Structure Descriptor Language

Many complex phenomena of modern life involve understanding the large scale behavior of many small scale interactions, for example, studying the spread of ideas through friend connections in social media, tracking patterns of fraud through credit card transactions, predicting the spread of disease from airline routes, and understanding a drug's behavior through the body via cellular pathways. These interactions can be modeled as a mathematical object known as a graph that captures the explicit and complex structure of the data.

Computations are performed on these graphs to build a predictive understanding of the underlying data. The challenge is that the existing software ecosystem is not optimized for these types of workloads. Performance improvements in software for graph computations would translate into gains in the fields using these tools.

This work aims to improve the software for graph computations through improved tooling. Additionally, this project will integrate its research developments into the undergraduate computer science curriculum for high-performance computing.

More specifically, the performance improvements for dense and regular computations from the last several decades have not translated to performance gains in sparse and irregular applications, such as graph computations. For example, an optimizing compiler needs very little information about the input data for a dense linear algebra operation -- other than matrix sizes and strides -- to extract performance.

This metadata is sufficient for a compiler to determine the control flow of the program and optimize for a given hardware target. This is not the case for the sparse equivalent of the same linear algebra operation, where the contents of the data and its structure are necessary to understand the behavior of the resulting program. This research project aims to bridge this gap through the following objectives.

First, the development of a language, the Graph Structure Descriptor Language, to approximate the structure of sparse data. Second, the creation of the compiler infrastructure that uses this language as the metadata needed to optimize code operating on sparse data. Third, the integration of this tooling into mainstream machine learning and graph packages that rely heavily on the performance of sparse computations.

This project is jointly funded by Software and Hardware Foundations core Program and the Established Program to Stimulate Competitive Research (EPSCoR).

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.