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

数据移动的成本远远超过了在当前计算机上执行算术运算的成本，而且这种不平衡预计只会变得更糟。因此，最大限度地减少算法实现中的数据移动是至关重要的。平铺是一种众所周知的数据局部性优化技术，广泛用于编译器以及用于密集矩阵/张量计算的高性能数值库。然而，稀疏计算的数据局部性优化是一个巨大的挑战，这在很大程度上是因为数据访问模式是先验未知的。该项目提出了一项研究计划，以系统地探索与稀疏矩阵/张量计算的数据局部性优化有关的一些问题。该项目确定了机器学习和数据分析中使用的稀疏计算的一个重要子类，并提出了在多核CPU和GPU上实现高性能并行实施的工具和技术。该项目更广泛的影响将是提高程序员的生产力，并使软件可移植性和高性能用于数据分析和机器学习中的应用。将通过沿多个方向的研究来解决数据依赖和不规则访问模式的数据局部性优化的挑战：1)稀疏矩阵的紧凑签名：机器学习和数据分析中使用的关键稀疏矩阵基元的数据访问模式之间的强烈关系驱动一维签名向量的开发，该一维签名向量捕捉二维稀疏模式的基本特征，因为它与存储器层次中所需的数据移动有关；2)稀疏平铺：稀疏矩阵签名向量将作为基于目标平台特征的动态决策的基础，用于平铺大小的选择和用于负载平衡执行的平铺的调度；3)矩阵重新编号/重新排序：将研究行/列重新排序对稀疏矩阵基元的性能的影响，并将设计新的重新排序方案以增强关键稀疏矩阵/张量原语的数据局部性；4)稀疏微核：将为CPU/GPU开发和优化微核，并将其用作在稀疏矩阵/张量计算的平铺执行中执行最内部平铺的最低层构建块；5)架构感知性能预测：将开发模型，将预测数据移动量的分析与使用算法和架构特征的机器学习相结合。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.