Collaborative Research: PPoSS: LARGE: General-Purpose Scalable Technologies for Fundamental Graph Problems

Indiana University, Bloomington IN

Investigators

Abstract

This project seeks to accelerate the execution of large graph problems on large, distributed machines, such as those found in datacenters. The graph computations considered appear in computational biology problems (for example, how species evolved), social network analysis problems, and verification of software systems (for example, how to prove that software is correct). These problems have many basic sub-computations in common, which this project will accelerate. The investigators will identify new ways to perform these sub-computations that are more efficient and will conceive new computing hardware that can execute them faster. Our society will benefit because this work will enable solving bigger versions of these problems faster and with less energy consumption. In addition, the project includes an education program that will teach computer science to high-school, college undergraduate and graduate students. The challenges of the graph problems considered stem from both the complexity of the algorithms used and the large compute and storage requirements of many graph problems. To address these challenges, this projects pursues an ambitious, cross-layer effort based on three interdependent main thrusts: new algorithms for graph problems, a core software framework for the efficient execution of these problems, and heterogeneous hardware to provide acceleration to these problems. The first thrust focuses on a few high-payoff algorithmic directions for the application domains considered: graph clustering in both static and dynamic settings; graph construction while preserving important information; and the application of machine learning (ML) techniques. In all these directions, the project uses approximations. In the second thrust, we develop a flexible programming layer that generates efficient code for a datacenter-scale platform. The project introduces a graph programming framework with a novel Domain-Specific Language (DSL) for graphs, high-performance numerical libraries for graph processing with scalable sparse methods, and a smart compiler with two intermediate representations that uses machine learning (ML) techniques. In the third thrust, the project speeds up the execution of graph applications in a large, distributed machine with a novel hardware accelerator. The accelerator features a high-level Instruction Set Architecture (ISA) with instructions that perform sparse matrix operations on tiles. A smart auto-tuner software helps generate and map code to various accelerators and general-purpose engines. The investigators are ten professors at the University of Illinois Urbana-Champaign, MIT, and Indiana University, with expertise in several distinct areas. The work will be done in close collaboration with industrial research groups. 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.