《PC10 中科大 并行计算 教学课件》由会员分享，可在线阅读，更多相关《PC10 中科大 并行计算 教学课件（37页珍藏版）》请在金锄头文库上搜索。
1、现代密码学理论与实践之五,1,2020/9/14,并 行 计 算,中国科学技术大学计算机科学与技术系 国家高性能计算中心(合肥) 2004年12月,现代密码学理论与实践之五,2,2020/9/14,第三篇 并行数值算法 第八章 基本通讯操作 第九章 稠密矩阵运算 第十章 线性方程组的求解 第十一章 快速傅里叶变换,现代密码学理论与实践之五,3,2020/9/14,第十章 线性方程组的求解 10.1 三角形方程组的求解 10.2 三对角方程组的求解 10.3 稠密线性方程组的求解 10.4 稀疏线性方程组的求解,现代密码学理论与实践之五,4,2020/9/14,10.1 三角形方程组的求解 10
2、.1.1 基本术语 10.1.2 上三角方程组的求解,基本术语,线性方程组的定义和符号 a1,1x1 + a1,2x2 + + a1,nxn = b1 a2,1x1 + a2,1x2 + + a2,nxn = b2 an,1x1 + an,1x2 + + an,nxn = bn 记为 AX=b,2020/9/14,5,现代密码学理论与实践之五,现代密码学理论与实践之五,6,2020/9/14,10.1 三角形方程组的求解 10.1.1 基本术语 10.1.2 上三角方程组的求解,上三角方程组的求解,上三角方程组的回代解法并行化 (1)SISD上的回代算法 Begin (1)for i=n do
3、wnto 1 do (1.1)xi=bi/aii (1.2)for j=1 to i-1 do bj=bj-ajixi aji=0 endfor endfor End,可并行化,2020/9/14,7,现代密码学理论与实践之五,上三角方程组的求解,上三角方程组的回代解法并行化 (2)SIMD-CREW上的并行回代算法 - 划分: p个处理器行循环带状划分 - 算法 Begin for i=n downto 1 do xi=bi/aii for all Pj, where 1jp do for k=j to i-1 step p do bk=bk-akixi aki=0 endfor endfo
4、r endfor End / p(n)=n, t(n)=n,2020/9/14,8,现代密码学理论与实践之五,现代密码学理论与实践之五,9,2020/9/14,第十章 线性方程组的求解 10.1 三角形方程组的求解 10.2 三对角方程组的求解 10.3 稠密线性方程组的求解 10.4 稀疏线性方程组的求解,现代密码学理论与实践之五,10,2020/9/14,10.2 三对角方程组的求解 10.2.1 直接求解法 10.2.2 奇偶规约法,三对角方程组的直接求解法,Gauss消去法(难以并行化) 消元 回代 注：由于三对角的 方程组的特殊性， 一次消元或一次 回代，只涉及邻 近一个方程，故 难
5、以并行化。,2020/9/14,11,现代密码学理论与实践之五,现代密码学理论与实践之五,12,2020/9/14,10.2 三对角方程组的求解 10.2.1 直接求解法 10.2.2 奇偶规约法,三对角方程组的直接求解法,奇偶规约求解法(可并行化) 三对角方程可以写成如下形式 fixi-1+gixi+hixi+1=bi i=1n f1=hn=0 串行算法描述 利用上下相邻方程消去偶序号方程中的奇下标变量: f2i-1x2i-2+g2i-1x2i-1+h2i-1x2i =b2i-1 f2ix2i-1 + g2ix2i + h2ix2i+1 =b2i f2i+1x2i +g2i+1x2i+1+h
6、2i+1x2i+2 = b2i+1 2i-1方程乘上某个数消去2i方程中的f2ix2i-1项, 2i+1方程乘上某个数 消去2i方程中的h2ix2i+1项, 使2i方程变为 ix2i-2+ix2i+ix2i+2=i i=1,2,n/2,2020/9/14,13,现代密码学理论与实践之五,三对角方程组的直接求解法,重复最终可得: case 1: case 2: g1x1+h1x2 =b1 . f2x1+g2x2+h2x3 =b2 . f3x2 +g3x3+h3x4=b3 . f4x3 +g4x4 =b4 . 可以分别得到 g1x1+h1x2 =b1 或 g1x1+h1x2 =b1 f2x1+g2
7、x2 =b2 f2x1+g2x2+h2x3 =b2 f3x2+g3x3 =b3 解得 x1,x2 或 x1, x2, x3 回代求解x 并行化分析: 、消去奇下标可以并行化； 回代求解可以并行化,2020/9/14,14,现代密码学理论与实践之五,现代密码学理论与实践之五,15,2020/9/14,第十章 线性方程组的求解 10.1 三角形方程组的求解 10.2 三对角方程组的求解 10.3 稠密线性方程组的求解 10.4 稀疏线性方程组的求解,现代密码学理论与实践之五,16,2020/9/14,10.3 稠密线性方程组的求解 10.3.1 有回代的高斯消去法 10.3.2 无回代的高斯-约旦
8、法 10.3.3 迭代求解的高斯-赛德尔法,有回代的高斯消去法,算法基本原理 求解过程分为消元和回代两个阶段，消元是将系数矩阵A化为上三角阵T，然后对TX=c进行回代求解。 消元过程中可以应用选主元方法，增加算法的数值稳定性。 下面是消元过程图：,2020/9/14,17,现代密码学理论与实践之五,有回代的高斯消去法,并行化分析 消元和回代均可以并行化； 选主元也可以并行化； 消元过程的并行化图示：处理器按行划分,2020/9/14,18,现代密码学理论与实践之五,现代密码学理论与实践之五,19,2020/9/14,10.3 稠密线性方程组的求解 10.3.1 有回代的高斯消去法 10.3.2
9、 无回代的高斯-约旦法 10.3.3 迭代求解的高斯-赛德尔法,无回代的高斯-约旦法,串行算法原理 消元: 通过初等行变换,将(A,b)化为主对角线矩阵, (方便起见, 记b为A的第n+1列) 求解: xj=aj,n+1/ajj,2020/9/14,20,现代密码学理论与实践之五,无回代的高斯-约旦法,SIMD-CREW上的并行算法 (1)处理器: n2+n个处理器, 这些处理器排成n(n+1)的矩阵, 处理器编号为Pik, i=1n, k=1n+1 (2)并行化分析 消元的并行化: / O(n) for j=1 to n-1, each Pik Par-do /第j次消元 Pij(ij):
10、aij j, k=j+1n+1): aik aik-ajk(aij/ajj) end for 求解: for each Pjj(j=1n) Par-do: xj aj,n+1/ajj /O(1) (3)时间分析: t(n)=O(n), p(n)=O(n2), c(n)=O(n3) 成本最优？,2020/9/14,21,现代密码学理论与实践之五,无回代的高斯-约旦法,成本最优？ 串行算法的最优时间：由于 x=A-1b A-1b(假设已有A-1): O(n2) 求A-1: 求A-1需要: 2次n/2n/2矩阵的逆 i(n/2) 6次n/2n/2矩阵的乘 m(n/2) 2次n/2n/2矩阵的加 a(
11、n/2) i(n)=i(n/2)+6m(n/2)+2a(n/2) a(n/2)=n2/2, m(n/2)=O(n/2)x) 2 i(n)=O(nx) 综上，串行算法的最优时间为O(nx) 2x2.5,2020/9/14,22,现代密码学理论与实践之五,现代密码学理论与实践之五,23,2020/9/14,10.3 稠密线性方程组的求解 10.3.1 有回代的高斯消去法 10.3.2 无回代的高斯-约旦法 10.3.3 迭代求解的高斯-赛德尔法,迭代求解的高斯-赛德尔法,串行算法原理 如果对某个k, 给定的误差允许值c有 则认为迭代是收敛的。 并行化分析 由于每次迭代需要使用本次迭代的前面部分值，
12、因而难以 得到同步的并行算法，下面给出一个异步的并行算法。,2020/9/14,24,现代密码学理论与实践之五,迭代求解的高斯-赛德尔法,MIMD异步并行算法 N个处理器(Nn)生成n个进程, 每个进程计算x的一个分量 算法 Begin (1)oldi xi0, newi xi0 (2)生成进程i (3)进程i repeat (i) oldi newi (ii)newi (bi-kiaikoldk)/aii until i=1n| oldi - newi |c xi newi End,2020/9/14,25,现代密码学理论与实践之五,现代密码学理论与实践之五,26,2020/9/14,第十章
13、 线性方程组的求解 10.1 三角形方程组的求解 10.2 三对角方程组的求解 10.3 稠密线性方程组的求解 10.4 稀疏线性方程组的求解,现代密码学理论与实践之五,27,2020/9/14,10.4 稀疏线性方程组的求解 10.4.1 线性方程组的并行化方法 10.4.2 稀疏线性方程组的迭代解法 10.4.3 高斯-赛德尔迭代法的并行化,线性方程方程的并行化方法,线性方程组选择算法的考虑因素 系数矩阵A的结构 dense Gaussian elimination, etc Sparse iterative method triangular substitution, odd-even
14、 reduction certain PDEs multigrid, etc 计算精度要求 Gaussian elimination: more accurate, more expensive Conjugate gradients: less accurate, less expensive 计算环境要求 architecture, available languages, compiler quality libraries?,2020/9/14,28,现代密码学理论与实践之五,线性方程方程的并行化方法,求解方法的并行化 (1)直接解法的并行化(用于稠密线性方程组) - Gauss消去法
15、(包括选主元的Gauss消去法) - Gauss-Jordan消去法 - LU分解法 (2)迭代法的并行化(用于稠密和稀疏线性方程组) - Jacobi - Gauss-Seidel(可异步并行化) - Jacobi OverRelaxation(JOR) - Gauss-Seidel OverRelaxation(SOR) - Conjugate Gradient,2020/9/14,29,现代密码学理论与实践之五,现代密码学理论与实践之五,30,2020/9/14,10.4 稀疏线性方程组的求解 10.4.1 线性方程组的并行化方法 10.4.2 稀疏线性方程组的迭代解法 10.4.3 高斯-赛德尔迭代法的并行化,稀疏线性方程方程的迭代解法,迭代解法,2020/9/14,31,现代密码
