(Parallel Algorithms and Scalability)

methods

PACT

Coarse-grain parallelisation of multi-imlicit Runge-Kutta methodsWorkpackage WP5.3 PASCA (Parallel Algorithms and Scalability)

Roman Trobec y, Bojan Orel z, Bostjan Slivnik yy

Jozef Stefan Institute, Slovenia, E-mail: roman.trobec@ijs.si, z University of Ljubljana

methods

Introduction

PACT

A parallel implementation for multi-implicit Runge-Kutta methods with real eigenvalues is described. The parallel method is analysed and the algorithm is devised. For the problem with d domains, the amount within the s-stage Runge-Kutta method, associated with the solution of system, is proportional to (sd)3 . The proposed parallelisation transforms the above system to s independent sub-systems of dimension d. The amount of work for the solution of such systems is proportional to sd3 . The solution of d dimensional sub-systems is the most complex operation within the Runge-Kutta method. The described parallel algorithm enable to solve each subsystem on a separate processor or on a separate set of processors.

Abstract

1 IntroductionSeveral research areas are faced with problems that can not be solved explicitly. With the increasing computer power, particularly with the parallel computers, many numerical methods gained in their importance. Let us mention two research areas where the numerical methods are an important tool for the problem solving. The basic physical equation which describes the heat transfer is the di usion equation:

Heat transfer simulation

ordinates equals

D stands for the di usion coe cient and r2 is Laplacian operator, which in Cartesian cofor simple one dimensional case. The expressions can be extended straightforward for more dimensions. It is therefore the partial di erential equation of the second order. Heat transfer is an example of a propagation problem i.e., an initial-value problem in an open domain (open with respect to one of the independent variables). In our case time t is taken as an independent variable with an open domain, because the initial heat distribution at time t0 is marched forward in time. Thus we are looking for a time evolution of a heat distribution. However, domains of other independent variables are closed. In one dimensional heat transfer for example, value of independent variables x, lies on interval (x; x ). For the variable we must provide boundary-conditions i.e., values of T at the boundary (like T (t) for any t> t0 ). The exact solution of the di usion equation can be computed only for simple cases i.e., for the geometrical bodies consisting of one material. However, in practice we are faced with much harder problems: with bodies of irregular shapes which can hardly be modelledlo hi xlo

@T= Dr2 T .@t

r2T=@ T@x2

2

Parallel Numerics 95/Sorrento, Italy/September 27-29, 1995

methods

Introduction

PACT

using geometrical approach, with non-uniform initial heat distribution for which no simple mathematical function can be found, and with a number of di erent di usion coe cients in the model 1]

. In this cases the di usion equation should be rewritten as where the di usion coe cient is a function of the co-ordinate x i.e., D represents a di usion coe cient in the point (x). Equation (1) can be semi-discretised in x variable. Let d be a given integer. The interval (x; x ) is divided with points x= i(x? x )=(d+ 1); i= 1; 2;:::; d into d+ 1 subintervals of length k= (x? x )=(d+ 1). The term 2 2 is replaced by the second divided di erence@ 2 T (x; t) T (x?1; t)? 2T (x; t)+ T (x+1; t);x lo hi i hi lo hi lo@ T@x

@T= D@ 2 T,@t@x2x

(1)

which yields a system of ordinary di erential equations dv(t)= Sv(t);

@x2

i

i

k2

i

i

where v(t) denotes:::; T (t);:::] . Matrix S represents the system, incorporating di usion coe cients 2?2 1 0::: 0 0 3 6 1?2 1::: 0 0 7 7 6 D6 .. .. 7 ... S= k2 6 . .7 6 6 0 0 0:::?2 1 7 7 4 5 0 0 0::: 1?2 with initial temperature distribution T (x; 0)= T0: (3)i T i

dt

(2)

Molecular dynamics integration

One of the most demanding calculation in molecular dynamics is the evaluation model of a system of N interacting particles in a cube of side L 2]. The periodic boundary conditions are imposed to conserve the number of particles. The initial velocities and positions for all particles are calculated in such a way that the average kinetic energy remains constant. To perform the MD simulation of such a system the forces acting on each particle have to be calculated for each time step h. The equation of motion X (4) m r= f (r );i i j

for N particles with masses m interacting through the Lennard-Jones potential has to be numerically integrated. Choosing the units appropriately, the pairwise forces at the distance r in the x direction can be expressed by?14? 1 r?8; (5) f (r )= (x? x ) r 2i ij x ij i j ij ij

6=

ij

i

Parallel Numerics 95/Sorrento, Italy/September 27-29, 1995

methods

Parallelisation of Runge-Kutta method

PACT

and correspondingly for the other directions. The number of all interactions is N (N? 1)=2. Using Newton's law the equation of motion (4) readsri

= f (r)

(6)

for a unit mass (m= 1). r(t) is the position vector of N particles at time t r(t)= r1; r2;:::; r], r their acceleration and f the force acting on a particular particle at time t. The Equation (6) can be rewritten in a system of the rst-order di erential equationsN

_= v _ v= f (r);r

(7)

with initial positions r0 and initial velocities v0 . Both of the mentioned systems of ordinary di erential equations (2) and (7) can be efciently solved by means of parallel multi-implicit Runge-Kutta methods 3]. In the next section the parallel de nition of the multi-implicit Runge-Kutta method will be devised. Then the parallel algorithm will be shown an …… 此处隐藏：5651字，全部文档内容请下载后查看。喜欢就下载吧 ……