利用Cannon算法证明跨节点的线程通信的代价要远高于本地跨核通信的代价

算法简介

算法流程图

算法设计方法和模式

任务划分：

根据矩阵乘法公式中的累加计算的可分离性，将参与计算的两个矩阵分解成 p 个小矩阵块(共有 p 个计算节点)，每个节点只进行局部的小矩阵乘法，最终计算结束后将局部的小结果矩阵发送回 Master 节点。

通讯分析：

由于算法在下发任务和收集结果的时候采用了主从模式，所以使用了 Master-Worker 的全局通讯，该部分通讯由于发送方只有一个 0 号线程，所以无法并行执行，只能串行执行。同时，在迭代进行小矩阵运算时，各计算节点之间也需要交换矩阵，进行了结构化通讯。该部分通讯由于通讯的局部特性，可以并行执行，能够提高效率。

任务组合：

每个节点负责一个小矩阵的串行计算，同时负责小矩阵之间的通讯传递。

处理器映射：

由于任务的划分个数等于处理器个数，所以在组合任务的同时完成了处理器映射。

Cannon 算法采用了主从模式的同时也采用了分而治之的模式。一方面，0 号线程作为 Master，负责矩阵 A 和矩阵 B 以及矩阵 C 的 I/O，也负责小矩阵的分发和结果的聚集。而其他节点作为 Worker 进行本地的小矩阵串行乘法计算。另一方面，Cannon 算法将两个大矩阵的乘法运算分解为若干各小矩阵的乘法运算，最终计算结束后，将计算结果聚集回来，也采用了分而治之的思想。cannon 算法不仅实现了矩阵乘法运算的并行化，也减少了分块矩阵乘法的局部存储量，节省了节点的内存开销。

算法复杂度

算法性能分析

除了线程的个数对算法的性能有影响，线程在不同节点的分布也对算法的性能有影响。

经过实验，发现在同一节点下 9 个线程的效率比 3 个节点下，每个节点 3 个线程，共 9 个线程的效率要高，通过 Vampir 分析，发现跨节点的线程通信的代价要远高于本地跨核通信的代价。

这也提醒我们，在设计和运行并行算法时，也与要考虑线程在不同节点之间和本节点之间通信的代价，尽量在本节点内通信。

下面两幅图是进行 1500*1500 的矩阵乘法是，都使用 9 个线程进行计算的性能分析。其中图一使用了 3 个节点，每个节点 3 个线程，图二只使用了 1 个节点，共 9 个线程。可以看出 3 个节点中有两个线程进行线程通信时代价很高，这是因为跨节点通信导致的，而图二则没有这种现象。

当矩阵过小时，cannon 算法由于计算时间相比较初始化和通讯代价较小，无法体现出并行算法的优势。

如 1110 的矩阵乘 1013 的矩阵，共使用 9 个线程：并行算法和穿行算法苏勇时间都小于 0.01s，如下图 3 所示并行算法中大部分计算量都是初始化工作和线程的通讯。

以 2000*2000 大小的矩阵和 9 个线程的计算为例(图 4)，可以看出，线程出现空闲等待的部分主要包括 0 号 Master 线程分发矩阵和收集结果的步骤，以及每完成一个周期的小矩阵块计算后需要同步再进入下一周期，此期间交换小矩阵块时的通信造成一定程度的空闲等待。

后续可以采用并行读写文件的方式将数据 I/O 也并行化，提高性能。

以下为性能测试的结果数据：

*500  500*500  16thread 1 node