Search NASA⌕ Search

SEARCH · Search NASA

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.

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

At least 829 records · Page 46

Impacts of floating-point non-associativity on reproducibility for HPC and deep learning applications

Run to run variability in parallel programs caused by floating-point non-associativity has been known to significantly affect reproducibility in iterative algorithms, due to accumulating errors. Non-reproducibility can critically affect the efficiency and effectiveness of correctness testing for stochastic programs. Recently, the sensitivity of deep learning training and inference pipelines to floating-point non-associativity has been found to sometimes be extreme. It can prevent certification for commercial applications, accurate assessment of robustness and sensitivity, and bug detection. New approaches in scientific computing applications have coupled deep learning models with high-performance computing, leading to an aggravation of debugging and testing challenges. Here we perform an investigation of the statistical properties of floating-point non-associativity within modern parallel programming models, and analyze performance and productivity impacts of replacing atomic operations with deterministic alternatives on GPUs. We examine the recently-added deterministic options in PyTorch within the context of GPU deployment for deep learning, uncovering and quantifying the impacts of input parameters triggering run to run variability and reporting on the reliability and completeness of the documentation. Finally, we evaluate the strategy of exploiting automatic determinism that could be provided by deterministic hardware, using the Groq LPUTM accelerator for inference portions of the deep learning pipeline. We demonstrate the benefits that a hardware-based strategy can provide within reproducibility and correctness efforts.

Shanmugavelu, Sanjif↗

Monte Carlo Explicitly Correlated Second-Order Many-Body Green’s Function Calculations of Semiconductor Band Gaps

A systematically converging series of ab initio, post-density-functional, size-consistent, electron-correlated approximations is desired for predictive computing of felectronic band structures of insulating, semiconducting, and metallic solids. A series that meets all of these desiderata (except the applicability to metals) is ab initio many-body Green's function theory based on Gaussian-type-orbital (GTO) basis sets. Here, its leading-order approximation, the second-order Green's function (GF2) method in the diagonal and frequency-independent approximations with the aug-cc-pVDZ basis set, is applied to the fundamental band gaps of three semiconductors (diamond, silicon, and silicon carbide in the zincblende structure) using cluster models. Corrections are made to the basis-set-incompleteness errors by the explicit-correlation (F12) ansatz (GF2-F12) for the valence band edges. The crystals are modeled as surface-passivated clusters of increasing sizes, whose wave functions are expanded by up to 2709 GTO basis functions. Immense computational costs of these calculations are overcome by the highly scalable stochastic algorithm of the Monte Carlo GF2-F12 method, whose operation cost per state increases only as a cubic power of system size, which has a tiny memory footprint and easily achieves near-perfect parallel efficiency on thousands of CPUs or on hundreds of GPUs. The correlated, F12-corrected highest-occupied and lowest-unoccupied molecular-orbital energy (HOMO-LUMO) gap is 5.78 ± 0.07 eV for C 87 H 76 as compared with the experimental value of the fundamental (indirect) band gap of bulk diamond at 5.48 eV. The correlated, F12-corrected HOMO-LUMO gaps for Si 75 H 76 and Si 32 C 43 H 76 are 2.56 ± 0.15 eV and 3.50 ± 0.12 eV, respectively, which are expected to decrease further with increasing cluster sizes. As a result, the experimental fundamental (indirect) band gaps of bulk silicon and silicon carbide are 1.17 eV and 2.42 eV, respectively.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗

Semi-implicit continuum kinetic modeling of weakly collisional parallel transport in a magnetic mirror

We present implicit-explicit (IMEX) kinetic simulations of weakly collisional parallel plasma transport in magnetic mirror configurations using the continuum code COGENT. The numerical scheme employs a Jacobian-free Newton–Krylov method with algebraic multigrid preconditioning to overcome the severe time step limitations imposed by strong mirror forces in fully explicit schemes. Applied to parameters relevant to the Wisconsin HTS Axisymmetric Mirror experiment, the IMEX approach enables time steps up to 2.5×10 4 times larger than those permitted by explicit methods, resulting in a 2500× speedup in 1D–2V simulations of parallel transport with kinetic ions and Boltzmann electrons. Additionally, a reduced bounce-averaged model for a square mirror is implemented to support the computationally intensive fully kinetic simulations. The bounce-averaged formulation is used to evaluate the numerical convergence of the velocity-space discretization algorithms and to assess the role of the collision model by comparing simulations employing the nonlinear Fokker–Planck and the simplified Lenard–Bernstein–Dougherty collision operators.

Collision theories↗

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

This paper describes two models of the cost of data movement in parallel numerical algorithms. 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 the 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.↗

Automated matching of pairs of SIR-B images for elevation mapping

During the SIR-B mission in October 1984, a significant number of overlapping synthetic aperture radar (SAR) images of various ground areas was collected. This has offered the first opportunity to perform stereo analyses on images from space that cover large ground areas to determine elevation information. This paper presents the preliminary results of an investigation to obtain elevation data from stereo pairs of SIR-B images. First, the accuracy with which elevation information can be derived from SIR-B image pairs is evaluated theoretically. It is shown that elevation accuracy is a function of the slant range resolution, the incidence angles with which the stereo pair is obtained, the accuracies in spacecraft state estimation, and determination of corresponding pixels in the stereo pair. Next, a hierarchical method is developed to match the corresponding pixels. This method involves iterative removal of local distortions and correlations of pairs of local neighborhoods in the two images. Since it is necessary to perform the matching at every pixel in the image, it is very computationally intensive. Therefore, it has been implemented on the Massively Parallel Processor (MPP) at the Goddard Space Flight Center (GSFC). The MPP's speed permits two iterations of this technique to operate on a pair of 512 x 512 images within 7 s. Results of applying this algorithm of SIR-B images of Mount Shasta, CA, are shown. The matching algorithm performs well in regions of the image with significant features. An approximate elevation image derived from the matching process corresponds to published topographic map data, except for certain obvious discontinuities.

Ramapriyan, H. K.↗

A system for routing arbitrary directed graphs on SIMD architectures

There are many problems which can be described in terms of directed graphs that contain a large number of vertices where simple computations occur using data from connecting vertices. A method is given for parallelizing such problems on an SIMD machine model that is bit-serial and uses only nearest neighbor connections for communication. Each vertex of the graph will be assigned to a processor in the machine. Algorithms are given that will be used to implement movement of data along the arcs of the graph. This architecture and algorithms define a system that is relatively simple to build and can do graph processing. All arcs can be transversed in parallel in time O(T), where T is empirically proportional to the diameter of the interconnection network times the average degree of the graph. Modifying or adding a new arc takes the same time as parallel traversal.

Tomboulian, Sherryl↗

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.↗

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.↗

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↗

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.↗

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.↗

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.↗

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.↗

Automatic Generation of Algorithms for High-Speed Reliable Lossy Data Compression (Final Report)

Fast reliable data compression is urgently needed for many leading-edge scientific instruments and for exascale high-performance computing applications because they produce vast amounts of data at extremely high rates. The goal of this project has been to develop a framework named LC that is able to automatically generate high-speed lossless and reliable lossy compression and decompression algorithms that can be customized for different kinds of data. The resulting LC framework is freely available on GitHub. To achieve high-speed operation, LC outputs optimized and parallelized CPU and GPU implementations of the generated algorithms. To ensure the quality of lossily compressed data, LC guarantees the user-provided error bound. To be able to customize the compression algorithm to various use cases, LC can synthesize millions of different algorithms and automatically search for the one that works best for the given data. We have already employed LC to create state-of-the-art lossless and lossy compressors for scientific data as well as leading lossless compressors for images. We hope that LC and the customized, fast, reliable, and CPU/GPU-compatible compression algorithms that it can generate will greatly benefit the many scientific applications that need not only high trustworthiness but also high performance.

97 MATHEMATICS AND COMPUTING↗

Particle simulation in a multiprocessor environment

A parallel implementation of a particle simulation method that is portable between a wide class of multiprocessor computers is presented. A fine grain spatial decomposition is utilized where several subdomains having a regular structure are computed at each processing node. This leads directly to an efficient and straightforward load balancing scheme if the number of subdomains at each processor is permitted to vary in an appropriate manner. Three dimensional simulations incorporating full thermochemical nonequilibrium are possible using the resulting code. Vectorizable algorithms are retained from earlier work allowing efficient use of deeply pipelined node processors where available. Performance results are presented from three different machine architectures demonstrating the portability of the code. On a 128-node Intel iPSC/860, performance is twice that of a single Cray-Y/MP CPU running a highly vectorized simulation code. Speedup is linear over the full range of number of processors on all target machines, indicating scalability of the method to higher degrees of parallelism.

Mcdonald, Jeffrey D.↗

Equilipy: a python package for calculating phase equilibria

The CALPHAD (CALculation of PHAse Diagram) approach (Nigel Saunders & Miodownik, 1998) provides predictions for thermodynamically stable phases in multicomponent-multiphase materials across a wide range of temperatures. Consequently, the CALPHAD calculations became an essential tool in materials and process design (Luo, 2015). Such design tasks frequently require navigating a high-dimensional space due to multiple components involved in the system. This increasing complexity demands high-throughput CALPHAD calculations, especially in the rapidly evolving field of alloy design. In response to the need, we developed Equilipy an open-source Python package designed for calculating phase equilibria of multicomponent-multiphase systems. Equilipy is specifically tailored for high-throughput CALPHAD calculations, offering parallel computations across multiple processors and nodes with the given NPT input conditions namely elemental compositions (N), pressure (P), and temperature (T). Equilipy utilizes the program structure and Gibbs energy functions from the Fortran-based program, Thermochimica (Piro et al., 2013), with incorporating a new Gibbs energy minimization algorithm. This algorithm, originally developed by Capitani and Brown in 1987 (Capitani & Brown, 1987), has been revised and implemented to enhance the stability and performance of calculations. The Fortran codes are precompiled and interfaced with Python via F2PY, ensuring high computation speed. Benchmark tests shown in Figure 1 demonstrate that Equilipy’s computation speed is comparable to those of established commercial software, TC-Python and PanPython. This result highlights its efficiency and potential applications in various scientific and industrial fields.

97 MATHEMATICS AND COMPUTING↗

Systematic generation of multibody equations of motion suitable for recursive and parallel manipulation

The formulation of a method known as the joint coordinate method for automatic generation of the equations of motion for multibody systems is summarized. For systems containing open or closed kinematic loops, the equations of motion can be reduced systematically to a minimum number of second order differential equations. The application of recursive and nonrecursive algorithms to this formulation, computational considerations and the feasibility of implementing this formulation on multiprocessor computers are discussed.

Nikravesh, Parviz E.↗

A single-assignment language in a distributed memory multiprocessor

The implementation of the single-assignment programming language SISAL (McGraw et al., 1985) on a Symult 2010 parallel computer is described. The advantages of single-assignment languages over imperative languages in a multiprocessor environment are reviewed; the characteristics of SISAL are summarized; the program-graph generation and dynamic data partitioning procedures are explained; and the application of SISAL in constructing a concurrent iterative multigrid algorithm is discussed in detail and illustrated with diagrams.

Evripidou, P.↗