使用MPI进行矩阵乘法

Question

我刚开始接触并行编程，正在尝试矩阵乘法。我已将问题分割如下：

令操作为mat3 = mat1 x mat2 我将mat2广播到通信器中的所有进程，并从mat1中切出一些行条带并将它们分散到通信器组中的进程。当所有进程都拥有整个mat2和相应的mat1条带时，它们将条带与mat2相乘，然后使用过程的本地结果进行收集操作，并在根进程中累加整个结果。

我想知道是否有更好的问题分割方法来在通用计算机上乘两个矩阵。

我的实现是在OpenMPI中完成的。

- fuzzy

Answer 1

文献中有各种关于矩阵乘法的算法可以扩展到MPI范例中。例如：

> 1Dsystolic [1] 
> 2D-systolic, Cannon’s algorithm [2];
> Fox’s algorithm [3];
> Berntsen’s algorithm [4];
> DNS algorithm [5].

如果忽略矩阵属性（如稀疏等），它基本上是关于如何在进程之间分布数据以最小化同步和负载不平衡（分布在每个进程中的工作量）的问题。

在这个最近的工作中，您可以看到两种不同的数据分布方法以及它们之间的比较。

论文：

[1] Golub G.H and Van C.H L., “Matrix Computations.”,Johns Hopkins University Press, 1989.
[2] Whaley R. C., Petitet A., Dongarra J. J., “Automated empirical optimizations of software and the ATLAS project” Parallel Computing 27, 1.2 (2001), 3.35.
[3] Fox G. C., Otto S. W., and Hey A. J. G., “Matrix algorithms on a hypercube I:
Matrix multiplication”,Parallel Computing, vol. 4, pp. 17-31. 1987.
[4] Berntsen J.,“Communication efficient matrix multiplication on hypercubes, Parallel Computing”, vol. 12, pp. 335-342, 1989.
[5] Ranka S. and Sahni S., “Hypercube Algorithms for Image Processing and Pattern Recognition”, Springer- Verlag, New York, NY, 1990.

- dreamcrash