B. D Lubachevsky. # Parallelizing an algorithm of Charles S. Peskin for describing incompressible flow of a fluid coupled to an elastic membrane online

. **(page 1 of 3)**

Online Library → B. D Lubachevsky → Parallelizing an algorithm of Charles S. Peskin for describing incompressible flow of a fluid coupled to an elastic membrane → online text (page 1 of 3)

Font size

Ultracomputer Note #42 May 1982

Parallelizing an Algorithm of Charles S. Peskin

for Describing Incompressible Flow of a Fluid

Coupled to an Elastic Membrane.

by

B. D. Lubachevsky

Computer Science Dept.

New York University

251 Mercer St., New York, N.Y. 10012

Abstract - An algorithm of Charles S. Peskin for simulation of

incompressible flow of a fluid coupled to an elastic membrane, was

implemented as a program for an asynchronous shared memory parallel

computer, the "NYU-Ultracomputer". The algorithm is an iterative

repetition of a cycle consisting of recomputing the position of the

membrane and the velocity of the fluid for successive descrete times.

Each iteration requires solving Navier-Stokes equations for the fluid,

using an FFT and algorithms for solving linear equations and also

includes an iterative minimization of a tension functional for

recomputation of the new position of the membrane. All these phases

are parallelized by spawning a number of independent tasks and waiting

for all of them to terminate. The program includes subroutines

REQUEST (INDEX) and SYNCH which provide coordination necessary for such

a spawning. Timing analysis of simulated executions predicts high

efficiency of this algorithm for parallel computers that include up to

hundreds of processing elements in the 2-D case and up to thousands of

processing elements in the 3-D case.

This work was supported in part by the Applied Mathematical Sciences

Program of the U.S. Department of Energy under Contract No.

DE-AC02-76ER03077, and in part by the National Science Foundation under

Grant No. NSF-MCS79-21258.

-2-

1. Introduction

Charles P. Peskin has developed [Pes] a serial algorithm for

simulation of incompressible flow of a fluid coupled to an elastic

membrane and has suggested ways of parallelizing this algorithm

[UCN18, UCN19, UCN20]. Note that serial simulation of one pulsation in

the 2-D model of blood flow through heart valves consumes about one

hour of CDC-6600 CPU time. Essential speed-up of these computations is

vitally important for further study and for the extension to the 3-D

case.

The present note describes a simplified 2-D version of this

algorithm implemented as a parallel FORTRAN program for the

"NYU-Ultracomputer" [UCN40], an asynchronous shared memory parallel

machine. Note that these simplifications mostly affected the

initialization part of the program concerned with the representation of

the membrane. In our simplified version the membrane was a stretched

ellipse, whereas in the realistic version it represents the heart. The

most time consuming "physics" of the simulation was practically

untouched. Parallel execution of this program was obtained using

simulators [UCN12, UCN28].

The algorithm is the iterative repetition of a cycle consisting of

recomputing position of the membrane and fluid velocity for successive

descrete times. This cycle includes several phases: solving

Navier-Stok.es equations for the fluid using an FFT , solving linear

equations, and performing an iterative Newton's minimization of a

-3-

tension functional for recomputation of the new position of the

membrane. The system of linear equations arising in this minimization

is solved using odd-even reduction method. Each phase was parallelized

by spawning a number of independent tasks and waiting for these tasks

to terminate. The program includes subroutines REQUEST (INDEX) and

SYNCH which coordinate the spawning and termination.

This note describes the structure of the parallel algorithm,

presents a timing analysis of simulated executions in the 2-D case, and

predicts efficiency of the algorithm in the 3-D case.

2. Serial algorithm.

The 2-D problem is described as follows. (N^ + I) ^ (N^ + 1) mesh

nodes are placed uniformly onto a square of size t >^ t â€¢ In this square

the field of flow velocities and the membrane positions are computed.

Periodic boundary conditions are assumed, i.e. the square is thought

of as representing a torus.

At the beginning of time step n the following data are available:

(i) an array of size N. N^ of flow velocity vectors ^Â±2'

iÂ»j = 0Â»1 Â» â€¢ â€¢ â€¢ jNj^-l ; i.e. a vector for each mesh node;

(ii) an array of size Nâ€ž of vectors of membrane positions X^,

k = 0,...,N2-1; i.e. a two-dimensional position for each membrane

point.

-4-

Membrane positions are thought of as material points fixed on the

elastic boundary, so that an increase of the distance between two

consecutive membrane points X^ and X^' (k' = (k+l)modN2) beyond some

threshold As causes elastic forces to increase.

Peskin's algorithm computes uj"*"^ and Xg'^l through the following

sequence of phases:

Phase 1 . Interpolate fluid velocity field from the mesh nodes onto the

membrane positions:

(2.1) Un = j; u^. D. j(X^) (Ax)2

i.j

where:

Ax = Â£/N^ is the mesh width;

UP is velocity vector of fluid flow at membrane positions #k,

k = 0,...,N2-1;

Dji^.(X), X = (x,y), is the two-dimensional weight function on

the mesh,

(2.2) D.^(x,y) = 6^^(x-iAx) x &i^yiy-2^y) ,

where one-dimensional weight-function 6 is given by expression

6^(x) = __ (1 + cos _â€” ) for lx| _< 2h and

Parallelizing an Algorithm of Charles S. Peskin

for Describing Incompressible Flow of a Fluid

Coupled to an Elastic Membrane.

by

B. D. Lubachevsky

Computer Science Dept.

New York University

251 Mercer St., New York, N.Y. 10012

Abstract - An algorithm of Charles S. Peskin for simulation of

incompressible flow of a fluid coupled to an elastic membrane, was

implemented as a program for an asynchronous shared memory parallel

computer, the "NYU-Ultracomputer". The algorithm is an iterative

repetition of a cycle consisting of recomputing the position of the

membrane and the velocity of the fluid for successive descrete times.

Each iteration requires solving Navier-Stokes equations for the fluid,

using an FFT and algorithms for solving linear equations and also

includes an iterative minimization of a tension functional for

recomputation of the new position of the membrane. All these phases

are parallelized by spawning a number of independent tasks and waiting

for all of them to terminate. The program includes subroutines

REQUEST (INDEX) and SYNCH which provide coordination necessary for such

a spawning. Timing analysis of simulated executions predicts high

efficiency of this algorithm for parallel computers that include up to

hundreds of processing elements in the 2-D case and up to thousands of

processing elements in the 3-D case.

This work was supported in part by the Applied Mathematical Sciences

Program of the U.S. Department of Energy under Contract No.

DE-AC02-76ER03077, and in part by the National Science Foundation under

Grant No. NSF-MCS79-21258.

-2-

1. Introduction

Charles P. Peskin has developed [Pes] a serial algorithm for

simulation of incompressible flow of a fluid coupled to an elastic

membrane and has suggested ways of parallelizing this algorithm

[UCN18, UCN19, UCN20]. Note that serial simulation of one pulsation in

the 2-D model of blood flow through heart valves consumes about one

hour of CDC-6600 CPU time. Essential speed-up of these computations is

vitally important for further study and for the extension to the 3-D

case.

The present note describes a simplified 2-D version of this

algorithm implemented as a parallel FORTRAN program for the

"NYU-Ultracomputer" [UCN40], an asynchronous shared memory parallel

machine. Note that these simplifications mostly affected the

initialization part of the program concerned with the representation of

the membrane. In our simplified version the membrane was a stretched

ellipse, whereas in the realistic version it represents the heart. The

most time consuming "physics" of the simulation was practically

untouched. Parallel execution of this program was obtained using

simulators [UCN12, UCN28].

The algorithm is the iterative repetition of a cycle consisting of

recomputing position of the membrane and fluid velocity for successive

descrete times. This cycle includes several phases: solving

Navier-Stok.es equations for the fluid using an FFT , solving linear

equations, and performing an iterative Newton's minimization of a

-3-

tension functional for recomputation of the new position of the

membrane. The system of linear equations arising in this minimization

is solved using odd-even reduction method. Each phase was parallelized

by spawning a number of independent tasks and waiting for these tasks

to terminate. The program includes subroutines REQUEST (INDEX) and

SYNCH which coordinate the spawning and termination.

This note describes the structure of the parallel algorithm,

presents a timing analysis of simulated executions in the 2-D case, and

predicts efficiency of the algorithm in the 3-D case.

2. Serial algorithm.

The 2-D problem is described as follows. (N^ + I) ^ (N^ + 1) mesh

nodes are placed uniformly onto a square of size t >^ t â€¢ In this square

the field of flow velocities and the membrane positions are computed.

Periodic boundary conditions are assumed, i.e. the square is thought

of as representing a torus.

At the beginning of time step n the following data are available:

(i) an array of size N. N^ of flow velocity vectors ^Â±2'

iÂ»j = 0Â»1 Â» â€¢ â€¢ â€¢ jNj^-l ; i.e. a vector for each mesh node;

(ii) an array of size Nâ€ž of vectors of membrane positions X^,

k = 0,...,N2-1; i.e. a two-dimensional position for each membrane

point.

-4-

Membrane positions are thought of as material points fixed on the

elastic boundary, so that an increase of the distance between two

consecutive membrane points X^ and X^' (k' = (k+l)modN2) beyond some

threshold As causes elastic forces to increase.

Peskin's algorithm computes uj"*"^ and Xg'^l through the following

sequence of phases:

Phase 1 . Interpolate fluid velocity field from the mesh nodes onto the

membrane positions:

(2.1) Un = j; u^. D. j(X^) (Ax)2

i.j

where:

Ax = Â£/N^ is the mesh width;

UP is velocity vector of fluid flow at membrane positions #k,

k = 0,...,N2-1;

Dji^.(X), X = (x,y), is the two-dimensional weight function on

the mesh,

(2.2) D.^(x,y) = 6^^(x-iAx) x &i^yiy-2^y) ,

where one-dimensional weight-function 6 is given by expression

6^(x) = __ (1 + cos _â€” ) for lx| _< 2h and