SEARCH · Engineering Papers

Results for “parallelize algorithm computation”

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.

SourceResearch connectionFrom yearThrough year

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

At least 1,639 records · Page 91

All sources NASA NTRS DOE OSTI

NASA NTRS1987

Galerkin/Runge-Kutta discretizations for parabolic equations with time dependent coefficients

A new class of fully discrete Galerkin/Runge-Kutta methods is constructed and analyzed for linear parabolic initial boundary value problems with time dependent coefficients. Unlike any classical counterpart, this class offers arbitrarily high order convergence while significantly avoiding what has been called order reduction. In support of this claim, error estimates are proved, and computational results are presented. Additionally, since the time stepping equations involve coefficient matrices changing at each time step, a preconditioned iterative technique is used to solve the linear systems only approximately. Nevertheless, the resulting algorithm is shown to preserve the original convergence rate while using only the order of work required by the base scheme applied to a linear parabolic problem with time independent coefficients. Furthermore, it is noted that special Runge-Kutta methods allow computations to be performed in parallel so that the final execution time can be reduced to that of a low order method.

Keeling, Stephen L.↗

NASA NTRS1989

Galerkin/Runge-Kutta discretizations for parabolic equations with time-dependent coefficients

Keeling, Stephen L.↗

NASA NTRS1994

Empirical study of parallel LRU simulation algorithms

This paper reports on the performance of five parallel algorithms for simulating a fully associative cache operating under the LRU (Least-Recently-Used) replacement policy. Three of the algorithms are SIMD, and are implemented on the MasPar MP-2 architecture. Two other algorithms are parallelizations of an efficient serial algorithm on the Intel Paragon. One SIMD algorithm is quite simple, but its cost is linear in the cache size. The two other SIMD algorithm are more complex, but have costs that are independent on the cache size. Both the second and third SIMD algorithms compute all stack distances; the second SIMD algorithm is completely general, whereas the third SIMD algorithm presumes and takes advantage of bounds on the range of reference tags. Both MIMD algorithm implemented on the Paragon are general and compute all stack distances; they differ in one step that may affect their respective scalability. We assess the strengths and weaknesses of these algorithms as a function of problem size and characteristics, and compare their performance on traces derived from execution of three SPEC benchmark programs.

Carr, Eric↗

NASA NTRS1997

Geopotential Error Analysis from Satellite Gradiometer and Global Positioning System Observables on Parallel Architecture

The recovery of a high resolution geopotential from satellite gradiometer observations motivates the examination of high performance computational techniques. The primary subject matter addresses specifically the use of satellite gradiometer and GPS observations to form and invert the normal matrix associated with a large degree and order geopotential solution. Memory resident and out-of-core parallel linear algebra techniques along with data parallel batch algorithms form the foundation of the least squares application structure. A secondary topic includes the adoption of object oriented programming techniques to enhance modularity and reusability of code. Applications implementing the parallel and object oriented methods successfully calculate the degree variance for a degree and order 110 geopotential solution on 32 processors of the Cray T3E. The memory resident gradiometer application exhibits an overall application performance of 5.4 Gflops, and the out-of-core linear solver exhibits an overall performance of 2.4 Gflops. The combination solution derived from a sun synchronous gradiometer orbit produce average geoid height variances of 17 millimeters.

Schutz, Bob E.↗

DOE OSTI2022

Assessing MP2 frozen natural orbitals in relativistic correlated electronic structure calculations

The high computational scaling with the basis set size and the number of correlated electrons is a bottleneck limiting applications of coupled cluster algorithms, in particular for calculations based on two- or four-component relativistic Hamiltonians, which often employ uncontracted basis sets. This problem may be alleviated by replacing canonical Hartree–Fock virtual orbitals by natural orbitals (NOs). Here, in this paper, we describe the implementation of a module for generating NOs for correlated wavefunctions and, in particular, second order Møller–Plesset perturbation frozen natural orbitals (MP2FNOs) as a component of our novel implementation of relativistic coupled cluster theory for massively parallel architectures [Pototschnig et al. J. Chem. Theory Comput. 17, 5509, (2021)]. Our implementation can manipulate complex or quaternion density matrices, thus allowing for the generation of both Kramers-restricted and Kramers-unrestricted MP2FNOs. Furthermore, NOs are re-expressed in the parent atomic orbital (AO) basis, allowing for generating coupled cluster singles and doubles NOs in the AO basis for further analysis. By investigating the truncation errors of MP2FNOs for both the correlation energy and molecular properties—electric field gradients at the nuclei, electric dipole and quadrupole moments for hydrogen halides HX (X = F–Ts), and parity-violating energy differences for H 2 Z 2 (Z = O–Se)—we find MP2FNOs accelerate the convergence of the correlation energy in a roughly uniform manner across the Periodic Table. It is possible to obtain reliable estimates for both energies and the molecular properties considered with virtual molecular orbital spaces truncated to about half the size of the full spaces.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

DOE OSTI2017

Parallelized Kalman-Filter-Based Reconstruction of Particle Tracks on Many-Core Processors and GPUs

For over a decade now, physical and energy constraints have limited clock speed improvements in commodity microprocessors. Instead, chipmakers have been pushed into producing lower-power, multi-core processors such as Graphical Processing Units (GPU), ARM CPUs, and Intel MICs. Broad-based efforts from manufacturers and developers have been devoted to making these processors user-friendly enough to perform general computations. However, extracting performance from a larger number of cores, as well as specialized vector or SIMD units, requires special care in algorithm design and code optimization. One of the most computationally challenging problems in high-energy particle experiments is finding and fitting the charged-particle tracks during event reconstruction. This is expected to become by far the dominant problem at the High-Luminosity Large Hadron Collider (HL-LHC), for example. Today the most common track finding methods are those based on the Kalman filter. Experience with Kalman techniques on real tracking detector systems has shown that they are robust and provide high physics performance. This is why they are currently in use at the LHC, both in the trigger and offine. Previously we reported on the significant parallel speedups that resulted from our investigations to adapt Kalman filters to track fitting and track building on Intel Xeon and Xeon Phi. Here, we discuss our progresses toward the understanding of these processors and the new developments to port the Kalman filter to NVIDIA GPUs.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

DOE OSTI2015

A method for data handling numerical results in parallel OpenFOAM simulations

Parallel computational fluid dynamics simulations produce vast amount of numerical result data. This paper introduces a method for reducing the size of the data by replaying the interprocessor traffic. The results are recovered only in certain regions of interest configured by the user. A known test case is used for several mesh partitioning scenarios using the OpenFOAM toolkit{sup ®}[1]. The space savings obtained with classic algorithms remain constant for more than 60 Gb of floating point data. Our method is most efficient on large simulation meshes and is much better suited for compressing large scale simulation results than the regular algorithms.

42 ENGINEERING↗

DOE OSTI2015

Relative entropy and optimization-driven coarse-graining methods in VOTCA

We discuss recent advances of the VOTCA package for systematic coarse-graining. Two methods have been implemented, namely the downhill simplex optimization and the relative entropy minimization. We illustrate the new methods by coarse-graining SPC/E bulk water and more complex water-methanol mixture systems. The CG potentials obtained from both methods are then evaluated by comparing the pair distributions from the coarse-grained to the reference atomistic simulations.We have also added a parallel analysis framework to improve the computational efficiency of the coarse-graining process.

74 ATOMIC AND MOLECULAR PHYSICS↗

DOE OSTI2016

On the Degradation of the Effectiveness of Nonlinear Diffusion Acceleration with Parallel Block Jacobi Splitting

MOOSE's radiation transport module Rattlesnake comprises a first order S N solver that can be accelerated with a flexible Nonlinear Diffusion Acceleration. At each NDA iteration, the streaming and collision operator of the S{sub N} equations are (approximately) inverted using a transport sweep. When executed on multiple processors parallel block Jacobi (PBJ) splitting is utilized lagging the processor sub-domain's incoming angular fluxes making the implemented method asynchronous, i.e. the convergence properties of NDA become dependent on the number of concurrent tasks and details of the partitioning. Within this work, we study the NDA convergence properties for the two-dimensional C5G7 benchmark problem PBJ with p = 1, 2, 4, 8, 12, 16, 24, 32, 48, 60, 72, 96 and 144 concurrent tasks. Rosa studied the convergence properties of PBJ splitting methods with and without transport synthetic acceleration (TSA) in slab geometry and two-dimensional Cartesian geometry, respectively. Rosa's iteration scheme lags both the incoming angular fluxes and the scattering source making it very similar to the method described here. Rosa found by means of Fourier analysis that convergence of unaccelerated PBJ can degrade for optically thin subdomains, i.e. for a large number of processors given a fixed domain size. Depending on the choice of parameters application of TSA can lead to an effective algorithm. In contrast to Rosa's work, this work focuses on PBJ splitting for NDA accelerated solution of the multigroup eigenvalue problem. Later, Zerr and Anistratov used their integral transport matrix method in conjunction with PBJ. This iteration scheme is different as it does not lag the scattering source. Nevertheless, Fourier analysis with Diamond Difference spatial discretization showed that the method degrades with increasing the overall size of the spatial domain while keeping the sub-domain size constant. In the case of an infinite medium, the observed spectral radius becomes unity. These references establish the iterative performance of PBJ for one-group fixed source problems discretized on rectangular cells, but for the Rattlesnake first order NDA method, an emphasis lies on multigroup eigenvalue problems. In this setting, the additional complication arises that the low order equations are not exactly inverted, but only to some iterative criterion. Further, as the low order problem is solved using Jacobian-Free Newton Krylov methods, a suitable preconditioner for the GMRES iterations is required. As the effectiveness of the preconditioners may decrease when more concurrent processes are used, we expect the low order solve to impact the overall effectiveness of the NDA method in parallel execution as well. Therefore, this work focuses on the question of how detrimental the asynchronicity of the high and low order iterative solutions is for the effectiveness of NDA solutions of realistic, unstructured grid, multigroup eigenvalue problems. The iterative convergence properties of Rattlesnake's NDA method for multigroup eigenvalue problems are studied for varying number of concurrent processes. Rattlesnake's NDA method is asynchronous because the high order transport sweep uses PBJ splitting and because the low order solve's preconditioners, algebraic multigrid and additive Schwarz, are asynchronous. We found that up to 144 processes the number of Picard iterations increases by a factor of 2-3 affecting but not destroying NDA's parallel performance for the C5G7 benchmark problem, a representative LWR (light water reactor) configuration. The solution of the NDA low order eigenvalue problem posed greater problems than expected for the solvers currently available in Rattlesnake mainly because of problems to effectively precondition the modified low-order problem. As a matter of fact, the low order problem becomes an advection-diffusion problem. Non-robustness was observed for the AMG preconditioned coarse mesh acceleration for more than 60 concurrent processes, which was fixed by increasing the number of permissible V-cycles per AMG call. For fine mesh acceleration AMG proved to be ineffective and we resorted to ASM. For both AMG and ASM, increasing number of linear iterations per nonlinear are observed when increasing the number of processes, but for ASM this problem appears to be worse. The results from this work also indicate that initial development efforts should be diverted from implementation of a high-order parallel sweeping algorithm to the effective and robust iterative solution of the low order NDA multigroup eigenvalue problem. (authors)

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2014

Development and Benchmarking of a Hybrid PIC Code For Dense Plasmas and Fast Ignition (Final Report)

Radiation processes play an important role in the study of both fast ignition and other inertial confinement schemes, such as plasma jet driven magneto-inertial fusion, both in their effect on energy balance, and in generating diagnostic signals. In the latter case, warm and hot dense matter may be produced by the convergence of a plasma shell formed by the merging of an assembly of high Mach number plasma jets. This innovative approach has the potential advantage of creating matter of high energy densities in voluminous amount compared with high power lasers or particle beams. An important application of this technology is as a plasma liner for the flux compression of magnetized plasma to create ultra-high magnetic fields and burning plasmas. HyperV Technologies Corp. has been developing plasma jet accelerator technology in both coaxial and linear railgun geometries to produce plasma jets of sufficient mass, density, and velocity to create such imploding plasma liners. An enabling tool for the development of this technology is the ability to model the plasma dynamics, not only in the accelerators themselves, but also in the resulting magnetized target plasma and within the merging/interacting plasma jets during transport to the target. Welch pioneered numerical modeling of such plasmas (including for fast ignition) using the LSP simulation code. Lsp is an electromagnetic, parallelized, plasma simulation code under development since 1995. It has a number of innovative features making it uniquely suitable for modeling high energy density plasmas including a hybrid fluid model for electrons that allows electrons in dense plasmas to be modeled with a kinetic or fluid treatment as appropriate. In addition to in-house use at Voss Scientific, several groups carrying out research in Fast Ignition (LLNL, SNL, UCSD, AWE (UK), and Imperial College (UK)) also use LSP. A collaborative team consisting of HyperV Technologies Corp., Voss Scientific LLC, FAR-TECH, Inc., Prism Computational Sciences, Inc. and Advanced Energy Systems Inc. joined efforts to develop new physics and numerical models for LSP in several key areas to enhance the ability of LSP to model high energy density plasmas (HEDP). This final report details those efforts. Areas addressed in this research effort include: adding radiation transport to LSP, first in 2D and then fully 3D, extending the EMHD model to 3D, implementing more advanced radiation and electrode plasma boundary conditions, and installing more efficient implicit numerical algorithms to speed complex 2-D and 3-D computations. The new capabilities allow modeling of the dominant processes in high energy density plasmas, and further assist the development and optimization of plasma jet accelerators, with particular attention to MHD instabilities and plasma/wall interaction (based on physical models for ion drag friction and ablation/erosion of the electrodes). In the first funding cycle we implemented a solver for the radiation diffusion equation. To solve this equation in 2-D, we used finite-differencing and applied the parallelized sparse-matrix solvers in the PETSc library (Argonne National Laboratory) to the resulting system of equations. A database of the necessary coefficients for materials of interest was assembled using the PROPACEOS and ATBASE codes from Prism. The model was benchmarked against Prism's 1-D radiation hydrodynamics code HELIOS, and against experimental data obtained from HyperV's separately funded plasma jet accelerator development program. Work in the second funding cycle focused on extending the radiation diffusion model to full 3-D, continued development of the EMHD model, optimizing the direct-implicit model to speed up calculations, add in multiply ionized atoms, and improved the way boundary conditions are handled in LSP. These new LSP capabilities were then used, along with analytic calculations and Mach2 runs, to investigate plasma jet merging, plasma detachment and transport, restrike and advanced jet accelerator design. In addition, a strong linkage to diagnostic measurements was made by modeling plasma jet experiments on PLX to support benchmarking of the code. A large number of upgrades and improvements advancing hybrid PIC algorithms were implemented in LSP during the second funding cycle. These include development of fully 3D radiation transport algorithms, new boundary conditions for plasma-electrode interactions, and a charge conserving equation of state that permits multiply ionized high-Z ions. The final funding cycle focused on 1) mitigating the effects of a slow-growing grid instability which is most pronounced in plasma jet frame expansion problems using the two-fluid Eulerian remap algorithm, 2) extension of the Eulerian Smoothing Algorithm to allow EOS/Radiation modeling, 3) simulations of collisionless shocks formed by jet merging, 4) simulations of merging jets using high-Z gases, 5) generation of PROPACEOS EOS/Opacity databases, 6) simulations of plasma jet transport experiments, 7) simulations of plasma jet penetration through transverse magnetic fields, and 8) GPU PIC code development. The tools developed during this project are applicable not only to the study of plasma jets, but also to a wide variety of HEDP plasmas of interest to DOE, including plasmas created in short-pulse laser experiments performed to study fast ignition concepts for inertial confinement fusion.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

DOE OSTI2021

Modeling of a chain of three plasma accelerator stages with the WarpX electromagnetic PIC code on GPUs

The fully electromagnetic particle-in-cell code WarpX is being developed by a team of the U.S. DOE Exascale Computing Project (with additional non-U.S. collaborators on part of the code) to enable the modeling of chains of tens to hundreds of plasma accelerator stages on exascale supercomputers, for future collider designs. The code is combining the latest algorithmic advances (e.g., Lorentz boosted frame and pseudo-spectral Maxwell solvers) with mesh refinement and runs on the latest computer processing unit and graphical processing unit (GPU) architectures. In this paper, we summarize the strategy that was adopted to port WarpX to GPUs, report on the weak parallel scaling of the pseudo-spectral electromagnetic solver, and then present solutions for decreasing the time spent in data exchanges from guard regions between subdomains. In Sec. IV, we demonstrate the simulations of a chain of three consecutive multi-GeV laser-driven plasma accelerator stages.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

DOE OSTI2016

Distributed Halide

Many image processing tasks are naturally expressed as a pipeline of small computational kernels known as stencils. Halide is a popular domain-specific language and compiler designed to implement image processing algorithms. Halide uses simple language constructs to express what to compute and a separate scheduling co-language for expressing when and where to perform the computation. This approach has demonstrated performance comparable to or better than hand-optimized code. Until now, however, Halide has been restricted to parallel shared memory execution, limiting its performance for memory-bandwidth-bound pipelines or large-scale image processing tasks. We present an extension to Halide to support distributed-memory parallel execution of complex stencil pipelines. These extensions compose with the existing scheduling constructs in Halide, allowing expression of complex computation and communication strategies. Existing Halide applications can be distributed with minimal changes, allowing programmers to explore the tradeoff between recomputation and communication with little effort. Approximately 10 new of lines code are needed even for a 200 line, 99 stage application. On nine image processing benchmarks, our extensions give up to a 1.4× speedup on a single node over regular multithreaded execution with the same number of cores, by mitigating the effects of non-uniform memory access. The distributed benchmarks achieve up to 18× speedup on a 16 node testing machine and up to 57× speedup on 64 nodes of the NERSC Cori supercomputer.

97 MATHEMATICS AND COMPUTING↗

NASA NTRS1978

A single user efficiency measure for evaluation of parallel or pipeline computer architectures

A precise statement of the relationship between sequential computation at one rate, parallel or pipeline computation at a much higher rate, the data movement rate between levels of memory, the fraction of inherently sequential operations or data that must be processed sequentially, the fraction of data to be moved that cannot be overlapped with computation, and the relative computational complexity of the algorithms for the two processes, scalar and vector, was developed. The relationship should be applied to the multirate processes that obtain in the employment of various new or proposed computer architectures for computational aerodynamics. The relationship, an efficiency measure that the single user of the computer system perceives, argues strongly in favor of separating scalar and vector processes, sometimes referred to as loosely coupled processes, to achieve optimum use of hardware.

Jones, W. P.↗

NASA NTRS1984

On the impact of communication complexity on the design of parallel numerical algorithms

This paper describes two models of the cost of data movement in parallel numerical alorithms. One model is a generalization of an approach due to Hockney, and is suitable for shared memory multiprocessors where each processor has vector capabilities. The other model is applicable to highly parallel nonshared memory MIMD systems. In this second model, algorithm performance is characterized in terms of the communication network design. Techniques used in VLSI complexity theory are also brought in, and algorithm-independent upper bounds on system performance are derived for several problems that are important to scientific computation.

Gannon, D. B.↗

DOE OSTI2018

Efficient reversible uniform and non-uniform random number generation in UNU.RAN

Reversible random number generations are useful in large-scale fault-tolerant parallel computations and parallel discrete event simulations that are based on reversible computation. The Universal Non-Uniform Random Number Generator (UNU.RAN) is one of the popular random number generators used in the simulation community, but the generators are forward-only in nature. In this paper, we develop new reverse algorithm for the default uniform random number generator algorithm of UNU.RAN and also a few nonuniform random generators that use the Transform Density Reduction (TDR) method. We verify the correctness of reversals of our algorithms and also provide performance results to demonstrate reverse computing runtime adds little overheads relative to its forward counterpart.

Yoginath, Srikanth↗

NASA NTRS1987

Implementation of an ADI method on parallel computers

In this paper the implementation of an ADI method for solving the diffusion equation on three parallel/vector computers is discussed. The computers were chosen so as to encompass a variety of architectures. They are the MPP, an SIMD machine with 16-Kbit serial processors; Flex/32, an MIMD machine with 20 processors; and Cray/2, an MIMD machine with four vector processors. The Gaussian elimination algorithm is used to solve a set of tridiagonal systems on the Flex/32 and Cray/2 while the cyclic elimination algorithm is used to solve these systems on the MPP. The implementation of the method is discussed in relation to these architectures and measures of the performance on each machine are given. Simple performance models are used to describe the performance. These models highlight the bottlenecks and limiting factors for this algorithm on these architectures. Finally conclusions are presented.

Fatoohi, Raad A.↗

DOE OSTI2023

VTK-m: Visualization for the Exascale Era and Beyond

A recent trend in modern high-performance computing is the increasing use of hybrid architectures, where the vast majority of performance comes from accelerators. Modern accelerators are based on Graphics Processing Units (GPU) that contain many low power cores that in their aggregate provides an extremely high computation rate. Current and future CPU processors are requiring more explicit parallelism as each successive version of the hardware packs in more cores, and technologies like hyperthreading and vector operations require even more parallel processing to leverage each core’s full potential. As an example, the Frontier supercomputer installed at Oak Ridge National Laboratories recently hit a record breaking 1.1 exaflops1 on the LINPACK HPC benchmark [Shoemaker 2022]. The system contains 37632 AMD MI250x GPUs which requires more than half a billion threads to keep the system fully utilized [Khizeran 2022].VTK-m is a toolkit of scientific visualization algorithms for these emerging processor architectures. VTK-m supports the fine-grained concurrency for data analysis and visualization algorithms required to drive extreme scale computing by providing abstract models for data and execution that can be applied to a variety of algorithms across many different processor architectures.

Bolstad, Mark↗

DOE OSTI2014

Final Report: Correctness Tools for Petascale Computing

In the course of developing parallel programs for leadership computing systems, subtle programming errors often arise that are extremely difficult to diagnose without tools. To meet this challenge, University of Maryland, the University of Wisconsin—Madison, and Rice University worked to develop lightweight tools to help code developers pinpoint a variety of program correctness errors that plague parallel scientific codes. The aim of this project was to develop software tools that help diagnose program errors including memory leaks, memory access errors, round-off errors, and data races. Research at Rice University focused on developing algorithms and data structures to support efficient monitoring of multithreaded programs for memory access errors and data races. This is a final report about research and development work at Rice University as part of this project.

97 MATHEMATICS AND COMPUTING↗