IPSJ SIG Technical Report Vol.2011-HPC-131 No /10/6 1 1 Parareal-in-Time Applicability of Time-domain Parallelism to Iterative Linear Calculus T

Size: px

Start display at page:

Download "IPSJ SIG Technical Report Vol.2011-HPC-131 No /10/6 1 1 Parareal-in-Time Applicability of Time-domain Parallelism to Iterative Linear Calculus T"

みずきいちぞの
4 years ago
Views:

1 1 1 Parareal-in-Time Applicability of Time-domain Parallelism to Iterative Linear Calculus Toshiya Taami 1 and Aira Nishida 1 The time-domain parallelism, nown as Parareal-in-Time algorithm, has been applied to scientific problems described by ordinary differential equations or partial differential equations. In this report, applicability of this algorithm to simple linear transformations such as matrix-vector multiplications, iterative calculus, etc., is studied through convergence and speed-up. At first, as a direct application of this algorithm, convergence to a series of vectors defined by matrix multiplications is analyzed from the viewpoint of perturbation. The speed-up ratio by this algorithm on a distributed parallel machine is measured and appropriate problem sizes for this scheme are analyzed. In addition to these analysis, applicability to general iterative calculations is reported. 1, yushu University 1. Introduction Parareal-in-Time 1) 10 2) 3),4) 5),6) Parareal-in-Time {x 0, x 1,..., x } F G t F G -Newton { } {x(r+1) } r {x } 7) F G 8) { } G F G Parareal-in-Time c 2011 Information Processing Society of Japan

2 f(x) Jacobian f (X) f(x) = 0 Newton X (r+1) = X (r) [ f (X (r) ) 1 f(x (r) ) (4) 1 2. Parareal-in-Time {x } x +1 = F (x ). (1) ( 1) x x 1 Parareal-in-Time F G +1 = G ( ) + F ( ) G ( ), (2) r F ( ) { } (r = 1, 2,...) r {x } 2.1 Newton Parareal-in-Time Parareal-in-Time { } r {x } 7),8) r X (r) ( f(x (r) ) 0, x(r) 1,... x(r) )T (1) 0 x 0 1 F 0 ( 0 ). F 1 ( 1 ) {x } f(x (r) ) = 0 X (r) (3) f (X (r) ) = 1 0 F 0( 0 ) 1 F 1( 1 ) F 1( 1 ) 1 (4) 0 = x 0 (6) [ +1 = F ( ) + F (x (r) ) (7) Jacobian F ( ) G ( ) [ F (x (r) ) G ( ) G ( ) (8) Parareal-in-Time (2) Newton {x } 2.2 Parareal-in-Time Parareal-in-Time 9),10) 9) F G 11),12) F G F G x 1 x = [G 1 + (F 1 G 1 ) x 1 = [G j + (F j G j ) x 0, (9) j=0 (5) 2 c 2011 Information Processing Society of Japan

3 F j G j (j ) G j F j G j G j F j G j (9) F j G j r r r +1 = G + (F G ) (10) Parareal-in-Time (2) Parareal-in-Time r ( ) ( )! = r ( r)!r! r e r, (11) 2π( r)r r 1 r Stirling Parareal-in-Time 2.3 Parareal-in-Time 3 (2) Parareal-in-Time 2 G F G (2) r = = 0 x 0 ( x (3) ) (9) r ( r (11) ) (2) (r + 1)( r) G r( r) F G 2 Parareal-in-Time r Parareal-in-Time r 2 r r 3. Parareal-in-Time Parareal-in-Time x +1 = [G + εf x = [G + εf x 0, (12) {x } G F N N ε ε ( 1) Parareal [G + εf r Parareal ε r 1 +1 [G = + ε G j F G 1 j + + ε r (F r ) j=0 G F ρ(g) ρ(f ) r Parareal x 0 (13) 3 c 2011 Information Processing Society of Japan

4 x [ρ(g) x 0 j=r+1 ( j ) [ j ερ(f ). (14) ρ(g) 1 r ε r ( ) [ r ερ(f ) ( ) e r [ r ερ(f ) (15) r ρ(g) 2π( r)r r ρ(g) r ερ(f ) ρ(g) x 3.1 (12) {x } Parareal G 1 1 F Gaussian Orthogonal Ensemble (GOE) 1 1 F ii 2 = 1 2N, F ij 2 = 1 4N (i j) (16) 3(a) ε = 0.01 r (15) ρ(g) = ρ(f ) = 1 F G r = 15 = x +1 = exp [ t H x i h 11),12) H x x +1 t/ h ε exp( iεh) = I [exp(iεh) 1 I iεh (17) I G = I 3 (a) Normalized Error r=5 r=10 r= Length of Sequence (b) Normalized Error r=10 r=20 r=30 Length of Sequence r=40 r= Parareal-in-Time (a) G + εf (b) exp(iεh) r + 1 (15) iεh (εf = iεh) H Gaussian Unitary Ensemble (GUE) 1 1 H ii 2 = H ij 2 = 1 4N x (1 iεh) x 0 3(b) ( ε = 0.01) = 1000 r = 50 r + 1 (15) Parareal-in-Time (15) r + 1 r + 2 G = I ρ(g) = ρ(f ) = 1 (18) 4 c 2011 Information Processing Society of Japan

5 1/T Limit of Speedup Speedup Ratio Max. Efficiency (1/r) K>>P>>1 K~P 4 K P T g T f T c 0 0 K Total Number of Rans (P) 4. Parareal-in-Time 5 Parareal-in-Time ( ) 1/r K P 1 1/T K P t Parareal-in-Time 13) MPI Send/Recv 64 (Westmere, 12 ) Xeon (InfiniBand QDR) G O(N) F O(N 2 ) 4.1 (12) r Parareal +1 = G + εf, (19) MPI 0 = x 0 2 Parareal r (19) (19) : : +1 εf (20) G, (21) 2 r F G T f T g T c K (12) K(T f + T g) Parareal-in-Time (19) r (20) rkt f (21) (r + 1)KT g ( 4 x (0) +1 = Gx(0) KT g ) P 1/P r [(r/p ) + 1KT g P T c(p 1) P S(r, K, P ) = rkt f P K(T f + T g ) P ( ) =, (22) r + P + 1 P (P 1) KT g + T c (P 1) r + T P + t K T T g /(T f + T g ) t T c /(T f + T g ) t 1/T T f /T g 5 c 2011 Information Processing Society of Japan

6 6 (a) Time (sec) Normal Method Normal Method Parareal Iterations Parareal (N=8192) Parareal (N=1024) (b) Speedup Ratio Linear Speedup r=10 r=20 r=40 Total Number of Ran N=8192 N= Parareal-in-Time : (a) r 512 ; (b) (N = 1024) (N = 8192) r = S(r, K, P )/P T 1 t 1 1/r r Parareal-in-Time r T G F 4.2 Parareal-in-Time MPI 6 ( 3.2 ) 1536 (K = 1536) 6(a) MPI 512 Parareal-in-Time r N = 8192 r = r 1 CPU (N = 1024) r 2.0 6(b) r = 10, 20, 40 MPI N = P N = 1024 r = r = r = N = 8192 r = r = r = t = 0 (22) 1 ( ) N = 8192 Parareal-in-Time N = 1024 (22) t N = Parareal-in-Time Parareal-in-Time 7 O(N 3 ) O(N 3 ) Parareal-in-Time Parareal-in- Time Ax = b (Successive Over-relaxation, SOR) (Conjugate Gradient, CG) SOR D L U [D + ε(l + U) x = b (23) SOR w x +1 = (1 w)x + w(d + εu) 1 [b εlx (24) 6 c 2011 Information Processing Society of Japan

7 Long Time Series (a) 10 0 (b) Eigenvalue Problem Small Matrix Multi-thread Linear Library Short Time Series Parareal-in-Time Acceleration Large Matrix Distributed-parallel Linear Library Parareal-in-Time ε Parareal-in-Time G Model 1: G = I ( ) [ +1 = + w (D + εu) 1 (b εl ) x(r) (25) Model 2: ε = 0 G [ +1 = (1 w) + wd 1 b + w (D + εu) 1 (b εl ) D 1 b (26) Parareal-in-Time D D jj 1 1 L U a ij 2 = 1/4N 100 ε (N = 100 ε = 0.1) b b 2 = 1 SOR Parareal-in-Time 8 (a) (b) D + ε(l + U) b x 0 SOR {x } (a) Model 1 (b) Model 8 Difference r=10 r=20 r=30 r=40 r= Iterations Difference Iterations r=10 r=20 r=30 r= SOR Parareal-in-Time : (a) Model 1 (b) Model 2 SOR x x 1 2 r Parareal-in-Time { } Model 1 Parareal Model 2 {x } Model 1 K = 100 r = 50 Model 2 w = 0.2 SOR w Gauss-Seidel w = 1 1 < w < 2 Parareal {x } w SOR Parareal-in-Time 5. Parareal-in-Time 1,000 7 c 2011 Information Processing Society of Japan

8 14) Parareal-in-Time Parareal-in-Time Parareal-in-Time SOR Parareal-in-Time ( 15) ) 10) 16) 1) J. Lions, Y. Maday, and G. Turinici, A parareal in time discretization of PDE s, C. R. Acad. Sci., Ser. I: Math. 232, (2001). 2) M. J. Gander and S. Vandewalle, On the Superlinear and Linear Convergence of the Parareal Algorithm, LNCSE 55, (Springer, 2007). 3) L. Baffico, S. Bernard, Y. Maday, G. Turinici, and G. Zérah, Parallel-in-time molecular-dynamics simulations, Phys. Rev. E66, (2002). 4) G. Bal and Q. Wu, Symplectic Parareal, LNCSE 60, (Springer, 2008). 5) T. Hara, T. Naito, and J. Umoto, Time-periodic finite element method for nonlinear diffusion equations, IEEE Trans. Magn., MAG-21, (1985). 6) K. Burrage, Parallel and Sequential Methods for Ordinary Differential Equations, (Oxford University Press Inc., NewYor, 1995). 7) M. J. Gander, Analysis of the Parareal Algorithm Applied to Hyperbolic Problems Using Characteristics, Bol. Soc. Esp. Mat. Apl. 42, (2008). 8) M. J. Gander and E. Hairer, Nonlinear Convergence Analysis for the Parareal Algorithm, LNCSE 60, (Springer, 2008). 9) G. A. Staff and E. M. Rønquist, Stability of the Parareal Algorithm, LNCSE 40, (Springer, 2005). 10) M. Duarte, M. Massot and S. Descombes, Parareal Operator Splitting Techniques for Multi-scale Reaction Waves: Numerical Analysis and Strategies, Math. Model. Num. Anal. 45 (5), (2011). 11) Y. Maday, G. Turinichi, Parallel in Time Algorithms for Quantum Control: Parareal Time Discretization Scheme, IJQC 93, (2003). 12) T. Taami and H. Fujisai, Analytic approach for controlling quantum states in complex systems, Phys. Rev. E75, (2007). 13) E. Aubanel, Scheduling of tass in the parareal algorithm, Parallel Computing 37, (2011). 14) A. Nishida, Experience in Developing an Open Source Scalable Software Infrastructure in Japan, Proc. ICCSA 2010, Part II, LNCS 6017, (2010). 15) Y. Inadomi, T. Taami, J. Mai, T. Kobayashi, and M. Aoyagi, RPC/MPI Hybrid Implementation of OpenFMO All Electron Calculations of a Ribosome, in Proc. ParCo2009, Adv. Par. Comp. 19, (2010). 16), HPC-129-3, 1 8 (2011) (C) ( ) 8 c 2011 Information Processing Society of Japan

IPSJ SIG Technical Report Vol.2014-HPC-143 No /3/3 Identity Parareal 1,2,a) 3 Parareal-in-Time (identity) Identity Parareal, Parareal-in-Time,

IPSJ SIG Technical Report Vol.2014-HPC-143 No /3/3 Identity Parareal 1,2,a) 3 Parareal-in-Time (identity) Identity Parareal, Parareal-in-Time, Identity Parareal 1,2,a) 3 Parareal-in-Time (identity) Identity Parareal, Parareal-in-Time, Identity Parareal, 1. 1 2 JST CREST 3 a) taami@cc.yushu-u.ac.jp 2001 Lions Pararealin-Time [1] [2], [3] [4],