Collaborative Research: SHF: Medium: Co-Optimizing Computation and Data Transformations for Sparse Tensors

稀疏张量计算是计算机辅助药物设计、欺诈检测和国家安全等重要应用的核心。及时执行这些应用程序可提高用户工作效率，并减少每次执行所带来的能源消耗。稀疏计算的特征是具有许多或大多数值为零的输入。为了避免零值数据的存储和计算效率低下，应用程序只存储非零，并使用辅助数据结构来恢复它们的位置。因此，稀疏张量计算表现出不可预测的存储器访问模式，其中包括通过辅助数据结构的间接性。因此，在当今的计算机体系结构上，稀疏张量计算的性能完全由数据的移动主导，通过存储系统和跨节点。数据移动在执行时间和能量消耗方面都很昂贵。随着高性能体系结构(传统并行体系结构、用作并行加速器的图形处理器和复杂的存储系统)变得越来越多样化，优化稀疏张量计算的数据移动给软件开发人员带来了性能和工作效率的挑战，他们最终要为每个平台编写特定于体系结构的低级代码。提出的方法同时优化了数据在内存中的组织方式、计算的结构化方式以减少数据移动的方式访问数据的方式，以及计算和数据移动如何最好地利用硬件体系结构的功能。由于数据的非零结构在程序执行之前是未知的，因此该方法还在其决策中检查运行时信息。由此产生的联合优化策略实现了一种内聚性方法，用于迭代地为广泛的稀疏计算做出调度和数据表示转换决策，并结合运行时适应。该项目正在开发一个编程框架，该框架允许对稀疏计算进行高级规范，并对其进行优化以减少数据移动。它由数据表示、数据布局和存储映射以及用于稀疏计算的并行调度组成。它使用数据依赖关系、运行时信息和体系结构特性来完全绑定最终生成的代码。该方法旨在允许处理具有依赖关系的稀疏张量计算，例如稀疏三角解算和用于线性方程组的许多其他解算器，对稀疏张量应用诸如Morton排序之类的重新排序，以及稀疏张量数据表示的后期绑定。研究的最新和最有意义的方面包括：(1)可组合的调度和数据转换，包括数据布局转换和存储映射；(2)检查器综合，用于数据表示、布局和存储映射之间的运行时数据转换，这些数据表示、布局和存储映射由外部函数组成；(3)支持依赖数据的张量计算；和，(4)在MLIR/LLVM编译器中部署的框架抽象。研究人员坚定地致力于扩大对计算的参与，并有全面的计划来吸引代表不足的群体。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Sparse tensor computations are central to important applications including computer-assisted drug design, fraud detection, and national security. Timely execution of these applications improves user productivity and reduces the energy consumption associated with each execution. Sparse computations are characterized as having inputs where many or most values are zero. To avoid the inefficiency of storing and computing on zero-valued data, applications only store the nonzeros, with auxiliary data structures to recover their locations. As a result, sparse tensor computations exhibit unpredictable memory-access patterns that include indirection through the auxiliary data structures. Consequently, on today’s computer architectures, performance of sparse tensor computations is completely dominated by the movement of data, through the memory system and across nodes. Data movement is expensive both in terms of execution time and energy expenditure. Optimizing data movement of sparse tensor computations as high-performance architectures have become increasingly diverse — conventional parallel architectures, graphics processors used as parallel accelerators and complex memory systems — creates a performance and productivity challenge for software developers who end up writing low-level architecture-specific code for each platform. The proposed approach simultaneously optimizes how data is organized in memory, how the computation is structured to access the data in a way that reduces data movement, and how the computation and data movement make best use of features of the hardware architectures. Since the nonzero structure of the data is unknown until program execution, the approach also examines runtime information in its decisions. The resulting co-optimization strategy enables a cohesive approach for iteratively making scheduling and data representation transformation decisions for a wide range of sparse computations and incorporating runtime adaptations.This project is developing a programming framework that permits high-level specification of a sparse computation and optimizes it to reduce data movement. It composes data representations, data layouts and storage mappings, and parallel schedules for sparse computations. It employs data dependencies, runtime information, and architecture features to fully bind the final generated code. This approach is intended to enable handling sparse tensor computations with dependences such as sparse triangular solve and many other solvers for systems of linear equations, applying reorderings such as Morton ordering on sparse tensors, and late binding of sparse tensor data representations. The novel and most significant aspects of the research include: (1) composable schedule and data transformations, including data layout transformations and storage mapping; (2) inspector synthesis for runtime data transformations between data representations, layouts, and storage mappings, which are composed with external functions; (3) support for data-dependent tensor computations; and, (4) framework abstractions deployed in the MLIR/LLVM compiler.The researchers are strongly committed to broadening participation in computing and have comprehensive plans to engage the underrepresented 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.