Collaborative Research: PPoSS: LARGE: A Full-Stack Architecture for Sparse Computation

协作研究：PPoSS：LARGE：稀疏计算的全栈架构

• 批准号: 2216964
• 负责人: Fredrik Berg Kjoelstad
• 金额: $ 110万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-10-01 至 2027-09-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2216964&HistoricalAwards=false
• 关键词: Collaborative; Research; PPoSS; LARGE; Full

Computer systems have been designed and optimized primarily for dense computations, i.e., those that process regularly structured data. But current systems are ill-suited to sparse computations, i.e., those that process unstructured data. Sparse computations are very common because many relations and interactions are sparse. For example, most people are not friends and most neurons are not directly connected. Sparse computations take advantage of this sparsity by encoding and processing only meaningful relations, such as storing only the non-zero elements of a matrix. These applications are crucial in many domains, like deep learning, data analytics, and scientific computing, but their irregular structure makes them inefficient and hard to scale in currentsystems, wasting billions of dollars yearly. This project aims to redesign the computing stack to provide first-class support for sparse computations. The project's novelties include a full system stack that spans programming languages, compilers, and specialized hardware architectures and large-scale computer systems. The project's impacts include making future parallel systems much more versatile, scalable, energy efficient and easier to program.This project takes a coordinated approach across the system stack to unlock the performance and scalability of sparse computations, because they pose challenges that cannot be addressed at a single layer. For example, sparse computations have a rich space of choices in algorithm, data representation, and schedule, which current languages and compilers cannot capture or optimize properly. The right choice of algorithm and data representation are often unknown in advance and may change at run-time, thwarting the rigid division between current compilers and schedulers. Irregular, data-dependent control and memory accesses stymie compiler analysis, hinder parallelization, make poor use of hardware, and introduce numerous side channels that thwart security. Finally, their data-intensive nature is a poor match to the processors and accelerators pervasive in current clusters and datacenters, which optimize for compute operations rather than to minimize data movement. To tackle these challenges, this project will develop a full system stack spanning domain-specific languages, a tightly integrated compiler and scheduler, and specialized hardware architectures and high-performance, multi-node computer systems and networks. This stack is built around a unifying abstraction, anovel sparse intermediate representation that (1) encodes semantic information on key sparse data structures and their iterations, (2) enables optimizing compiler transformations and dynamic scheduling decisions, and (3) can be easily compiled to parallel architectures, including graphics processing units (GPUs), general-purpose processors, our proposed specialized architecture, and their combination. The full stack will be designed with security at the forefront, leveraging novel cross-layer techniques to achieve secure high performance. This system will be rigorously evaluated using a broad set of sparse applications and at a wide range of system scales, including large-scale clusters with hundreds of GPUs or tens of specialized processors. By innovating across the full software and hardware stack, these techniques will achieve performance, scalability, and efficiency gains that single-layer approaches cannot provide.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.

计算机系统主要针对密集计算（即处理规则结构化数据的计算）进行设计和优化。但当前的系统不适合稀疏计算，即处理非结构化数据的系统。稀疏计算非常常见，因为许多关系和交互都是稀疏的。例如，大多数人都不是朋友，大多数神经元也没有直接连接。稀疏计算通过仅编码和处理有意义的关系来利用这种稀疏性，例如仅存储矩阵的非零元素。这些应用程序在深度学习、数据分析和科学计算等许多领域至关重要，但它们的不规则结构使其效率低下，并且难以在当前系统中扩展，每年浪费数十亿美元。该项目旨在重新设计计算堆栈，为稀疏计算提供一流的支持。该项目的新颖之处包括涵盖编程语言、编译器、专用硬件架构和大型计算机系统的完整系统堆栈。该项目的影响包括使未来的并行系统更加通用、可扩展、节能且更易于编程。该项目在整个系统堆栈中采用协调方法来解锁稀疏计算的性能和可扩展性，因为它们带来了无法在单层。例如，稀疏计算在算法、数据表示和调度方面有丰富的选择空间，当前的语言和编译器无法正确捕获或优化。算法和数据表示的正确选择通常是事先未知的，并且可能在运行时发生变化，从而阻碍了当前编译器和调度程序之间的严格划分。不规则的、数据相关的控制和内存访问会阻碍编译器分析、阻碍并行化、硬件利用率低下，并引入大量阻碍安全的侧通道。最后，它们的数据密集型性质与当前集群和数据中心中普遍存在的处理器和加速器不匹配，后者针对计算操作进行优化，而不是最大限度地减少数据移动。为了应对这些挑战，该项目将开发涵盖特定领域语言的完整系统堆栈、紧密集成的编译器和调度程序、专用硬件架构以及高性能、多节点计算机系统和网络。该堆栈围绕统一抽象、新颖的稀疏中间表示构建，该表示 (1) 对关键稀疏数据结构及其迭代的语义信息进行编码，(2) 能够优化编译器转换和动态调度决策，(3) 可以轻松编译为并行架构，包括图形处理单元（GPU）、通用处理器、我们提出的专用架构及其组合。整个堆栈的设计将以安全为先，利用新颖的跨层技术来实现安全的高性能。该系统将使用广泛的稀疏应用程序和广泛的系统规模进行严格评估，包括具有数百个 GPU 或数十个专用处理器的大型集群。通过在整个软件和硬件堆栈上进行创新，这些技术将实现单层方法无法提供的性能、可扩展性和效率提升。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力优势和能力进行评估，被认为值得支持。更广泛的影响审查标准。

项目成果

Indexed Streams: A Formal Intermediate Representation for Fused Contraction Programs

索引流：融合收缩程序的正式中间表示

• DOI: 10.1145/3591268
• 发表时间: 2023-06
• 期刊: Proceedings of the ACM on Programming Languages
• 作者: Kovach, Scott;Kolichala, Praneeth;Gu, Tiancheng;Kjolstad, Fredrik
• 通讯作者: Kjolstad, Fredrik

Mosaic: An Interoperable Compiler for Tensor Algebra

Mosaic：张量代数的可互操作编译器

• DOI: 10.1145/3591236
• 发表时间: 2023-06
• 期刊: Proceedings of the ACM on Programming Languages
• 作者: Bansal, Manya;Hsu, Olivia;Olukotun, Kunle;Kjolstad, Fredrik
• 通讯作者: Kjolstad, Fredrik

SpDISTAL: Compiling Distributed Sparse Tensor Computations

SpDISTAL：编译分布式稀疏张量计算

• DOI: 10.1109/sc41404.2022.00064
• 发表时间: 2022-07-28
• 期刊: SC22: International Conference for High Performance Computing, Networking, Storage and Analysis
• 作者: Rohan Yadav;Alex Aiken;Fredrik Kjolstad
• 通讯作者: Fredrik Kjolstad