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

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

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.