并行矩阵乘法——Cannon算法的原理实现以及性能评测
源码：https://github.com/Cloveryww/MPI-parallel-algorithms/tree/master/cannon
欢迎Star！！！
———————————————————————————————————————————
算法简介
算法流程图
算法设计方法和模式
任务划分：
根据矩阵乘法公式中的累加计算的可分离性，将参与计算的两个矩阵分解成p个小矩阵块(共有p个计算节点)，每个节点只进行局部的小矩阵乘法，最终计算结束后将局部的小结果矩阵发送回Master节点。
通讯分析：
由于算法在下发任务和收集结果的时候采用了主从模式，所以使用了Master-Worker的全局通讯，该部分通讯由于发送方只有一个0号线程，所以无法并行执行，只能串行执行。同时，在迭代进行小矩阵运算时，各计算节点之间也需要交换矩阵，进行了结构化通讯。该部分通讯由于通讯的局部特性，可以并行执行，能够提高效率。
任务组合：
每个节点负责一个小矩阵的串行计算，同时负责小矩阵之间的通讯传递。
处理器映射：
由于任务的划分个数等于处理器个数，所以在组合任务的同时完成了处理器映射。
Cannon算法采用了主从模式的同时也采用了分而治之的模式。一方面，0号线程作为Master，负责矩阵A和矩阵B以及矩阵C的I/O，也负责小矩阵的分发和结果的聚集。而其他节点作为Worker进行本地的小矩阵串行乘法计算。另一方面，Cannon算法将两个大矩阵的乘法运算分解为若干各小矩阵的乘法运算，最终计算结束后，将计算结果聚集回来，也采用了分而治之的思想。cannon算法不仅实现了矩阵乘法运算的并行化，也减少了分块矩阵乘法的局部存储量，节省了节点的内存开销。
算法复杂度
设计算的是一个n*n的矩阵乘一个n*n的矩阵，共有p个节点，那么Cannon算法的时间复杂度计算如下：
矩阵乘加的时间由于采用了并行化，所以所需时间为：
若不考虑节点延迟时间，设节点之间通讯的启动时间为，传输每个数字的时间为
，则在两个节点间传输一个子矩阵的时间是：
所以节点之间传输子矩阵所需的时间为：
综上，cannon算法总的所需时间为：
算法的时间复杂度为:
cannon算法中每个节点（除0号Master节点外）只需要3个小矩阵块大小的内存空间，相比较条带分割的矩阵并行乘法，大大降低了其空间复杂度，共需内存大小
因此，算法的空间复杂度为：
算法性能分析
|
矩阵大小 线程数 |
500*500 |
1000*1000 |
1500*1500 |
2000*2000 |
1 |
0.99 |
5.87 |
22.21 |
74.90 |
4 |
0.27 |
1.46 |
5.05 |
9.86 |
9 |
0.11 |
0.83 |
2.28 |
5.78 |
16 |
0.05 |
0.47 |
1.43 |
2.97 |
除了线程的个数对算法的性能有影响，线程在不同节点的分布也对算法的性能有影响。
经过实验，发现在同一节点下9个线程的效率比3个节点下，每个节点3个线程，共9个线程的效率要高，通过Vampir分析，发现跨节点的线程通信的代价要远高于本地跨核通信的代价。
这也提醒我们，在设计和运行并行算法时，也与要考虑线程在不同节点之间和本节点之间通信的代价，尽量在本节点内通信。
下面两幅图是进行1500*1500的矩阵乘法是，都使用9个线程进行计算的性能分析。其中图一使用了3个节点，每个节点3个线程，图二只使用了1个节点，共9个线程。可以看出3个节点中有两个线程进行线程通信时代价很高，这是因为跨节点通信导致的，而图二则没有这种现象。
图 1
图 2
当矩阵过小时，cannon算法由于计算时间相比较初始化和通讯代价较小，无法体现出并行算法的优势。
如11*10的矩阵乘10*13的矩阵，共使用9个线程：并行算法和穿行算法苏勇时间都小于0.01s，如下图3所示并行算法中大部分计算量都是初始化工作和线程的通讯。
图 3
以2000*2000大小的矩阵和9个线程的计算为例(图4)，可以看出，线程出现空闲等待的部分主要包括0号Master线程分发矩阵和收集结果的步骤，以及每完成一个周期的小矩阵块计算后需要同步再进入下一周期，此期间交换小矩阵块时的通信造成一定程度的空闲等待。
后续可以采用并行读写文件的方式将数据I/O也并行化，提高性能。
图 4