CAREER: Communication-Avoiding Tensor Decomposition Algorithms

职业：避免通信的张量分解算法

• 批准号: 1942892
• 负责人: Grey Ballard
• 金额: $ 56.01万
• 依托单位: Wake Forest University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-03-01 至 2025-02-28
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1942892&HistoricalAwards=false
• 关键词: CAREER; Communication; Avoiding; Tensor; Decomposition

Advances in sensors and measurement technologies, extreme-scale scientific simulations, and digital communications all contribute to a data avalanche that is overwhelming analysts. Standard data-analytic techniques often require information to be organized into two-dimensional tables, where, for example, rows correspond to subjects and columns correspond to features. However, many of today's data sets involve multi-way relationships and are more naturally represented in higher-dimensional tables called tensors. For example, movies are naturally 3D tensors, communication information tracked between senders and receivers across time and across multiple modalities can be represented by a 4D tensor, and scientific simulations tracking multiple variables in three physical dimensions and across time are 5D tensors. Tensor decompositions are the most common method of unsupervised exploration and analysis of multidimensional data. These decompositions can be used to discover hidden patterns in data, find anomalies in behavior, remove noise from measurements, or compress prohibitively large data sets. The aim of this project is to develop efficient algorithms for computing these decompositions, allowing for analysis of multidimensional datasets that would otherwise take too much time or memory. The education plan includes the development of a textbook and course aimed to introduce undergraduate and graduate students to tensor decompositions and multidimensional data analysis.Computing tensor decompositions on data of today’s magnitude in reasonable time requires algorithms to be efficient, not only in the number of arithmetic operations they perform, but also in the amount of data they communicate through the memory hierarchy and among processors. This project aims to develop communication-efficient algorithms for computing tensor decompositions that will scale well to data sets of arbitrary size and dimension; these algorithms will enable efficient and accurate analysis of huge datasets that require distribution across multiple processors’ memories. The first thrust of the project will be to prove communication lower bounds for the key kernels used by algorithms for computing the most common decompositions, and use those bounds to drive algorithmic improvements. The second thrust of the project will be to use randomization to trade off deterministic accuracy for reduced data movement and computational complexity. The third thrust is to adapt the developed algorithms to variants of these decompositions. The algorithms produced by the proposed project will contribute to both high-level productivity-oriented software packages and highly efficient, parallel implementations written in low-level languages.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.

传感器和测量技术的进步，极端规模的科学模拟和数字通信都有助于数据雪崩，这是压倒性的分析。 标准的数据分析技术通常需要将信息组织成二维表格，例如，行对应于主题，列对应于特征。 然而，今天的许多数据集涉及多路关系，并且更自然地表示在称为张量的高维表中。 例如，电影自然是3D张量，跨时间和跨多个模态跟踪的发送者和接收者之间的通信信息可以由4D张量表示，并且在三个物理维度和跨时间跟踪多个变量的科学模拟是5D张量。 张量分解是多维数据的无监督探索和分析的最常见方法。 这些分解可用于发现数据中隐藏的模式，发现行为中的异常，从测量中去除噪声，或压缩过大的数据集。 这个项目的目的是开发有效的算法来计算这些分解，允许多维数据集的分析，否则会花费太多的时间或内存。 该教育计划包括开发一本教科书和一门课程，旨在向本科生和研究生介绍张量分解和多维数据分析。在合理的时间内对当今量级的数据计算张量分解要求算法高效，不仅在它们执行的算术运算数量上，而且在它们通过存储器层次结构和处理器之间通信的数据量上。该项目旨在开发用于计算张量分解的通信高效算法，这些算法将很好地扩展到任意大小和维度的数据集;这些算法将能够有效和准确地分析需要分布在多个处理器内存中的大型数据集。 该项目的第一个推力将是证明用于计算最常见分解的算法所使用的关键内核的通信下限，并使用这些界限来推动算法的改进。该项目的第二个重点将是使用随机化来权衡确定性精度，以减少数据移动和计算复杂性。第三个推力是适应这些分解的变种开发的算法。 该项目所产生的算法将有助于高层次的生产力为导向的软件包和高效，并行实现编写的低级languages.This奖项反映了NSF的法定使命，并已被认为是值得通过评估使用基金会的智力价值和更广泛的影响审查标准的支持。

项目成果

Parallel Algorithms for Tensor Train Arithmetic

• DOI: 10.1137/20m1387158
• 发表时间: 2020-11
• 期刊: SIAM J. Sci. Comput.
• 作者: Hussam Al Daas;Grey Ballard;P. Benner

Parallel Tensor Train Rounding using Gram SVD

使用 Gram SVD 进行并行张量训练舍入

• DOI: 10.1109/ipdps53621.2022.00095
• 发表时间: 2022
• 期刊: Proceedings of the 2022 IEEE International Parallel and Distributed Processing Symposium
• 作者: Al Daas, Hussam;Ballard, Grey;Manning, Lawton
• 通讯作者: Manning, Lawton

Brief Announcement: Tight Memory-Independent Parallel Matrix Multiplication Communication Lower Bounds

简短公告：严格的内存独立并行矩阵乘法通信下界

• DOI: 10.1145/3490148.3538552
• 发表时间: 2022
• 期刊: Proceedings of the 34th Annual ACM Symposium on Parallelism in Algorithms and Architectures
• 作者: Al Daas, Hussam;Ballard, Grey;Grigori, Laura;Kumar, Suraj;Rouse, Kathryn
• 通讯作者: Rouse, Kathryn

Visualizing Parallel Dynamic Programming using the Thread Safe Graphics Library

使用线程安全图形库可视化并行动态编程

• DOI: 10.1109/eduhpc54835.2021.00009
• 发表时间: 2021
• 期刊: 2021 IEEE/ACM Ninth Workshop on Education for High Performance Computing (EduHPC
• 作者: Ballard, Grey;Parsons, Sarah
• 通讯作者: Parsons, Sarah

Parallel Memory-Independent Communication Bounds for SYRK

SYRK 的并行内存独立通信范围

• DOI: 10.1145/3558481.3591072
• 发表时间: 2023
• 期刊: Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures
• 作者: Al Daas, Hussam;Ballard, Grey;Grigori, Laura;Kumar, Suraj;Rouse, Kathryn
• 通讯作者: Rouse, Kathryn