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

PPoSS：规划：加速分布式平台上大规模图计算的跨层方法

• 批准号: 2028861
• 负责人: Josep Torrellas
• 金额: $ 25万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-10-01 至 2022-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2028861&HistoricalAwards=false
• 关键词: PPoSS; Planning; Cross; Layer; Approach

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.

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

项目成果

FLEX: fixing flaky tests in machine learning projects by updating assertion bounds

• DOI: 10.1145/3468264.3468615
• 发表时间: 2021-08
• 期刊: Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering
• 作者: Saikat Dutta;A. Shi;Sasa Misailovic

WISE: Predicting the Performance of Sparse Matrix Vector Multiplication with Machine Learning

• DOI: 10.1145/3572848.3577506
• 发表时间: 2023-02
• 期刊: Proceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming
• 作者: Serif Yesil;Azin Heidarshenas;Adam Morrison;J. Torrellas

Diamont: Dynamic Monitoring of Uncertainty for Distributed Asynchronous Programs

Diamont：分布式异步程序不确定性的动态监控

• DOI: 10.1007/978-3-030-88494-9_10
• 发表时间: 2021
• 期刊: 2021 in Runtime Verification
• 作者: Fernando, Vimuth;Joshi, Keyur;Laurel, Jacob;Misailovic, Sasa
• 通讯作者: Misailovic, Sasa

Accelerating Distributed-Memory Autotuning via Statistical Analysis of Execution Paths

• DOI: 10.1109/ipdps49936.2021.00014
• 发表时间: 2021-03
• 期刊: 2021 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
• 作者: Edward Hutter;Edgar Solomonik

Faster and Scalable Algorithms for Densest Subgraph and Decomposition

• 发表时间: 2022
• 作者: Elfarouk Harb;Kent Quanrud;C. Chekuri