分布式平台：稀疏矩阵计算

SpGEMM在集群系统上的研究主要集中在节点间通信的最小化上。Jin等人进行一系列实验来研究SpGEMM在PC（个人计算机）集群上的数据通信问题。他们发现由于通信开销，集群很难利用低层次的并行性。因此，想要成功实现并行计算，充分利用高层次并行性至关重要。高层次并行度的增加使得负载均衡的工作更加容易。无论数据通信中使用的是单播还是多播通信，动态调度算法总是比静态调度算法更能保证负载均衡。对于外积并行的SpGEMM，Akbudak等人提出了三个超图模型，这些模型无须任何输入数据的复制，便可实现输入和输出矩阵的同步划分。三个超图模型分别对输入矩阵A和B进行按列和按行的一维划分。第一个超图模型对输出矩阵进行基于非零元的二维划分，而第二个和第三个模型分别对输出矩阵进行按行和按列的一维划分。对应于此划分方案的是两阶段并行SpGEMM算法：无通信的局部SpGEMM计算和多个单节点间的局部SpGEMM结果的累加操作。

Bethune等人研究了开源稀疏线性代数库DBCSR（分布式块压缩稀疏行）中SpGEMM在不同分布式系统上的性能。DBCSR格式编码的矩阵以块压缩的CSR格式存储，分布在由P个MPI进程组成的二维处理器网格上。进程间通信基于通信规约的2.5维算法。

一旦所有数据到达目的进程，就开始执行局部的乘法计算。每个进程传输的数据量按缩放。Selvitopi等人在基于图和超图划分的MapReduce任务中实现map和reduce任务的静态调度。其任务分配的局部性减少了shuffle阶段的数据传输量，并且均衡的计算保证了任务的快速执行。他们证明了他们的调度方法在SpGEMM的MapReduce并行化方面的有效性。他们的模型可以节省大量的数据传输，并且最终实现了相比于随机调度高达4.2倍的加速比。(https://www.xing528.com)

Demirci等人在Accumulo上设计了一种分布式SpGEMM算法，该算法是基于Google Bigtable设计的高度可扩展的分布式key-value存储。这项工作的基本思想是：在将一个key对应的value发送到远程节点之前，先在本地对它们进行规约。他们使用tablet服务器遍历sub−A中的多行，在执行任何计算之前，先将需要一起处理的行分批或者进行批处理扫描操作。同时减少了查找操作的次数和B矩阵行的冗余检索，所以行的批处理大大减少了服务器之间的延迟和通信量。