MPI

一种基于MPI的分布式共轭梯度算法 : 

一种基于MPI的分布式共轭梯度算法 Presented by ZhuangLi

Outline : 

Outline 共轭梯度法 How To Improve Register && Cache Blocking Optimizations Parallel Optimizations && SIMDization MPI Optimizations Data Decomposition 算法总结 矩阵-向量乘实验 实验总结 下一步工作

共轭梯度法 : 

共轭梯度法 数学上，共轭梯度法是求解特定线性系统的数值解的方法，其中的系数矩阵为对称和正定的实数阵。 共轭梯度法是一个迭代方法，所以它适用于稀疏矩阵系统，因为这些系统对于类似乔莱斯基(QR)分解这样的直接方法计算量太大了。 这类系统在数值求解偏微分方程时相当常见

具体应用 : 

具体应用 共轭梯度法主要用于求解下列线性系统 : 其中矩阵 是对称正定实系数矩阵。 非对称阵可以通过左乘转置矩阵构造出对称阵 ，该项操作会加大条件数。

基本流程 : 

基本流程 经过一些简化，可以得到下列求解 的算法

一些观察的结果 : 

一些观察的结果 迭代过程中存在大量的矩阵与向量乘的操作 对于传统的矩阵-向量乘法，其计算复杂度为O(nm)，其中n，m为A矩阵的维度。 结论：矩阵-向量乘是本算法的计算热点，也是进行性能优化的切入点。

Slide 7: 

T(n)=O(f(n)) 效率 时间效率 = +空间效率 算法！ T(n) ≤ × f(n) C C1×C2 算法 性能优化 ?

How To Improve : 

How To Improve 矩阵-向量乘的性能优化，可以由四方面入手： 1. 数据结构的优化(Register && Cache Blocking Optimizations) 2.单结点的并行优化(Parallel Optimizations && SIMDization) 3.分布式的并行优化(MPI Optimizations) 4.分块大小的预调优处理(Data Decomposition)

传统的数据结构 : 

传统的数据结构 传统的对于矩阵数据的主要记录方式分作两类： 一类是列出矩阵的所有元素，以数据表的形式存储。 另一类则是仅仅存储矩阵中的非零元素，将之标记为<r，c，v>的三元组，其中表示r该元素的行号，c表示该元素的列号，v表示该元素的值。

Register && Cache Blocking Optimizations : 

Register && Cache Blocking Optimizations Register && Cache Blocking Optimizations利用BSCR进行实现。 BSCR，全称Blocked Compressed Sparse Row，是一种高度压缩的分块存储结构。 该结构对第二类记录方式进行了有效的改进，大大降低了存储的冗余度，使用了四个不同意义的向量<row，block，col，val>，有效保存了原矩阵的信息，并保持了对矩阵中划分块的控制，从而便于计算量在各个结点上的相关部署。

结构 : 

结构 设分块阵大小为X*Y，原矩阵大小为M*N。 row向量累计原矩阵自顶向下每X行内的分块数，从而可以通过[ row(i), row(i + 1) )就能够表示出第[i*X, ( i + 1 )* X)行内分块号的区间，从而通过row向量支配block向量。 block向量根据类似的原理记录每个块内的非0元素区间，每X个block元素记录一个块的结构，其中每2个相邻元素构成一个区间来表示块中某一行的元素编码区间。 col与val向量一一对应了非0元素的列号与值，在每个block区间内依次记录。

总结 : 

总结 Register && Cache Blocking Optimizations带来的性能提升: 1.节省了大量的空间存储 2.块内元素分布连续，在矩阵-向量乘中可以通过设定分块的列维度的大小，使得进行乘法的向量中元素与分块中元素保持在cache中，提高cache命中率，减少CPU二次访存所带来的开销。 3.稀疏存储法使得复杂度由O(nm)->O(E) 其中n，m分别为原矩阵的维度，E为稀疏阵中非0元素的个数。

Parallel Optimizations && SIMDization : 

Parallel Optimizations && SIMDization Parallel Optimizations采用POSIX Threads 进行实现。 POSIX Threads 是Threads的POSIX标准，定义了创建和操纵线程的一套API。 实现 POSIX 线程标准的库常被称作 Pthreads，一般用于 Unix-like POSIX 系统，如 Linux、 Solaris，但是 Microsoft Windows上的实现也存在，例如， pthreads-w32。 SIMDization即单指令多数据流优化，可以利用Intel SSE指令或Pipe技术实现。 SSE(Streaming SIMD Extensions)是英特尔在AMD的3D Now!发布一年之后，在其计算机芯片Pentium III中引入的指令集，是继MMX的扩充指令集。SSE 指令集提供了 70 条新指令。AMD后来在Athlon XP中加入了对这个新指令集的支持。

POSIX Threads && NUMA-Awareness : 

POSIX Threads && NUMA-Awareness 随着计算机硬件的不断发展，越来越多的计算机采用了多核的平台构架，传统的串行计算不能有效地利用多核平台的优势，其对机器本身性能的利用也是相当不充分的。 回顾矩阵-向量乘，我们首先用BSCR结构对其进行了分块处理，其主要目的是为了cache的高命中。而目前大多数的多核架构中，cache数也并非唯一，相反大多数架构中每1个或2个CPU都带有一个cache(如NUMA)。

POSIX Threads && NUMA-Awareness : 

POSIX Threads && NUMA-Awareness 因此，我们可以用pthreads创建与CPU总数一样多的线程，并使得每个线程与CPU绑定，从而高效地并行处理数据。 必要步骤：设计一个合理的分配方案。

SIMDization : 

SIMDization SSE指令是一种单指令多数据指令，它可以使得4对浮点同时进行运算，但只需要1次运算的周期。Linux下效果不是很好。 另外，一种称为Pipe技术的优化，可以在CPU的支持下同时读取2个不同的内存地址。但Linux下效果不是很好。

总结 : 

总结 Parallel Optimizations && SIMDization带来的性能提升 1.将计算分配给多CPU并行进行，提升了计算效率。 2.SSE指令将4对浮点数进行并行运算，提升了运算效率率。 3. 关键在于如何分配计算量，使得负载平衡。

MPI Optimizations : 

MPI Optimizations MPI ，全称Message Passing Interface，是消息传递并行程序设计的标准之一，当前通用的是MPI1.1规范。 MPI的实现包括MPICH、LAM、IBM MPL等多个版本，最常用和稳定的是MPICH 。 利用MPI的上层API可以实现点对点的通信，以及集群通信，从而实现整个算法的分布式计算。

MPI Optimizations : 

MPI Optimizations 将计算分配由单结点线程扩展到多结点线程，加大计算的并行程度。 对每个不同结点，根据其CPU数计算出具体到各个线程计算量的分配。 必要步骤：仍然是计算的分配方案，以使得负载平衡，从而抵消通讯开销。

总结 : 

总结 Intel MPI带来的性能提升 1.计算具有分布特性，能使更多的CPU参与进计算，从而提高计算效率。 2.在一定条件下，参与计算的计算机越多，计算速度越快，直到达到通讯开销的瓶颈。 3.具有更多可调配方案。

Data Decomposition : 

Data Decomposition 在集群硬件部署之后，利用特别选取的n个矩阵所构成的基准矩阵集 ，对集群计算性能进行调优。 设 为 的基准矩阵，对其生成的 随机向量 ，选用所有 的矩阵分块方式，利用以上所述的各种优化以及当前分配方案，进行矩阵与向量乘的运算，从而统计出集群在不同分块方式下的运算开销。 在基准矩阵集测试完成之后，对于不同的分块方式分别计算出集群运算的平均开销，选取其中平均开销最小的分块方式作为集群进行矩阵向量乘的最终分块方法。

基本运算流程 : 

基本运算流程 1. 当有新的结点加入计算集群时，采用预调优算法确定该结点的计算线程数并得到适用于集群计算的最优矩阵分块大小； 2. 读入系数矩阵时，将矩阵数据结构按最优分块大小，转换为方便灵活的分块压缩结构； 3. 在计算任务执行之前，根据各个结点的预调优数据为每个结点的线程分配计算量； 4. 当共轭梯度法演算流程执行矩阵与向量乘时，利用MPI自动将计算任务分配到集群中的计算结点。 5. 当计算完成后将结果主动归约到主结点，以多线程集群的工作方式提高运算效率。

算法总结 : 

算法总结 基于MPI的分布式共轭梯度算法带来的性能提升 1、利用了cache局部性原理，采用高度压缩及灵活方便的结构针对稀疏矩阵进行分块处理，大大降低了计算时间复杂度中的常数，节省了大量的存储空间，提升了算法的演算效率。 2、充分利用了多核平台以及集群计算的性能优势，将计算中的热点并行化处理，利用多线程以及MPI的分布式技术，以较小的通讯开销换取了高性能的计算效率。 3、对集群可以进行整体性能上的自动调优，新的结点可以在加入后迅速发挥计算效力

矩阵-向量乘实验 : 

矩阵-向量乘实验 实验平台：Redhat Linux 7.0 P4 3.4G , 3.4G 双核 首先利用Sparsity自带的调优器设置分块大小，然后使用4个基准矩阵对六种不同的实现分别进行实验，每一次实验重复进行100次测试。 Mul： BSCR MulBySSE：BSCR + SSE MulByPipe BSCR + Pipe MulByThreadesWithSSE：BSCR + Pthreades + SSE MulByThreadesWithOutSSE：BSCR + Pthreades Sparsity：加州大学的BSCR代码(GCC)

实验一 : 

实验一 Matrix : Pres_Poisson.mtx R = 14822 C = 14822 NZ = 365313

实验二 : 

实验二 Matrix : engine.mtx R = 143571 C = 143571 NZ = 2424822

实验三 : 

实验三 Matrix : wang3.mtx R = 26064 C = 26064 NZ = 177168

实验四 : 

实验四 Matrix : comsol.mtx R = 1500 C = 1500 NZ = 97645

实验总结 : 

实验总结 观察： SSE与Pipe的优化在Linux下表现并不是很好。(windows下表现还是不错的) 基于BSCR的矩阵向量乘法的实现已经与Sparsity不相上下，并且绝大多数情况下要快。 结论： 多线程并行运算下效率有几乎一倍的提升。(并行优化效果明显) 在BSCR的向量乘法较Sparsity要快的case中，都有很高的cache命中率。(单结点上的cache命中率决定了其运算效率)

下一步工作 : 

下一步工作 算法在分布式结点上的部署与实验 分布式计算中集群通讯的优化 自动调优脚本的实现

Slide 31: 

Q&A Thank you!