数据划分优化
数据划分通常对规模较大的数据进行划分，将分解后的数据块聚集或映射到多个处理器上，实现在多个进程上同时执行以加快程序运行速度。
在保证结果正确的前提下要使数据划分后程序的性能较好就需要使负载尽可能保持均衡。
以矩阵乘算法为例，基础的并行算法是使用0号进程将生成的矩阵完整的广播到各个进程，这样可确保结果的正确性但效率不高，所以可以采用数据划分方法让不同的进程去执行矩阵A某个分块和矩阵B某个分块的乘法计算得到结果C的不同部分，最后将C的不同部分聚合以得到完整的结果C，这里常用的矩阵划分方法有三种，分别为按行、按列以及棋盘式划分方法。
按行分解
由于在计算矩阵C的第i行时只需要用到矩阵A的第i行以及完整的矩阵B，因此每个进程上存储A中多余的行会增加很多不必要的通信，可以使用按行划分解的方式，每个进程负责处理矩阵A的若干行与矩阵B相乘，得到结果C中的若干行，最后合并结果。
采用按行分解的矩阵乘并行算法的实现流程如下：
① 由0进程生成矩阵A和B。
② 0号进程将矩阵B发送到所有进程。
③ 0号进程依据总进程数与矩阵维数的关系划分任务，分别将A的对应若干行发送给不同的进程。
④ 各个进程完成矩阵C部分行的计算。
⑤ 将结果聚合到0号进程。
与MPI_Bcast类似，MPI_Scatter也是一个一对多的通信函数，但是与MPI_Bcast的不同之处在于，MPI_Scatter的0号进程向每个进程发送的数据可以是不同的，0号进程将连续的4个不同的数据按照进程号大小的顺序依次发送给通信域中的所有进程。
此函数的原型如下，其所有参数对根进程来说都是有意义的，而对于子进程来说只需考虑recvbuf、recvcount、recvtype、root和comm，参数root和comm在所有参与计算的进程中都必须是一致的。
int MPI_Scatter(const void *sendbuf, int sendcount, MPI_Datatype sendtype, void *recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm)
sendbuf 发送消息缓冲区的起始地址
sendcount 发送给的数据个数
sendtype 发送的数据类型
recvbuf 接收缓冲区的起始地址
recvcount 待接收的元素个数
recvtype 接收类型
root 数据发送进程的序列号
comm 通信域和MPI_Scatter相反，MPI_Gather是一个典型的用于多对一通信的函数。每个进程都会将一个相同大小的数据块发送给根进程，这些数据到达根进程后，会按照进程号的大小排序存储到接收缓冲区，因此根进程需要开辟出一块足以容纳所有进程发送数据的空间。
此函数的原型如下，参数recvcount是指根进程接收每个进程发来的数据大小，此调用中的所有参数对根进程来说都是有意义的，而对于其它子进程只需考虑sendbuf、sendcount、sendtype、root和comm，其它的参数虽然没有意义但是却不能省略，root和comm在所有进程中都必须是一致的。
int MPI_Gather(const void *sendbuf, int sendcount, MPI_Datatype sendtype, void *recvbuf, int recvcount, MPI_Datatype recvtype,int root, MPI_Comm comm)
sendbuf 发送缓冲区的起始地址
sendcount 每个进程发送的数据个数
sendtype 发送的数据类型
recvbuf 接收缓冲区的起始地址
recvcount 从每个进程接收到的数据个数
recvtype 接收的数据类型
root 接收进程的进程号
comm 通信域 按列分解
按行分解矩阵乘原理是通过降低矩阵A在每个进程中的存储空间降低了通信消耗以及内存的使用，但没有对B矩阵进行处理，使用按列分解方法可以同时降低B矩阵内存开销，即将A矩阵和B矩阵按照行分解的方法进行划分，每个进程负责处理矩阵A的若干列与矩阵B的若干行相乘，以得到结果C中的一部分，最后将各个进程的计算结果进行归约操作得到完整的结果矩阵C。
采用按列分解的矩阵乘并行算法的实现流程如下：
① 由0进程生成矩阵A和B。
② 0号进程依据总进程数与矩阵维数的关系划分任务，分别将A的对应若干列和B对应的若干行发送给不同的进程。
③ 各个进程完成部分矩阵C的计算。
④ 将各个进程的矩阵C汇聚到0号进程，并对各个C矩阵的对应位置进行归约求和操作。
MPI_Reduce将组内每个进程输入缓冲区中的数据在相应的位置按给定的操作进行运算，并将其结果返回到0号进程。当进程数为4时使用MPI_Reduce进行求和归约时，会将所有进程对应位置的数据进行求和，最后将结果汇聚到0号进程。
MPI_Reduce其函数原型如下，对于所有进程来说，都会有count个以sendbuf为起始地址的datatype类型的数据，不同进程中的所有对应位置的数据都互相进行归约操作，待操作完成后将结果存储于0号进程中的recvbuf位置处。
int MPI_Reduce(const void *sendbuf, void *recvbuf, int count,MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm)
sendbuf 要进行归约操作的元素的起始地址
recvbuf 存放归约结果的起始地址
count sendbuf中的数据个数
datatype sendbuf的元素类型
op 归约操作符
root 根进程的进程号
comm 通信域棋盘式分解
前面实现了按行分解以及按列分解的并行矩阵乘法运算，但是这两种分解方法都存在着一个问题，即随着问题规模的增加通信量和存储量也会急剧增加，导致缓存命中率下降影响程序性能，而对矩阵进行棋盘式分解在进行运算时能够极大的提高缓存的命中率。
在棋盘式分解中，所有进程构成一个虚拟网格，并且所要处理的A矩阵和B矩阵也要按照这个网格进行数据划分，每个进程只负责一个块内的矩阵乘法，进程间的关系类似一种基于二维网格的虚拟拓扑结构。
这种分解方法的虚拟网格数和进程数是一一对应的。进一步节省了存储量以及通信总量，具有较高的可扩展性。
在基于棋盘式分解的并行矩阵乘算法中，最突出的代表是Cannon算法。Cannon算法是一种存储有效的算法。为了使两矩阵的下标满足相乘的要求，它不是将矩阵完整的行或列进行多播传送，而是有目的地在各行和各列上实施循环位移，降低处理器的总存储要求，解决了使用按行分解算法时由于矩阵维数增加而带来的内存快速消耗问题。算法实现的流程如下：
① 将矩阵A和B分成√P*√P个分块，每个分块负责n/√P*n/√P的数据。其中P为进程总数，n为矩阵维数。并将每块矩阵按照行优先的顺序映射到P个处理器上。
② 将块A_(i,j) (0<=i,j<√P)向左循环移动i步，将块B_(i,j) (0<=i,j<√P)向上循环移动j步。
③ P_(i,j)执行乘法和加法运算，将块A_(i,j) (0<=i,j<√P)向左循环移动1步；将块B_(i,j) (0<=i,j<√P)向上循环移动1步。
④ 重复第3步，在P_(i,j)中共执行√P次乘法和加法运算和√P次块A_(i,j)和B_(i,j)的循环单步移动。
例如：在开启9进程时，矩阵A和矩阵B使用Cannon算法的矩阵位移示意如右图所示，其中每个分块对应着一个进程，每个进程仅计算结果C的部分数据。
在实现Cannon算法时会使用到以下MPI函数
MPI_Cart_create
MPI_Cart_rank
MPI_Cart_cords
MPI_Cart_shift
MPI_Sendrecv
MPI_Sendrecv_replace
当建立进程与分块矩阵之间的虚拟拓扑时，需要使用函数MPI_Cart_create。在建立虚拟拓扑之后，需要用到函数MPI_Cart_rank以及MPI_Cart_coords以方便进程与进程之间进行数据交换。在获取进程的进程号时需要使用函数MPI_Cart_shift。此外，需要使用MPI_Sendrecv或MPI_Sendrecv_replace函数避免由手动控制进程间数据的循环位移可能会引发的死锁问题。下面对这些函数进行详细介绍。
MPI_Cart_create函数用于描述任意维的笛卡尔结构，其函数原型如下。
int MPI_Cart_create(MPI_Comm comm_old, int ndims, int *dims, int *periods,int reorder, MPI_Comm *comm_cart)
comm_old 输入通信域
ndims 笛卡尔网格的维数
dims 大小为ndims的整数数组，定义每一维的进程数。对于二维，就是指每行和每列各多少进程
periods 大小为ndims的逻辑数组定义在一维上网格的周期性。即数组越界后能否正确循环指定进程号
reorder 标识数是否可以重排序
comm_cart 带有新的笛卡尔拓扑的通信域MPI_Cart_rank函数用于笛卡尔通信域comm中的坐标coors映射为进程号rank，其函数原型如下。
int MPI_Cart_rank(MPI_Comm comm, int *coords, int *rank)
comm 带有笛卡尔结构的通信域
coords 坐标，是一个整数数组
rank 坐标对应的一维线性坐标，是一个整数MPI_Cart_coords函数将comm通信域中的一维线性坐标映射为maxdims维的笛卡尔坐标coords，其函数原型如下。
int MPI_Cart_coords(MPI_Comm comm, int rank, int maxdims, int *coords)
comm 带有笛卡尔结构的通信域
rank 一维线性坐标，是一个整数
maxdims 维数
coords 返回一维线性坐标对应的坐标MPI_Cart_shift用于获取本进程在笛卡尔网格的direction维度上距离为disp的进程编号信息，其函数原型如下。
int MPI_Cart_shift(MPI_Comm comm, int direction, int disp, int *rank_source, int *rank_dest)
comm 带有笛卡尔结构的通信域
direction 需要平移的坐标维数
disp 偏移量
rank_source 本进程在direction维disp正方向距离的进程号
rank_dest 本进程在direction维disp反方向距离的进程号MPI_Sendrecv_replace函数用于在同一标识的起始地址处阻塞地交换数据，其函数原型如下，所交换的数据的个数以及数据类型也都应该相同。
int MPI_Sendrecv_replace(void * buf, int count, MPI_Datatype datatype,int dest, int sendtag, int source, int recvtag, MPI_Comm comm, MPI_Status *status);
buf 发送和接收数据的起始地址
count 发送和接收数据的个数
datatype 数据类型
dest 目的进程号
sendtag 发送数据的标识
source 源进程号
recvtag 接收数据的标识
comm 源和目的的通信域
status 发送和接收的状态MPI_Sendrecv_replace函数用于在同一标识的起始地址处阻塞地交换数据，其函数原型如下，所交换的数据的个数以及数据类型也都应该相同。
