Collaborative Research: PPoSS: Planning: Cross-layer Coordination and Optimization for Scalable and Sparse Tensor Networks (CROSS)

高维数据计算或分析在许多领域都变得越来越重要，例如量子化学/物理、量子电路模拟、脑处理、社交网络、医疗保健和机器/深度学习等。张量作为高维数据的一种表示形式，正发挥着越来越重要的作用，张量方法也是如此。在过去的几年里，人们从高性能计算以及编译器和计算机体系结构的角度对低维数据(三维到五维)的张量分解或因式分解进行了广泛的研究，而针对超高维数据(超过十维)的张量网络和提取有物理意义的潜在变量的张量网络由于其复杂的数学性质、极高的计算复杂性和更多领域相关的挑战而不发达。该项目的新颖性是多方面的：1)具有算法和系统优化的内存异构性感知表示，可用于解决其他问题，如不规则应用和稀疏数值方法；2)专门的稀疏张量网络加速器架构的硬件-软件协同设计，这是稀疏张量网络的最早硬件实现之一。该项目的影响是：1)推进最先进的张量分解研究，以模拟真正的高阶和稀疏数据；2)通过研究热切的应用程序，触发从学术界到研究实验室到行业的更紧密的长期合作；3)带来适当的教育机会。该项目为配备各种类型加速器的异类系统(如GPU、TPU和FPGA)以及具有动态和非易失性随机存取存储器(DRAM NVRAM)的异类存储器提出了可扩展和稀疏张量网络的跨层协调和优化。本研究旨在通过引入约束、正则化、字典和/或领域知识来研究广泛使用的张量网络中的稀疏性，以获得更好的数据压缩、更快的计算速度、更低的内存使用量和更好的可解释性。除了稀疏性的挑战，稀疏张量网络还受到维度灾难、严重的数据随机性和不规则的程序和内存访问行为的影响。该规划项目从四个角度进行了初步研究，旨在解决这些挑战：(1)内存异构性感知的表示和数据(重)排列，(2)智能页面排列的平衡稀疏张量收缩(SPTC)算法，(3)记忆和智能分配以降低计算成本，(4)稀疏张量网络的专用加速器架构。优化的稀疏张量网络将包括高性能计算、算法、编译器、计算机体系结构和性能建模，并将在多个应用场景下进行测试。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

High-dimensional data computation or analytics are gaining importance in many domains, such as quantum chemistry/physics, quantum circuit simulation, brain processing, social networks, healthcare and machine/deep learning, to name a few. Tensors, a representation of high-dimensional data, are playing an increasingly critical role, and so are tensor methods. Tensor decompositions or factorizations of low-dimensional data (three to five dimensions) have been extensively studied over the past years from a high-performance computing and also compiler and computer architecture angles for their computational core operations, while tensor networks targeting very high-dimensional data (over ten dimensions) and extracting physically meaningful latent variables are underdeveloped because of their complicated mathematical nature, extremely high computational complexity, and more domain-dependent challenges. The project’s novelties are manifold: 1) memory heterogeneity-aware representations with algorithm and system optimizations, which could be adopted to solve other problems such as irregular applications and sparse numerical methods; 2) hardware-software co-design of specialized, sparse-tensor network-accelerator architectures, that are among the first hardware implementations of sparse-tensor networks. The project’s impacts are 1) advancing state-of-the-art tensor decomposition studies to model true higher-order and sparse data; 2) triggering a closer long-term collaboration ranging from academia to research labs to industry by studying solicitous applications; 3) bringing appropriate educational opportunities.This project proposes Cross-layer cooRdination and Optimization for Scalable and Sparse-Tensor Networks (CROSS) for heterogeneous systems that are equipped with various types of accelerators, such as GPUs, TPUs and FPGAs, as well as heterogeneous memories with dynamic and non-volatile random-access memories (DRAM+NVRAM). This research aims to study the sparsity in widely used tensor networks by introducing constraints, regularization, dictionaries, and/or domain knowledge for better data compression, faster computation, lower memory usage and better interpretability. Besides the sparsity challenges, sparse-tensor networks also suffer from the curse of dimensionality, aggravated data randomness and irregular program and memory access behaviors. This planning project conducts preliminary research that aims to address these challenges from four perspectives: (1) memory heterogeneity-aware representations and data (re-)arrangement, (2) balanced sparse tensor contraction (SpTC) algorithms with smart page arrangement, (3) memoization and intelligent allocation to reduce computational cost, and (4) specialized accelerator architectures for sparse-tensor networks. The optimized sparse tensor networks will encompass efforts from high-performance computing, algorithms, compilers, computer architecture and performance modeling and will be tested under multiple application scenarios.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.