This work develops a set of new technologies in parallel and distributed algorithms, high-performance numerical methods, compilers, and computer architecture. These technologies accelerate large-scale graph computations on heterogeneous distributed computers. Graph computations are used in many domains, including computational-biology applications, road and network traffic management, product recommendation, and path-planning problems in robotics. The work uses a new approach to solving graph computations that relies on approximation techniques, which allow the computation to be more parallel without hurting correctness. Solving large-scale graph problems delivers advances in multiple scientific domains, as well as in societal issues. The work tackles the problem in a cross-layer manner, focusing on the synergies between algorithms, numerics, compilers, and computer architecture. Optimizing in this way exposes major opportunities. This work is done in collaboration with industrial partners, including IBM, a leading developer of high-end computer systems on which graph problems run. The work also includes an effort to revamp the course offerings in the Computer Science Department at the University of Illinois. In particular, it creates multidisciplinary courses in the general area of graph-related problems, parallel computing, and related technologies. It also provides research opportunities to undergraduates and under-represented students.
Graphs are one of today’s most important application domains. As the compute and storage needs of individual graph problems dramatically increase, there is a need to find solutions to these problems that are both scalable and broadly applicable. This work performs a cross-layer effort to accelerate large-scale graph computations on distributed machines. In the algorithms area, the work investigates efficient parallel graph algorithms by leveraging approximation, continuous optimization techniques such as linear programming, and the use of sparsification methods. Different models of parallel computation are examined. In the numerics area, this work brings these algorithms to the state of practice by developing distributed-memory libraries of sparse-matrix computations for approximate graph algorithms. These libraries include techniques in graph algorithms, sparse linear solvers, and numerical optimization. In the compiler area, the work develops novel techniques for approximate computation of graph applications, as well as automated verification approaches to guarantee their correctness. In the computer architecture area, the work speeds-up the resulting sparse-matrix computations with novel hardware. Specifically, hardware modules in the processors, memory hierarchies, and network interfaces support a new data type that operates on groups of graph vertices at a time. Also, heterogeneous nodes include hardware accelerators of sparse computations that speed-up these applications multiple times. Overall, the impact of this work will be advancing many graph applications, helping scientific discoveries and improving social interactions.
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.
