Cla*_*ara 2 algorithm parallel-processing matrix mpi
为了在并行模式下计算2个矩阵A和B(nxm维度)之间的乘积,我有以下限制:服务器向每个客户端发送矩阵A中的多个行,以及矩阵B中的多个行.这不能改变.此外,客户端可以在彼此之间交换信息,以便计算矩阵产品,但是它们不能要求服务器发送任何其他数据.
这应该尽可能最有效地完成,这意味着通过最小化进程之间发送的消息数量 - 被认为是昂贵的操作 - 并尽可能地并行进行小型计算.
根据我的研究,实际上客户端之间交换的最大数量的消息是n ^ 2,以防每个进程向其他所有进程广播其线路.现在,问题在于如果我最小化发送的消息数量 - 这将是用于分配输入数据的log(n) - 但计算只能由一个或多个进程完成,但无论如何,它不是不再是并行完成的,这是问题的主要思想.
什么是更有效的算法,可以计算这个产品？
(我正在使用MPI,如果它有任何区别).
要C = A x B逐个元素计算矩阵乘积,您只需计算C(i,j) = dot_product(A(i,:),B(:,j)).也就是说,C的(i,j)元素是A的第i行和B的第j列的点积.
如果你坚持发送A行和B行,那么你将很难编写一个性能超过简单串行程序的并行程序.相反,你应该做的是将A行和B行发送到处理器以计算C的元素.如果你被限制发送A行和B行,那么我建议你这样做,但计算服务器上的产品.也就是说,忽略所有工作者处理器并只是连续执行计算.
一种替代方案是在工作处理器上计算部分点积并累积部分结果.这需要一些棘手的编程; 它可以完成,但是如果你第一次尝试编写一个优于(执行速度)简单串行程序的程序,我会非常惊讶.
(是的,还有其他方法可以分解矩阵 - 矩阵产品以进行并行执行,但它们比上述更复杂.如果你想研究它们,那么Matrix Computations就是开始阅读的地方.)
您还需要仔细考虑您提出的效率措施 - 最有效的消息传递程序将是不传递任何消息的程序.如果消息传递的成本远远超过计算成本,那么两个度量的无消息传递实现将是最有效的.一般来说,并行程序效率的衡量标准是加速比与处理器数量的比率:因此,8个处理器的8倍加速是非常有效的(通常无法实现).
如上所述,你的问题不是一个明智的问题.问题制定者错误地指定了它,或者您错误地说明(或误解)了正确的规范.