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

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

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.