权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Software optimization by synergy of machine learning and high performance computing

机器学习和高性能计算协同优化软件

基本信息

批准号：
18F18786
负责人：
須田礼仁
金额：
$ 0.96万
依托单位：
The University of Tokyo
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2018
资助国家：
日本
起止时间：
2018-11-09 至 2021-03-31
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18F18786/
关键词：
通信削減アルゴリズム matrix powers kernel parallel computing sparse matrix spMV iterative methods 深層学習 Dense layer Pruning データ圧縮

项目摘要

We implemented DMPK (Diamond Matrix Powers Kernel) with parallelization of MPI and optimized assignment of tasks to processors. We also analyzed the amount of communication and redundant computation when using different number of phases and compared them to PA1 and PA2, which are the known methods of matrix powers kernel. These results been presented at HPCAsia2020 in Fukuoka.Matrix Powers Kernel (MPK) algorithms calculate the vector Akx, obtained by multiplying an initial vector x with the k-th power of matrix A. Our algorithm, Diamond Matrix Powers Kernel (DMPK) generalizes the MPK algorithms PA1 and PA2 by Demmel et al. PA1 and PA2 can be used for general matrices. They improve performance by reducing the amount of communication, which is often the bottleneck, but they introduce redundant computations. In scientific computations with regular access patterns, diamond tiling algorithms achieve similar communication avoidance without introducing any redundant communication by introducing moving index domains. By combining these two approaches, DMPK, is applicable to general matrices and makes it possible to reduce the amount of redundant computation at the price of slightly higher amount of communication. This is done by translating the concept of moving index domains to general matrices: the algorithm is performed in “phases” and after each phase the graph (corresponding to the matrix) is repartitioned.

通过MPI的并行化和任务的优化分配实现了DMPK（Diamond Matrix Powers Kernel）。我们还分析了使用不同相位数时的通信量和冗余计算量，并将其与矩阵幂核的已知方法PA 1和PA 2进行了比较。这些结果已在福冈的HPCAsia2020上展示。矩阵幂核（MPK）算法计算向量Akx，该向量通过将初始向量x乘以矩阵A的k次幂获得。本文提出的钻石矩阵幂核算法（DMPK）是Demmel等人提出的MPK算法PA1和PA2的推广，PA1和PA2可用于一般矩阵。它们通过减少通信量来提高性能，这通常是瓶颈，但它们引入了冗余计算。在具有规则访问模式的科学计算中，菱形平铺算法通过引入移动索引域来实现类似的通信避免，而不引入任何冗余通信。通过结合这两种方法，DMPK，适用于一般的矩阵，并使得它有可能减少冗余的计算量，在稍高的通信量的代价。这是通过将移动索引域的概念转换为一般矩阵来完成的：该算法在“阶段”中执行，并且在每个阶段之后，图（对应于矩阵）被重新分区。