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

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

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.