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

协作研究：SHF：中：稀疏张量的协同优化计算和数据转换

• 批准号: 2107556
• 负责人: Mary Hall
• 金额: $ 43万
• 依托单位: University of Utah
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-01-01 至 2025-12-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2107556&HistoricalAwards=false
• 关键词: Collaborative; Research; SHF; Medium; Co

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.

稀疏张量计算是重要应用的核心，包括计算机辅助的药物设计，欺诈检测和国家安全。这些应用程序的及时执行可改善用户的生产，并减少与每个执行相关的能耗。稀疏计算的特征是具有许多或大多数值为零的输入。为了避免在零价值数据上存储和计算的效率低下，应用仅存储非齐射的数据，并使用辅助数据结构来恢复其位置。结果，稀疏张量计算暴露了不可预测的内存访问模式，其中包括通过辅助数据结构进行间接的。因此，在当今的计算机体系结构上，稀疏张量计算的性能完全由数据，通过存储系统和跨节点的移动控制。在执行时间和能源消耗方面，数据移动都很昂贵。优化稀疏张量计算作为高性能体系结构的数据移动已变得越来越多样化 - 传统的并行体系结构，用作并行加速器的图形处理器和复杂的内存系统 - 为最终为每个平台编写低级特定于特定于每个平台的低级体系结构的软件开发人员创造了性能和生产力挑战。所提出的方法简单地优化了如何在内存中组织数据的方式，如何以减少数据移动的方式访问数据，以及计算和数据移动如何充分利用硬件体系结构的功能。由于数据的非零结构在程序执行之前是未知的，因此该方法还检查了决策中的运行时信息。由此产生的合作策略为迭代的调度和数据表示形式转换决策提供了一种凝聚力的方法，并进行了广泛的稀疏计算，并结合了运行时适应。该项目正在开发一个编程框架，允许对稀疏计算的高级规范进行高级规范，以减少数据流动。它构成了数据表示，数据布局和存储映射以及稀疏计算的并行计划。它采用数据依赖性，运行时信息和体系结构功能来完全绑定最终生成的代码。这种方法旨在使稀疏张量计算具有依赖性，例如稀疏三角求解和许多其他求解器，用于线性方程系统，将重新排序（例如莫尔顿订购）在稀疏张力张子上以及稀疏张量数据表示的较晚结合。研究的新颖和最重要的方面包括：（1）可组合的时间表和数据转换，包括数据布局转换和存储映射； （2）检查器合成用于数据表示，布局和存储映射之间的运行时数据转换，这些映射由外部功能组成； （3）支持数据依赖性张量计算； （4）部署在MLIR/LLVM编译器中的框架抽象。研究人员强烈致力于扩大计算机的参与，并制定了全面的计划，以参与代表性不足的组。这奖反映了NSF的法定任务，并通过使用基金会的知识优点和广泛的影响来通过评估来诚实地通过评估来进行评估，以诚实地进行支持。

项目成果

Code Synthesis for Sparse Tensor Format Conversion and Optimization

稀疏张量格式转换和优化的代码综合

• 发表时间: 2023
• 期刊: International Symposium on Code Generation and Optimization
• 作者: Popoola, Tobi;Zhao, Tuowen;St. George, Aaron;Bhetwal, Kalyan;Strout, Michelle;Hall, Mary;Olschanowsky, Catherine
• 通讯作者: Olschanowsky, Catherine

Polyhedral Specification and Code Generation of Sparse Tensor Contraction with Co-iteration

• DOI: 10.1145/3566054
• 发表时间: 2022-08
• 期刊: ACM Transactions on Architecture and Code Optimization
• 影响因子: 1.6
• 作者: Tuowen Zhao;Tobi Popoola;Mary W. Hall;C. Olschanowsky;M. Strout

Runtime Composition of Iterations for Fusing Loop-carried Sparse Dependence

用于融合循环携带稀疏依赖的迭代的运行时组合

• DOI: 10.1145/3581784.3607097
• 发表时间: 2023
• 期刊: ACM
• 作者: Cheshmi, Kazem;Strout, Michelle;Mehri Dehnavi, Maryam
• 通讯作者: Mehri Dehnavi, Maryam