CAREER: Recursive Distributed Matrix and Tensor Decompositions on Neural Engines

University Of Houston, Houston TX

Investigators

Abstract

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.