大家好,我最近在做一个算法的并行设计过程中遇到个问题,希望能通过在该版的讨论找到解决思路.不管应用背景,存在疑问的那段代码就是并行矩阵乘法,问题描述如下.

矩阵A:1500x1500 矩阵B:1500x1500, A与B相乘后得C,同样也是1500x1500,在16节点Beowulf机群上(每个节点只有一个CPU)使用MPICH2实现(C语言)算法并行设计,并行矩阵乘算法参考陈国良老师编写的<并行算法实践>.简单说来,就是将C=AxB中的左矩阵A按行划分,右矩阵B按列划分,分别存储在不同的机器上,然后在各计算节点间传送B矩阵的各子块实现运算.假设有p个处理器,A从行方向被分解为p块,各子块记为A(i);B从列方向分解为p块,各块为B(j);计算共分(p-1)步,步骤如下:

1. {dy}步, p个计算节点上A,B矩阵存储状况依次为A(1),B(1);A(2),B(2);...;A(p),B(p),各计算节点A(i)和B(j)相乘，得C(ij)

2. 第二步, p个计算节点交换B矩阵，交换后A，B矩阵在各机器分布情况为A(1),B(2);A(2),B(3);...;A(p-1),B(p);A(p),B(1),各节点A(i)和B(j)相乘，得C(ij)

3. 按第二步方法继续传输数据，直到计算完矩阵C所有的子块C(ij)

这个算法在16个节点上的计算时间如下：

CPU个数       计算时间

1                   63秒

2                   26秒

4                   10秒

8                   6秒

16                2.5秒

在不考虑通信时间的前提下，按理说p个计算节点的计算时间应该是1个CPU时的p分之一，但是可以看出，当CPU数大于1时，计算时间小于p分之一，为超加速比。如果考虑网络通信的话，计算部分的超加速现象更加明显，不知这个现象如何解释？个人猜测是否是由于A、B被分解后，每次参与运算的子矩阵规模变小，内存操作时间大幅降低，从而出现超加速比现象？不知这种解释是否合理？本人非计算机专业出身，此前未接触过并行矩阵运算方向的研究，希望能向高手请教。

这就是一个超线性加速比的现象。

那么，什么是超线性加速比呢？简单来说，就是在p个处理器上运行的并行程序的运行速度是相应的串行程序运行速度的p倍甚至p倍以上。我们知道，理想的并行程序运行速度是串行程序运行速度的p倍，但是由于通信延迟，负载不均等原因，是很难达到理想的速度的。

但是这个超线性加速比现象应该如何解释呢？基本的解释是并行程序完成了较少的工作。最通常的情况是，并行执行时所要访问的数据都驻留在每个处理器的cache中，而顺序执行时必须访问存储器系统中较慢的部分，因为此时数据无法全都驻留在单个cache中。当然，超线性加速比现象毕竟是很少的，因为存储器系统更有效的使用必定会克制所有的并行开销。第二种超线性加速比情况出现在当所要查找的元素已发现因而终止搜索时。当搜索以并行方式进行时，能以不同的次序有效地进行，意味着总的被搜索数据量将少于顺序搜索的情况。因此，并行执行将完成较少的工作。

也就是说，出现这种情况是因为并行程序完成的总体工作量实际上是少于串行程序的，因此造成了超线性加速比现象的出现。