2018/12/27 6
国防科学技术大学并行与分布处理重点实验室
一般稀疏矩阵与稠密向量的并行乘法(续)

例如，对非零元结构对应于下图的稀疏矩阵，在 两个进程上并行计算时，红线对应的分布更好
2018/12/27
7
国防科学技术大学并行与分布处理重点实验室
将一次迭代内所有操作一起并行计算时的考虑
在内积并行计算时，为平衡负载，最好将 向量分量个数平均分布到各个进程，而向 量分量的分布与矩阵的行分布相对应，这 对应于对图进行分割时，使得各子图中的 结点数相等 在稀疏矩阵与向量并行乘时，为平衡负载， 应使得各子图内所有顶点的出边总数大致 相当 这两个目标有时是相互冲突的

使负载更平衡的一种分布形式
20分布处理重点实验室
一般稀疏矩阵与稠密向量的并行乘法

一般稀疏矩阵的非零元结构对应于一个有 向图，矩阵与向量进行乘法时，yk的计算所 依赖的x分量对应于图中结点k的出边 对应于yk的计算量完全由k的出边数量决定


在计算y＝Ax时，寻找使负载平衡且通信量 最少的矩阵行分布就等价于对图G进行分割， 使各子图内所有顶点的出边总数大致相当， 而所有子图间的边数之和最少

2018/12/27 8
x ( x1 , x2 , xn )，y ( y1 , y2 , yn )，
则有 ( x, y) x1 y1 x2 y2 xn yn . 例子：
P0 x0~99 y0~99 P1 x100~199 y100~199 P2 x200~299 y200~299 P3 x300~399 y300~399
2018/12/27
2
国防科学技术大学并行与分布处理重点实验室
非零元结构对应于网格的矩阵与向量相乘

简单的一维分布
2018/12/27
3
国防科学技术大学并行与分布处理重点实验室
非零元结构对应于网格的矩阵与向量相乘(续)

二维分布
2018/12/27
4
国防科学技术大学并行与分布处理重点实验室
非零元结构对应于网格的矩阵与向量相乘(续)
国防科学技术大学并行与分布处理重点实验室
迭代法中基本操作的并行算法

内积的并行计算
非零元结构对应于网格的矩阵与向量相乘 一般稀疏矩阵与稠密向量的并行乘法 将一次迭代内所有操作一起并行计算时的 考虑
2018/12/27
1
国防科学技术大学并行与分布处理重点实验室
内积的并行计算
假设要计算(x,y)，其中