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 199 records · Page 11
All sourcesNASA NTRSDOE OSTI
NASA NTRS1984

Finite element computation on nearest neighbor connected machines

Research aimed at faster, more cost effective parallel machines and algorithms for improving designer productivity with finite element computations is discussed. A set of 8 boards, containing 4 nearest neighbor connected arrays of commercially available floating point chips and substantial memory, are inserted into a commercially available machine. One-tenth Mflop (64 bit operation) processors provide an 89% efficiency when solving the equations arising in a finite element problem for a single variable regular grid of size 40 by 40 by 40. This is approximately 15 to 20 times faster than a much more expensive machine such as a VAX 11/780 used in double precision. The efficiency falls off as faster or more processors are envisaged because communication times become dominant. A novel successive overrelaxation algorithm which uses cyclic reduction in order to permit data transfer and computation to overlap in time is proposed.

Mcaulay, A. D.↗
NASA NTRS1994

Computationally efficient multibody simulations

Computationally efficient approaches to the solution of the dynamics of multibody systems are presented in this work. The computational efficiency is derived from both the algorithmic and implementational standpoint. Order(n) approaches provide a new formulation of the equations of motion eliminating the assembly and numerical inversion of a system mass matrix as required by conventional algorithms. Computational efficiency is also gained in the implementation phase by the symbolic processing and parallel implementation of these equations. Comparison of this algorithm with existing multibody simulation programs illustrates the increased computational efficiency.

Ramakrishnan, Jayant↗
NASA NTRS2011

Accelerated Adaptive MGS Phase Retrieval

The Modified Gerchberg-Saxton (MGS) algorithm is an image-based wavefront-sensing method that can turn any science instrument focal plane into a wavefront sensor. MGS characterizes optical systems by estimating the wavefront errors in the exit pupil using only intensity images of a star or other point source of light. This innovative implementation of MGS significantly accelerates the MGS phase retrieval algorithm by using stream-processing hardware on conventional graphics cards. Stream processing is a relatively new, yet powerful, paradigm to allow parallel processing of certain applications that apply single instructions to multiple data (SIMD). These stream processors are designed specifically to support large-scale parallel computing on a single graphics chip. Computationally intensive algorithms, such as the Fast Fourier Transform (FFT), are particularly well suited for this computing environment. This high-speed version of MGS exploits commercially available hardware to accomplish the same objective in a fraction of the original time. The exploit involves performing matrix calculations in nVidia graphic cards. The graphical processor unit (GPU) is hardware that is specialized for computationally intensive, highly parallel computation. From the software perspective, a parallel programming model is used, called CUDA, to transparently scale multicore parallelism in hardware. This technology gives computationally intensive applications access to the processing power of the nVidia GPUs through a C/C++ programming interface. The AAMGS (Accelerated Adaptive MGS) software takes advantage of these advanced technologies, to accelerate the optical phase error characterization. With a single PC that contains four nVidia GTX-280 graphic cards, the new implementation can process four images simultaneously to produce a JWST (James Webb Space Telescope) wavefront measurement 60 times faster than the previous code.

Lam, Raymond K.↗
NASA NTRS1990

Parallel Architecture For Robotics Computation

Universal Real-Time Robotic Controller and Simulator (URRCS) is highly parallel computing architecture for control and simulation of robot motion. Result of extensive algorithmic study of different kinematic and dynamic computational problems arising in control and simulation of robot motion. Study led to development of class of efficient parallel algorithms for these problems. Represents algorithmically specialized architecture, in sense capable of exploiting common properties of this class of parallel algorithms. System with both MIMD and SIMD capabilities. Regarded as processor attached to bus of external host processor, as part of bus memory.

Fijany, Amir↗
NASA NTRS1991

Parallel computation of manipulator inverse dynamics

In this article, parallel computation of manipulator inverse dynamics is investigated. A hierarchical graph-based mapping approach is devised to analyze the inherent parallelism in the Newton-Euler formulation at several computational levels, and to derive the features of an abstract architecture for exploitation of parallelism. At each level, a parallel algorithm represents the application of a parallel model of computation that transforms the computation into a graph whose structure defines the features of an abstract architecture, i.e., number of processors, communication structure, etc. Data-flow analysis is employed to derive the time lower bound in the computation as well as the sequencing of the abstract architecture. The features of the target architecture are defined by optimization of the abstract architecture to exploit maximum parallelism while minimizing architectural complexity. An architecture is designed and implemented that is capable of efficient exploitation of parallelism at several computational levels. The computation time of the Newton-Euler formulation for a 6-degree-of-freedom (dof) general manipulator is measured as 187 microsec. The increase in computation time for each additional dof is 23 microsec, which leads to a computation time of less than 500 microsec, even for a 12-dof redundant arm.

Fijany, Amir↗
NASA NTRS1990

Highly parallel sparse Cholesky factorization

Several fine grained parallel algorithms were developed and compared to compute the Cholesky factorization of a sparse matrix. The experimental implementations are on the Connection Machine, a distributed memory SIMD machine whose programming model conceptually supplies one processor per data element. In contrast to special purpose algorithms in which the matrix structure conforms to the connection structure of the machine, the focus is on matrices with arbitrary sparsity structure. The most promising algorithm is one whose inner loop performs several dense factorizations simultaneously on a 2-D grid of processors. Virtually any massively parallel dense factorization algorithm can be used as the key subroutine. The sparse code attains execution rates comparable to those of the dense subroutine. Although at present architectural limitations prevent the dense factorization from realizing its potential efficiency, it is concluded that a regular data parallel architecture can be used efficiently to solve arbitrarily structured sparse problems. A performance model is also presented and it is used to analyze the algorithms.

Gilbert, John R.↗
NASA NTRS1987

Reverse time migration: A seismic processing application on the connection machine

The implementation of a reverse time migration algorithm on the Connection Machine, a massively parallel computer is described. Essential architectural features of this machine as well as programming concepts are presented. The data structures and parallel operations for the implementation of the reverse time migration algorithm are described. The algorithm matches the Connection Machine architecture closely and executes almost at the peak performance of this machine.

Fiebrich, Rolf-Dieter↗
NASA NTRS1990

Parallel homotopy curve tracking on a hypercube

An investigation is conducted to find good parallel algorithms for solving systems of nonlinear equations using probability-one homotopy methods. Particular attention is paid to algorithms for the hypercube. Methods for one of the most computationally expensive steps of the homotopy approach, the computation of the kernel of the Jacobian matrix of the homotopy map, are studied. General nonlinear systems of equations with small and dense Jacobian matrices are considered, however, polynomial systems are not, since their structure leads to different strategies for parallelism. The mathematics behind the homotopy algorithm is summarized and the use of orthogonal factorizations is discussed. Parallel algorithms for orthogonal factorizations and triangular system solving are described. Computational results are presented and discussed.

Chakraborty, A.↗
NASA NTRS1983

Finite element computation with parallel VLSI

This paper describes a parallel processing computer consisting of a 16-bit microcomputer as a master processor which controls and coordinates the activities of 8086/8087 VLSI chip set slave processors working in parallel. The hardware is inexpensive and can be flexibly configured and programmed to perform various functions. This makes it a useful research tool for the development of, and experimentation with parallel mathematical algorithms. Application of the hardware to computational tasks involved in the finite element analysis method is demonstrated by the generation and assembly of beam finite element stiffness matrices. A number of possible schemes for the implementation of N-elements on N- or n-processors (N is greater than n) are described, and the speedup factors of their time consumption are determined as a function of the number of available parallel processors.

Mcgregor, J.↗
NASA NTRS2021

An Efficient and Accurate Algorithm for Computing Grid-Averaged Solar Fluxes for Horizontally Inhomogeneous Clouds

A computationally efficient method is presented to account for the horizontal cloud inhomogeneity by using a radiatively equivalent plane parallel homogeneous (PPH) cloud. The algorithm can accurately match the calculations of the reference (rPPH) independent column approximation (ICA) results, but use only the same computational time required for a single plane parallel computation. The effective optical depth of this synthetic sPPH cloud is derived by exactly matching the direct transmission to that of the inhomogeneous ICA cloud. The ffective9 scattering asymmetry factor is found from a pre-calculated albedo inverse look-up-table that is allowed to vary over the range from -1.0 to 1.0. In the special cases of conservative scattering and total absorption, the synthetic method is exactly equivalent to the ICA, with only a small bias (about 0.2% in flux) relative to ICA due to imperfect interpolation in using the look-up tables. In principle, the ICA albedo can be approximated accurately regardless of cloud inhomogeneity. For a more complete comparison, the broadband shortwave albedo and transmission calculated from the synthetic sPPH cloud and averaged over all incident directions, have the RMS biases of 0.26% and 0.76%, respectively, for inhomogeneous clouds over a wide variation of particle size. The advantages of the synthetic PPH method are that (1) it is not required that all the cloud subcolumns have uniform microphysical characteristic, (2) it is applicable to any 1D radiative transfer scheme, and (3) it can handle arbitrary cloud optical depth distributions and an arbitrary number of cloud subcolumns with uniform computational efficiency.

cloud inhomogeneity↗
NASA NTRS1991

Parallel Methods on Large-Scale Structural Analysis and Physics Applications; Symposium, Hampton, VA, Feb. 5, 6, 1991, Selected Papers

Recent advances in parallel methods and algorithms integrated into large-scale codes are presented. Consideration is given to problem decomposition (substructuring), efficient matrix solution algorithms for shared memory architectures, dynamic and transient analysis algorithms for shared memory architectures, and algorithms for distributed and massively parallel architectures. Particular attention is given to partitioning of unstructured problems for parallel processing, parallel-vector computation for linear-structural analysis and nonlinear unconstraint optimization problems, a parallel-vector equation solver for unsymmetric matrices on supercomputers, parallel nonlinear finite element dynamic response, multigrid algorithms for solving structural mechanics problems on supercomputers, structural analysis on massively parallel computers, explicit finite element methods with contact-impact on SIMD computers, and the impact of mapping and sparsity on parallelized finite element method modules.

Storaasli, Olaf O.↗
DOE OSTI2025

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

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

Layer-parallel↗
NASA NTRS1988

A parallel expert system for the control of a robotic air vehicle

Expert systems can be used to govern the intelligent control of vehicles, for example the Robotic Air Vehicle (RAV). Due to the nature of the RAV system the associated expert system needs to perform in a demanding real-time environment. The use of a parallel processing capability to support the associated expert system's computational requirement is critical in this application. Thus, algorithms for parallel real-time expert systems must be designed, analyzed, and synthesized. The design process incorporates a consideration of the rule-set/face-set size along with representation issues. These issues are looked at in reference to information movement and various inference mechanisms. Also examined is the process involved with transporting the RAV expert system functions from the TI Explorer, where they are implemented in the Automated Reasoning Tool (ART), to the iPSC Hypercube, where the system is synthesized using Concurrent Common LISP (CCLISP). The transformation process for the ART to CCLISP conversion is described. The performance characteristics of the parallel implementation of these expert systems on the iPSC Hypercube are compared to the TI Explorer implementation.

Shakley, Donald↗
NASA NTRS1987

Computational structures for robotic computations

The computational problem of inverse kinematics and inverse dynamics of robot manipulators by taking advantage of parallelism and pipelining architectures is discussed. For the computation of inverse kinematic position solution, a maximum pipelined CORDIC architecture has been designed based on a functional decomposition of the closed-form joint equations. For the inverse dynamics computation, an efficient p-fold parallel algorithm to overcome the recurrence problem of the Newton-Euler equations of motion to achieve the time lower bound of O(log sub 2 n) has also been developed.

Lee, C. S. G.↗
NASA NTRS1988

Parallel matrix multiplication on the Connection Machine

Matrix multiplication is a computation and communication intensive problem. Six parallel algorithms for matrix multiplication on the Connection Machine are presented and compared with respect to their performance and processor usage. For n by n matrices, the algorithms have theoretical running times of O(n to the 2nd power log n), O(n log n), O(n), and O(log n), and require n, n to the 2nd power, n to the 2nd power, and n to the 3rd power processors, respectively. With careful attention to communication patterns, the theoretically predicted runtimes can indeed be achieved in practice. The parallel algorithms illustrate the tradeoffs between performance, communication cost, and processor usage.

Tichy, Walter F.↗
NASA NTRS1990

Photonic processing at NASA Ames Research Center

The Photonic Processing group is engaged in applied research on optical processors in support of the Ames vision to lead the development of autonomous intelligent systems. Optical processors, in conjunction with numeric and symbolic processors, are needed to provide the powerful processing capability that is required for many future agency missions. The research program emphasizes application of analog optical processing, where free-space propagation between components allows natural implementations of algorithms requiring a large degree of parallel computation. Special consideration is given in the Ames program to the integration of optical processors into larger, heterogeneous computational systems. Demonstration of the effective integration of optical processors within a broader knowledge-based system is essential to evaluate their potential for dependable operation in an autonomous environment such as space. The Ames Photonics program is currently addressing several areas of interest. One of the efforts is to develop an optical correlator system with two programmable spatial light modulators (SLMs) to perform distortion invariant pattern recognition. Another area of research is optical neural networks, also for use in distortion-invariant pattern recognition.

Ochoa, Ellen↗
NASA NTRS2013

NASA Tech Briefs, March 2013

Topics covered include: Remote Data Access with IDL Data Compression Algorithm Architecture for Large Depth-of-Field Particle Image Velocimeters Vectorized Rebinning Algorithm for Fast Data Down-Sampling Display Provides Pilots with Real-Time Sonic-Boom Information Onboard Algorithms for Data Prioritization and Summarization of Aerial Imagery Monitoring and Acquisition Real-time System (MARS) Analog Signal Correlating Using an Analog-Based Signal Conditioning Front End Micro-Textured Black Silicon Wick for Silicon Heat Pipe Array Robust Multivariable Optimization and Performance Simulation for ASIC Design; Castable Amorphous Metal Mirrors and Mirror Assemblies; Sandwich Core Heat-Pipe Radiator for Power and Propulsion Systems; Apparatus for Pumping a Fluid; Cobra Fiber-Optic Positioner Upgrade; Improved Wide Operating Temperature Range of Li-Ion Cells; Non-Toxic, Non-Flammable, -80 C Phase Change Materials; Soft-Bake Purification of SWCNTs Produced by Pulsed Laser Vaporization; Improved Cell Culture Method for Growing Contracting Skeletal Muscle Models; Hand-Based Biometric Analysis; The Next Generation of Cold Immersion Dry Suit Design Evolution for Hypothermia Prevention; Integrated Lunar Information Architecture for Decision Support Version 3.0 (ILIADS 3.0); Relay Forward-Link File Management Services (MaROS Phase 2); Two Mechanisms to Avoid Control Conflicts Resulting from Uncoordinated Intent; XTCE GOVSAT Tool Suite 1.0; Determining Temperature Differential to Prevent Hardware Cross-Contamination in a Vacuum Chamber; SequenceL: Automated Parallel Algorithms Derived from CSP-NT Computational Laws; Remote Data Exploration with the Interactive Data Language (IDL); Mixture-Tuned, Clutter Matched Filter for Remote Detection of Subpixel Spectral Signals; Partitioned-Interval Quantum Optical Communications Receiver; and Practical UAV Optical Sensor Bench with Minimal Adjustability.

Source record↗
NASA NTRS2018

Parallel Monotonic Basin Hopping for Low Thrust Trajectory Optimization

Monotonic Basin Hopping has been shown to be an effective method of solving low thrust trajectory optimization problems. This paper outlines an extension to the common serial implementation by parallelizing it over any number of available compute cores. The Parallel Monotonic Basin Hopping algorithm described herein is shown to be an effective way to more quickly locate feasible solutions, and improve locally optimal solutions in an automated way without requiring a feasible initial guess. The increased speed achieved through parallelization enables the algorithm to be applied to more complex problems that would otherwise be impractical for a serial implementation. Low thrust cislunar transfers and a hybrid Mars example case demonstrate the effectiveness of the algorithm. Finally, a preliminary scaling study quantifies the expected decrease in solve time compared to a serial implementation.,

McCarty, Steven L.↗