並列計算の数理とアルゴリズムサンプルページこの本の定価判型などは, 以下の URL からご覧いただけます. このサンプルページの内容は, 初版 1 刷発行時のものです.

Size: px

Start display at page:

Download "並列計算の数理とアルゴリズムサンプルページこの本の定価判型などは, 以下の URL からご覧いただけます. このサンプルページの内容は, 初版 1 刷発行時のものです."

よいかずのしろ
5 years ago
Views:

2 並列計算の数理とアルゴリズムサンプルページこの本の定価判型などは, 以下の URL からご覧いただけます. このサンプルページの内容は, 初版 1 刷発行時のものです.

3 Calcul scientifique parallèle by Frédéric Magoulès and François-Xavier Roux Copyright c 2013 Frédéric Magoulès and François-Xavier Roux Japanese translation rights arranged with Frédéric Magoulès through Japan UNI Agency, Inc., Tokyo

4 i OpenMP MPI

5 ii Ecole Normale SupérieuredeCachan Ecole Centrale Paris Institut des Sciences de l Ingénieur de Toulon et du Var Ecole Supérieure des Sciences et Technologies de l Ingénieur de Nancy Conservatoire National des Arts et Métiers Université Henri Poincaré Université Pierre & Marie Curie &

6 iii... 1 I II

7 iv III 93 7 LU LU LU LU ND )

8 v IV CG GMRES MINRES ORTHODIR BiCG QMR BiCGSTAB

9 vi

10 1 200, flops 1 1 1flops 48 MPI OpenMP 4 I

11 LU 8 9 LU

12 I

13 (floating point) 2 2 (flops, floating-point operations per second) 1 10 Gflops (Giga = 10 9 ) 1 1 Tflops (Tera = ) 1 1 Pflops (Peta = )

14 GHz MHz Mflops (Mega = 10 6 ) 20 GHz Pflops 100 MHz GHz 100 Mflops Pflops (ALU: Arithmetic Logic Unit) 3

15 CPU 2

16 ( 5) = ( 0654) =

18 47 3 OpenMP MPI for i =2 to n x(i) =y(i)+a(i) x(i 1)

19 48 3 n = p q+1 x(i) p +1 {x(1),x(q +1),,x(k q+1),,x(p q+1)} x(k q+1)=z(k)+b(k) x ( (k 1) q+1 ) z(k) b(k) (k 1) q+2 k q x(i 1) = z + b x(i 0 ) x(i) =y(i)+a(i) x(i 1) = ( y(i)+a(i) z ) + ( a(i) b ) x(i 0 ) z(k) b(k) z(k) =y((k 1) q+1) b(k) =a((k 1) q+1) for i =(k 1) q+2 to k q z(k) =y(i)+a(i) z(k) b(k) =a(i) b(k) z(k) b(k) p p z(k) b(k) p +1 {x(1),x(q +1),,x(k q+ 1),,x(p q+1)} for k =1 to p x(k q+1)=y(k)+b(k) x((k 1) q+1) x p for i =(k 1) q+2 to k q x(i) =y(i)+a(i) x(i 1) 1 p k p

20 n 1 (+, ) for i =2 to n x(i) =y(i)+a(i) x(i 1) p =(n 1)/q 2q 2 q 1 z(k) =y((k 1) q+1) b(k) =a((k 1) q+1) for i =(k 1) q+2 to k q z(k) =y(i) +a(i) z(k) b(k) =a(i) b(k) 2n n p (+, ) for k =1 to p x(k q+1)=y(k)+b(k) x((k 1) q+1) p q 1 (+, ) n p (+, ) for i =(k 1) q+2 to k q x(i) =y(i)+a(i) x(i 1) p

21 50 3 b(k) i =(k 1) q+2 i =(k 1) q a(i) b(k) 0 y(k) for k =1 to p x(k q+1)=y(k)+b(k) x((k 1) q+1) for k =1 to p x(k q+1)=y(k) x(k) p for i =(k 1) q+2 to k q x(i) =y(i)+a(i) x(i 1) p q =2 p =(n 1)/2 1 1 (n 1)/2 k z(k) =y(2 k 1)

22 b(k) =a(2 k 1) z(k) =y(2 k)+a(2 k) z(k) b(k) =a(2 k) b(k) p +1 = (n +1)/2 for k =1 to (n +1)/2 z(k) =y(2 k)+a(2 k) y(2 k 1) b(k) =a(2 k) a(2 k 1) x for k =1 to (n 1)/2 x(2 k)=y(2 k)+a(2 k) x(2 k 1) n A B C A = B C A ij B i C j for i =1 to n for j =1 to n for k =1 to n A(i, j) =A(i, j)+b(i, k) C(k, j)

23 94 7 LU LU (Crout factorization) (Cholesky factorization) 7.1 LU 7.1 LU A LU L U A = LU A L U LU Ax = b 1 Ly = b for i =1 to n for j =1 to i 1 b(i) =b(i) l(i, j) y(j) y(i) =b(i)/l(i, i) U 0 Ux = y for i = n to 1 for j = i +1 to n y(i) =y(i) u(i, j) x(j)

24 7.1 LU 95 x(i) =y(i)/u(i, i) A 2 2 ( ) A11 A 12 A = A 21 A 22 A 11 A 22 n 1 n 2 A 12 A 21 (n 1,n 2 ) (n 2,n 1 ) 7.2 LU A LU ( ) ( )( ) A11 A 12 L11 0 U11 U 12 = 7.1 A 21 A 22 L 21 I 0 S 22 L 11 U A A 11 A 11 = L 11 U 11 A 7.1 ( ) ( )( ) A11 A 12 L11 0 U11 U 12 = A 21 A 22 L 21 I 0 S 22 ( ) L11 U 11 L 11 U 12 = L 21 U 11 L 21 U 12 + S 22 A 11 = L 11 U 11 A 21 = L 21 U 11

25 96 7 LU A 12 = L 11 U 12 A 22 = L 21 U 12 + S 22 1 A 11 = L 11 U 11 2 L 21 U 12 S 22 = A 21 U11 1 = L 1 11 A 12 S 22 = A 22 L 21 U 12 S 22 (Schur complement) A 11 S 22 = A 22 A 21 A 1 11 A S 22 = A 22 L 21 U 12 = A 22 A 21 U 1 11 L 1 11 A 12 LU 7.3 A 11 S 22 = A 22 A 21 A 1 11 A 12 A LU LU A 11 = L 11 U 11 S 22 = L 22 U 22 ( ) ( )( ) A11 A 12 L11 0 U11 U 12 = A 21 A 22 L 21 L 22 0 U 22 L 21 U 12 ( ) ( )( ) A11 A 12 L11 0 U11 U 12 = A 21 A 22 L 21 I 0 S 22 LU ( ) ( )( ) A11 A 12 L11 0 U11 U 12 = A 21 A 22 L 21 L 22 0 U 22

26 = ( L11 U 11 L 11 U 12 ) L 21 U 11 L 21 U 12 + L 22 U L 11 U 11 L 21 U S 22 = L 22 U 22 A 22 = L 21 U 12 + L 22 U 22 = L 21 U 12 + S 22 LU A 11 L 21 U 12 S 22 S (Gauss factorization) 1(a(1, 1)) A 11 L 11 =(l(1, 1)) U 11 =(u(1, 1)) a(1, 1) = l(1, 1) u(1, 1) l(1, 1) = 1 u(1, 1) = a(1, 1) A 21 L 21 1 A 12 U 12 1 n 1 S 22 2 n l(1, 1) = 1 u(1, 1) = a(1, 1) for i =2 to n l(i, 1) = a(i, 1)/u(1, 1) for j =2 to n u(1,j)=a(1,j) for j =2 to n for i =2 to n s(i, j) =a(i, j) l(i, 1) u(1,j)

27 98 7 LU S 22 A L 21 U 12 S 22 1 S 22 A L 21 U 12 S 22 u(1, 1) a(1, 1) l(1, 1) 1 A L U for k =1 to n 1 for i = k +1 to n a(i, k) =a(i, k)/a(k, k) for j = k +1 to n for i = k +1 to n a(i, j) =a(i, j) a(i, k) a(k, j) A = LU L 1 U n 1 L n 1 U n 1 n 2 n 1 + n 2 = n =dima n A 11 A 21 A 12 A 22 A 11 L 11 U 11 A L 21 U 12 S 22 = A 22 A 21 U11 1 L 1 11 A n 1 1 S 22 = A 22 A 21 U 1 11 L 1 11 A 12 0

28 BiCGSTAB 192 BLAS 59 flops 4 Gflops 4 GMRES(m) 173 GMRES 169, 172, , 192, 226 GPU 15 LaPack 59 LU 94 Mflops 5 MIMD 16, 20 MKL 135 MPI 19, 40 MUMPS 135 OpenMP 33, 40 ORTHODIR 177, 192, 211 Pardiso 135 Pflops 4 private 33 QMR 188, 190 ScaLaPack 59, 114 shared 33 SIMD 15 SMP 13 SPMD 20 Tflops , 19, , , , 19, , , 113, 119, 120, 122, 127, 130, 131, 207, 209, 212, 215, , 212, 214

29 246 90, , , LU , , 197, , 155, 158, 174, 184, 188, , , 154, 157, , 35

30 (Frédéric Magoulès) 1999 & Ph.D. & (François-Xavier Roux) 1986 ONERA 1992 CNAM & Ph.D. & PD 2013 Ph.D. c FAX Printed in Japan ISBN

<4D F736F F D B B BB2D834A836F815B82D082C88C602E646F63>

<4D F736F F D B B BB2D834A836F815B82D082C88C602E646F63> 入門モーター工学サンプルページこの本の定価判型などは, 以下の URL からご覧いただけます. http://www.morikita.co.jp/books/mid/074351 このサンプルページの内容は, 初版 1 刷発行当時のものです. 10 kw 21 20 50 2 20 IGBT IGBT IGBT 21 (1) 1 2 (2) (3) ii 20 2013 2 iii iv...

並列計算の数理とアルゴリズム サンプルページ この本の定価 判型などは, 以下の URL からご覧いただけます. このサンプルページの内容は, 初版 1 刷発行時のものです.

並列計算の数理とアルゴリズムサンプルページこの本の定価判型などは, 以下の URL からご覧いただけます. このサンプルページの内容は, 初版 1 刷発行時のものです.