并行矩阵产品

Question

为了计算并行模式下2个矩阵A和B（nxm维度）之间的乘积，我有以下限制：服务器向每个客户端发送来自矩阵A的若干行，来自矩阵B的行。这不能改变。此外，客户可以在彼此之间交换信息，以便计算矩阵产品，但是他们不能要求服务器发送任何其他数据。

这应做最有效的可能，通过最小化进程之间发送的消息的数量意思 - 视为一个昂贵的操作 - 并且通过这样做小的计算并行地，尽可能多地。

据我的研究，客户之间交换的实际消息的次数最多为n^2，在情况下，每个进程广播其线路连接到所有其他人。现在，问题是，如果我最小化发送的消息数 - 这将围绕分发输入数据的log（n） - 但计算只能由一个进程完成，或者更多，但无论如何，它不是再一次平行完成，这是问题的主要思想。

什么可能是一个更有效的算法，可以计算这个产品？

（我正在使用MPI，如果它有任何区别）。

Answer 1

为了计算矩阵乘积C = A x B元素的元素，你简单地计算C(i,j) = dot_product(A(i,:),B(:,j))。也就是说，C的（i，j）元素是A的第i行和第j列的点积。

如果你坚持发送A行和B行的行，那么你将有编写一个并行程序的难度很大，它的性能超过了一个简单的串行程序。相反，你应该做的是发送行A和B的列到处理器计算C的元素。如果你被约束发送A行和B行，那么我建议你这样做，但计算产品在服务器上。也就是说，忽略所有的工作处理器，只是连续执行计算。

一种替代方法是计算工作人员处理器上的部分点积并累积部分结果。这将需要一些棘手的编程;它可以完成，但如果在第一次尝试时，您可以编写一个优于简单串行程序的程序（在执行速度上），我会感到非常惊讶。

（是的，还有其他的方法来分解矩阵，矩阵产品，为并行执行，但他们比前面更为复杂。如果你想调查这些然后Matrix Computations是开始阅读的地方。）

您还需要认真思考您提出的效率衡量标准 - 最有效的信息传递程序将是不传递任何信息的程序。如果消息传递的成本远远超过计算成本，那么无信息传递的实现将是两种方法最有效的。一般来说，并行程序的效率度量是加速比与处理器数量的比率：所以在8个处理器上的8倍加速是完全有效的（并且通常不可能实现）。

正如你所说的是不是一个明智的问题。问题制定者可能错误地指定了它，或者你错误地陈述了（或误解了）正确的规范。

Answer 2

某些东西不对：如果两个矩阵都有n x m尺寸，则它们不能相乘（除非n = m）。在A * B的情况下，A必须具有与B具有行数一样多的列。你确定服务器没有发送B的转置行吗？这相当于从B发送列，在这种情况下解决方案是微不足道的。

假设所有这些都检出，并且您的客户确实从A和B获得了行：最简单的解决方案可能是为每个客户端将其行的矩阵B发送到客户端＃0，该客户端重新对原始矩阵B ，然后将其列发送回其他客户端。基本上，客户＃0将作为一个真正知道如何有效分解数据的服务器。这将是2*(n-1)消息（不包括用于统一产品矩阵的消息），但考虑您如何在客户端之间分配A和B矩阵的消息，没有显着的性能损失（它仍然是O(n)消息）。

这里最大的瓶颈显然是矩阵B的初始聚集和重新分配，这个矩阵非常可缩放，所以如果你有相当小的矩阵和很多进程，你可能会更好地在服务器上串行计算产品。

Answer 3

我不知道这是否是功课。但如果它不是家庭作业，那么你应该使用一个图书馆。一种想法是ScaLAPACK的

http://www.netlib.org/scalapack/scalapack_home.html

的ScaLAPACK在FORTRAN writtten，但你可以从C调用它++。