Search NASA⌕ Search

SEARCH · Search NASA

Results for “data 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 703 records · Page 39
All sourcesNASA NTRSDOE OSTI
NASA NTRS1988

Single-Mode Projection Filters for Modal Parameter Identification for Flexible Structures

Single-mode projection filters are developed for eigensystem parameter identification from both analytical results and test data. Explicit formulations of these projection filters are derived using the orthogonal matrices of the controllability and observability matrices in the general sense. A global minimum optimization algorithm is applied to update the filter parameters by using the interval analysis method. The updated modal parameters represent the characteristics of the test data. For illustration of this new approach, a numerical simulation for the MAST beam structure is shown by using a one-dimensional global optimization algorithm to identify modal frequencies and damping. Another numerical simulation of a ten-mode structure is also presented by using a two-dimensional global optimization algorithm to illustrate the feasibility of the new method. The projection filters are practical for parallel processing implementation.

Huang, Jen-Kuang↗
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 OSTI2020

Distributed Outage Detection in Power Distribution Networks

Real time topology knowledge is essential for situational awareness of power distribution networks. Line outages change the topology of a distribution network. Hence, outage detection is an important task. Most of the existing outage detection algorithms are centralized, in which sensors communicate their data to a control center which performs outage detection using the received data. However, with the increasing size of the distribution network and with different areas of the network being monitored by different operators, communication is a bottleneck and scalability is a major concern. To address these issues, we propose a novel outage detection algorithm using a divide and conquer approach. First, we divide a distribution network into sub-networks, such that outage detection can be run in parallel in each sub-network independently ensuring scalability to large networks. Further, to reduce the latency, bandwidth and attenuation challenges associated with communications in a large network, we divide each sub-network into multiple control areas which communicate only with their neighbors. We employ a distributed iterative load estimation across the control areas of each sub-network and then use the load estimate for local outage detection in each control area. Here, the performance of our algorithm is evaluated for multiple feeder models and compared against traditional centralized outage detection algorithms.

29 ENERGY PLANNING, POLICY, AND ECONOMY↗
NASA NTRS1994

The application of compiler-assisted multiple instruction retry to VLIW architectures

Very Long Instruction Word (VLIW) architectures enhance performance by exploiting fine-grained instruction level parallelism. We describe the development of two compiler assisted multiple instruction word retry schemes for VLIW architectures. The first scheme utilizes the compiler techniques previously developed for processors with single functional units. A compiler generated hazard-free code with different degrees of rollback capability for uniprocessors is compacted by a modified VLIW trace scheduling algorithm. Nops are then inserted in the scheduled code words to resolve data hazards for VLIW architectures. Performance is compared under three parameters: the rollback distance for uni-processors; the number of functional units; and the rollback distance for VLIW architectures. The second scheme employs a hardware read buffer to resolve frequently occurring data hazards, and utilizes the compiler to resolve the remaining hazards. Performance results are shown for six benchmark programs.

Chen, Shyh-Kwei↗
NASA NTRS2009

Multilayer Cloud Detection with the MODIS Near-Infrared Water Vapor Absorption Band

Data Collection 5 processing for the Moderate Resolution Imaging Spectroradiometer (MODIS) onboard the NASA Earth Observing System EOS Terra and Aqua spacecraft includes an algorithm for detecting multilayered clouds in daytime. The main objective of this algorithm is to detect multilayered cloud scenes, specifically optically thin ice cloud overlying a lower-level water cloud, that presents difficulties for retrieving cloud effective radius using single layer plane-parallel cloud models. The algorithm uses the MODIS 0.94 micron water vapor band along with CO2 bands to obtain two above-cloud precipitable water retrievals, the difference of which, in conjunction with additional tests, provides a map of where multilayered clouds might potentially exist. The presence of a multilayered cloud results in a large difference in retrievals of above-cloud properties between the CO2 and the 0.94 micron methods. In this paper the MODIS multilayered cloud algorithm is described, results of using the algorithm over example scenes are shown, and global statistics for multilayered clouds as observed by MODIS are discussed. A theoretical study of the algorithm behavior for simulated multilayered clouds is also given. Results are compared to two other comparable passive imager methods. A set of standard cloudy atmospheric profiles developed during the course of this investigation is also presented. The results lead to the conclusion that the MODIS multilayer cloud detection algorithm has some skill in identifying multilayered clouds with different thermodynamic phases

Wind, Galina↗
NASA NTRS1992

Mapping unstructured grid computations to massively parallel computers

Investigated here is this mapping problem: assign the tasks of a parallel program to the processors of a parallel computer such that the execution time is minimized. First, a taxonomy of objective functions and heuristics used to solve the mapping problem is presented. Next, we develop a highly parallel heuristic mapping algorithm, called Cyclic Pairwise Exchange (CPE), and discuss its place in the taxonomy. CPE uses local pairwise exchanges of processor assignments to iteratively improve an initial mapping. A variety of initial mapping schemes are tested and recursive spectral bipartitioning (RSB) followed by CPE is shown to result in the best mappings. For the test cases studied here, problems arising in computational fluid dynamics and structural mechanics on unstructured triangular and tetrahedral meshes, RSB and CPE outperform methods based on simulated annealing. Much less time is required to do the mapping and the results obtained are better. Compared with random and naive mappings, RSB and CPE reduce the communication time two fold for the test problems used. Finally, we use CPE in two applications on a CM-2. The first application is a data parallel mesh-vertex upwind finite volume scheme for solving the Euler equations on 2-D triangular unstructured meshes. CPE is used to map grid points to processors. The performance of this code is compared with a similar code on a Cray-YMP and an Intel iPSC/860. The second application is parallel sparse matrix-vector multiplication used in the iterative solution of large sparse linear systems of equations. We map rows of the matrix to processors and use an inner-product based matrix-vector multiplication. We demonstrate that this method is an order of magnitude faster than methods based on scan operations for our test cases.

Hammond, Steven Warren↗
DOE OSTI2025

Computing material volume fractions on a superimposed mesh as applied to Monte Carlo particle transport simulations

Here, we present a newly implemented ray tracing algorithm in OpenMC for efficiently computing material volume fractions on superimposed meshes in complex geometries. By firing rays along each coordinate direction through the geometry, the approach accumulates track-length data in each mesh element, thereby determining the fractional composition of each material. Scaling studies on three different models—a random tetrahedra configuration, the Frascati Neutron Generator ITER dose rate benchmark, and a stellarator design—show excellent parallel performance, with nearly linear speedup on modern multi-threaded and distributed-memory systems. An analysis of the residual error relative to high-resolution reference solutions demonstrated that under optimal conditions it decreases as 1/R, where R is the number of rays fired, making it straightforward to achieve user-prescribed accuracy. This new functionality enables practical, mesh-based approaches for detailed nuclear analyses in production Monte Carlo workflows without resorting to expensive, fully conformal or unstructured meshing.

Monte Carlo↗
NASA NTRS1987

Solving very large, sparse linear systems on mesh-connected parallel computers

The implementation of Pan and Reif's Parallel Nested Dissection (PND) algorithm on mesh connected parallel computers is described. This is the first known algorithm that allows very large, sparse linear systems of equations to be solved efficiently in polylog time using a small number of processors. How the processor bound of PND can be matched to the number of processors available on a given parallel computer by slowing down the algorithm by constant factors is described. Also, for the important class of problems where G(A) is a grid graph, a unique memory mapping that reduces the inter-processor communication requirements of PND to those that can be executed on mesh connected parallel machines is detailed. A description of an implementation on the Goodyear Massively Parallel Processor (MPP), located at Goddard is given. Also, a detailed discussion of data mappings and performance issues is given.

Opsahl, Torstein↗
NASA NTRS1986

Application of data flow concepts to a multigrid solver for the Euler equations

In this study a multigrid solver for Euler equations (FLO52R) was examined to determine its performance potential on a hypothetical computer using a data flow architecture. The proposed computer would require massive parallelism to realize its design performance. On the other hand this parallelism would be more easily realized than with a conventional vector processor such as the Cray-1S. Several changes to the proposed design substantially alleviated most of the remaining bottlenecks to parallel processing. Other changes allowed clearer definition of memory access and disk I/O. Finally, a portion of the algorithm was rewritten to improve parallel performance. With these changes, performance levels approaching that of a Cray-1S may be possible for a computer costing far less. Estimates are given for overall speed, memory, and network bandwidth, and for instruction memory requirements.

Merriam, M. L.↗
NASA NTRS1989

Maximum likelihood estimation for distributed parameter models of flexible spacecraft

A distributed-parameter model of the NASA Solar Array Flight Experiment spacecraft structure is constructed on the basis of measurement data and analyzed to generate a priori estimates of modal frequencies and mode shapes. A Newton-Raphson maximum-likelihood algorithm is applied to determine the unknown parameters, using a truncated model for the estimation and the full model for the computation of the higher modes. Numerical results are presented in a series of graphs and briefly discussed, and the significant improvement in computation speed obtained by parallel implementation of the method on a supercomputer is noted.

Taylor, L. W., Jr.↗
NASA NTRS1991

A parallel-pipelined architecture for a multi carrier demodulator

Analog devices have been used for processing the information on board the satellites. Presently, digital devices are being used because they are economical and flexible as compared to their analog counterparts. Several schemes of digital transmission can be used depending on the data rate requirement of the user. An economical scheme of transmission for small earth stations uses single channel per carrier/frequency division multiple access (SCPC/FDMA) on the uplink and time division multiplexing (TDM) on the downlink. This is a typical communication service offered to low data rate users in commercial mass market. These channels usually pertain to either voice or data transmission. An efficient digital demodulator architecture is provided for a large number of law data rate users. A demodulator primarily consists of carrier, clock, and data recovery modules. This design uses principles of parallel processing, pipelining, and time sharing schemes to process large numbers of voice or data channels. It maintains the optimum throughput which is derived from the designed architecture and from the use of high speed components. The design is optimized for reduced power and area requirements. This is essential for satellite applications. The design is also flexible in processing a group of a varying number of channels. The algorithms that are used are verified by the use of a computer aided software engineering (CASE) tool called the Block Oriented System Simulator. The data flow, control circuitry, and interface of the hardware design is simulated in C language. Also, a multiprocessor approach is provided to map, model, and simulate the demodulation algorithms mainly from a speed view point. A hypercude based architecture implementation is provided for such a scheme of operation. The hypercube structure and the demodulation models on hypercubes are simulated in Ada.

Kwatra, S. C.↗
NASA NTRS1990

Solving unstructured grid problems on massively parallel computers

A highly parallel graph mapping technique that enables one to efficiently solve unstructured grid problems on massively parallel computers is presented. Many implicit and explicit methods for solving discretized partial differential equations require each point in the discretization to exchange data with its neighboring points every time step or iteration. The cost of this communication can negate the high performance promised by massively parallel computing. To eliminate this bottleneck, the graph of the irregular problem is mapped into the graph representing the interconnection topology of the computer such that the sum of the distances that the messages travel is minimized. It is shown that using the heuristic mapping algorithm significantly reduces the communication time compared to a naive assignment of processes to processors.

Hammond, Steven W.↗
DOE OSTI2020

TriC: Distributed-memory Triangle Counting by Exploiting the Graph Structure

Graph analytics has emerged as an important tool in the analysis of large scale data from diverse application domains such as social networks, cyber security and bioinformatics. Counting the number of triangles in a graph is a fundamental kernel with several applications such as detecting the community structure of a graph or in identifying important vertices in a graph. The ubiquity of massive datasets is driving the need to scale graph analytics on parallel systems. However, numerous challenges exist in efficiently parallelizing graph algorithms, especially on distributed-memory systems. Irregular memory accesses and communication patterns, low computation to communication ratios, and the need for frequent synchronization are some of the leading challenges. In this paper, we present TriC, our distributed-memory implementation of triangle counting in graphs using the Message Passing Interface (MPI), as a submission to the 2020 GraphChallenge competition. Using a set of synthetic and real-world inputs from the challenge, we demonstrate a speedup of up to 90x relative to previous work on 32 processor-cores of a NERSC Cori node. We also provide details from distributed runs with up to8192 processes along with strong scaling results. The observations presented in this work provide an understanding of the system-level bottlenecks at scale that specifically impact sparse-irregular workloads and will therefore benefit other efforts to parallelize graph algorithms.

Halappanavar, Mahantesh↗
NASA NTRS1992

Cascaded VLSI neural network architecture for on-line learning

High-speed, analog, fully-parallel, and asynchronous building blocks are cascaded for larger sizes and enhanced resolution. A hardware compatible algorithm permits hardware-in-the-loop learning despite limited weight resolution. A computation intensive feature classification application was demonstrated with this flexible hardware and new algorithm at high speed. This result indicates that these building block chips can be embedded as an application specific coprocessor for solving real world problems at extremely high data rates.

Thakoor, Anilkumar P.↗
NASA NTRS1998

Parallel Implicit Algorithms for CFD

The main goal of this project was efficient distributed parallel and workstation cluster implementations of Newton-Krylov-Schwarz (NKS) solvers for implicit Computational Fluid Dynamics (CFD.) "Newton" refers to a quadratically convergent nonlinear iteration using gradient information based on the true residual, "Krylov" to an inner linear iteration that accesses the Jacobian matrix only through highly parallelizable sparse matrix-vector products, and "Schwarz" to a domain decomposition form of preconditioning the inner Krylov iterations with primarily neighbor-only exchange of data between the processors. Prior experience has established that Newton-Krylov methods are competitive solvers in the CFD context and that Krylov-Schwarz methods port well to distributed memory computers. The combination of the techniques into Newton-Krylov-Schwarz was implemented on 2D and 3D unstructured Euler codes on the parallel testbeds that used to be at LaRC and on several other parallel computers operated by other agencies or made available by the vendors. Early implementations were made directly in Massively Parallel Integration (MPI) with parallel solvers we adapted from legacy NASA codes and enhanced for full NKS functionality. Later implementations were made in the framework of the PETSC library from Argonne National Laboratory, which now includes pseudo-transient continuation Newton-Krylov-Schwarz solver capability (as a result of demands we made upon PETSC during our early porting experiences). A secondary project pursued with funding from this contract was parallel implicit solvers in acoustics, specifically in the Helmholtz formulation. A 2D acoustic inverse problem has been solved in parallel within the PETSC framework.

Keyes, David E.↗
DOE OSTI2019

Parallel beamlet dose calculation via beamlet contexts in a distributed multi‐GPU framework

Purpose Dose calculation is one of the most computationally intensive, yet essential tasks in the treatment planning process. With the recent interest in automatic beam orientation and arc trajectory optimization techniques, there is a great need for more efficient model‐based dose calculation algorithms that can accommodate hundreds to thousands of beam candidates at once. Foundational work has shown the translation of dose calculation algorithms to graphical processing units ( GPU s), lending to remarkable gains in processing efficiency. But these methods provide parallelization of dose for only a single beamlet, serializing the calculation of multiple beamlets and under‐utilizing the potential of modern GPU s. In this paper, the authors propose a framework enabling parallel computation of many beamlet doses using a novel beamlet context transformation and further embed this approach in a scalable network of multi‐ GPU computational nodes. Methods The proposed context‐based transformation separates beamlet‐local density and TERMA into distinct beamlet contexts that independently provide sufficient data for beamlet dose calculation. Beamlet contexts are arranged in a composite context array with dosimetric isolation, and the context array is subjected to a GPU collapsed‐cone convolution superposition procedure, producing the set of beamlet‐specific dose distributions in a single pass. Dose from each context is converted to a sparse representation for efficient storage and retrieval during treatment plan optimization. The context radius is a new parameter permitting flexibility between the speed and fidelity of the dose calculation process. A distributed manager‐worker architecture is constructed around the context‐based GPU dose calculation approach supporting an arbitrary number of worker nodes and resident GPU s. Phantom experiments were executed to verify the accuracy of the context‐based approach compared to Monte Carlo and a reference CPU ‐ CCCS implementation for single beamlets and broad beams composed by addition of beamlets. Dose for representative 4 π beam sets was calculated in lung and prostate cases to compare its efficiency with that of an existing beamlet‐sequential GPU ‐ CCCS implementation. Code profiling was also performed to evaluate the scalability of the framework across many networked GPU s. Results The dosimetric accuracy of the context‐based method displays <1.35% and 2.35% average error from the existing serialized CPU ‐ CCCS algorithm and Monte Carlo simulation for beamlet‐specific PDD s in water and slab phantoms, respectively. The context‐based method demonstrates substantial speedup of up to two orders of magnitude over the beamlet‐sequential GPU ‐ CCCS method in the tested configurations. The context‐based framework demonstrates near linear scaling in the number of distributed compute nodes and GPU s employed, indicating that it is flexible enough to meet the performance requirements of most users by simply increasing the hardware utilization. Conclusions The context‐based approach demonstrates a new expectation of performance for beamlet‐based dose calculation methods. This approach has been successful in accelerating the dose calculation process for very large‐scale treatment planning problems ‐ such as automatic 4 π IMRT beam orientation and VMAT arc trajectory selection, with hundreds of thousands of beamlets ‐ in clinically feasible timeframes. The flexibility of this framework makes it as a strong candidate for use in a variety of other very large‐scale treatment planning tasks and clinical workflows.

Neph, Ryan↗
DOE OSTI2024

Integrating machine learning interatomic potentials with hybrid reverse Monte Carlo structure refinements in RMCProfile

Structure refinement with reverse Monte Carlo (RMC) is a powerful tool for interpreting experimental diffraction data. To ensure that the under-constrained RMC algorithm yields reasonable results, the hybrid RMC approach applies interatomic potentials to obtain solutions that are both physically sensible and in agreement with experiment. To expand the range of materials that can be studied with hybrid RMC, we have implemented a new interatomic potential constraint in RMCProfile that grants flexibility to apply potentials supported by the Large-scale Atomic/Molecular Massively Parallel Simulator ( LAMMPS ) molecular dynamics code. This includes machine learning interatomic potentials, which provide a pathway to applying hybrid RMC to materials without currently available interatomic potentials. To this end, we present a methodology to use RMC to train machine learning interatomic potentials for hybrid RMC applications.

Cuillier, Paul↗
DOE OSTI2018

pnnl/SHAD

Scalable High-performance Algorithms and Data-structures. Scalable High-performance Algorithms and Data-structures (SHAD) is an application programming interface based on a generic software library. It has a modular design that enables reuse of modules. The core of this software tool set is built on an Abstract Runtime interface and it's library includes the common data structures such as array, vector, map and set. It is designed to accommodate significant amount of data which can be accessed in massively parallel environments, and used as building blocks for SHAD extensions, i.e. higher level software libraries.

Castellana, Vito↗