PPoSS: Planning: A Cross-Layer Approach to Accelerate Large-Scale Graph Computations on Distributed Platforms

这项工作在并行和分布式算法、高性能数值方法、编译器和计算机体系结构方面开发了一套新技术。这些技术加速了异构分布式计算机上的大规模图计算。图计算被用于许多领域，包括计算生物学应用、道路和网络交通管理、产品推荐和机器人中的路径规划问题。这项工作使用了一种新的方法来解决依赖于近似技术的图计算，它允许计算在不损害正确性的情况下更加并行。解决大规模图形问题可以在多个科学领域以及社会问题上取得进展。这项工作以跨层的方式解决了这个问题，重点关注算法、数字、编译器和计算机体系结构之间的协同作用。以这种方式进行优化暴露了重大机会。这项工作是与工业伙伴（包括IBM）合作完成的，IBM是运行图形问题的高端计算机系统的领先开发商。这项工作还包括努力改进伊利诺伊大学计算机科学系的课程设置。特别是，它在图形相关问题、并行计算和相关技术的一般领域创建了多学科课程。它还为本科生和代表性不足的学生提供研究机会。图是当今最重要的应用领域之一。随着单个图问题的计算和存储需求急剧增加，有必要为这些问题找到既可扩展又广泛适用的解决方案。这项工作执行了跨层的努力，以加速分布式机器上的大规模图形计算。在算法领域，通过利用近似、连续优化技术（如线性规划）和稀疏化方法的使用，研究了有效的并行图算法。研究了不同的并行计算模型。在数值领域，本工作通过为近似图算法开发稀疏矩阵计算的分布式内存库，将这些算法带入实践状态。这些库包括图算法、稀疏线性求解器和数值优化技术。在编译器领域，该工作开发了图形应用程序近似计算的新技术，以及保证其正确性的自动验证方法。在计算机体系结构领域，这项工作用新的硬件加快了稀疏矩阵计算的速度。具体来说，处理器、内存层次结构和网络接口中的硬件模块支持一种新的数据类型，这种数据类型一次操作一组图顶点。此外，异构节点包括稀疏计算的硬件加速器，可以将这些应用程序的速度提高数倍。总的来说，这项工作的影响将推动许多图形应用程序，帮助科学发现和改善社会互动。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.