Collaborative Research: PPoSS: LARGE: General-Purpose Scalable Technologies for Fundamental Graph Problems

合作研究：PPoSS：大型：解决基本图问题的通用可扩展技术

• 批准号: 2316234
• 负责人: Md Ariful Azad
• 金额: $ 54.74万
• 依托单位: Indiana University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-08-01 至 2028-07-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2316234&HistoricalAwards=false
• 关键词: Collaborative; Research; PPoSS; LARGE; General

This project seeks to accelerate the execution of large graph problems on large, distributed machines, such as those found in datacenters. The graph computations considered appear in computational biology problems (for example, how species evolved), social network analysis problems, and verification of software systems (for example, how to prove that software is correct). These problems have many basic sub-computations in common, which this project will accelerate. The investigators will identify new ways to perform these sub-computations that are more efficient and will conceive new computing hardware that can execute them faster. Our society will benefit because this work will enable solving bigger versions of these problems faster and with less energy consumption. In addition, the project includes an education program that will teach computer science to high-school, college undergraduate and graduate students, with an emphasis on students from disadvantaged backgrounds. The challenges of the graph problems considered stem from both the complexity of the algorithms used and the large compute and storage requirements of many graph problems. To address these challenges, this projects pursues an ambitious, cross-layer effort based on three interdependent main thrusts: new algorithms for graph problems, a core software framework for the efficient execution of these problems, and heterogeneous hardware to provide acceleration to these problems. The first thrust focuses on a few high-payoff algorithmic directions for the application domains considered: graph clustering in both static and dynamic settings; graph construction while preserving important information; and the application of machine learning (ML) techniques. In all these directions, the project uses approximations. In the second thrust, we develop a flexible programming layer that generates efficient code for a datacenter-scale platform. The project introduces a graph programming framework with a novel Domain-Specific Language (DSL) for graphs, high-performance numerical libraries for graph processing with scalable sparse methods, and a smart compiler with two intermediate representations that uses machine learning (ML) techniques. In the third thrust, the project speeds up the execution of graph applications in a large, distributed machine with a novel hardware accelerator. The accelerator features a high-level Instruction Set Architecture (ISA) with instructions that perform sparse matrix operations on tiles. A smart auto-tuner software helps generate and map code to various accelerators and general-purpose engines. The investigators are ten professors at the University of Illinois Urbana-Champaign, MIT, and Indiana University, with expertise in several distinct areas. The work will be done in close collaboration with industrial research groups.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.

该项目旨在加快在大型分布式机器（例如数据中心中发现的）上执行大图问题。所考虑的图计算出现在计算生物学问题中（例如，物种如何发展），社交网络分析问题和软件系统的验证（例如，如何证明该软件是正确的）。这些问题具有许多共同的基本子计算，该项目将加速。调查人员将确定执行这些效率更高的子计算的新方法，并将构想可以更快地执行它们的新计算硬件。我们的社会将受益，因为这项工作将使解决这些问题的更大版本更快，能耗更少。此外，该项目还包括一项教育计划，该计划将向高中，大学本科生和研究生教授计算机科学，重点是来自弱势背景的学生。图形问题的挑战源于所使用的算法的复杂性以及许多图形问题的大量计算和存储要求。为了应对这些挑战，这些项目基于三个相互依存的主要推力来追求雄心勃勃的跨层努力：用于图形问题的新算法，这是有效地执行这些问题的核心软件框架以及为这些问题加速的异质硬件。第一个推力集中在考虑的应用程序域的一些高付费算法方向上：静态和动态设置中的图形聚类；在保留重要信息的同时，图形结构；以及机器学习（ML）技术的应用。在所有这些方向上，项目都使用近似值。在第二个推力中，我们开发了一个灵活的编程层，该编程层为数据中心尺度平台生成有效的代码。该项目介绍了一个具有新颖域特异性语言（DSL）的图形编程框架，用于图形，具有可扩展稀疏方法的图形处理的高性能数值库以及具有两个使用机器学习（ML）技术的中间表示的智能编译器。在第三个推力中，该项目加快了带有新型硬件加速器的大型分布式机器中图形应用程序的执行。该加速器具有高级指令集体系结构（ISA），并具有在瓷砖上执行稀疏矩阵操作的说明。智能自动调节软件有助于生成并映射到各种加速器和通用引擎。研究人员是伊利诺伊大学Urbana-Champaign，麻省理工学院和印第安纳大学的十名教授，在几个不同领域具有专业知识。这项工作将与工业研究小组密切合作进行。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛影响的评论标准来评估值得支持的。