University:
Boston University
Course:
MET CS 201 | Introduction to Programming
Academic year:

2022
Views:

480

Pages:

14
Author:

karencillaki50

Cartesian Topology As applied to a 2D Laplace Equation Laplace Equation Laplace Equation: u u  2 0 2 x y 2 2 (1) Boundary Conditions: u ( x,0)  sin(x) 0 u ( x,1)  sin(x)e u (0, y )  u (1, y )  0 x x1 0 x1 0 y1 (2) 0  x  1; 0  y  1 (3) Analytical solution: u( x, y)  sin(x)e xy Laplace Equation Discretized Discretize Equation (1) by centered-difference yields: uin, 1 j  uin1,j  uin1,j  ui,jn 1  ui,jn 1 4 i  1,2, ,m; j  1,2, ,m (4) where n and n+1 denote the current and the next time step, respectively, while ui,jn  u n(xi ,y j ) i  0,1,2, ,m  1; j  0,1,2, ,m  1  u n(ix, jy ) For simplicity, we take x  y  1 m1 (5) Computational Domain y, j u(x,1)  sin(x)e x x, i u(1,y)  0 u(0,y)  0 u(x,1)  sin(x) uin, j 1  n n uin1,j  uin1,j  ui,j  1  ui,j 1 4 i  1,2,  ,m; j  1,2,  ,m Five-point Finite-Difference Stencil x Interior (or solution) cells. x o x x Where solution of the Laplace equation are sought. Exterior (or boundary) cells. Green cells denote cells where homogeneous boundary conditions are imposed while non-homogeneous boundary conditions are colored in blue. (i, j) x x o x x Solution Contour Plot Domain Decompositions 1D Domain Decomposition 2D Domain Decomposition Thread 3 Thread 2 Thread 3 Thread 0 Thread 1 Thread 2 Thread 1 Thread 0 Unknowns At Border Cells – 1D Five-point finite-difference stencil applied at thread domain border cells require cells from neighboring threads and/or boundary cells. Message passing required x x x o x x x o x x thread 2 thread 1 x x o x x thread 0 Message Passing to Fill Boundary Cells thread 2 thread 1 current thread thread 0 For Individual Threads . . . Recast 5-pt finite-difference stencil for individual threads vn,1,k  vn,k1,  vn,k1,  vn,,k 1  vn,,k 1 4 ξ  1,2, ,m; η  1,2, ,m' m'  m/p; k  0,1,2, ,p  1 Boundary Conditions vn,,mk '1  vn,,1k 1 ;   0,  , m  1; k  0 vn,,0k  vn,,mk ' 1 ;   0,  , m  1; 0  k  p  1 vn,,mk '1  vn,,1k 1 ;   0,  , m  1; 0  k  p  1 vn,,0k  vn,,mk ' 1 ;   0,  , m  1; k  p  1 thread k of p threads • For simplicity, assume m divisible by p • B.C. time-dependent • B.C. obtained by message-passing • Additional boundary conditions on next page Relationship Between u and v Physical boundary conditions vn,,0k  u ( xi ,0)  sin(xi );   i  0,  , m  1; k  0 vn,,mk '1  u ( xi ,1)  sin(xi )e  ;   i  0,  , m  1; k  p  1 v0n,,k  u (0, y  k *m ' )  0;   1,  , m' ; 0  k  p  1 vmn ,k1,  u (1, y  k *m ' )  0;   1,  , m' ; 0  k  p  1 Relationship between global solution u and thread-local solution v un,  k *m'  vn,,k ξ  1,2,  , m; η  1,2,  , m' m'  m/p; k  0,1,2,  , p  1 MPI Functions Needed For Job • MPI_Sendrecv ( = MPI_Send + MPI_Recv) – to set boundary conditions for individual threads • MPI_Allreduce – to search for global error to determine whether convergence has been reached. • MPI_Cart_Create – to create Cartesian topology • MPI_Cart_Coords – to find equivalent Cartesian coordinates of given rank • MPI_Cart_Rank – to find equivalent rank of Cartesian coordinates • MPI_Cart_shift – to find current thread’s adjoining neighbor threads Successive Over Relaxation 1. Make initial guess for u at all interior points (i,j).  n (0  ωn  2) 2. Define a scalar ui' , j at all interior points (i,j). uin, j 1   nui', j  (1   n )uin, j 3. Use 5-pt stencil to compute 4. Compute 5. Stop if prescribed convergence threshold is reached. uin, j  uin, j 1 7. Go to step 2. 6. Update:  i, j  0  0 ;  1  1 1 / 2 ;  2  1  1 / 4 2 2 1  n  1  1 2 n1 / 4 ; n2   1  ( 2( m1) ) 2 In Step 3, compute u’ with u at time n+1 wherever possible to accelerate convergence. This inhibits parallelism. Red-Black SOR Scheme To enable parallelism, note that solution at black cells (by virtue of 5-pt stencil) depend on 4 neighbor red cells. Conversely, red solution cells depend only on 4 respective adjoining black cells. 1. Compute v at black cells at time n+1 in parallel with v at red cells at time n. 2. Compute v at red cells at time n+1 in parallel with v at black cells at time n+1. 3. Repeat steps 1 and 2 until converged Can alternate order of steps 1 and 2. x x o x x x x o x x X x x O o x Xx