CAREER: Recursive Distributed Matrix and Tensor Decompositions on Neural Engines

矩阵和张量分解是科学计算中最重要的组成部分之一，在以数据为中心的计算和机器学习模型中越来越重要。缺乏能够有效处理大型数据集和利用无处不在的神经引擎的软件和算法阻碍了进步。基于复杂数据分发方案的遗留分布式矩阵包不仅会增加在新领域采用的摩擦，而且还会阻碍大规模探索尖端算法。新的令人兴奋的算法，如随机线性代数、结构化矩阵计算和高级特征分解，与神经引擎协同，仍然没有被探索，临时的，或者很难被非专家在数值分析中使用。新的强大架构——神经引擎——承诺了数量级的性能和能源效益，但在神经网络之外的使用仍然是一个挑战。本提案旨在通过协同研发，创建一个统一的软件系统，在神经引擎上实现高性能、可扩展、分布式矩阵和张量分解。该项目解决了三个研究重点，以实现其目标。A)与传统的以算法为中心的算法设计相比，本研究侧重于通信高效的算法变体。实现上述目标的一个核心挑战是避免和管理数据移动。神经引擎的计算速度已经变得惊人的快，而数据移动延迟和带宽远远落后，差距正在扩大。B)将神经引擎与最先进的数值算法相结合。最近的数值分析在随机算法、低精度直接分解作为前置条件以及基于极性分解的特征系统的新的光谱分治方法方面取得了一些令人兴奋的进展。这些新的发展不仅本身令人兴奋，而且它们有潜力很好地利用神经引擎，并自然地与以通信为中心的算法相结合。C)探索通用分布式阵列（Universal Distributed Array， UDA），这是一种基于多维循环数据分布方案的新数据结构，可实现负载均衡、可扩展性，并统一支持所有矩阵和张量分解。该方案扩展了循环数据分发方案，以支持通信高效的算法，包括递归算法（由于灵活的对齐），并扩展了多维数据分发方案以支持张量分解。该项目将在分布式神经引擎上开发高效、可扩展、易于使用的通信和计算原语，并将包括最有用的矩阵/张量分解算法作为可组合和可扩展的库。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Matrix and tensor decompositions are one of the most important building blocks for scientific computing and are increasingly important in data-centric computing and machine-learning models. The lack of software and algorithms that can efficiently deal with large data sets and exploit the ubiquitous availability of neural engines is holding back progress. Legacy distributed matrix packages based on complex data distribution schemes not only add friction in adoption in new areas but also impede the exploration of cutting-edge algorithms at scale. New exciting algorithms such as randomized linear algebra, structured matrix computation, and advanced eigen decompositions that are synergistic to neural engines remain unexplored, ad-hoc, or hard to use by non-experts in numerical analysis. New powerful architectures -- neural engines -- promise orders of magnitudes o performance and energy benefits but remain a challenge to use outside of neural networks. This proposal aims to create a unified software system to achieve high-performance, scalable, distributed matrix and tensor decompositions on neural engines through concerted research and development.This project addresses three research thrusts to achieve its goals. A) In contrast to conventional arithmetic-centric algorithm design, this research focuses on communication-efficient algorithm variants. A central challenge in realizing the proposed goals is the avoidance, and management, of data movement. Computation speed has become amazingly fast on neural engines, while data movement latency and bandwidth lag far behind and the gap is widening. B) Incorporation of neural engines to state-of-the-art numerical algorithms. Recent numerical analysis has seen some exciting developments in randomized algorithms, low-precision direct decomposition as a preconditioner, and novel polar decomposition-based spectral divide-and-conquer methods for eigensystems. These new developments are not only exciting by themselves, but they have the potential to exploit neural engines especially well and blend with communication-centric algorithms naturally. C) Exploration of Universal Distributed Array (UDA), a new data structure based on a multi-dimensional cyclic data distribution scheme, to achieve load balancing, scalability, and unified support for all matrix and tensor decompositions. This proposal extends the cyclic data-distribution scheme to support communication-efficient algorithms including recursive algorithms due to flexible alignment, and to multi-dimensional to support tensor decomposition. The project will develop efficient, scalable, and easy-to-use communication and computational primitives on distributed neural engines and will include the most useful matrix/tensor decomposition algorithms as a composable and extensible library.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.