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.

计算机系统的设计和优化主要用于密集计算，即定期结构化数据的计算系统。但是当前的系统不适合稀疏计算，即处理非结构化数据的系统。稀疏计算非常普遍，因为许多关系和相互作用都是稀疏的。例如，大多数人不是朋友，大多数神经元没有直接连接。稀疏计算通过仅编码和处理有意义的关系来利用这种稀疏性，例如仅存储矩阵的非零元素。这些应用在许多领域中至关重要，例如深度学习，数据分析和科学计算，但是它们的不规则结构使它们效率低下且难以扩展在Currentystems中，每年浪费数十亿美元。该项目旨在重新设计计算堆栈，以为稀疏计算提供一流的支持。该项目的新颖性包括一个完整的系统堆栈，该堆栈涵盖编程语言，编译器和专业硬件体系结构和大型计算机系统。该项目的影响包括使未来的并行系统更加广泛，可扩展，能源效率且更易于编程。该项目在整个系统堆栈中采用协调的方法来解锁稀疏计算的性能和可扩展性，因为它们构成了无法在单层上无法解决的挑战。例如，稀疏计算在算法，数据表示和时间表中具有丰富的选择空间，当前语言和编译器无法正确捕获或优化它们。正确的选择算法和数据表示形式通常是未知的，并且可能在运行时发生变化，从而挫败了当前编译器和调度程序之间的刚性划分。不规则的，与数据有关的控制和内存访问Stymie编译器分析，阻碍并行化，使硬件的使用不佳，并引入了众多的侧道渠道阻碍了安全性。最后，他们的数据密集型性质与当前群集和数据中心的处理器和加速器普遍存在，这是对计算操作进行优化而不是最小化数据移动的。为了应对这些挑战，该项目将开发完整的系统堆栈，跨越域特异性语言，紧密集成的编译器和调度程序，以及专业的硬件体系结构以及高性能，多节点计算机系统和网络。该堆栈围绕着统一的摘要，稀疏的中间表示形式构建，（（1）编码有关关键稀疏数据结构及其迭代的语义信息，（2）启用优化的编译器转换和动态调度决策，以及（3）可以轻松地编译为平行的架构，包括绘画处理方（包括绘制图形），一般架构（GPUS），一般架构，构建了一般构建，构建了一般构建，并构建了一般 - 构建企业。完整的堆栈将以安全性在最前沿设计，利用新颖的跨层技术来实现安全的高性能。该系统将使用广泛的稀疏应用程序和广泛的系统尺度进行严格评估，其中包括具有数百个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
• 作者: S. Kovach;Praneeth Kolichala;Tiancheng Gu;Fredrik Kjolstad

Mosaic: An Interoperable Compiler for Tensor Algebra

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

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

SpDISTAL: Compiling Distributed Sparse Tensor Computations

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