Transcription

1

2 i

3 ii Cannon LU Cholesky Cholesky Cholesky Jacobi Gauss-Seidel Householder

4 iii MPI MPI MPI MPI 63 MPI MPI MPI MPI MPI MPI MPI MPI MPI 107 HPL A.1 BLAS LAPACK ScaLAPACK A.2 FFTW A.3 PETSc MPI reference 123

5 iv 125

6 1. 2. MPI MPI MPI MPI 3. FORTRAN/C

7 2

8

9

10 [1, 2] HPCC 1TFLOPS 1TB 1TB/s I/O 3T 1993 HPCC 1) HPCS 2) ASTA 3) NREN 10 4) BRHR HPCC 1) 10 2) 3) 4) 5) 6) 5

11 6 7) 8) CT 9) 10) 11) 12) ASCI ASCI ASCI Lawrence Livermore Los Alamos Sandia Intel IBM SGI/Cray 1TFLOPS 50TFLOPS [4] John Napier 1642 Pascal 1848 George Boole Herman Hollerith Herman Hollerith IBM

12 John W. Mauchly J. Presper Eckert ENIAC (Electronic Numerical Integrator and Computer) Bell William B. Shockley John Bardeen Walter H. Brattain FORTRAN COBOL 1958 Robert Noyce INTEL IBM INTEL Cray INTEL 3.0Ghz

13 8 60 Mainframe IBM Burroughs IlliacIV 64 CPU SIMD I/O 16CPU 1975 IBM360/85 360/91 360/91 360/85 360/85 360/91 CDC7600 IlliacIV 1976 CRAY-1 15 CRAY-1 RISC CRAY-1 80MHz DEC PDP11 16 PDP11/40 16 C.mmp 80 SMP Cache C.mmp

14 i8086/i8087 Intel ipsc INMOS Transputer Intel Paragon IBM SP Vulcan IBM RISC Scalability 90 DASH IEEE 90 CM-5 CRAY T3D NUMA MPI/PVM IBM SP TFLOPS 1000TFLOPS 100TFLOPS TOP A TOP TOP TOP500 [3] TOP

15 10 1.1: TOP10 Rank site computer R max country/year processor/manufacturer R peak 1 IBM/DOE BlueGene/L DD2 beta-system, 0.7GHz PowerPC United States/ / IBM NASA/Ames SGI Altix 1.5GHz, Voltaire Infiniband United States/ / SGI Earth Sim. Center Earth-Simulator Japan/ / NEC Barcelona SC eserver BladeCenter 2.2GHz PowerPC, Myrinet Spain/ / IBM LLNL Thunder Itanium2 Tiger4 1.4GHz, Quadrics United States/ / California Digital Corp LANL ASCI Q - AlphaServer SC45, 1.25GHz United States/ / HP Virginia Tech System X Dual 2.3GHz Apple XServe, Infiniband United States/ / Self-made IBM - Rochester BlueGene/L DD1 Prototype 0.5GHz PowerPC United States/ / IBM/ LLNL NAVOCEANO eserver pseries GHz Power United States 2944 / IBM NCSA Tungsten PowerEdge1750 Xeon 3.06GHz, Myrinet 9819 United States/ / Dell 15300

16 TOP500 TOP500 50% 1.2: TOP500 count share R max sum R peak sum procrssor sum Cluster Constellations MPP [1, 2]: SISD SIMD MISD MIMD SIMD MIMD PVP Parallel Vector Processor SMP,Symmetric Multiprocessor MPP Massively Parallel Processor Cluster DSM Distributied Shared Memory SMP DSM MPP I/O SMP I/O I/O

17 12 CPU CPU CPU Cache Cache Cache Bus or Crossbar Switch Memory Memory I/O 1.1: / I/O SMP 3 2 SMP 64 SMP SGI Power Challenge XL 32 MIPS R10000 COMPAQ Alphaserver 84005/ Alpha HP HP9000/T HP PA9000 IBM RS6000/R40 8 RS6000

18 CPU0 CPUn CPU0 CPUn Cache Cache Cache Cache HUB HUB Router M0 Router Mp Node0 Nodep High Performance Interconnect Network 1.2: 1.2 DSM SMP DSM CPU CPU (Cache) I/O SMP NUMA 3 SMP DSM

19 14 DSM CC-NUMA DSM SGI Origin GB/ 1 DSM DSM SGI Origin SGI Altix M0 Cache CPU0 M1 Cache CPU1 Mp Cache CPUp Specialized Interconnect Network 1.3: 1.3 MPP I/O MPP MPP

20 MPP ICT Dawning IBM ASCI White 8192 Intel ASCI Red 9632 Cray T3E Linux ( ) TOP500 Supercomputer Sites Cluster@TOP500 : cluster howto : Linux Linux

21 16 Linux : RedHat, Debian, SuSE, Mandrake,... ( ) : Myrinet, QsNet, Dolphin SCI, Infiniband,... : gcc/g++/g77, PGI, Intel,... MPI : MPICH, LAM-MPI,... : NFS, PVFS, Lustre... : PBS, Condor, LSF,... : BLAS MKL, ATLAS, Kazushige Goto s BLAS ( ) FFTW LAPACK ScaLAPACK : PETSc UG Internet IP ( x), (NTP) NIS/LDAP (NFS) IP (IP Masquerading) (NAT, Network Address Translation) Internet (ipchains iptables) LVS (Linux Virtual Server) UPS San Diego (SDSC) 1985 cyberinfrastructure

22 SDSC SDSC (NCSA) NCSA NCSA cyberinfrastructure NCSA National Science Foundation TeraGrid Pittsburgh Carnegie Mellon Pittsburgh Westing house Electric 1986 Pennsylvania

23 IT TOP A A GHz TB 80TB 61TB QsNet(Quadrics ) 300MB 7 B SGI Onyx MIPS R MHZ 384

24 I/O 1.07GB/s 2.4GB/s 3.2GB/s 3.2GB/s32GB657GB IP 128M 104M 48 RGBA C 2000-II GB 628GB 405GB 223GB

25 20

26 : T s q T p (q) S p (q) = T s T p (q) : q S p (q) (2.1) E p (q) = S p(q) q (2.2) : W T (FLOP/s) Perf = W T (2.3) 80 FLOP/s 90 MFLOP/s GFLOP/s 21 GFLOP/s TFLOP/s PFLOP/s Amdahl α q S p (q) = 1 α + (1 α)/q (2.4) Amdahl q S p (q) 1/α Gustafson α q S p (q) = α + q (1 α) (2.5) 21

27 : 2.2: 2 2. S p (q) = O(q) S p (q) = O(q/(1 + log(q)))

28 : Lapalace u(x, y) = f(x, y) (x, y) Ω = (0, a) (0, b) (2.6) u(x, y) Ω = g(x, y) f(x, y) g(x, y) Ω 2.4 (a) (b) 2.4: 2.5 Ω 1 Ω 2

29 24 u u(x, y) = f(x, y) u(x, y) Ω1 = u 0 (x, y) Ω 1 (2.7) u(x, y) = f(x, y) u(x, y) Ω2 = u 0 (x, y) Ω 2 (2.8) 2.7 u u 1 2 u 1 = u 1 1 Ω 1 u 1 1 = u 0 Ω Ω 1 (2.9) u 2 = u 1 2 Ω 2 u 1 2 = u 0 Ω Ω 2 (2.10) u 1 = 1/2(u u 1 2) 2.5: 2.4 Newton 2.11

30 F (x) D R n D x x 2.11 F (x) = 0 (2.11) F (x) Jacobi G(x) = F (x) x (0) Newton x (k+1) = x (k) G 1 (x (k) )F (x (k) ), k = 0,..., (2.12) 2.12 G(x (k) )δ (k) = F (x (k) ) (2.13) δ (k) = x (k+1) x (k) 2.5 a 0,j, a i,j := F (a i 1,j ), i = 1,..., n, j = 1,..., m (2.14) j i () j ( 5 Gauss Seidel ) j (2.14) PDE i (2.14) i q a i,j q {a i,j, i = n k,..., n k+1 1} P k k = 0,..., q 1, 1 = n 0 < n 1 < < n q = n q = 3 : 2.6

31 26 P 0 P 1 P 2 1 a i,1 := F (a i 1,1 ), a n1 1,1 a n2 1,1 i = 1,..., n 1 1, a n1 1,1 P 1 2 a i,2 := F (a i 1,2 ), a i,1 := F (a i 1,1 ), a n2 1,1 i = 1,..., n 1 1, i = n 1,..., n 2 1, a n1 1,2 P 1 a n2 1,1 P 2 3 a i,3 := F (a i 1,3 ), a i,2 := F (a i 1,2 ), a i,1 := F (a i 1,1 ), i = 1,..., n 1 1, i = n 1,..., n 2 1, i = n 2,..., n a n1 1,3 P 1 a n2 1,2 P m a i,m := F (a i 1,m ), a i,m 1 := F (a i 1,m 1 ), a i,m 2 := F (a i 1,m 2 ), i = 1,..., n 1 1, i = n 1,..., n 2 1, i = n 2,..., n a n1 1,m P 1 a n2 1,m 1 P 2 m+1 a i,m := F (a i 1,m ), a i,m 1 := F (a i 1,m 1 ), i = n 1,..., n 2 1, i = n 2,..., n a n2 1,m P 2 m+2 a i,m := F (a i 1,m ), i = n 2,..., n 2.1: 2.6:

32 q = 2 3 n 1 s = a i (2.15) i=0 (2.15) n = 2 m q s 000 (0 : n) s s 000 (0 : n) s 000 (0 : n) = s 000 (0 : n/2) + s 100 (n/2 : n/2) s 000 (0 : n/2) = s 000 (0 : n/4) + s 010 (n/4 : n/4) s 100 (n/2 : n/2) = s 100 (n/2 : n/4) + s 110 (3n/4 : n/4) s 000 (0 : n/4) = s 000 (0 : n/8) + s 001 (n/8 : n/8) s 010 (n/4 : n/4) = s 010 (n/4 : n/8) + s 011 (3n/8 : n/8) s 100 (n/2 : n/4) = s 100 (n/2 : n/8) + s 101 (5n/8 : n/8) s 110 (3n/4 : n/4) = s 110 (3n/4 : n/8) + s 111 (7n/8 : n/8) (2.16) s xxx (k : l) = k+l 1 i=k a i P xxx xxx : 2.7 x (0) (2.17)

33 28 x (k+1) = b + Ax (k) (2.17) A n n b x (k) n x (k+1) 2.8: x (k+1) x (k+1) x (k+1) Amdahl Gustafson 2. m n A x P 0 4 A = [A 0, A 1, A 2, A 3 ] A i P i y = Ax

34

35

36 ,,. MPP,,., [6, 7]. [8],.,, p, P j j, P myid, send(x, j) recv(x, j) P myid x P j P j x, P myid., i mod p i p.,,,.,,.,,., : T c = α+β N, α, β, N.,,. 8 8, 3 2, : A 00 A 01 A 02 A 03 A 04 A 05 A 06 A 07 A 10 A 11 A 12 A 13 A 14 A 15 A 16 A 17 A 20 A 21 A 22 A 23 A 24 A 25 A 26 A 27 A 30 A 31 A 32 A 33 A 34 A 35 A 36 A 37 (3.1) A 40 A 41 A 42 A 43 A 44 A 45 A 46 A 47 A 50 A 51 A 52 A 53 A 54 A 55 A 56 A 57 A 60 A 61 A 62 A 63 A 64 A 65 A 66 A 67 A 70 A 71 A 72 A 73 A 74 A 75 A 76 A 77 31

37 32 A 00 A 02 A 04 A 06 A 01 A 03 A 05 A 07 A 30 A 32 A 34 A 36 A 31 A 33 A 35 A 37 A 60 A 62 A 64 A 66 A 61 A 63 A 65 A 67 A 10 A 12 A 14 A 16 A 11 A 13 A 15 A 17 (3.2) A 40 A 42 A 44 A 46 A 41 A 43 A 45 A 47 A 70 A 72 A 74 A 76 A 71 A 73 A 75 A 77 A 20 A 22 A 24 A 26 A 21 A 23 A 25 A 27 A 50 A 52 A 54 A 56 A 51 A 53 A 55 A 57 m n p q, A ij P kl (k = i mod p, l = j mod q)., 4 : Ax = b min x R n Ax b 2, b R m Ax = λx, Ax = λbx A = UΣV T 3.1,.,. C = A B (3.3) A B m k k n, C m n., m = m p, k = k p n = n p, A B (i-j-k ) do i=1, m do j=1, L do k=1, n c(i, j) = c(i, j) + a(i, k) * b(k, j) enddo enddo enddo

38 (j-k-i ) do j=1, L do k=1, n do i=1, m c(i, j) = c(i, j) + a(i, k) * b(k, j) enddo enddo enddo A B : [ ] T [ ] A = A T 0 A T 1... A T p 1, B = B 0 B 1... B p 1 (3.4) C = (C i,j ) = (A i B j ), C i,j m n. A i, B i C i,j, j = 0,..., p 1 P i,.,. p, C i,j, C p. C i,j, : for i = 0 to p 1 do l i+myid mod p C l = A B, mp1 myid+1 mod p, mm1 myid-1 mod p if i p 1, send(b, mm1), recv(b, mp1) end{f or}, C l = C myid,l, A = A myid, B, k n, p 1. DTA , CA , DTA 1 = 2 k (n n), CA 1 = m k n/p : A B, A (3.4), B [ ] T B = B0 T B1 T... Bp 1 T (3.5) C i A i C i, A i B, [ ] A i = A i0 A i1... A i,p 1

39 34 p 1 C i = A i B = A i,j B j A, B C 3.1.2, P myid for i = 0 to p 1 do l i+myid mod p C = C + A l B, mp1 myid+1 mod p, mm1 myid-1 mod p if i p 1, send(b, mm1), recv(b, mp1) end{f or} 3.1.1, C, A l = A myid,l A B, B (3.4), A : [ ] A = A 0 A 1... A p 1 (3.6) C B, [, ] B i A T, B i = Bi0 T Bi1 T... Bi,p 1 T, C. p 1 C j = A B j = A i B i,j A B, : for i = 0 to p 1 do l i+myid mod p C = C + A B l, mp1 myid+1 mod p, mm1 myid-1 mod p if i p 1, send(a, mm1), recv(a, mp1) end{f or} , DTA 3 = 2 m (k k). m n, DTA 1 DTA 3. j=0 i=0

40 m n, m n, DTA 3 DTA 1., A B, A (3.6), B (3.5). p 1 C = A B = A i B i C p C,,,,. C B i = [ B i0 B i1... B i,p 1 ] C = A B myid for i = 1 to p 1 do i=0 p 1 C j = A i B ij i=0 l i+myid mod p, k myid imodp T = A B l send(t, l), recv(t, k) C = C + T end{f or}, DTA 4 = 2 m (n n). C, 3.1.4, C Cannon A, B C m m,, A = (A ij ) m m, B = (B ij ) m m, C = (C ij ) m m, A ij, B ij C ij n n, p = m m. Cannon, Q = (Q ij ) { In, j i + 1 mod m Q ij = 0 n,

41 36 I n 0 n n. D (l) A diag(a i,i+l mod m ), A = m 1 l=0 D(l) A Ql. = diag(d(l) i ) = C = A B = m 1 l=0 m 1 D (l) A Ql B = l=0 D (l) A B(l) B (l) = Q l B = Q B (l 1).,, P myid = P myrow,mycol, A ij,b ij, C ij P ij, P myid C = 0 for i = 0 to m 1 do k myrow+i mod m; mp1 mycol+1 mod m; mm1 mycol-1 mod m; if mycol=k then else send(a, (myrow, mp1)); copy(a, tmpa); recv(tmpa, (myrow, mm1)); if k mp1, send(tmpa, (myrow, mp1)); end{if} C = C+tmpA B; mp1 myrow+1 mod m; mm1 myrow-1 mod m; if i m 1 then send(b, (mm1, mycol)); recv(b, (mp1, mycol)); end{if} end{f or}, A, C, B. DTA 5 = m 2 n 2 + (m 1) 2 n 2 = 2(2m 1)n 2 = 4m 2 n 2 / p 2m 2 n 2 /p.,.,, p 4, Cannon. 3.2,.,,

42 , Linpack.,,. Ax = b, A LU, L,U, Q, AQ = LU.,, Ly = b Ux = y LU n n A = (a ij ) LU., Gauss,, L. a k A k for j = 0 to n 2 do find l: a lj = max{ a ij, i = j,..., n 1} if l j, swap A j and A l if a jj = 0, A is singular and return a ij = a ij /a jj, i = j + 1,..., n 1 for k = j + 1 to n 1 do a ik = a ik a ij a jk, i = j + 1,..., n 1 end{f or} end{f or} 3.2.1, A, a ik a ij a jk, A. LU, (wrap) A, A i P i mod p. n = p m, A i A i p + myid, : A 00 A 0p A 01 A 0,p+1 A 02 A 0,p+2 A 10 A 1p A 11 A 1,p+1 A 12 A 1,p A n 1,0 A n 1,p A n 1,1 A n 1,p+1 A n 1,2 A n 1,p+2 (3.7) P myid.

43 icol= 0 for j = 0 to n 2 do if myid=j mod p then find l: a l,icol = max{ a i,icol, i = j,..., n 1} if l j, swap a j,icol and a l,icol if a j,icol = 0, A is singular and kill all processes a i,icol = a i,icol /a j,icol, i = j + 1,..., n 1 f i j 1 = a i,icol, i = j + 1,..., n 1 send(l, myid+1) and send(f, myid+1) icol+1 icol else recv(l, myid-1) and recv(f, myid+1) if myid+1 j mod p, send(l, myid+1) and send(f, myid+1) end{if} if l j, swap A j and A l for k=icol to m 1 do a ik = a ik f i a jk, i = j + 1,..., n 1 end{f or} end{f or} LU,,.,, , Lx = b.,, for i = 0 to n 1 do x i = b i /l ii for j = i + 1 to n 1 do b j = b j l ji x i

44 end{f or} end{f or} b L, b,., L, b,.,.,,,,.. LU, flag gb, : k = 0 for i = 0 to n 1 do if myid i mod p then gb i = b k /l ki, flag i = 1, k + 1 k end{if} if flag i 1, wait for j = k to m 1 do b j = b j l ji gb i end{f or} end{f or},, b,,.,.,,,.,.,,

45 40,,.,. 3 : (3.8) : k = 0 if myid=0, then u i = b i, i = 0,..., n 1, v i = 0, i = 0,..., p 2 else u i = 0, i = 0,..., n 1 for i = 0 to n 1 do

46 if i > 0, recv(v, i 1 mod p) x k = (u i + v 0 )/l ik v j = v j+1 + u i+1+j l i+1+j,k x k, j = 0,..., p 3 v p 2 = u i+p 1 l i+p 1,k x k send(v, i + 1 mod p) u j = u j l jk x k, j = i + p,..., n 1 k + 1 k end{f or} [10]. 3.3 A LU, Cholesky, A = R T R, R., Cholesky. Cholesky,,. Cholesky Cholesky Cholesky, Cholesky, [11]. Cholesky for j = 0 to n 1 do a jj = a jj j 1 a jk a jk, a jj = a jj k=0 for i = j + 1 to n 1 a ij = (a ij j 1 a jk a ik )/a jj end{f or} end{f or} k=0, R T A, j, R T,. j j, R.

47 42, F, p 1, (p 1) n, A, P myid : 2 R T for i = 0 to m 1 do k = i p + myid, l = k p + 1 if k > 0 then, recieve G from P myid 1 for j = 0 to p 2 do a i,j+l = (a i,j+l j+l 1 a it g jt )/g j,j+l F j = G j+1 t=0 end{f or} a ik = a ik k 1 a it a it t=0 a ik = a ik, F p 2 = A i Send F to P myid+1 for e = i + 1 to m 1 do for j = 0 to p 2 do a e,j+l = (a e,j+l j+l 1 a et g jt )/g j,j+l a ek = (a ek k 1 end{f or} end{f or} t=0 t=0 a et a it )/a ik R T p,, p,,. [11] Cholesky Cholesky Cholesky : [ ] coshφ sinhφ H = sinhφ coshφ, : H = (1 ρ 2 ) 1 2 [ ] 1 ρ ρ 1

48 ρ = tanh( φ). A R T R,. A = D + U T + U, D,U, W = D 1/2 U, V = D 1/2 + W. A = V T V W T W : [ ] [ I 0 R T 0 0 I ] [ R 0 ] [ = V T W T ] [ I 0 0 I ] [ V W ] I n n, Cholesky, m 2m Θ : [ ] [ ] I 0 I 0 Θ T Θ = 0 I 0 I I m m, (pseudo-orthogonal)., Q [ ] [ ] V R Q = W 0 A = R T R, Q. [12] R S n n, R T R S T S, R, : s kk r 1 kk < 1, 1 k n R S n n, R T R S T S, ρ k s kk r 1 kk, q (k) ij = 1 k n, ˆQ = Q (n) Q(n 1) Q (1), Q (k) : 1, i = j k i = j n + k (1 ρ 2 1 k ) 2, i = j = k i = j = n + k (1 ρ 2 1 k ) 2 ρ k, (i, j) = (k, n + k) (i, j) = (n + k, k) 0, [ ] [ ] R, = S ˆQ R, ˆQ, R, S S.

49 44 Q (k), R S k, [ ] H k = (1 ρ 2 k) ρk ρ k 1 [ ] [ ] Rk H k Q R (k) k k + n. Q (k) S. S k Q n n, p 1,n = 1 p i,i 1 = 1, 2 i n. 2, Cholesky : V 0 = V, W 0 = W, A = V T V W T W for i = 0 to n 1 do [ ] [ ] [ ] V i+1 I 0 V i = ˆQ (i) W i+1 0 Q W i end { for } ˆQ (i) ˆQ, ˆQ (i) W i 0. A β, i β A Cholesky,, [12]. H k,, Cholesky 3 ˆQ (i) Q (k), Q (k) V i W i k, 2 l, M 2 l, H. M = HM m 21 = 0. m 21 = 0, H, ρ = m 21 m l., M = KB, K = diag(k 1, K 2 ) 2 2, K 1 > 0 K 2 > 0. G = K 1 HK, K 2 2. B = GB, M = K B. K,. K,. L = K 2, L = K 2, L.

50 α = L 2 L 1, β = b 21 b 11. L = (1 αβ 2 ) 1 L, [ ] 1 αβ G = β 1 H ρ = m 21 m 1 11 = K 2b 21 K 1 b 11. [ ] [ HK = (1 ρ 2 ) 1 K 2 1 K2 2 b 21 K 1 b 11 = (1 αβ 2 ) αβ K K 2b 21 b 11 K 2 β 1. ] R S n n, E F, R T ER S T F S, α k = F k E k, β k = s kk r kk, [ ] [ ] R = S ˆQ R S ˆQ = Q (n) Q(n 1) Q (1), Q (k), E F : 1, i = j q (k) α k β k, i = k, j = n + k ij = β k, i = n + k, j = k 0, E k Ẽ k =, 1 α k βk 2 Fk =, 1 k n 1 α k βk 2 R T Ẽ R S T F S = R T ER S T F S, R, S.,. A = V T EV W T F W, Cholesky : V 0 = V, W 0 = W, E 0 = E, F 0 = F for i = 0 to n 1 do [ ] [ V i+1 I 0 = W i+1 0 P E i+1 k = E i k 1 α i k βi k ] ˆQ (i) [ V i 2, F i+1 k = W i ] F i k F k 1 αk i βi 2, 1 k n k

51 46 F1 i+1 = end { for } i+1 F n, F i+1 i+1 k+1 = F k, 1 k n 1 ˆQ (i) ˆQ ,, [13] [14].,. Ax = d, a 0 b 0 c 1 a 1 b 1 A = T (c, a, b) = c n 2 a n 2 b n 2 c n 1 a n 1,, [16, 14]. : A 0 B 0 B0 T A 1 B 1 A = Bp 3 T A p 2 B p 2 B T p 2 A p 1 B i,a i. A i LDL T, D,L. A i = L i D i L T i, L = diag(l i ), L 1 AL T = D 0 B0 B 0 T D 1 B B p 3 T D p 2 Bp 2 B T p 2 D p 1

52 B i = L 1 i B i L T i+1 = B il T i+1, 0. D i, B i 0, D i B i, D i B i B i T.,,., LDL T, R T R,, LDL T., : (1) L i, D i, A i = L i D i L T i ; (2), B i ; (3), ; (4).,.,,,.,., Jacobi Ax = b (3.9) A m m D L U A A = D L U 3.9 Dx = b + (L + U)x (3.10) 3.10 x D x

53 48 Jacobi x (0) Jacobi x (k+1) = D 1 (L + U)x (k) + D 1 b (3.11) G = D 1 (L + U) = I D 1 A g = D 1 b x + = Gx + g (3.12) Gauss-Seidel Gauss-Seidel 3.9 n a ij x j = b i, i = 1,..., n (3.13) j=1 x (0) Gauss-Seidel (Gauss-Seidel ) k = 0 x (k+1) 1 = (b 1 n j=2 a 1jx (k) j )/a 11 x (k+1) 2 = (b 2 a 21 x (k+1) 1 n j=3 a 2jx (k) j )/a x (k+1) n 1 x (k+1) n = (b n 1 n 2 j=1 a n 1,jx (k+1) j = (b n n 1 )/a nn j=1 a njx (k+1) j a n 1,n x (k) n )/a n 1,n 1 x (k+1) x (k) 2 < ɛ x (k+1) x (0) 2 k = k s i = n j=i+1 a ijx (0) j i = 1,..., n 1 s n = ( Gauss-Seidel ) k = 0 for i = 1, n do x (k+1) i = (b i s i )/a ii, s i = 0 for j = 1, n, j i do s j = s j + a ji x (k+1) i end{for}

54 end{for} x (k+1) x (k) 2 < ɛ x (k+1) x (0) 2 k = k s j 3.6,,. 60, [17] x = Bx + c, ρ( B ) < 1,., [18] x = F x, F P -,. P - (P-contraction) [19] x = F x, [18]. A A, x x, A 0 A 0. F x i f i (x) f i (x 1,..., x n ), x (j), j = 0, 1,..., N F R n R n, F x (0) x (j) R n, j = 1, 2,..., J = {J j j = 1, 2,...} S = {(s (j) 1,..., s (j) n ) j = 1, 2,...} x (j) i = x (j 1) i, i / J j f i (x (s(j) 1 ) 1,..., x (s(j) n n ) ), i J j, J {1, 2,..., n}, S N n., i = 1,..., n, J S : (1) s (j) i j 1, j = 1, 2,...; (2) s (j) i j ; (3) i J j (j = 1, 2,...). [18],.

55 F x F y A x y, A ρ(a) < 1. x = F x , Ax = b., A, A = B C, : x = B 1 Cx + B 1 b (3.14) B , ρ( B 1 C ) < 1,. A M, M H, [19]. [19] A, B C, A = B C, B 1 0 B 1 C 0, A = B C A A = B C, ρ(b 1 C) < 1 A 1 A B C n n, C B, ρ(c) ρ(b) A, a ij 0 (i j), a ii > 0, A M. [20] A = B C A A M, (3.14)., Jacobi Gauss-Seidel., A A = D L U, D,L U A,A = B C, B = D αl, C = (1 α)l + U, 0 α 1, (3.14).,,,.

56 A n n A R n Ax = λx (3.15) 3.15 (λ, x) A λ A x A A a 1 b 1 b 1 a 2 b 2 b 2 a 3 b x = λx (3.16) b n 2 a n 1 b n 1 P n (λ) = det(a λi) P n (λ) 3.16 A i A i b j 0 j = 1,..., n 1 A i α 1 < α 2 <... < α i A i+1 β 1 < β 2 <... < β i < β i+1 A i A i+1 β 1 < α 1 < β 2 < α 2 <... < β i < α i < β i+1 b n 1 A P 0 (λ) = 1 P 1 (λ) = a 1 λ P n (λ) = (a n λ)p n 1 (λ) b 2 n 1P n 2 (λ) n = 2,... a n (3.17) Q n (λ) = P n (λ)/p n 1 (λ) Q 1 (λ) = a 1 λ Q n (λ) = (a n λ) b 2 n 1/Q n 1 (λ) n = 2,... (3.18)

57 52 A α 3.18 Q i (α) 0 Q i (a) Q i (b) [a, b) A [α 0, α n ) α = (α 0 + α n )/2 Q i (α) 0 k α k = α [α 0, α k ) [α k, α n ) [a, b) A 1 λ ( ) c = (a + b)/2, if b a < ɛ, then stop compute Q i (c) for all i if λ < c, then b = c, otherwise a = c λ (A λi)x k+1 = x k (3.19) x 0 x 0 inf ɛ Householder Householder H = I 2uu T (3.20) u 2 = 1 H H 3.20 e i I i x Householder Hx = αe 1 Householder u H = I 2uu T / u 2 2 Householder Hx = x 2(u T x/ u 2 2)u = αe 1 α = x 2 u x e 1 u = x + βe 1 β 2 x 2 2 x βx 1 + β x 2( x βx 1 ) 2 x βx 1 + β βe 2 1 = αe 1 (3.21) 3.21 x β 2 x 2 2 = 0 β = sign(x 1 ) x 2 α = β Householder QR

58 ( ) α u T A = (3.22) u B Householder H Hu = βe 1 G = G ( ) T ( ) ( ) ( ) 1 0 α u T 1 0 α βe T G T AG = = 1 0 H u B 0 H βe 1 H T BH ( H ) (3.23) H T BH 3.23 Householder H T BH H T BH Householder H = I 2vv T /(v T v) H T BH = (I 2vv T /(v T v))b(i 2vv T /(v T v)) = B 2vv T B/(v T v) 2Bvv T /(v T v) + 4(v T Bv)vv T /(v T v) 2 (3.24) τ = 2/(v T v) x = Bv w = vt x 2 v τx H T BH = B vw T wv T (3.25) x = Bv B q u v A = B uv T vu T 2. A Ax = b Jacobi

59 54

60

61

62 4.1 (Master-slave) (SPMD) (MPMD) SPMD 57

63 58 SPMD SPMD

64 MPI 5.1 MPI MPI Message Passing Interface,., SPCs (Scalable Parallel Computers) NOWs (Networks of Workstations) COWs (Clusters of Workstations).,. MPI PVM,,,,,. 4, MPI, MPI,, MPI PVM. SPCs, SPMD MPI. MPI, MPI MPI_. C,,, MPI_,,, Fortran, MPI,., MPI (Process Group), MPI MPI_COMM_WORLD,,., MPI (communicator). MPI,, Fortran, MPI, MPI [5]. 5.2 MPI π π = dx (5.1) 1 + x2 59

65 60 MPI 5.1 n h = 1/n x i = ih i = 0, 1,..., n x dx = n 1 [ h 2 2 ( x 2 i i= x 2 i+1 ɛ N = 4/3ɛ n N π program computing_pi include mpif.h x dx n 1 2 i=0 integer iam, np, comm, ierr integer n, i, num, is, ie real*8 pi, h, eps, xi, s [ h 2 ( x 2 i ) h3 12 ( 4 ) ] (5.2) 1 + ξi )] < ɛ (5.3) 1 + x 2 i+1 call mpi_init(ierr) call mpi_comm_dup(mpi_comm_world, comm, ierr) call mpi_comm_rank(comm, iam, ierr) call mpi_comm_size(comm, np, ierr) print *, Process, iam, of, np, is running! if(iam.eq. 0) then write(*, *) Number of digits(1-16)= read(*, *) num endif call mpi_bcast(num, 1, mpi_integer, 0, comm, ierr) eps = 1 do 10 i=1, num eps = eps * continue n = sqrt(4.0/(3.0*eps)) h = 1.0/n num = n/np if(iam.eq. 0) then s = 2.0 xi = 0 is = 0

66 5.2 MPI 61 ie = num elseif(iam.eq. np-1) then s = 1.0 is = iam*num ie = n - 1 xi = is * h else s = 0.0 is = iam*num ie = is + num xi = is * h endif do 20 i=is+1, ie xi = xi + h s = s + 4.0/(1.0+xi*xi) 20 continue call mpi_reduce(s, pi, 1, mpi_double_precision, mpi_sum, & 0, comm, ierr) if(iam.eq. 0) then pi = h*pi write(*, *) The pi =, pi endif call mpi_finalize(ierr) end

67 62 MPI

68 MPI MPI, MPI_Init( ) MPI_Finalize( ). : MPI INIT C int MPI_Init( int *argc, char ***argv ) F MPI_INIT( IERROR ) INTEGER IERROR ANSI C main argc argv, MPI_Init. Fortran, MPI_INIT. MPI, MPI ( MPI_INITIALIZED), MPI,. MPI FINALIZE C int MPI_Finalize( void ) F MPI_FINALIZE( IERROR ) INTEGER IERROR MPI., MPI, MPI_INIT., MPI_INIT, MPI_INITIALIZED, MPI_INIT. MPI INITIALIZED C int MPI_Initialized( int flag ) F MPI_INITIALIZED( FLAG, IERROR ) LOGICAL FLAG INTEGER IERROR OUT FLAG, MPI_INIT, TRUE, FALSE. MPI MPI_ERROR_STRING,. 63

69 64 MPI MPI ERROR STRING C int MPI_Error_string( int errorcode, char *string, int *len ) F MPI_ERROR_STRING( ERRORCODE, STRING, LEN, IERROR ) INTEGER ERRORCODE, LEN, IERROR CHARACTER*(*) STRING IN ERRORCODE, MPI. OUT STRING, ERRORCODE. OUT LEN, STRING., STRING MPI_MAX_ERROR_STRING.

70 MPI,,,. 7.1 MPI MPI COMM GROUP C int MPI_Comm_group( MPI_Comm comm, MPI_Group *group ) F MPI_COMM_GROUP( COMM, GROUP, IERROR ) INTEGER COMM, GROUP, IERROR IN COMM,. OUT GROUP, COMM. MPI_COMM_GROUP,. MPI GROUP FREE C int MPI_group_free( MPI_Group *group ) F MPI_GROUP_FREE( GROUP, IERROR ) INTEGER GROUP, IERROR INOUT GROUP, MPI_GROUP_NULL. MPI_GROUP_FREE,. MPI GROUP SIZE C int MPI_Group_size( MPI_Group group, int *size ) F MPI_GROUP_SIZE( GROUP, SIZE, IERROR ) INTEGER GROUP, SIZE, IERROR IN GROUP,. OUT SIZE,. 65

71 66 MPI MPI_GROUP_EMPTY, SIZE 0. MPI GROUP RANK C int MPI_Group_rank( MPI_Group group, int *rank ) F MPI_GROUP_RANK( GROUP, RANK, IERROR ) INTEGER GROUP, RANK, IERROR IN GROUP,. OUT RANK,., RANK MPI_UNDEFINED. C F MPI GROUP TRANSLATE RANKS int MPI_Group_translate_ranks(MPI_Group group1,int n,int *ranks1, MPI_Group group2, int *ranks2) MPI_GROUP_TRANSLATE_RANKS(GROUP1,N,RANKS1,GROUP2,RANKS2,IERROR) INTEGER GROUP1, N, RANKS1(*), GROUP2, RANKS2(*), IERROR IN GROUP1, 1. IN N, RANKS1 RANKS2. IN RANKS1, 1. IN GROUP2, 2. OUT RANKS2, RANKS RANKS1, 2, RANKS2 RANKS1 MPI_UNDEFINED. MPI GROUP INCL C int MPI_Group_incl( MPI_Group group, int n, int *ranks, MPI_Group *newgroup) F MPI_GROUP_INCL( GROUP, N, RANKS, NEWGROUP, IERROR ) INTEGER GROUP, N, RANKS(*), NEWGROUP, IERROR

72 7.1 MPI 67 IN GROUP,. IN N, RANKS. IN RANKS,. OUT NEWGROUP, RANKS. MPI GROUP EXCL C int MPI_Group_excl( MPI_Group group, int n, int *ranks, MPI_Group *newgroup) F MPI_GROUP_EXCL( GROUP, N, RANKS, NEWGROUP, IERROR ) INTEGER GROUP, N, RANKS(*), NEWGROUP, IERROR IN GROUP,. IN N, RANKS. IN RANKS,. OUT NEWGROUP, RANKS. MPI GROUP UNION C int MPI_Group_union( MPI_Group group1, MPI_Group group2, MPI_Group *newgroup) F MPI_GROUP_UNION( GROUP1, GROUP2, NEWGROUP, IERROR ) INTEGER GROUP1, GROUP2, NEWGROUP, IERROR IN GROUP1, 1. IN GROUP2, 2. OUT NEWGROUP, 1 2. MPI GROUP INTERSECTION C int MPI_Group_intersection( MPI_Group group1, MPI_Group group2, MPI_Group *newgroup) F MPI_GROUP_INTERSECTION( GROUP1, GROUP2, NEWGROUP, IERROR ) INTEGER GROUP1, GROUP2, NEWGROUP, IERROR

73 68 MPI IN GROUP1, 1. IN GROUP2, 2. OUT NEWGROUP, 1 2. MPI GROUP DIFFERENCE C int MPI_Group_difference( MPI_Group group1, MPI_Group group2, MPI_Group *newgroup) F MPI_GROUP_DIFFERENCE( GROUP1, GROUP2, NEWGROUP, IERROR ) INTEGER GROUP1, GROUP2, NEWGROUP, IERROR IN GROUP1, 1. IN GROUP2, 2. OUT NEWGROUP, 1 2.,. 7.2 MPI. MPI COMM SIZE C int MPI_Comm_size( MPI_Comm comm, int *size ) F MPI_COMM_SIZE( COMM, SIZE, IERROR ) INTEGER COMM, SIZE, IERROR IN COMM,. OUT SIZE,. MPI COMM RANK C int MPI_Comm_rank( MPI_Comm comm, int *rank ) F MPI_COMM_RANK( COMM, RANK, IERROR ) INTEGER COMM, RANK, IERROR

74 7.2 MPI 69 IN COMM,. OUT RANK,. MPI COMM DUP C int MPI_Comm_dup( MPI_Comm comm, MPI_Comm *newcomm ) F MPI_COMM_DUP( COMM, NEWCOMM, IERROR ) INTEGER COMM, NEWCOMM, IERROR IN COMM,. OUT NEWCOMM, COMM. MPI COMM CREATE C int MPI_Comm_create(MPI_Comm comm,mpi_group group,mpi_comm *newcomm) F MPI_COMM_CREATE( COMM, GROUP, NEWCOMM, IERROR ) INTEGER COMM, GROUP, NEWCOMM, IERROR IN COMM,. IN GROUP, COMM. OUT NEWCOMM, GROUP. MPI COMM SPLIT C int MPI_Comm_split(MPI_Comm comm, int color, int key, MPI_Comm *newcomm) F MPI_COMM_SPLIT( COMM, COLOR, KEY, NEWCOMM, IERROR ) INTEGER COMM, COLOR, KEY, NEWCOMM, IERROR IN COMM,. IN COLOR,. IN KEY,. OUT NEWCOMM,.

75 70 MPI COMM, COLOR,, COLOR. MPI COMM FREE C int MPI_Comm_free( MPI_Comm *comm ) F MPI_COMM_FREE( COMM, IERROR ) INTEGER COMM, IERROR INOUT COMM,.

76 MPI,,. MPI,. 8.1 MPI SEND C int MPI_Send(void* buf,int count,mpi_datatype datatype,int dest, int tag, MPI_Comm comm ) F MPI_SEND(BUF, COUNT, DATATYPE, DEST, TAG, COMM, IERROR ) <type> BUF(*) INTEGER COUNT, DATATYPE, DEST, TAG, COMM, IERROR IN BUF,. IN COUNT,. IN DATATYPE,. IN DEST,. IN TAG,. IN COMM,. COUNT BUF. MPI RECV C int MPI_Recv(void* buf,int count,mpi_datatype datatype,int source, int tag, MPI_Comm comm, MPI_Status *status ) F MPI_RECV(BUF, COUNT, DATATYPE, SOURCE, TAG, COMM, STATUS, IERROR ) <type> BUF(*) INTEGER COUNT,DATATYPE,SOURCE,TAG,COMM, STATUS(MPI_STATUS_SIZE),IERROR 71

77 72 MPI OUT BUF,. IN COUNT,. IN DATATYPE,. IN SOURCE,. IN TAG,. IN COMM,. OUT STATUS,., SOURCE TAG, MPI_ANY_SOURCE MPI_ANY_TAG,. STATUS C, Fortran, MPI_SOURCE, MPI_TAG MPI_ERROR. STATUS,, MPI_GET_COUNT. MPI Fortran C : Fortran MPI MPI datatype Fortran datatype MPI_INTEGER MPI_REAL MPI_DOUBLE_PRECISION MPI_COMPLEX MPI_LOGICAL MPI_CHARACTER MPI_BYTE INTEGER REAL DOUBLE PRECISION COMPLEX LOGICAL CHARACTER(1) MPI_PACKED C MPI

78 MPI datatype MPI_CHAR MPI_SHORT MPI_INT MPI_LONG MPI_UNSIGNED_CHAR MPI_UNSIGNED_SHORT MPI_UNSIGNED_INT MPI_UNSIGNED_LONG MPI_FLOAT MPI_DOUBLE MPI_LONG_DOUBLE MPI_BYTE Fortran datatype signed char signed short int signed int signed long int unsigned char unsigned short int unsigned int unsigned long int float double long double MPI_PACKED MPI_BYTE MPI_PACKED Fortran C, MPI_BYTE, MPI_PACKED., MPI, MPI, MPI. MPI MPI_INIT, MPI_COMM_RANK, MPI_COMM_SIZE, MPI MPI_FINALIZE, MPI_SEND MPI_RECV p, myid (myid= 0,..., p 1) m, m (myid + 1) mod p. program ring c c The header file mpif.h must be included when you use MPI fuctions. c include mpif.h integer myid, p, mycomm, ierr, m, status(mpi_status_size), & next, front, mod, n c c Create MPI parallel environment and get the necessary data. c call mpi_init( ierr ) call mpi_comm_dup( mpi_comm_world, mycomm, ierr) call mpi_comm_rank( mycomm, myid, ierr ) call mpi_comm_size( mycomm, p, ierr ) c c Beginning the main parallel work on each process. c m = myid front = mod(p+myid-1, p) next = mod(myid+1, p)

79 74 MPI c c Communication with each other. c if(myid.eq. 0) then call mpi_recv(n, 1, mpi_integer, front, 1, mycomm, status, ierr) call mpi_send(m, 1, mpi_integer, next, 1, mycomm, ierr) m = n else call mpi_send(m, 1, mpi_integer, next, 1, mycomm, ierr) call mpi_recv(m, 1, mpi_integer, front, 1, mycomm, status, ierr) endif c c Ending of parallel work. c print *, The value of m is, m, on Process, myid call mpi_comm_free(mycomm, ierr) c c Remove MPI parallel environment. c call mpi_finalize(ierr) end MPI GET COUNT C int MPI_Get_count(MPI_Status status,mpi_datatype datatype,int *count) F MPI_GET_COUNT( STATUS, DATATYPE, COUNT, IERROR ) INTEGER STATUS(MPI_STATUS_SIZE), DATATYPE, COUNT, IERROR IN STATUS,. IN DATATYPE,. OUT COUNT,..,, C F MPI SENDRECV int MPI_Sendrecv(void *sendbuf,int sendcount,mpi_datatype sendtype, int dest,int sendtag,void *recvbuf, int recvcount, MPI_Datatype recvtype, int source, int recvtag, MPI_Comm comm, MPI_Status *status ) MPI_SENDRECV(SENDBUF, SENDCOUNT, SENDTYPE, DEST, SENDTAG, RECVBUF, RECVCOUNT,RECVTYPE,SOURCE,RECVTAG,COMM,STATUS,IERROR) <type> SENDBUF(*), RECVBUF(*) INTEGER SENDCOUNT, SENDTYPE, DEST, SENDTAG, RECVCOUNT, RECVTYPE SOURCE, RECVTAG, COMM, STATUS(MPI_STATUS_SIZE), IERROR

80 IN SENDBUF,. IN SENDCOUNT,. IN SENDTYPE,. IN DEST,. IN SENDTAG,. OUT RECVBUF,. IN RECVCOUNT,. IN RECVTYPE,. IN SOURCE,. IN RECVTAG,. IN COMM,. OUT STATUS,., : call mpi_sendrecv(m, 1, mpi_integer, next, 1, n, 1, mpi_integer, & front, 1, mycomm, status, ierr) m = n MPI_SENDRECV,,. C F MPI SENDRECV REPLACE int MPI_Sendrecv_replace(void *sendbuf,int count,mpi_datatype datatype, int dest,int sendtag,int source, int recvtag, MPI_Comm comm, MPI_Status *status ) MPI_SENDRECV_REPLACE(BUF, COUNT, DATATYPE, DEST, SENDTAG, SOURCE, RECVTAG, COMM, STATUS, IERROR ) <type> BUF(*) INTEGER COUNT, DATATYPE, DEST, SENDTAG, SOURCE, RECVTAG, COMM, STATUS(MPI_STATUS_SIZE), IERROR

81 76 MPI OUT BUF,. IN COUNT,. IN DATATYPE,. IN DEST,. IN SENDTAG,. IN SOURCE,. IN RECVTAG,. IN COMM,. OUT STATUS,., BUF : call mpi_sendrecv_replace(m, 1, mpi_integer, next, 1, & front, 1, mycomm, status, ierr), MPI_SENDRECV_REPLACE., MPI MPI_PROC_NULL, , p 1 0 m, :... if(myid.eq. 0) front = MPI_PROC_NULL if(myid.eq. p-1) next = MPI_PROC_NULL call mpi_sendrecv_replace(m, 1, mpi_integer, next, 1, & front, 1, mycomm, status, ierr) MPI PROBE C int MPI_Probe(int source,int tag,mpi_comm comm,mpi_status *status ) F MPI_PROBE( SOURCE, TAG, COMM, STATUS, IERROR ) INTEGER SOURCE, TAG, COMM, STATUS(MPI_STATUS_SIZE), IERROR IN SOURCE,. IN TAG,. IN COMM,. OUT STATUS,.

82 MPI_IPROBE, MPI_PROBE. MPI IPROBE C int MPI_Iprobe(int source, int tag, MPI_Comm comm, int* flag, MPI_Status *status ) F MPI_IPROBE( SOURCE, TAG, COMM, FLAG, STATUS, IERROR ) LOGICAL FLAG INTEGER SOURCE, TAG, COMM, STATUS(MPI_STATUS_SIZE), IERROR IN SOURCE,. IN TAG,. IN COMM,. OUT FLAG,, FLAG TRUE. OUT STATUS,. SOURCE, TAG COMM,. SOURCE TAG MPI_RECV, (wildcard) MPI_ANY_SOURCE MPI_ANY_TAG. 8.2,,.,,. C F MPI ISEND int MPI_Isend(void* buf,int count,mpi_datatype datatype,int dest, int tag, MPI_Comm comm, MPI_Request *request ) MPI_ISEND(BUF, COUNT, DATATYPE, DEST, TAG, COMM, REQUEST, IERROR) <type> BUF(*) INTEGER COUNT, DATATYPE, DEST, TAG, COMM, REQUEST, IERROR

83 78 MPI IN BUF,. IN COUNT,. IN DATATYPE,. IN DEST,. IN TAG,. IN COMM,. OUT REQUEST,. C F MPI IRECV int MPI_Irecv(void* buf,int count,mpi_datatype datatype,int source, int tag, MPI_Comm comm, MPI_Request *request ) MPI_IRECV(BUF, COUNT, DATATYPE, SOURCE, TAG, COMM, REQUEST, IERROR) <type> BUF(*) INTEGER COUNT, DATATYPE, SOURCE, TAG, COMM, REQUEST, IERROR OUT BUF,. IN COUNT,. IN DATATYPE,. IN SOURCE,. IN TAG,. IN COMM,. OUT REQUEST,. MPI_ISEND MPI_IRECV,, : MPI WAIT C int MPI_Wait( MPI_Request *request, MPI_Status *status ) F MPI_WAIT( REQUEST, STATUS, IERROR ) INTEGER REQUEST, STATUS(MPI_STATUS_SIZE), IERROR INOUT REQUEST,. OUT STATUS,.

84 REQUEST, MPI_WAIT. MPI TEST C int MPI_Test(MPI_Request *request, int* flag, MPI_Status *status) F MPI_TEST( REQUEST, FLAG, STATUS, IERROR ) LOGICAL FLAG INTEGER REQUEST, STATUS(MPI_STATUS_SIZE), IERROR INOUT REQUEST,. OUT FLAG, REQUEST TRUE. OUT STATUS,. STATUS, STATUS MPI_TEST_CANCELLED. MPI REQUEST FREE C int MPI_Request_free( MPI_Request *request ) F MPI_REQUEST_FREE( REQUEST, IERROR ) INTEGER REQUEST, IERROR INOUT REQUEST,, MPI_REQUEST_NULL. REQUEST,,. MPI WAITANY C int MPI_Waitany( int count, MPI_Request *array_of_requests, int *index, MPI_Status *status ) F MPI_WAITANY(COUNT, ARRAY_OF_REQUESTS, INDEX, STATUS, IERROR) INTEGER COUNT, ARRAY_OF_REQUESTS(*), INDEX, STATUS(MPI_STATUS_SIZE), IERROR IN COUNT,. INOUT ARRAY_OF_REQUESTS,. OUT INDEX,. OUT STATUS,.

85 80 MPI,,, MPI_WAITANY. C F MPI TESTANY int MPI_Testany( int count, MPI_Request *array_of_requests, int *index, int *flag, MPI_Status *status ) MPI_TESTANY(COUNT,ARRAY_OF_REQUESTS,INDEX,FLAG,STATUS,IERROR) LOGICAL FLAG INTEGER COUNT, ARRAY_OF_REQUESTS(*), INDEX, STATUS(MPI_STATUS_SIZE), IERROR IN COUNT,. INOUT ARRAY_OF_REQUESTS,. OUT INDEX,. OUT FLAG,, FLAG=TRUE. OUT STATUS,.. C F MPI WAITALL int MPI_Waitall( int count, MPI_Request *array_of_requests, MPI_Status *array_of_statuses ) MPI_WAITALL(COUNT,ARRAY_OF_REQUESTS,ARRAY_OF_STATUSES,IERROR) INTEGER COUNT, ARRAY_OF_REQUESTS(*), ARRAY_OF_STATUSES(MPI_STATUS_SIZE, *), IERROR IN COUNT,. INOUT ARRAY_OF_REQUESTS,. INOUT ARRAY_OF_STATUSES,.,.

86 C F MPI TESTALL int MPI_Testall( int count, MPI_Request *array_of_requests, int *flag, MPI_Status *array_of_statuses ) MPI_TESTALL(COUNT,ARRAY_OF_REQUESTS,FLAG,ARRAY_OF_STATUSES,IERROR) LOGICAL FLAG INTEGER COUNT, ARRAY_OF_REQUESTS(*), ARRAY_OF_STATUSES(MPI_STATUS_SIZE, *), IERROR IN COUNT,. INOUT ARRAY_OF_REQUESTS,. OUT FLAG,, FLAG=FALSE. INOUT ARRAY_OF_STATUSES,.. MPI CANCEL C int MPI_Cancel( MPI_Request *request ) F MPI_CANCEL( REQUEST, IERROR ) INTEGER REQUEST, IERROR INOUT REQUEST,., MPI_WAIT MPI_TEST,. REQUEST, : MPI TEST CANCELLED C int MPI_Test_cancelled( MPI_Status *status, int *flag ) F MPI_TEST_CANCELLED( STATUS, FLAG, IERROR ) LOGICAL FLAG INTEGER REQUEST, IERROR IN STATUS,. OUT FLAG,, FLAG=TRUE.

87 82 MPI 8.3 MPI SEND INIT C int MPI_Send_init(void* buf,int count,mpi_datatype datatype,int dest, int tag, MPI_Comm comm, MPI_Request *request ) F MPI_SEND_INIT(BUF, COUNT, DATATYPE, DEST, TAG, COMM, REQUEST, IERROR ) <type> BUF(*) INTEGER COUNT, DATATYPE, DEST, TAG, COMM, REQUEST, IERROR IN BUF,. IN COUNT,. IN DATATYPE,. IN DEST,. IN TAG,. IN COMM,. OUT REQUEST,. C F MPI RECV INIT int MPI_Recv_init(void* buf,int count,mpi_datatype datatype,int source, int tag, MPI_Comm comm, MPI_Request *request ) MPI_RECV_INIT(BUF, COUNT, DATATYPE, SOURCE, TAG, COMM, REQUEST, IERROR) <type> BUF(*) INTEGER COUNT, DATATYPE, SOURCE, TAG, COMM, REQUEST, IERROR OUT BUF,. IN COUNT,. IN DATATYPE,. IN SOURCE,. IN TAG,. IN COMM,. OUT REQUEST,.

88 MPI_SEND_INIT MPI_RECV_INIT,,,., MPI_START MPI_STARTALL. MPI START C int MPI_Start( MPI_Request *request ) F MPI_START( REQUEST, IERROR ) INTEGER REQUEST, IERROR INOUT REQUEST,. MPI_START, MPI_SEND_INIT MPI_RECV_INIT. MPI STARTALL C int MPI_Startall( int count, MPI_Request *array_of_request ) F MPI_STARTALL( COUNT, ARRAY_OF_REQUEST, IERROR ) INTEGER COUNT, ARRAY_OF_REQUEST, IERROR IN COUNT,. INOUT ARRAY_OF_REQUEST, , m,, : c c program mring include mpif.h integer iter parameter(iter = 3) integer myid, p, mycomm, ierr, m, status(mpi_status_size, 2), & next, front, mod, n, i, requests(2) call mpi_init( ierr ) call mpi_comm_dup( mpi_comm_world, mycomm, ierr) call mpi_comm_rank( mycomm, myid, ierr ) call mpi_comm_size( mycomm, p, ierr ) print *, Process, myid, of, p, is running

89 84 MPI c m = myid front = mod(p+myid-1, p) next = mod(myid+1, p) call mpi_send_init(m, 1, mpi_integer, next, 1, mycomm, & requests(1), ierr) call mpi_recv_init(n, 1, mpi_integer, front, 1, mycomm, & requests(2), ierr) do 10 i=1, iter call mpi_startall(2, requests, ierr) call mpi_waitall(2, requests, status, ierr) m = n 10 continue print *, The value of m is, m, on Process, myid c call mpi_comm_free(mycomm, ierr) call mpi_finalize(ierr) stop end 8.4 MPI, MPI, (buffered-mode) (synchronous-mode), MPI (ready-mode).,.,,. MPI_BSEND,,,,,. MPI_SSEND,,,. MPI_RSEND,,. MPI_IBSEND, MPI_BSEND. MPI_ISSEND, MPI_SSEND. MPI_IRSEND, MPI_RSEND. MPI_BSEND_INIT, MPI_SEND_INIT. MPI_SSEND_INIT, MPI_SEND_INIT. MPI_RSEND_INIT, MPI_SEND_INIT.

90 8.4 MPI 85, : MPI BUFFER ATTACH C int MPI_Buffer_attach( void *buffer, int size ) F MPI_BUFFER_ATTACH( BUFFER, SIZE, IERROR ) <TYPE> BUFFER(*) INTEGER SIZE, IERROR IN BUFFER,. IN SIZE,.. MPI BUFFER DETACH C int MPI_Buffer_detach( void *buffer, int *size ) F MPI_BUFFER_DETACH( BUFFER, SIZE, IERROR ) <TYPE> BUFFER(*) INTEGER SIZE, IERROR OUT BUFFER,. OUT SIZE,.

91 86 MPI

92 MPI 9.1 MPI C,, MPI,., : ; (displacement)., (type map). : T ypemap = {(type 0, disp 0 ),..., (type n 1, disp n 1 )}, disp i type i, i = 0,..., n 1.. MPI TYPE CONTIGUOUS C int MPI_Type_contiguous(int count, MPI_Datatype oldtype, MPI_Datatype *newtype ) F MPI_TYPE_CONTIGUOUS( COUNT, OLDTYPE, NEWTYPE, IERROR ) INTEGER COUNT, OLDTYPE, NEWTYPE, IERROR IN COUNT, OLDTYPE. IN OLDTYPE,. OUT NEWTYPE,., COUNT,. COUNT=5, OLDTYPE=INTEGER, NEWTYPE 5. MPI TYPE VECTOR C int MPI_Type_vector( int count, int blocklength, int stride, MPI_Datatype oldtype,mpi_datatype *newtype ) F MPI_TYPE_VECTOR(COUNT,BLOCKLENGTH,STRIDE,OLDTYPE,NEWTYPE,IERROR) INTEGER COUNT, BLOCKLENGTH, STRIDE, OLDTYPE, NEWTYPE, IERROR 87

93 88 MPI IN COUNT, OLDTYPE. IN BLOCKLENGTH,. IN STRIDE, OLDTYPE. IN OLDTYPE,. OUT NEWTYPE,. COUNT=3, BLOCKLENGTH=2, STRIDE=3, OLDTYPE=INTEGER, NEWTYPE , 2, 2. MPI TYPE HVECTOR C int MPI_Type_hvector(int count, int blocklength, int stride, MPI_Datatype oldtype, MPI_Datatype *newtype) F MPI_TYPE_HVECTOR(COUNT,BLOCKLENGTH,STRIDE,OLDTYPE,NEWTYPE,IERROR) INTEGER COUNT, BLOCKLENGTH, STRIDE, OLDTYPE, NEWTYPE, IERROR IN COUNT, OLDTYPE. IN BLOCKLENGTH,. IN STRIDE,. IN OLDTYPE,. OUT NEWTYPE,. MPI_TYPE_VECTOR,,. C F MPI TYPE INDEXED int MPI_Type_indexed( int count, int *array_of_blocklengths, int *array_of_displacements, MPI_Datatype oldtype, MPI_Datatype *newtype ) MPI_TYPE_INDEXED(COUNT,ARRAY_OF_BLOCKLENGTHS,ARRAY_OF_DISPLACEMENTS, OLDTYPE, NEWTYPE, IERROR ) INTEGER COUNT, ARRAY_OF_BLOCKLENGTHS(*), ARRAY_OF_DISPLACEMENTS(*), OLDTYPE, NEWTYPE, IERROR

94 IN COUNT, OLDTYPE. IN ARRAY_OF_BLOCKLENGTHS,. IN ARRAY_OF_DISPLACEMENTS,. IN OLDTYPE,. OUT NEWTYPE,. ARRAY_OF_BLOCKLENGTHS ARRAY_OF_DISPLACEMENTS OLDTYPE, ARRAY_OF_DISPLACEMENTS. MPI_TYPE_VECTOR,. MPI_TYPE_VECTOR(COUNT,BLOCKLENGTH,STRIDE,OLDTYPE,NEWTYPE,IERROR) MPI_TYPE_INDEXED(COUNT,LENGTHS,DISPLACEMENTS,OLDTYPE,NEWTYPE,IERROR) LENGTHS(i)=BLOCKLENGTH, DISPLACEMENTS(i)=i*STRIDE, i=0,..., COUNT-1. MPI_TYPE_INDEXED OLDTYPE,. C F MPI TYPE HINDEXED int MPI_Type_hindexed(int count, int *array_of_blocklengths, int *array_of_displacements, MPI_Datatype oldtype, MPI_Datatype *newtype ) MPI_TYPE_HINDEXED(COUNT,ARRAY_OF_BLOCKLENGTHS,ARRAY_OF_DISPLACEMENTS, OLDTYPE, NEWTYPE, IERROR ) INTEGER COUNT, ARRAY_OF_BLOCKLENGTHS(*), ARRAY_OF_DISPLACEMENTS(*), OLDTYPE, NEWTYPE, IERROR IN COUNT, OLDTYPE. IN ARRAY_OF_BLOCKLENGTHS,. IN ARRAY_OF_DISPLACEMENTS,. IN OLDTYPE,. OUT NEWTYPE,.,.

95 90 MPI C F MPI TYPE STRUCT int MPI_Type_struct(int count, int *array_of_blocklengths, int *array_of_displacements, MPI_Datatype *array_of_types,mpi_datatype *newtype) MPI_TYPE_STRUCT(COUNT, ARRAY_OF_BLOCKLENGTHS, ARRAY_OF_DISPLACEMENTS, ARRAY_OF_TYPES, NEWTYPE, IERROR) INTEGER COUNT, ARRAY_OF_BLOCKLENGTHS(*), ARRAY_OF_DISPLACEMENTS(*), ARRAY_OF_TYPES(*), NEWTYPE, IERROR IN COUNT,. IN ARRAY_OF_BLOCKLENGTHS,. IN ARRAY_OF_DISPLACEMENTS,. IN ARRAY_OF_TYPES,. OUT NEWTYPE,. MPI, MPI_TYPE_STRUCT,.,,,,. MPI TYPE COMMIT C int MPI_Type_commit( MPI_Datatype *datatype ) F MPI_TYPE_COMMIT( DATATYPE, IERROR ) INTEGER DATATYPE, IERROR INOUT DATATYPE,. MPI, MPI_TYPE_COMMIT. MPI TYPE FREE C int MPI_Type_free( MPI_Datatype *datatype ) F MPI_TYPE_FREE( DATATYPE, IERROR ) INTEGER DATATYPE, IERROR

96 INOUT DATATYPE,. MPI TYPE EXTENT C int MPI_Type_extent(MPI_Datatype datatype, MPI_Aint *extent) F MPI_TYPE_EXTENT( DATATYPE, EXTENT, IERROR ) INTEGER DATATYPE, EXTENT, IERROR IN DATATYPE,. OUT EXTENT,. MPI ADDRESS C int MPI_Address( void* location, MPI_Aint *address ) F MPI_ADDRESS( LOCATION, ADDRESS, IERROR ) <type> LOCATION(*) INTEGER ADDRESS, IERROR IN LOCATION,. OUT ADDRESS,. MPI_TYPE_EXTENT MPI_ADDRESS, C,, MPI. #include <stdio.h> #include "mpi.h" typedef struct { double value; char str; } data; void main(argc, argv) int argc; char **argv; { int p, myid, lens[3]={1, 1, 1}, i; MPI_Comm mycomm; data tst[3]; MPI_Datatype new, type[3] = {MPI_DOUBLE, MPI_CHAR, MPI_UB}; MPI_Aint disp[3], size; MPI_Status status; MPI_Init( &argc, &argv );

97 92 MPI } MPI_Comm_dup( MPI_COMM_WORLD, &mycomm); MPI_Comm_rank( mycomm, &myid); MPI_Comm_size( mycomm, &p); if (myid == 0) for(i=0; i<3; i++) { tst[i].value = 1.0; tst[i].str= a ; } printf("\nthe Process %1d of %1d is running.\n", myid, p); MPI_Address(&tst[0], &disp[0]); MPI_Address(&tst[0].str, &disp[1]); for (i=1; i>=0; i--) disp[i] -= disp[0]; MPI_Type_struct(3, lens, disp, type, &new); MPI_Type_commit(&new); MPI_Type_extent(new, &size); if(myid == 0) printf("\nthe Extent of Data Type is %d.\n", size); if(myid == 0) MPI_Ssend(tst, 3, new, 1, 1, mycomm); else if (myid == 1) MPI_Recv(tst, 3, new, 0, 1, mycomm, &status); MPI_Type_free(&new); if(myid == 1) printf("\\nthe values are \%f and \%c\n", tst[1].value, tst[1].str); MPI_Comm_free(&mycomm); MPI_Finalize();. C, MPI, MPI (pseudo datatype) MPI_UB, MPI MPI_LB. MPI +new+ MPI_TYPE_EXTENT 4 8, 4, 12, 16. MPI_TYPE_SIZE, 9. MPI TYPE SIZE C int MPI_Type_size( MPI_Datatype datatype, int *size ) Fortran MPI_TYPE_SIZE( DATATYPE, SIZE, IERROR ) INTEGER DATATYPE, SIZE, IERROR IN DATATYPE,. OUT SIZE,.

98 9.2 MPI 93 MPI GET ELEMENTS C int MPI_Get_elements(MPI_Status *status,mpi_datatype datatype,int *count) F MPI_GET_ELEMENTS( STATUS, DATATYPE, COUNT, IERROR ) INTEGER STATUS(MPI_STATUS_SIZE), DATATYPE, COUNT, IERROR IN STATUS,. IN DATATYPE,. OUT COUNT, MPI. MPI_GET_COUNT, MPI_GET_COUNT, MPI_GET_ELEMENTS MPI. MPI, C MPI_INT (Fortran MPI_INTEGER), MPI_GET_COUNT MPI_GET_ELEMENTS..... call mpi_type_contiguous(2, mpi_integer, type, ierr) call mpi_type_commit(type, ierr) if(myid.eq. 0.and. p.gt. 1) then call mpi_send(ia, 3, mpi_integer, 1, 1, mycomm, ierr) elseif(myid.eq. 1) then call mpi_recv(ia, 2, type, 0, 1, mycomm, status, ierr) call mpi_get_count(status, type, count1, ierr) call mpi_get_elements(status, type, count2, ierr) endif...,,, MPI_GET_COUNT., MPI,, MPI,, MPI MPI_BOTTOM, MPI,. 9.2 MPI PVM (Parallel Virtual Machine), MPI MPI

99 94 MPI.. C F MPI PACK int MPI_Pack(void* inbuf, int incount, MPI_Datatype datatype, void* outbuf,int outsize,int *position,mpi_comm comm) MPI_PACK(INBUF, INCOUNT, DATATYPE, OUTBUF, OUTSIZE, POSITION, COMM, IERROR ) <type> INBUF(*), OUTBUF(*) INTEGER INCOUNT, DATATYPE, OUTSIZE, POSITION, COMM, IERROR IN INBUF,. IN INCOUNT,. IN DATATYPE,. OUT OUTBUF,. IN OUTSIZE,. INOUT POSITION,. IN COMM,. C F MPI UNPACK int MPI_Unpack(void* inbuf,int insize,int *position,void* outbuf, int outcount, MPI_Datatype datatype, MPI_Comm comm) MPI_UNPACK( INBUF, INSIZE, POSITION, OUTBUF, OUTCOUNT, DATATYPE, COMM, IERROR ) <type> INBUF(*), OUTBUF(*) INTEGER INSIZE, POSITION, OUTCOUNT, DATATYPE, COMM, IERROR IN INBUF,. IN INSIZE,. INOUT POSITION,. OUT OUTBUF,. IN OUTCOUNT,. IN DATATYPE,. IN COMM,.

100 9.2 MPI 95, MPI_PACKED., MPI : MPI PACK SIZE C int MPI_Pack_size( int incount, MPI_Datatype datatype, MPI_Comm comm, int *size ) F MPI_PACK_SIZE( INCOUNT, DATATYPE, COMM, SIZE, IERROR ) INTEGER INCOUNT, DATATYPE, COMM, SIZE, IERROR IN INCOUNT,. IN DATATYPE,. IN COMM,. OUT SIZE,. SIZE,. MPI_PACK MPI_UNPACK, ,,. : c c c program pack include mpif.h integer maxbuf, len parameter (maxbuf = 200, len = 10) integer myid, p, mycomm, ierr, status(mpi_status_size, 2), & ia(len), count1, count2, i, pos real*8 a(len) character buf(maxbuf) call mpi_init( ierr ) call mpi_comm_dup( mpi_comm_world, mycomm, ierr) call mpi_comm_rank( mycomm, myid, ierr ) call mpi_comm_size( mycomm, p, ierr ) print *, Process, myid, of, p, is running if(myid.eq. 0) then do 10 i=1, len

101 96 MPI ia(i) = i a(i) = dble(i) 10 continue endif call mpi_pack_size(len, mpi_integer, mycomm, count1, ierr) call mpi_pack_size(len, mpi_double_precision, mycomm, count2, i) print *, The pack size of 10 integer and real8 are:, & count1, count2 pos = 1 if(myid.eq. 0.and. p.gt. 1) then call mpi_pack(ia, len, mpi_integer, buf, maxbuf, pos, & mycomm, ierr) call mpi_pack(a, len, mpi_double_precision, buf, maxbuf, pos, & mycomm, ierr) call mpi_send(buf, pos-1, mpi_packed, 1, 1, mycomm, ierr) elseif(myid.eq. 1) then call mpi_recv(buf, maxbuf, mpi_packed, 0, 1, mycomm, & status, ierr) call mpi_unpack(buf, maxbuf, pos, ia, len, mpi_integer, & mycomm, ierr) call mpi_unpack(buf, maxbuf, pos, a, len, mpi_double_precision, & mycomm, ierr) print *, The received values are:, a(1), a(2), a(3) endif call mpi_comm_free(mycomm, ierr) call mpi_finalize(ierr) stop end

102 MPI A 0 P 0 P 1 A 0 A 0 P 2 P 3 A 0 A : A 0 A 1 A 2 A 3 P 0 P 1 P 2 P 3 A 0 A 1 A 2 A : (collective communication) ( 2).,, (barrier synchronization) (global communication functions) (global reduction operations) MPI BARRIER C int MPI_Barrier( MPI_Comm comm ) F MPI_BARRIER( COMM, IERROR ) INTEGER COMM, IERROR 97

103 98 MPI A 0 A 1 A 2 A 3 P 0 A 0 A 0 A 0 A 1 A 1 A 2 A 2 A 3 A 3 P 1 P 2 A 1 A 2 A 0 A 1 A 2 A 3 P 3 A : A 0 A 1 A 2 A 3 P 0 A 0 B 0 C 0 D 0 B 0 C 0 B 1 C 1 B 2 C 2 B 3 C 3 P 1 P 2 A 1 A 2 B 1 B 2 C 1 C 2 D 1 D 2 D 0 D 1 D 2 D 3 P 3 A 3 B 3 C 3 D :

104 IN COMM,. MPI, COMM,,., MPI BCAST C int MPI_Bcast( void* buffer, int count, MPI_Datatype datatype, int root, MPI_Comm comm ) F MPI_BCAST( BUFFER, COUNT, DATATYPE, ROOT, COMM, IERROR ) <type> BUFFER(*) INTEGER COUNT, DATATYPE, ROOT, COMM, IERROR INOUT BUFFER,. IN COUNT,. IN DATATYPE,. IN ROOT,. IN COMM,. COMM, ROOT, BUFFER COMM., MPI. C F MPI GATHER int MPI_Gather( void* sendbuf, int sendcount, MPI_Datatype sendtype, void* recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm ) MPI_GATHER( SENDBUF, SENDCOUNT, SENDTYPE, RECVBUF, RECVCOUNT, RECVTYPE, ROOT, COMM, IERROR ) <type> SENDBUF(*), RECVBUF(*) INTEGER SENDCOUNT, SENDTYPE, RECVCOUNT, RECVTYPE, ROOT, COMM, IERROR

105 100 MPI IN SENDBUF,. IN SENDCOUNT,. IN SENDTYPE,. OUT RECVBUF,. IN RECVCOUNT,. IN RECVTYPE,. IN ROOT,. IN COMM,. MPI (gather), COMM ( ROOT) ROOT, RECVBUF. ROOT, RECVBUF. MPI GATHERV C int MPI_Gatherv(void* sendbuf, int sendcount, MPI_Datatype sendtype, void* recvbuf, int *recvcounts, int *displs, MPI_Datatype recvtype, int root, MPI_Comm comm ) F MPI_GATHERV( SENDBUF, SENDCOUNT, SENDTYPE, RECVBUF, RECVCOUNTS, DISPLS, RECVTYPE, ROOT, COMM, IERROR ) <type> SENDBUF(*), RECVBUF(*) INTEGER SENDCOUNT, SENDTYPE, RECVCOUNTS(*), DISPLS(*), RECVTYPE, ROOT, COMM, IERROR IN SENDBUF,. IN SENDCOUNT,. IN SENDTYPE,. OUT RECVBUF,. IN RECVCOUNTS,. IN DISPLS,. IN RECVTYPE,. IN ROOT,. IN COMM,. MPI_GATHER,,, MPI_GATHER. MPI :

106 , ROOT,,. c c program gather include mpif.h integer maxbuf, len, mp parameter (maxbuf = 200, len = 10, mp = 5) integer myid, p, mycomm, ierr, root, ia(len), iga(maxbuf), i, & displs(mp), counts(mp) call mpi_init( ierr ) call mpi_comm_dup( mpi_comm_world, mycomm, ierr) call mpi_comm_rank( mycomm, myid, ierr ) call mpi_comm_size( mycomm, p, ierr ) print *, Process, myid, of, p, is running c do 10 i=1, len ia(i) = i+myid*len 10 continue c do 20 i=1, p displs(i) = 20*i-20 counts(i) = len 20 continue root = 0 c c c c c call mpi_gather(ia, len, mpi_integer, iga, len, mpi_integer, & root, mycomm, ierr) if(myid.eq. root) then print *, The gather values are:, & iga(1), iga(len+1), iga(2*len+1) endif call mpi_gatherv(ia, len, mpi_integer, iga, counts, displs, & mpi_integer, root, mycomm, ierr) if(myid.eq. root) then print *, The gatherv values are:, & iga(2), iga(2*len+2), iga(4*len+2) endif call mpi_comm_free(mycomm, ierr) call mpi_finalize(ierr)