Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “parallel algorithms”

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 721 records · Page 40
All sourcesNASA NTRSDOE OSTI
NASA NTRS1989

Parallel Eigenvalue extraction

A new numerical algorithm for the solution of large-order eigenproblems typically encountered in linear elastic finite element systems is presented. The architecture of parallel processing is utilized in the algorithm to achieve increased speed and efficiency of calculations. The algorithm is based on the frontal technique for the solution of linear simultaneous equations and the modified subspace eigenanalysis method for the solution of the eigenproblem. Assembly, elimination and back-substitution of degrees of freedom are performed concurrently, using a number of fronts. All fronts converge to and diverge from a predefined global front during elimination and back-substitution, respectively. In the meantime, reduction of the stiffness and mass matrices required by the modified subspace method can be completed during the convergence/divergence cycle and an estimate of the required eigenpairs obtained. Successive cycles of convergence and divergence are repeated until the desired accuracy of calculations is achieved. The advantages of this new algorithm in parallel computer architecture are discussed.

Akl, Fred A.↗
DOE OSTI2016

Petascale Orbital-Free Density Functional Theory Enabled by Small-Box Algorithms

Orbital-free density functional theory (OFDFT) is a quantum-mechanics-based method that utilizes electron density as its sole variable. The main computational cost in OFDFT is the ubiquitous use of the fast Fourier transform (FFT), which is mainly adopted to evaluate the kinetic energy density functional (KEDF) and electron–electron Coulomb interaction terms. We design and implement a small-box FFT (SBFFT) algorithm to overcome the parallelization limitations of conventional FFT algorithms. We also propose real-space truncation of the nonlocal Wang–Teter KEDF kernel. The scalability of the SBFFT is demonstrated by efficiently simulating one full optimization step (electron density, energies, forces, and stresses) of 1,024,000 lithium (Li) atoms on up to 65,536 cores. We perform other tests using Li as a test material, including calculations of physical properties of different phases of bulk Li, geometry optimizations of nanocrystalline Li, and molecular dynamics simulations of liquid Li. All of the tests yield excellent agreement with the original OFDFT results, suggesting that the OFDFT-SBFFT algorithm opens the door to efficient first-principles simulations of materials containing millions of atoms.

Chemistry↗
DOE OSTI2015

Ion-Stockmayer clusters: Minima, classical thermodynamics, and variational ground state estimates of Li{sup +}(CH{sub 3}NO{sub 2}){sub n} (n = 1–20)

Structural optimizations, classical NVT ensemble, and variational Monte Carlo simulations of ion Stockmayer clusters parameterized to approximate the Li{sup +}(CH{sub 3}NO{sub 2}){sub n} (n = 1–20) systems are performed. The Metropolis algorithm enhanced by the parallel tempering strategy is used to measure internal energies and heat capacities, and a parallel version of the genetic algorithm is employed to obtain the most important minima. The first solvation sheath is octahedral and this feature remains the dominant theme in the structure of clusters with n ≥ 6. The first “magic number” is identified using the adiabatic solvent dissociation energy, and it marks the completion of the second solvation layer for the lithium ion-nitromethane clusters. It corresponds to the n = 18 system, a solvated ion with the first sheath having octahedral symmetry, weakly bound to an eight-membered and a four-membered ring crowning a vertex of the octahedron. Variational Monte Carlo estimates of the adiabatic solvent dissociation energy reveal that quantum effects further enhance the stability of the n = 18 system relative to its neighbors.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2021

Butterfly Factorization Via Randomized Matrix-Vector Multiplications

This paper presents an adaptive randomized algorithm for computing the butterfly factorization of an m × n matrix with m ≈ n provided that both the matrix and its transpose can be rapidly applied to arbitrary vectors. The resulting factorization is composed of O(log n) sparse factors, each containing O(n) nonzero entries. The factorization can be attained using O(n 3/2 log n) computation and O(n log n) memory resources. Furthermore, the proposed algorithm can be implemented in parallel and can apply to matrices with strong or weak admissibility conditions arising from surface integral equation solvers as well as multi-frontal-based finite-difference, finite-element, or finite-volume solvers. A distributed-memory parallel implementation of the algorithm demonstrates excellent scaling behavior.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS2009

Analysis of Aeroheating Augmentation due to Reaction Control System Jets on Orion Crew Exploration Vehicle

The analysis of effects of the reaction control system jet plumes on aftbody heating of Orion entry capsule is presented. The analysis covered hypersonic continuum part of the entry trajectory. Aerothermal environments at flight conditions were evaluated using Langley Aerothermal Upwind Relaxation Algorithm (LAURA) code and Data Parallel Line Relaxation (DPLR) algorithm code. Results show a marked augmentation of aftbody heating due to roll, yaw and aft pitch thrusters. No significant augmentation is expected due to forward pitch thrusters. Of the conditions surveyed the maximum heat rate on the aftshell is expected when firing a pair of roll thrusters at a maximum deceleration condition.

Dyakonov, Artem A.↗
NASA NTRS1983

Parallel solution of finite element equations

The paper examines several parallel processing solution algorithms for finite element equations arising in linear equilibrium problems. Two basic groups of algorithms, direct and iterative, are investigated with respect to a number of parallel computer architectures and associated selection criteria. The direct algorithms include: LR-Gauss, Crout, Cholesky, Cyclic Reduction and WZ-factorization. The iterative methods examined are: Accelerated Gauss-Seidel, Surrogate Stiffness, Jacobi, Series Expansion, and Energy Monte Carlo. For real-time applications, where the object is to minimize the execution time, Cyclic Reduction appears to be best suited. This assumes a computer with an unlimited number of parallel processors. However, for computers with a limited number of parallel processors that must be used efficiently, both Gauss factorization and Jacobi-like iterative methods rank favorably.

Salama, M.↗
DOE OSTI2022

Optimizing the hit finding algorithm for liquid argon TPC neutrino detectors using parallel architectures

Neutrinos are particles that interact rarely, so identifying them requires large detectors which produce lots of data. Processing this data with the computing power available is becoming even more difficult as the detectors increase in size to reach their physics goals. Liquid argon time projection chamber (LArTPC) neutrino experiments are expected to grow in the next decade to have 100 times more wires than in currently operating experiments, and modernization of LArTPC reconstruction code, including parallelization both at data- and instruction-level, will help to mitigate this challenge. The LArTPC hit finding algorithm is used across multiple experiments through a common software framework. In this paper we discuss a parallel implementation of this algorithm. Using a standalone setup we find speedup factors of two times from vectorization and 30–100 times from multi-threading on Intel architectures. The new version has been incorporated back into the framework so that it can be used by experiments. On a serial execution, the integrated version is about 10 times faster than the previous one and, once parallelization is enabled, more speedups comparable to the standalone program are achieved.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗
NASA NTRS1989

Parallel processing environment for multi-flexible body dynamics

The implementation of a dynamics solution algorithm with inherent parallelism which is applicable to the dynamics of large flexible space structures is described. The algorithm is unique in that parts of the solution can be computed simultaneously by working with different branches of its tree topology. The algorithm exhibits close to 0(n) type behavior. The data flow within the solution algorithm is discussed along with results from its implementation in a multiprocessing environment. A model of the United States Space Station is used as an example. The results show that, with fast multiple scalar processors, an efficient algorithm, and symbolically generated equations of motion, real-time performance can be achieved with present-day hardware technology, even with complex dynamical models.

Venugopal, Ravi↗
DOE OSTI2015

Structures of 38-atom gold-platinum nanoalloy clusters

Bimetallic nanoclusters, such as gold-platinum nanoclusters, are nanomaterials promising wide range of applications. We perform a numerical study of 38-atom gold-platinum nanoalloy clusters, Au{sub n}Pt{sub 38−n} (0 ≤ n ≤ 38), to elucidate the geometrical structures of these clusters. The lowest-energy structures of these bimetallic nanoclusters at the semi-empirical level are obtained via a global-minimum search algorithm known as parallel tempering multi-canonical basin hopping plus genetic algorithm (PTMBHGA), in which empirical Gupta many-body potential is used to describe the inter-atomic interactions among the constituent atoms. The structures of gold-platinum nanoalloy clusters are predicted to be core-shell segregated nanoclusters. Gold atoms are observed to preferentially occupy the surface of the clusters, while platinum atoms tend to occupy the core due to the slightly smaller atomic radius of platinum as compared to gold’s. The evolution of the geometrical structure of 38-atom Au-Pt clusters displays striking similarity with that of 38-atom Au-Cu nanoalloy clusters as reported in the literature.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
NASA NTRS1982

Advanced digital SAR processing study

A highly programmable, land based, real time synthetic aperture radar (SAR) processor requiring a processed pixel rate of 2.75 MHz or more in a four look system was designed. Variations in range and azimuth compression, number of looks, range swath, range migration and SR mode were specified. Alternative range and azimuth processing algorithms were examined in conjunction with projected integrated circuit, digital architecture, and software technologies. The advaced digital SAR processor (ADSP) employs an FFT convolver algorithm for both range and azimuth processing in a parallel architecture configuration. Algorithm performace comparisons, design system design, implementation tradeoffs and the results of a supporting survey of integrated circuit and digital architecture technologies are reported. Cost tradeoffs and projections with alternate implementation plans are presented.

Martinson, L. W.↗
NASA NTRS1994

Methodologies and systems for heterogeneous concurrent computing

Heterogeneous concurrent computing is gaining increasing acceptance as an alternative or complementary paradigm to multiprocessor-based parallel processing as well as to conventional supercomputing. While algorithmic and programming aspects of heterogeneous concurrent computing are similar to their parallel processing counterparts, system issues, partitioning and scheduling, and performance aspects are significantly different. In this paper, we discuss critical design and implementation issues in heterogeneous concurrent computing, and describe techniques for enhancing its effectiveness. In particular, we highlight the system level infrastructures that are required, aspects of parallel algorithm development that most affect performance, system capabilities and limitations, and tools and methodologies for effective computing in heterogeneous networked environments. We also present recent developments and experiences in the context of the PVM system and comment on ongoing and future work.

Sunderam, V. S.↗
DOE OSTI2017

Probabilistic Cosmological Mass Mapping from Weak Lensing Shear

We infer gravitational lensing shear and convergence fields from galaxy ellipticity catalogs under a spatial process prior for the lensing potential. We demonstrate the performance of our algorithm with simulated Gaussian-distributed cosmological lensing shear maps and a reconstruction of the mass distribution of the merging galaxy cluster Abell 781 using galaxy ellipticities measured with the Deep Lens Survey. Given interim posterior samples of lensing shear or convergence fields on the sky, we describe an algorithm to infer cosmological parameters via lens field marginalization. In the most general formulation of our algorithm we make no assumptions about weak shear or Gaussian-distributed shape noise or shears. Because we require solutions and matrix determinants of a linear system of dimension that scales with the number of galaxies, we expect our algorithm to require parallel high-performance computing resources for application to ongoing wide field lensing surveys.

79 ASTRONOMY AND ASTROPHYSICS↗
DOE OSTI2015

An efficient tensor transpose algorithm for multicore CPU, Intel Xeon Phi, and NVidia Tesla GPU

An efficient parallel tensor transpose algorithm is suggested for shared-memory computing units, namely, multicore CPU, Intel Xeon Phi, and NVidia GPU. The algorithm operates on dense tensors (multidimensional arrays) and is based on the optimization of cache utilization on x86 CPU and the use of shared memory on NVidia GPU. From the applied side, the ultimate goal is to minimize the overhead encountered in the transformation of tensor contractions into matrix multiplications in computer implementations of advanced methods of quantum many-body theory (e.g., in electronic structure theory and nuclear physics). A particular accent is made on higher-dimensional tensors that typically appear in the so-called multireference correlated methods of electronic structure theory. Depending on tensor dimensionality, the presented optimized algorithms can achieve an order of magnitude speedup on x86 CPUs and 2-3 times speedup on NVidia Tesla K20X GPU with respect to the na ve scattering algorithm (no memory access optimization). Furthermore, the tensor transpose routines developed in this work have been incorporated into a general-purpose tensor algebra library (TAL-SH).

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Performance and Feature Improvements in Parareal-based Power System Dynamic Simulation

In recent years, a novel Parareal-based approach has been developed for fast transient simulations of large power system interconnections. Parareal belongs to the class of Parallel-in-time algorithms for solution of systems of differential-algebraic equations in parallel over an interval of time. The selection of a reasonably fast and accurate coarse solution is crucial to improve the performance of Parareal algorithm. Semi-analytical solution methods are one promising approach to achieve this goal. They have been investigated, and some preliminary results are presented here. In addition, Parareal-based simulator has been expanded to enable co-simulation with OpenDSS, a widely used open-source distribution system simulator. Preserving the parallel nature of the Parareal approach and taking advantage of the parallel capabilities of the latest versions of OpenDSS, each distribution system can be solved in their entirety on different processors in parallel within the main Parareal simulator. This paper also presents the structure of the transmission and distribution co-simulation and some results with different dynamic models of inverter-based resources in the distribution systems.

Park, Byungkwon↗
DOE OSTI2017

Summer Proceedings 2016: The Center for Computing Research at Sandia National Laboratories

Solving sparse linear systems from the discretization of elliptic partial differential equations (PDEs) is an important building block in many engineering applications. Sparse direct solvers can solve general linear systems, but are usually slower and use much more memory than effective iterative solvers. To overcome these two disadvantages, a hierarchical solver (LoRaSp) based on H2-matrices was introduced in [22]. Here, we have developed a parallel version of the algorithm in LoRaSp to solve large sparse matrices on distributed memory machines. On a single processor, the factorization time of our parallel solver scales almost linearly with the problem size for three-dimensional problems, as opposed to the quadratic scalability of many existing sparse direct solvers. Moreover, our solver leads to almost constant numbers of iterations, when used as a preconditioner for Poisson problems. On more than one processor, our algorithm has significant speedups compared to sequential runs. With this parallel algorithm, we are able to solve large problems much faster than many existing packages as demonstrated by the numerical experiments.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2019

Scalable Contour Tree Computation by Data Parallel Peak Pruning

As data sets grow to exascale, automated data analysis and visualization are increasingly important, to intermediate human understanding and to reduce demands on disk storage via in situ analysis. Trends in architecture of high performance computing systems necessitate analysis algorithms to make effective use of combinations of massively multicore and distributed systems. One of the principal analytic tools is the contour tree, which analyses relationships between contours to identify features of more than local importance. Unfortunately, the predominant algorithms for computing the contour tree are explicitly serial, and founded on serial metaphors, which has limited the scalability of this form of analysis. While there is some work on distributed contour tree computation, and separately on hybrid GPU-CPU computation, there is no efficient algorithm with strong formal guarantees on performance allied with fast practical performance. Furthermore, we report the first shared SMP algorithm for fully parallel contour tree computation, with formal guarantees of O(lg V lg t) parallel steps and O(V lg V) work for data with V samples and t contour tree supernodes, and implementations with more than 30× parallel speed up on both CPU using TBB and GPU using Thrust and up 70× speed up compared to the serial sweep and merge algorithm.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS2018

Solution of Ordinary Differential Equations in Gradient-Based Multidisciplinary Design Optimization

A gradient-based approach to multidisciplinary design optimization enables efficient scalability to large numbers of design variables. However, the need for derivatives causes difficulties when integrating ordinary differential equations (ODEs) in models. To simplify this, we propose the use of the general linear methods framework, which unifies all Runge-Kutta and linear multistep methods. This approach enables rapid implementation of integration methods without the need to differentiate each one, even in a gradient-based optimization context. We also develop a new parallel time integration algorithm that enables vectorization across time steps. We present a set of benchmarking results using a stiff ODE, a non-stiff nonlinear ODE, and an orbital dynamics ODE, and compare integration methods. In a modular gradient-based multidisciplinary design optimization context, we find that the new parallel time integration algorithm with high-order implicit methods, especially Gauss-Legendre collocation, is the best choice for a broad range of problems.

Hwang, John T.↗
NASA NTRS1994

Automated Instrumentation, Monitoring and Visualization of PVM Programs Using AIMS

We present views and analysis of the execution of several PVM (Parallel Virtual Machine) codes for Computational Fluid Dynamics on a networks of Sparcstations, including: (1) NAS Parallel Benchmarks CG and MG; (2) a multi-partitioning algorithm for NAS Parallel Benchmark SP; and (3) an overset grid flowsolver. These views and analysis were obtained using our Automated Instrumentation and Monitoring System (AIMS) version 3.0, a toolkit for debugging the performance of PVM programs. We will describe the architecture, operation and application of AIMS. The AIMS toolkit contains: (1) Xinstrument, which can automatically instrument various computational and communication constructs in message-passing parallel programs; (2) Monitor, a library of runtime trace-collection routines; (3) VK (Visual Kernel), an execution-animation tool with source-code clickback; and (4) Tally, a tool for statistical analysis of execution profiles. Currently, Xinstrument can handle C and Fortran 77 programs using PVM 3.2.x; Monitor has been implemented and tested on Sun 4 systems running SunOS 4.1.2; and VK uses XIIR5 and Motif 1.2. Data and views obtained using AIMS clearly illustrate several characteristic features of executing parallel programs on networked workstations: (1) the impact of long message latencies; (2) the impact of multiprogramming overheads and associated load imbalance; (3) cache and virtual-memory effects; and (4) significant skews between workstation clocks. Interestingly, AIMS can compensate for constant skew (zero drift) by calibrating the skew between a parent and its spawned children. In addition, AIMS' skew-compensation algorithm can adjust timestamps in a way that eliminates physically impossible communications (e.g., messages going backwards in time). Our current efforts are directed toward creating new views to explain the observed performance of PVM programs. Some of the features planned for the near future include: (1) ConfigView, showing the physical topology of the virtual machine, inferred using specially formatted IP (Internet Protocol) packets: and (2) LoadView, synchronous animation of PVM-program execution and resource-utilization patterns.

Mehra, Pankaj↗