OAC: Small: Data Locality Optimization for Sparse Matrix/Tensor Computations

OAC：小型：稀疏矩阵/张量计算的数据局部性优化

• 批准号: 2009007
• 负责人: Ponnuswamy Sadayappan
• 金额: $ 49.94万
• 依托单位: University of Utah
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-07-01 至 2024-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2009007&HistoricalAwards=false
• 关键词: OAC; Small; Data; Locality; Optimization

The cost of data movement vastly exceeds the cost of execution of arithmetic operations on current computers and the imbalance is only expected to get worse. Hence the minimization of data movement in the implementation of algorithms is critical. Tiling is a well known technique for data-locality optimization and is widely used in compilers as well as high-performance numerical libraries for dense matrix/tensor computations. However, data-locality optimization for sparse computations is a significant challenge, in large part because the data access patterns are not known a priori. This project proposes a plan of research to systematically explore a number of issues pertaining to data-locality optimization for sparse matrix/tensor computations. The project identifies an important subclass of sparse computations used in machine learning and data analytics, and proposes tools and techniques to enable high-performance parallel implementations on multicore CPUs and GPUs. The broader impact of the project will be the enhancement of programmer productivity and the enabling of software portability and high performance for applications in data analytics and machine learning.The challenge of data-locality optimization for the data-dependent and irregular access patterns that occur with sparse matrix/tensor computations will be addressed through research along multiple directions: 1) Compact signatures for sparse matrices: the strong relationship between the data access patterns for key sparse matrix primitives of use in machine learning and data analytics drives the development of one-dimensional signature vectors that capture the essential characteristics of the two-dimensional sparsity pattern as it pertains to needed data movement in a memory hierarchy; 2) Sparse tiling: Sparse matrix signature vectors will serve as a basis for dynamic decisions based on target platform characteristics, for tile size selection and scheduling of tiles for load-balanced execution; 3) Matrix renumbering/reordering: The impact of row/column reordering on the performance of sparse matrix primitives will be investigated, and new reordering schemes will be devised to enhance data-locality for key sparse matrix/tensor primitives; 4) Sparse microkernels: Microkernels will be developed and optimized for CPUs/GPUs, and used as the lowest-level building blocks that execute the innermost tiles in the tiled execution of sparse matrix/tensor computations; 5) Architecture-aware performance prediction: Models will be developed that combine analysis of predicted data-movement volume in combination with machine learning using algorithmic and architectural features.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.

数据移动的成本大大超过了当前计算机上算术操作执行的成本，并且预计不平衡会变得更糟。因此，在实施算法中，数据流动的最小化至关重要。平铺是一种众所周知的数据局部优化技术，可广泛用于编译器以及密集矩阵/张量计算的高性能数值库。但是，稀疏计算的数据局部性优化是一个重大挑战，在很大程度上是因为数据访问模式尚不清楚。该项目提出了一项研究计划，以系统地探索与稀疏矩阵/张量计算的数据局部优化有关的许多问题。该项目确定了在机器学习和数据分析中使用的稀疏计算的重要子类，并提出了工具和技术，以实现对多核CPU和GPU的高性能并行实现。 The broader impact of the project will be the enhancement of programmer productivity and the enabling of software portability and high performance for applications in data analytics and machine learning.The challenge of data-locality optimization for the data-dependent and irregular access patterns that occur with sparse matrix/tensor computations will be addressed through research along multiple directions: 1) Compact signatures for sparse matrices: the strong relationship between the data access patterns for key sparse机器学习和数据分析中使用的矩阵原始图驱动了一维签名向量的开发，这些向量捕获了二维稀疏模式的基本特征，因为它与内存层次结构中需要的数据移动有关； 2）稀疏瓷砖：稀疏矩阵签名向量将作为基于目标平台特征的动态决策的基础，用于瓷砖尺寸的选择和瓷砖调度，以进行负载平衡的执行； 3）矩阵重新定制/重新排序：将研究行/列重新排序对稀疏基质原语的性能的影响，并将设计新的重新排序方案，以增强对关键稀疏矩阵/张量原始原始原始原始的数据局部性； 4）稀疏微粒：将针对CPU/GPU开发和优化微粒，并用作最低级别的构建块，该块在稀疏矩阵/张量计算的瓷砖执行中执行最内部的瓷砖； 5）建筑感知的性能预测：将开发模型，将预测数据移动量的分析与使用算法和建筑特征结合机器学习结合。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛影响的审查标准来通过评估来支持的。

项目成果

Sparsity-Aware Tensor Decomposition

稀疏感知张量分解

• DOI: 10.1109/ipdps53621.2022.00097
• 发表时间: 2022
• 期刊: 2022 IEEE International Parallel and Distributed Processing Symposium
• 作者: Kurt, Sureyya Emre;Raje, Saurabh;Sukumaran-Rajam, Aravind;Sadayappan, P.
• 通讯作者: Sadayappan, P.

Efficient Tiled Sparse Matrix Multiplication through Matrix Signatures

• DOI: 10.1109/sc41405.2020.00091
• 发表时间: 2020-11
• 期刊: SC20: International Conference for High Performance Computing, Networking, Storage and Analysis
• 作者: Süreyya Emre Kurt;Aravind Sukumaran-Rajam;F. Rastello;P. Sadayappan

Communication Optimization for Distributed Execution of Graph Neural Networks

• DOI: 10.1109/ipdps54959.2023.00058
• 发表时间: 2023-05
• 期刊: 2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
• 作者: Süreyya Emre Kurt;Jinghua Yan;Aravind Sukumaran-Rajam;Prashant Pandey;P. Sadayappan