Software optimization by synergy of machine learning and high performance computing

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

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.