Fast Poisson solvers based on fast Fourier transform (FFT) computations are among the
fastest techniques to solve Poisson equation on uniform grids. In this paper, the
authors present two parallel distributed implementations of a 3-D fast Poisson
solver in the context of the atmospheric simulation code. The first approach
consists of implementing data movement between each computational step so that no
elementary computational routine involves communication. The second approach aims at
reducing the global data movement and requires the parallelization of one step of
the fast Poisson solver. Experimental results on a 128-node Cray T3E are presented
to illustrate the advantages and drawbacks of each approach.
Get full access to this article
View all access options for this article.
References
1.
Asworth, M.
, and
Lyne, A.1988.
A segmented FFT algorithms for the vector computers
. Parallel Computing6:
217-224
.
2.
Averbuch, A.
,
Gabber, E.
,
Gordissky, B.
, and
Medan, Y.1990.
A parallel FFT on a MIMD machine
. Parallel Computing15:
61-74
.
3.
Averbuch, A.
,
Israeli, M.
, and
Vozovoi, L.1998.
A fast Poisson solver of arbitrary order accuracy in rectangular regions
. SIAM J. Scientific Computing19 (3):
933-952
.
4.
Briggs, W. L.
, and
Turnbull, T.1988.
Fast Poisson solvers on MIMD machines
. Parallel Computing6:
265-274
.
5.
Buzbee, B.
,
Golub, G. H.
, and
Nielson, C.1970.
On direct methods for solving Poisson’s equation
. SIAM J. Numerical Analysis7:
627-656
.
6.
Calvin, C.1996.
Implementation of parallel FFT algorithms on distributed memory machines
with minimum overhead of communication
. Parallel Computing22:
1255-1279
.
7.
Chamberlain, R. M.1988.
Gray code, fast Fourier transforms, and hypercubes
. Parallel Computing6:
225-233
.
8.
Chan, T. F.
, and
Mathew, T. P.1994. Domain Decomposition Algorithms.
Cambridge, UK: Cambridge University Press
.
9.
Foster, I.
,
Gropp, W.
, and
Stevens, R.1992.
The parallel scalability of spectral transform method
. Monthly Weather Review120 (5):
835-850
.
10.
Golub, G. H.
,
Huang, L. C.
,
Simon, H.
, and
Tang, W. P.1998.
A fast Poisson solver for the finite difference solution of the
incompressible Navier-Stokes equations
. SIAM J. Scientific Computing19 (5):
1606-1624
.
11.
Gupta, A.
, and
Kumar, V.1993.
The scalability of FFT on parallel computers
. IEEE Transactions on Parallel and Distributed Systems4:
922-932
.
12.
Gustafson, J.
,
Montry, G.
, and
Benner, R.1988.
Development of parallel methods for a 1024-processor hypercube
. SIAM J. Scientific Computing9 (4):
609-638
.
13.
Héreil, P. 1998. Développement et test d’un
modèle non-hydrostatique pour les écoulements
atmosphériques de méso-échelle sur relief. Ph.D.
dissertation, Université Paul Sabatier, Toulouse, France.
14.
Jabouille, P.
,
Guivarch, R.
,
Kloos, P.
,
Gazen, D.
,
Cicquel, N.
,
Giraud, L.
,
Asencio, N.
,
Ducrocq, V.
,
Escobar, J.
,
Redelsperger, J. -L.
,
Stein, J.
, and
Pinty, J. -P.
1999.
Parallelization of the French meteorological mesoscale model MésoNH
. In EUROPAR ’99 Parallel Processing, eds.
P. Amestoy
,
Ph. Berger
,
M. Daydé
,
V. Frayssé
,
L. Giraud
, and
D. Ruiz
,
1417-1422
. New York: Springer-Verlag.
15.
Jhonsson, S. L.
, and
Krawitz, R. L.1992.
Cooley-Tuckey FFT on the connection machine
. Parallel Computing18:
1201-1221
.
16.
Lafore, J. P.
,
Stein, J.
,
Asencio, N.
,
Bougeault, P.
,
Ducrocq, V.
,
Duron, J.
,
Fischer, C.
,
Héreil, P.
,
Mascart, P.
,
Pinty, J. -P.
,
Redelsperger, J. -L.
,
Richard, E.
, and
Vila-Guerau deArellano, J.1998.
The Méso-NH atmospheric simulation system: I. Adiabatic
formulation and control simulations
. Annales Geophysicae16:
90-109
.
17.
Message Passing Interface Forum
. 1994.
MPI: A message-passing interface standard [Special issue]
. Int. J. Supercomputer Applications and High Performance Computing8 (3/4).
18.
Meurant, G. A.1999. Computer Solution of Large Linear Systems.
Amsterdam: North-Holland
.
19.
Quarteroni, A.
, and
Valli, A.1999. Domain Decomposition Methods for Partial Differential
Equations.
Oxford, UK: Oxford Science Publications
.
20.
Sameh, A.1984. A fast Poisson solver for multiprocessors. In
Elliptic Solvers II.
New York: Academic Press
.
21.
Schumann, U.
, and
Sweet, R. A.1998.
Fast-Fourier transforms for direct solution of Poisson’s equation
with staggered boundary conditions
. J. Comp. Phys.75:
123-137
.
22.
Schwarztrauber, P. N.1974.
A direct method for the discrete solution of separable elliptic equations
. SIAM J. Numerical Analysis11:
1136-1150
.
23.
Smith, B. F.
,
Bjørstad, P.
, and
Gropp, W.1996. Domain Decomposition, Parallel Multilevel Methods for Elliptic
Partial Differential Equations.
New York: Cambridge University Press
.
24.
Temperton, C.1979.
Direct methods for the solution of the discrete Poisson equation: Some comparisons
. J. Comp. Phys.31:
1-20
.
25.
Tong, C.
, and
Schwarztrauber, P. N.1991.
Ordered fast Fourier transform on a massively parallel hypercube multiprocessor
. J. Parallel and Distributed Computing12:
50-59
.
26.
van Loan, C.1992. Computational Frameworks for the Fast Fourier Transform.
Philadelphia: SIAM
.
27.
Wesseling, P.1992. An Introduction to Multigrid Methods.
West Sussex, UK: Wiley
.
