Search NASA⌕ Search

SEARCH · Search NASA

Results for “parallel multigrid”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 109 records · Page 6
All sourcesNASA NTRSDOE OSTI
DOE OSTI2020

Multigrid-Reduction-in-Time for the Rotating Shallow Water Equations

We consider multilevel time-parallel methods for the numerical solution of the rotating shallow water equations. In particular, the multigrid-reduction-in-time (MGRIT) algorithm is used for the parallel time integration. An asymptotic model is used at the coarse levels while the full model is employed at the finer levels. The asymptotic model is well-suited for highly oscillatory partial differential equations like the rotating shallow water equations because it can accurately and stably take the required large time-steps on coarse levels. Our work exploits the flexibility of the MGRIT algorithm in terms of the number of levels and relaxation schemes to show some computational benefits, especially with respect to FCF-relaxation and data reuse.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS2000

A Two Colorable Fourth Order Compact Difference Scheme and Parallel Iterative Solution of the 3D Convection Diffusion Equation

A new fourth order compact difference scheme for the three dimensional convection diffusion equation with variable coefficients is presented. The novelty of this new difference scheme is that it Only requires 15 grid points and that it can be decoupled with two colors. The entire computational grid can be updated in two parallel subsweeps with the Gauss-Seidel type iterative method. This is compared with the known 19 point fourth order compact differenCe scheme which requires four colors to decouple the computational grid. Numerical results, with multigrid methods implemented on a shared memory parallel computer, are presented to compare the 15 point and the 19 point fourth order compact schemes.

Zhang, Jun↗
DOE OSTI2024

Cold Plasma Measurements

We have continued the simulation campaign in support of our ongoing magnetospheric cold plasma research project. This project aims to develop the next-generation particle instruments to measure the properties of the cold particle populations in the Earth’s magnetosphere. For this purpose, simulations have been performed with a Particle-In-Cell (PIC) code called the Curvilinear PIC (CPIC). The code is formulated in curvilinear geometry and couples the standard PIC algorithm with algorithms for the generation and adaptation of the underlaying computational mesh. It conforms to complex objects like spacecraft and it can place more grid points in regions where higher resolution is needed. The code also features a scalable solver based on the multigrid algorithm and it is fully parallelized via domain decomposition and MPI.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗
NASA NTRS2000

A Domain-Decomposed Multilevel Method for Adaptively Refined Cartesian Grids with Embedded Boundaries

Preliminary verification and validation of an efficient Euler solver for adaptively refined Cartesian meshes with embedded boundaries is presented. The parallel, multilevel method makes use of a new on-the-fly parallel domain decomposition strategy based upon the use of space-filling curves, and automatically generates a sequence of coarse meshes for processing by the multigrid smoother. The coarse mesh generation algorithm produces grids which completely cover the computational domain at every level in the mesh hierarchy. A series of examples on realistically complex three-dimensional configurations demonstrate that this new coarsening algorithm reliably achieves mesh coarsening ratios in excess of 7 on adaptively refined meshes. Numerical investigations of the scheme's local truncation error demonstrate an achieved order of accuracy between 1.82 and 1.88. Convergence results for the multigrid scheme are presented for both subsonic and transonic test cases and demonstrate W-cycle multigrid convergence rates between 0.84 and 0.94. Preliminary parallel scalability tests on both simple wing and complex complete aircraft geometries shows a computational speedup of 52 on 64 processors using the run-time mesh partitioner.

Aftosmis, M. J.↗
NASA NTRS1989

International Conference on Numerical Methods in Fluid Dynamics, 11th, Williamsburg, VA, June 27-July 1, 1988, Proceedings

Recent advances in computational fluid dynamics (CFD) are discussed in reviews and reports. Topics addressed include CFD models in plasma dynamics, parallel computation for simulation studies, CFD for hypersonic airbreathing aircraft, multigrid methods for the steady incompressible Navier-Stokes equations, upwind differencing techniques, TV stable schemes for shock-interacting flows, Euler models of hypersonic vortex flows, parallel multilevel adaptive methods, and vortex methods for slightly viscous three-dimensional flows. Consideration is given to the accuracy of node-based solutions on irregular meshes, multigrid calculations for cascades, a finite-volume-element method for planar cavity flow, parallel heterogeneous mesh refinement for advection-diffusion equations, the convergence of the spectral-viscosity method for nonlinear conservation laws, and numerical simulations of Taylor vortices in a spherical gap.

Dwoyer, D. L.↗
DOE OSTI2025

TorchBraid: High-Performance Layer-Parallel Training of Deep Neural Networks with MPI and GPU Acceleration

TorchBraid is a high-performance implementation of layer-parallel training for deep neural networks (DNNs) supporting MPI-based parallelism and GPU acceleration. Layer-parallel training has been developed to overcome the serialization inherent in forward and backward propagation of DNNs that limits utilization of computational resources in the strong scaling limit. To achieve this, TorchBraid integrates the PyTorch neural network framework with the state-of-the-art XBraid time-parallel library. Furthermore, this article presents the use and performance of TorchBraid, in addition to solutions for overcoming the algorithmic challenges inherent in combining automatic differentiation with layer-parallel. Results are presented with and without GPU acceleration for the Tiny ImageNet and MNIST image classification data sets, as well as recurrent neural networks. Overall, TorchBraid enables fast training of DNNs, both in a strong and weak scaling context. In addition to the TorchBraid software, several new advances in applying layer-parallel algorithms are detailed. Integration of layer-parallel with data-parallel algorithms is presented for the first time, showing the computational advantages of the combination. Standard deep learning techniques, like batch-normalization, are developed for layer-parallel training. Finally, a new approach combining layer-parallel with spatial coarsening in order to accelerate training for 3D image classification shows roughly a 10× speedup over serial execution.

Layer-parallel↗
NASA NTRS1987

Performance studies of the multigrid algorithms implemented on hypercube multiprocessor systems

In this paper, we analyze and compare the performance on a hypercube multiprocessor of some of the major multigrid techniques used in practice. The model problem considered here is that of solving the 2-D incompressible Navier-Stokes equations representing the flow between two parallel plates. Results obtained by implementing the different multigrid schemes on an iPSC are presented. Effects on the overall performance of various parameters of the algorithms, of the partitioning strategies employed, and of some of the characteristics of the underlying architecture are discussed.

Naik, Vijay K.↗
DOE OSTI2022

Asynchronous Truncated Multigrid-Reduction-in-Time

In this paper, we present the new “asynchronous truncated multigrid-reduction-in-time” (AT-MGRIT) algorithm for introducing time parallelism to the solution of discretized time-dependent problems. The new algorithm is based on the multigrid-reduction-in-time (MGRIT) approach, which, in certain settings, is equivalent to another common multilevel parallel-in-time method, Parareal. In contrast to Parareal and MGRIT that both consider a global temporal grid over the entire time interval on the coarsest level, the AT-MGRIT algorithm uses truncated local time grids on the coarsest level, each grid covering certain temporal subintervals. Further, these local grids can be solved completely in an independent way from each other, which reduces the sequential part of the algorithm and, thus, increases parallelism in the method. Here, we study the effect of using truncated local coarse grids on the convergence of the algorithm, both theoretically and numerically, and show, using challenging nonlinear problems, that the new algorithm consistently outperforms classical Parareal/MGRIT in terms of time to solution.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Adaptive Mesh Refinement for Parallel in Time Methods

The project applied the multigrid-reduction-in-time (MGRIT) algorithm to an existing sub-cycled adaptive mesh refinement (AMR) code to investigate the performance of flows dominated by inertial physics. Previous work demonstrated good performance from MGRIT+AMR applied to flows dominated by diffusive physics. Consistent with previous experience, inertial physics negatively affected convergence rates and performance. Efforts to circumvent this issue by appealing to the physics of turbulence were investigated. It has been demonstrated that scales can be effectively transferred between multigrid levels for a turbulent flow resulting in a) partial convergence observed and b) nearly identical results to sequential time-stepping. Performance improvements have not yet been demonstrated - attempts at coarsening the grid on coarser MG levels compromises the solution quality and leads to divergence. This report summarize the accomplishments for the time-frame from 10/5/2020 to 12/31/2020 with an informal no-cost-extension to 05/20/2021

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

A New Semistructured Algebraic Multigrid Method

Multigrid methods are well suited to large massively parallel computer architectures because they are mathematically optimal and display good parallelization properties. Since current architecture trends are favoring regular compute patterns to achieve high performance, the ability to express structure has become much more important. The hypre software library provides high-performance multigrid preconditioners and solvers through conceptual interfaces, including a semistructured interface that describes matrices primarily in terms of stencils and logically structured grids. This paper presents a new semistructured algebraic multigrid (SSAMG) method built on this interface. The numerical convergence and performance of a CPU implementation of this method are evaluated for a set of semistructured problems. In conclusion, SSAMG achieves significantly better setup times than hypre’s unstructured AMG solvers and comparable convergence. In addition, the new method is capable of solving more complex problems than hypre’s structured solvers.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Reducing communication in algebraic multigrid with multi-step node aware communication

Algebraic multigrid (AMG) is often viewed as a scalable [Formula: see text] solver for sparse linear systems. Yet, AMG lacks parallel scalability due to increasingly large costs associated with communication, both in the initial construction of a multigrid hierarchy and in the iterative solve phase. This work introduces a parallel implementation of AMG that reduces the cost of communication, yielding improved parallel scalability. It is common in Message Passing Interface (MPI), particularly in the MPI-everywhere approach, to arrange inter-process communication, so that communication is transported regardless of the location of the send and receive processes. Performance tests show notable differences in the cost of intra- and internode communication, motivating a restructuring of communication. In this case, the communication schedule takes advantage of the less costly intra-node communication, reducing both the number and the size of internode messages. Node-centric communication extends to the range of components in both the setup and solve phase of AMG, yielding an increase in the weak and strong scaling of the entire method.

Computer Science↗
DOE OSTI2018

A Parallel Solver for Graph Laplacians

Problems from graph drawing, spectral clustering, network flow and graph partitioning can all be expressed in terms of graph Laplacian matrices. There are a variety of practical approaches to solving these problems in serial. However, as problem sizes increase and single core speeds stagnate, parallelism is essential to solve such problems quickly. We present an unsmoothed aggregation multigrid method for solving graph Laplacians in a distributed memory setting. We introduce new parallel aggregation and low degree elimination algorithms targeted specifically at irregular degree graphs. These algorithms are expressed in terms of sparse matrix-vector products using generalized sum and product operations. This formulation is amenable to linear algebra using arbitrary distributions and allows us to operate on a 2D sparse matrix distribution, which is necessary for parallel scalability. Our solver outperforms the natural parallel extension of the current state of the art in an algorithmic comparison. We demonstrate scalability to 576 processes and graphs with up to 1.7 billion edges.

Konolige, Tristan↗
DOE OSTI2024

Non-Intrusive Parallel-in-Time Solvers for Partial Differential Equations (Final Report)

Many time-dependent problems and simulations are often modeled using Partial Differential Equations. Traditional modeling approaches that use sequential time-stepping are reaching a bottleneck in optimizing efficiency. The Center of Applied Science and Computing at Lawrence Livermore National Laboratory extensively works on parallelizing these algorithms to leverage the increasing computational power from the growing number of processors in computer hardware. In particular, they aim to design non-intrusive algorithms that can generalize to a variety of problems and sizes without requiring additional information from or modifications on the original problems. Multigrid Reduction in Time (MGRIT) is a parallel-in-time algorithm that is designed to be non-intrusive. This project focuses on increasing the efficiency of MGRIT by approximating the coarse-grid operator using machine learning approaches as a means to find the most non-intrusive, or general, solution.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Multigrid reduction in time with Richardson extrapolation

The advent of exascale computing will leave many users with access to more computational resources than they can simultaneously use, e.g., billion-way parallelism. In particular, this is true for time-dependent simulations that limit parallelism to the spatial domain. One method to add parallelism in time to existing simulation codes and thus take advantage of ever larger compute resources is Multigrid Reduction in Time (MGRIT). The goal is to achieve a smaller time-to-solution through parallelism in time. In this paper, MGRIT is enhanced with Richardson extrapolation in a cost-efficient way to produce a parallel-in-time method with improved accuracy. Overall, this leads to a large improvement in the accuracy per computational cost of MGRIT.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1993

An integrated runtime and compile-time approach for parallelizing structured and block structured applications

Scientific and engineering applications often involve structured meshes. These meshes may be nested (for multigrid codes) and/or irregularly coupled (called multiblock or irregularly coupled regular mesh problems). A combined runtime and compile-time approach for parallelizing these applications on distributed memory parallel machines in an efficient and machine-independent fashion was described. A runtime library which can be used to port these applications on distributed memory machines was designed and implemented. The library is currently implemented on several different systems. To further ease the task of application programmers, methods were developed for integrating this runtime library with compilers for HPK-like parallel programming languages. How this runtime library was integrated with the Fortran 90D compiler being developed at Syracuse University is discussed. Experimental results to demonstrate the efficacy of our approach are presented. A multiblock Navier-Stokes solver template and a multigrid code were experimented with. Our experimental results show that our primitives have low runtime communication overheads. Further, the compiler parallelized codes perform within 20 percent of the code parallelized by manually inserting calls to the runtime library.

Agrawal, Gagan↗
DOE OSTI2023

Fast Multigrid Reduction-in-Time for Advection via Modified Semi-Lagrangian Coarse-Grid Operators

Many iterative parallel-in-time algorithms have been shown to be highly efficient for diffusion-dominated partial differential equations (PDEs) but are inefficient or even divergent when applied to advection-dominated PDEs. We consider the application of the multigrid reduction-in-time (MGRIT) algorithm to linear advection PDEs. Here, the key to efficient time integration with this method is using a coarse-grid operator that provides a sufficiently accurate approximation to the so-called ideal coarse-grid operator. For certain classes of semi-Lagrangian discretizations, we present a novel semi-Lagrangian-based coarse-grid operator that leads to fast and scalable multilevel time integration of linear advection PDEs. The coarse-grid operator is composed of a semi-Lagrangian discretization followed by a correction term, with the correction designed so that the leading-order truncation error of the composite operator is approximately equal to that of the ideal coarse-grid operator. Parallel results show substantial speed-ups over sequential time integration for variable-wave-speed advection problems in one and two spatial dimensions, and using high-order discretizations up to order five. The proposed approach establishes the first practical method that provides small and scalable MGRIT iteration counts for advection problems.

97 MATHEMATICS AND COMPUTING↗