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

这项工作开发了一套新的技术，在并行和分布式算法，高性能数值方法，编译器和计算机体系结构。这些技术加速了异构分布式计算机上的大规模图计算。图计算被用于许多领域，包括计算生物学应用，道路和网络交通管理，产品推荐和机器人中的路径规划问题。这项工作使用了一种新的方法来解决依赖于近似技术的图形计算，这使得计算更加并行，而不会损害正确性。解决大规模图形问题可以在多个科学领域以及社会问题中取得进展。这项工作以跨层的方式解决问题，重点是算法，数值，编译器和计算机体系结构之间的协同作用。以这种方式进行优化会带来重大机遇。这项工作是与工业合作伙伴合作完成的，包括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.