中国科学技术大学计算机科学与技术系 国家高性能计算中心(合肥) 2004年12月

Presentation on theme: "中国科学技术大学计算机科学与技术系 国家高性能计算中心(合肥) 2004年12月"— Presentation transcript:

1 中国科学技术大学计算机科学与技术系 国家高性能计算中心(合肥) 2004年12月
并 行 计 算 中国科学技术大学计算机科学与技术系 国家高性能计算中心(合肥) 2004年12月

2 第三篇 并行数值算法 第八章 基本通讯操作 第九章 稠密矩阵运算 第十章 线性方程组的求解 第十一章 快速傅里叶变换
第三篇 并行数值算法 第八章 基本通讯操作 第九章 稠密矩阵运算 第十章 线性方程组的求解 第十一章 快速傅里叶变换

3 第十章 线性方程组的求解 10. 1 三角形方程组的求解 10. 2 三对角方程组的求解 10. 3 稠密线性方程组的求解 10
第十章 线性方程组的求解 三角形方程组的求解 三对角方程组的求解 稠密线性方程组的求解 稀疏线性方程组的求解

4 10.1 三角形方程组的求解 10.1.1 基本术语 10.1.2 上三角方程组的求解
10.1 三角形方程组的求解 基本术语 上三角方程组的求解

5 基本术语 线性方程组的定义和符号 a1,1x1 + a1,2x2 + … + a1,nxn = b1
an,1x an,1x … + an,nxn = bn 记为 AX=b 国家高性能计算中心（合肥） 2019/1/2

6 10.1 三角形方程组的求解 10.1.1 基本术语 10.1.2 上三角方程组的求解
10.1 三角形方程组的求解 基本术语 上三角方程组的求解

7 上三角方程组的求解 上三角方程组的回代解法并行化 (1)SISD上的回代算法 Begin (1)for i=n downto 1 do
(1.1)xi=bi/aii (1.2)for j=1 to i-1 do bj=bj-ajixi aji=0 endfor End 可并行化 国家高性能计算中心（合肥） 2019/1/2

8 上三角方程组的求解 上三角方程组的回代解法并行化 (2)SIMD-CREW上的并行回代算法 - 划分: p个处理器行循环带状划分 - 算法
Begin for i=n downto 1 do xi=bi/aii for all Pj, where 1≤j≤p do for k=j to i-1 step p do bk=bk-akixi aki=0 endfor End // p(n)=n, t(n)=n 国家高性能计算中心（合肥） 2019/1/2

9 第十章 线性方程组的求解 10. 1 三角形方程组的求解 10. 2 三对角方程组的求解 10. 3 稠密线性方程组的求解 10
第十章 线性方程组的求解 三角形方程组的求解 三对角方程组的求解 稠密线性方程组的求解 稀疏线性方程组的求解

10 10.2 三对角方程组的求解 直接求解法 奇偶规约法

11 三对角方程组的直接求解法 Gauss消去法(难以并行化) ①消元 ②回代 注：由于三对角的 方程组的特殊性， 一次消元或一次 回代，只涉及邻
近一个方程，故 难以并行化。 国家高性能计算中心（合肥） 2019/1/2

12 10.2 三对角方程组的求解 直接求解法 奇偶规约法

13 三对角方程组的直接求解法 奇偶规约求解法(可并行化) fixi-1+gixi+hixi+1=bi i=1~n f1=hn=0 串行算法描述
三对角方程可以写成如下形式 fixi-1+gixi+hixi+1=bi i=1~n f1=hn=0 串行算法描述 ①利用上下相邻方程消去偶序号方程中的奇下标变量: f2i-1x2i-2+g2i-1x2i-1+h2i-1x2i =b2i-1 f2ix2i g2ix2i + h2ix2i =b2i f2i+1x2i +g2i+1x2i+1+h2i+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 国家高性能计算中心（合肥） 2019/1/2

14 三对角方程组的直接求解法 并行化分析: ①、②消去奇下标可以并行化； ②重复①最终可得: case 1: case 2:
g1x1+h1x =b f2x1+g2x2+h2x =b f3x2 +g3x3+h3x4=b f4x3 +g4x4 =b 可以分别得到 g1x1+h1x2 =b 或 g1x1+h1x =b1 f2x1+g2x2 =b f2x1+g2x2+h2x3 =b2 f3x2+g3x =b3 解得 x1,x2 或 x1, x2, x3 ③回代求解x 并行化分析: ①、②消去奇下标可以并行化； ③回代求解可以并行化 国家高性能计算中心（合肥） 2019/1/2

15 第十章 线性方程组的求解 10. 1 三角形方程组的求解 10. 2 三对角方程组的求解 10. 3 稠密线性方程组的求解 10
第十章 线性方程组的求解 三角形方程组的求解 三对角方程组的求解 稠密线性方程组的求解 稀疏线性方程组的求解

16 10.3 稠密线性方程组的求解 10.3.1 有回代的高斯消去法 10.3.2 无回代的高斯-约旦法 10.3.3 迭代求解的高斯-赛德尔法
10.3 稠密线性方程组的求解 有回代的高斯消去法 无回代的高斯-约旦法 迭代求解的高斯-赛德尔法

17 有回代的高斯消去法 算法基本原理 求解过程分为消元和回代两个阶段，消元是将系数矩阵A化为上三角阵T，然后对TX=c进行回代求解。
消元过程中可以应用选主元方法，增加算法的数值稳定性。 下面是消元过程图： 国家高性能计算中心（合肥） 2019/1/2

18 有回代的高斯消去法 并行化分析 消元和回代均可以并行化； 选主元也可以并行化； 消元过程的并行化图示：处理器按行划分
国家高性能计算中心（合肥） 2019/1/2

19 10.3 稠密线性方程组的求解 10.3.1 有回代的高斯消去法 10.3.2 无回代的高斯-约旦法 10.3.3 迭代求解的高斯-赛德尔法
10.3 稠密线性方程组的求解 有回代的高斯消去法 无回代的高斯-约旦法 迭代求解的高斯-赛德尔法

20 无回代的高斯-约旦法 串行算法原理 ①消元: 通过初等行变换,将(A,b)化为主对角线矩阵, (方便起见, 记b为A的第n+1列)
②求解: xj=a’j,n+1/a’jj 国家高性能计算中心（合肥） 2019/1/2

21 无回代的高斯-约旦法 SIMD-CREW上的并行算法 (1)处理器: n2+n个处理器, 这些处理器排成n×(n+1)的矩阵,
处理器编号为Pik, i=1~n, k=1~n+1 (2)并行化分析 ①消元的并行化: // O(n) for j=1 to n-1, each Pik Par-do //第j次消元 Pij(i<>j): aij <— 0 Pik(i<>j, k=j+1~n+1): aik <— aik-ajk(aij/ajj) end for ②求解: for each Pjj(j=1~n) Par-do: xj <— aj,n+1/ajj //O(1) (3)时间分析: t(n)=O(n), p(n)=O(n2), c(n)=O(n3) 成本最优？ 国家高性能计算中心（合肥） 2019/1/2

22 无回代的高斯-约旦法 成本最优？ 串行算法的最优时间：由于 x=A-1b ①A-1b(假设已有A-1): O(n2) ②求A-1:
∴求A-1需要: 2次n/2×n/2矩阵的逆 i(n/2) 6次n/2×n/2矩阵的乘 m(n/2) 2次n/2×n/2矩阵的加 a(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<x<2.5 => i(n)=O(nx) 综上，串行算法的最优时间为O(nx) 2<x<2.5 国家高性能计算中心（合肥） 2019/1/2

23 10.3 稠密线性方程组的求解 10.3.1 有回代的高斯消去法 10.3.2 无回代的高斯-约旦法 10.3.3 迭代求解的高斯-赛德尔法
10.3 稠密线性方程组的求解 有回代的高斯消去法 无回代的高斯-约旦法 迭代求解的高斯-赛德尔法

24 迭代求解的高斯-赛德尔法 串行算法原理 并行化分析 如果对某个k, 给定的误差允许值c有 则认为迭代是收敛的。
由于每次迭代需要使用本次迭代的前面部分值，因而难以 得到同步的并行算法，下面给出一个异步的并行算法。 国家高性能计算中心（合肥） 2019/1/2

25 迭代求解的高斯-赛德尔法 MIMD异步并行算法 Begin N个处理器(N≤n)生成n个进程, 每个进程计算x的一个分量 算法
(1)oldi  xi0, newi  xi0 (2)生成进程i (3)进程i repeat (i) oldi  newi (ii)newi  (bi-∑k<iaik×oldk-∑k>iaik×oldk)/aii until ∑i=1~n| oldi - newi |<c xi  newi End 国家高性能计算中心（合肥） 2019/1/2

26 第十章 线性方程组的求解 10. 1 三角形方程组的求解 10. 2 三对角方程组的求解 10. 3 稠密线性方程组的求解 10
第十章 线性方程组的求解 三角形方程组的求解 三对角方程组的求解 稠密线性方程组的求解 稀疏线性方程组的求解

27 10. 4 稀疏线性方程组的求解 10. 4. 1 线性方程组的并行化方法 10. 4. 2 稀疏线性方程组的迭代解法 10. 4
10.4 稀疏线性方程组的求解 线性方程组的并行化方法 稀疏线性方程组的迭代解法 高斯-赛德尔迭代法的并行化

28 线性方程方程的并行化方法 线性方程组选择算法的考虑因素 系数矩阵A的结构 计算精度要求 计算环境要求
dense Gaussian elimination, etc Sparse iterative method triangular substitution, odd-even reduction certain PDEs multigrid, etc 计算精度要求 Gaussian elimination: more accurate, more expensive Conjugate gradients: less accurate, less expensive 计算环境要求 architecture, available languages, compiler quality libraries? 国家高性能计算中心（合肥） 2019/1/2

29 线性方程方程的并行化方法 求解方法的并行化 (1)直接解法的并行化(用于稠密线性方程组)
- Gauss消去法(包括选主元的Gauss消去法) - Gauss-Jordan消去法 - LU分解法 (2)迭代法的并行化(用于稠密和稀疏线性方程组) - Jacobi - Gauss-Seidel(可异步并行化) - Jacobi OverRelaxation(JOR) - Gauss-Seidel OverRelaxation(SOR) - Conjugate Gradient 国家高性能计算中心（合肥） 2019/1/2

30 10. 4 稀疏线性方程组的求解 10. 4. 1 线性方程组的并行化方法 10. 4. 2 稀疏线性方程组的迭代解法 10. 4
10.4 稀疏线性方程组的求解 线性方程组的并行化方法 稀疏线性方程组的迭代解法 高斯-赛德尔迭代法的并行化

31 稀疏线性方程方程的迭代解法 迭代解法 国家高性能计算中心（合肥） 2019/1/2

32 10. 4 稀疏线性方程组的求解 10. 4. 1 线性方程组的并行化方法 10. 4. 2 稀疏线性方程组的迭代解法 10. 4
10.4 稀疏线性方程组的求解 线性方程组的并行化方法 稀疏线性方程组的迭代解法 高斯-赛德尔迭代法的并行化

33 高斯-赛德尔迭代法的并行化 由PDE离散产生的稀疏线性方程组 (1)Laplace方程 国家高性能计算中心（合肥） 2019/1/2

34 高斯-赛德尔迭代法的并行化 (2)由五点格式的离散化(假设g(x,y)=0) 国家高性能计算中心（合肥） 2019/1/2

35 高斯-赛德尔迭代法的并行化 A为稀疏的块三对角矩阵 国家高性能计算中心（合肥） 2019/1/2

36 高斯-赛德尔迭代法的并行化 Gauss-Seidel迭代解法的并行化 (1)两种串行算法的计算顺序及其并行化 顺序1 顺序2
顺序 顺序2 注: 顺序1难以并行化；顺序2可以小规模并行化 国家高性能计算中心（合肥） 2019/1/2

37 高斯-赛德尔迭代法的并行化 (2) 红黑着色并行算法 ①并行计算所有的红点 ②并行计算所有的黑点 ③重复①、②直至满足精度要求
国家高性能计算中心（合肥） 2019/1/2