Multigrid methods with space–time concurrency

被引：33

作者：

Falgout R.D. ^{[1
]}

Friedhoff S. ^{[2
,3
]}

Kolev T.V. ^{[1
]}

MacLachlan S.P. ^{[4
]}

Schroder J.B. ^{[1
]}

Vandewalle S. ^{[2
]}

机构：

[1] Center for Applied Scientific Computing, Lawrence Livermore National Laboratory, P. O. Box 808, L-561, Livermore, 94551, CA

[2] Department of Computer Science, KU Leuven, Celestijnenlaan 200a - box 2402, Leuven

[3] Fakultät für Mathematik und Naturwissenschaften, Bergische Universität Wuppertal, Wuppertal

[4] Department of Mathematics and Statistics, Memorial University of Newfoundland, St. John’s, NL

来源：

Computing and Visualization in Science | 2017年 / 18卷 / 4-5期

基金：

美国国家科学基金会; 加拿大自然科学与工程研究理事会;

关键词：

Multigrid methods; Parallel-in-time integration; Space–time discretizations;

D O I：

10.1007/s00791-017-0283-9

中图分类号：

学科分类号：

摘要：

We consider the comparison of multigrid methods for parabolic partial differential equations that allow space–time concurrency. With current trends in computer architectures leading towards systems with more, but not faster, processors, space–time concurrency is crucial for speeding up time-integration simulations. In contrast, traditional time-integration techniques impose serious limitations on parallel performance due to the sequential nature of the time-stepping approach, allowing spatial concurrency only. This paper considers the three basic options of multigrid algorithms on space–time grids that allow parallelism in space and time: coarsening in space and time, semicoarsening in the spatial dimensions, and semicoarsening in the temporal dimension. We develop parallel software and performance models to study the three methods at scales of up to 16K cores and introduce an extension of one of them for handling multistep time integration. We then discuss advantages and disadvantages of the different approaches and their benefit compared to traditional space-parallel algorithms with sequential time stepping on modern architectures. © 2017, US Government.

引用

页码：123 / 143

页数：20

共 47 条

[1]

Ashby S.F., Falgout R.D., A parallel multigrid preconditioned conjugate gradient algorithm for groundwater flow simulations, Nucl. Sci. Eng., 124, 1, pp. 145-159, (1996)

[2]

Bastian P., Burmeister J., Horton G., Implementation of a parallel multigrid method for parabolic partial differential equations, Parallel Algorithms for PDEs, Proc. 6th GAMM Seminar Kiel, January 19–21, 1990, pp. 18-27, (1990)

[3]

Bjorhus M., On domain decomposition, subdomain iteration and waveform relaxation. Ph.D. thesis, Department of Mathematical Sciences, Norwegian Institute of Technology, University of Trondheim, (1995)

[4]

Bolten M., Moser D., Speck R., A multigrid perspective on the parallel full approximation scheme in space and time. Numerical Linear Algebra with Applications pp. e2110–n/a (2017), E2110 nla, (2017)

[5]

Brandt A., Multi-level adaptive solutions to boundary-value problems, Math. Comput., 31, pp. 333-390, (1977)

[6]

Buzbee B.L., Golub G.H., Nielson C.W., On direct methods for solving Poisson’s equations, SIAM J. Numer. Anal., 7, pp. 627-656, (1970)

[7]

Chartier P., Philippe B., A parallel shooting technique for solving dissipative ODEs, Computing, 51, 3-4, pp. 209-236, (1993)

[8]

Christlieb A.J., Macdonald C.B., Ong B.W., Parallel high-order integrators, SIAM J. Sci. Comput., 32, 2, pp. 818-835, (2010)

[9]

De Sterck H., Manteuffel T.A., McCormick S.F., Olson L., Least-squares finite element methods and algebraic multigrid solvers for linear hyperbolic PDEs, SIAM J. Sci. Comput., 26, 1, pp. 31-54, (2004)

[10]

Emmett M., Minion M.L., Toward an efficient parallel in time method for partial differential equations, Commun. Appl. Math. Comput. Sci., 7, 1, pp. 105-132, (2012)

← 1 2 3 4 5 →