Copyright
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 LibraryB. D LubachevskyParallelizing 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
QR-code for this ebook


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


1 3

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