SEARCH · Search NASA

Results for “Parallel algorithm”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

SourceResearch connectionFrom yearThrough year

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

At least 1,279 records · Page 71

All sources NASA NTRS DOE OSTI

NASA NTRS1984

Research in applied mathematics, numerical analysis, and computer science

Research conducted at the Institute for Computer Applications in Science and Engineering (ICASE) in applied mathematics, numerical analysis, and computer science is summarized and abstracts of published reports are presented. The major categories of the ICASE research program are: (1) numerical methods, with particular emphasis on the development and analysis of basic numerical algorithms; (2) control and parameter identification; (3) computational problems in engineering and the physical sciences, particularly fluid dynamics, acoustics, and structural analysis; and (4) computer systems and software, especially vector and parallel computers.

Source record↗

NASA NTRS1985

Iterative solution of large, sparse linear systems on a static data flow architecture - Performance studies

The applicability of static data flow architectures to the iterative solution of sparse linear systems of equations is investigated. An analytic performance model of a static data flow computation is developed. This model includes both spatial parallelism, concurrent execution in multiple PE's, and pipelining, the streaming of data from array memories through the PE's. The performance model is used to analyze a row partitioned iterative algorithm for solving sparse linear systems of algebraic equations. Based on this analysis, design parameters for the static data flow architecture as a function of matrix sparsity and dimension are proposed.

Reed, D. A.↗

NASA NTRS1988

Material parameter measurements at high temperatures

Alternate fixtures of techniques for the measurement of the constitutive material parameters at elevated temperatures are presented. The technique utilizes scattered field data from material coated cylinders between parallel plates or material coated hemispheres over a finite size groundplane. The data acquisition is centered around the HP 8510B Network Analyzer. The parameters are then found from a numerical search algorithm using the Newton-Ralphson technique with the measured and calculated fields from these canonical scatters. Numerical and experimental results are shown.

Dominek, A.↗

NASA NTRS1989

Investigation of the applicability of a functional programming model to fault-tolerant parallel processing for knowledge-based systems

In a fault-tolerant parallel computer, a functional programming model can facilitate distributed checkpointing, error recovery, load balancing, and graceful degradation. Such a model has been implemented on the Draper Fault-Tolerant Parallel Processor (FTPP). When used in conjunction with the FTPP's fault detection and masking capabilities, this implementation results in a graceful degradation of system performance after faults. Three graceful degradation algorithms have been implemented and are presented. A user interface has been implemented which requires minimal cognitive overhead by the application programmer, masking such complexities as the system's redundancy, distributed nature, variable complement of processing resources, load balancing, fault occurrence and recovery. This user interface is described and its use demonstrated. The applicability of the functional programming style to the Activation Framework, a paradigm for intelligent systems, is then briefly described.

Harper, Richard↗

NASA NTRS1999

Dynamic Load Balancing for Adaptive Computations on Distributed-Memory Machines

Dynamic load balancing is central to adaptive mesh-based computations on large-scale parallel computers. The principal investigator has investigated various issues on the dynamic load balancing problem under NASA JOVE and JAG rants. The major accomplishments of the project are two graph partitioning algorithms and a load balancing framework. The S-HARP dynamic graph partitioner is known to be the fastest among the known dynamic graph partitioners to date. It can partition a graph of over 100,000 vertices in 0.25 seconds on a 64- processor Cray T3E distributed-memory multiprocessor while maintaining the scalability of over 16-fold speedup. Other known and widely used dynamic graph partitioners take over a second or two while giving low scalability of a few fold speedup on 64 processors. These results have been published in journals and peer-reviewed flagship conferences.

Source record↗

NASA NTRS2000

Optimization of Microelectronic Devices for Sensor Applications

The NASA/JPL goal to reduce payload in future space missions while increasing mission capability demands miniaturization of active and passive sensors, analytical instruments and communication systems among others. Currently, typical system requirements include the detection of particular spectral lines, associated data processing, and communication of the acquired data to other systems. Advances in lithography and deposition methods result in more advanced devices for space application, while the sub-micron resolution currently available opens a vast design space. Though an experimental exploration of this widening design space-searching for optimized performance by repeated fabrication efforts-is unfeasible, it does motivate the development of reliable software design tools. These tools necessitate models based on fundamental physics and mathematics of the device to accurately model effects such as diffraction and scattering in opto-electronic devices, or bandstructure and scattering in heterostructure devices. The software tools must have convenient turn-around times and interfaces that allow effective usage. The first issue is addressed by the application of high-performance computers and the second by the development of graphical user interfaces driven by properly developed data structures. These tools can then be integrated into an optimization environment, and with the available memory capacity and computational speed of high performance parallel platforms, simulation of optimized components can proceed. In this paper, specific applications of the electromagnetic modeling of infrared filtering, as well as heterostructure device design will be presented using genetic algorithm global optimization methods.

Cwik, Tom↗

NASA NTRS2006

Exploiting Quantum Resonance to Solve Combinatorial Problems

Quantum resonance would be exploited in a proposed quantum-computing approach to the solution of combinatorial optimization problems. In quantum computing in general, one takes advantage of the fact that an algorithm cannot be decoupled from the physical effects available to implement it. Prior approaches to quantum computing have involved exploitation of only a subset of known quantum physical effects, notably including parallelism and entanglement, but not including resonance. In the proposed approach, one would utilize the combinatorial properties of tensor-product decomposability of unitary evolution of many-particle quantum systems for physically simulating solutions to NP-complete problems (a class of problems that are intractable with respect to classical methods of computation). In this approach, reinforcement and selection of a desired solution would be executed by means of quantum resonance. Classes of NP-complete problems that are important in practice and could be solved by the proposed approach include planning, scheduling, search, and optimal design.

Zak, Michail↗

NASA NTRS2013

Comparison of Simulated Contrast Performance of Different Phase Induced Amplitude Apodization (PIAA) Coronagraph Configurations

We compare the broadband contrast performances of several Phase Induced Amplitude Apodization (PIAA) coronagraph configurations through modeling and simulations. The basic optical design of the PIAA coronagraph is the same as NASA's High Contrast Imaging Testbed (HCIT) setup at the Jet Propulsion Laboratory (JPL). Using a deformable mirror and a broadband wavefront sensing and control algorithm, we create a "dark hole" in the broadband point-spread function (PSF) with an inner working angle (IWA) of 2(f lambda/D)(sub sky). We evaluate two systems in parallel. One is a perfect system having a design PIAA output amplitude and not having any wavefront error at its exit-pupil. The other is a realistic system having a design PIAA output amplitude and the measured residual wavefront error. We also investigate the effect of Lyot stops of various sizes when a postapodizer is and is not present. Our simulations show that the best 7.5%-broadband contrast value achievable with the current PIAA coronagraph is approximately 1.5x10(exp -8).

adaptive optics↗

NASA NTRS2017

Structure Assembly by a Heterogeneous Team of Robots Using State Estimation, Generalized Joints, and Mobile Parallel Manipulators

Autonomous robotic assembly by mobile field robots has seen significant advances in recent decades, yet practicality remains elusive. Identified challenges include better use of state estimation to and reasoning with uncertainty, spreading out tasks to specialized robots, and implementing representative joining methods. This paper proposes replacing 1) self-correcting mechanical linkages with generalized joints for improved applicability, 2) assembly serial manipulators with parallel manipulators for higher precision and stability, and 3) all-in-one robots with a heterogeneous team of specialized robots for agent simplicity. This paper then describes a general assembly algorithm utilizing state estimation. Finally, these concepts are tested in the context of solar array assembly, requiring a team of robots to assemble, bond, and deploy a set of solar panel mockups to a backbone truss to an accuracy not built into the parts. This paper presents the results of these tests.

Komendera, Erik E.↗

NASA NTRS2025

Efficient GPU-Accelerated MultiSource Global Fit Pipeline for LISA Data Analysis

The large-scale analysis task of deciphering gravitational-wave signals in the LISA data stream will be difficult, requiring a large amount of computational resources and extensive development of computational methods. Its high dimensionality, multiple model types, and complicated noise profile require a global fit to all parameters and input models simultaneously. In this work, we detail our global fit algorithm, called “Erebor,” designed to accomplish this challenging task. It is capable of analyzing current state-of-the-art datasets and then growing into the future as more pieces of the pipeline are completed and added. We describe our pipeline strategy, the algorithmic setup, and the results from our analysis of the LDC2A Sangria dataset, which contains massive black hole binaries, compact galactic binaries, and a parametrized noise spectrum whose parameters are unknown to the user. The Erebor algorithm includes three unique and very useful contributions: GPU acceleration for enhanced computational efficiency; ensemble Markov Chain Monte Carlo (MCMC) sampling with multiple MCMC walkers per temperature for better mixing and parallelized sample creation; and special online updates to reversible-jump (or transdimensional) sampling distributions to ensure sampler mixing and accurate initial estimates for detectable sources in the data.We recover posterior distributions for all 15 (6) of the injected massive black hole binaries (MBHB) in the LDC2A training (hidden) dataset. We catalog ∼12000 galactic binaries (∼8000 as high confidence detections) for both the training and hidden datasets. All of the sources and their posterior distributions are provided in publicly available catalogs.

LISA↗

NASA NTRSDate not supplied

A Parallelized Oxidation-Driven Surface Recession Framework in DSMC Code, SPARTA

Spacecrafts rely on ablative thermal protection systems (TPS) made of composites consisting of a carbon-based reinforcement and a polymeric matrix. These materials are designed to withstand high-temperature oxidation and surface recession during re-entry into the Earth's atmosphere. However, ablation occurs due to a complex interplay of thermal, mechanical, and chemical factors, making it challenging to determine the individual impact of each on the TPS's overall degradation. In this study, we have developed an ablation model that can leverage a finite rate carbon oxidation model to predict material recession and surface states more accurately. Stochastic PArallel Rarified-gas Time-accurate Analyzer (SPARTA), a direct-simulation Monte Carlo (DSMC) code, is modified to allow oxidation-driven ablation of implicitly defined carbon surfaces. In SPARTA, implicit surfaces are generated from the grid corner point values via a marching cubes algorithm, therefore creating a new set of surface elements every time ablation is performed. The finite-rate oxidation model developed by Gopalan et. al can perform both gas-surface and pure-surface reactions and is now adapted to tally surface data on a per grid cell basis. The ablation functionality was also adjusted so once the reactions have occurred, the number of reactions leading to CO formation can be converted to corner point reduction values; therefore, carbon removal is directly proportional to surface recession. We also briefly discuss some unique challenges associated with parallelizing this dynamic surface state and geometry. Finally, we analyze the performance of this parallelized implicit chemistry model with simple 2D and 3D benchmark cases by producing surface state statistics, area changes over time, and visualization across a range of surface temperatures and processors with and without load-balancing.

DSMC↗

NASA NTRS1994

A Navier-Strokes Chimera Code on the Connection Machine CM-5: Design and Performance

We have implemented a three-dimensional compressible Navier-Stokes code on the Connection Machine CM-5. The code is set up for implicit time-stepping on single or multiple structured grids. For multiple grids and geometrically complex problems, we follow the 'chimera' approach, where flow data on one zone is interpolated onto another in the region of overlap. We will describe our design philosophy and give some timing results for the current code. A parallel machine like the CM-5 is well-suited for finite-difference methods on structured grids. The regular pattern of connections of a structured mesh maps well onto the architecture of the machine. So the first design choice, finite differences on a structured mesh, is natural. We use centered differences in space, with added artificial dissipation terms. When numerically solving the Navier-Stokes equations, there are liable to be some mesh cells near a solid body that are small in at least one direction. This mesh cell geometry can impose a very severe CFL (Courant-Friedrichs-Lewy) condition on the time step for explicit time-stepping methods. Thus, though explicit time-stepping is well-suited to the architecture of the machine, we have adopted implicit time-stepping. We have further taken the approximate factorization approach. This creates the need to solve large banded linear systems and creates the first possible barrier to an efficient algorithm. To overcome this first possible barrier we have considered two options. The first is just to solve the banded linear systems with data spread over the whole machine, using whatever fast method is available. This option is adequate for solving scalar tridiagonal systems, but for scalar pentadiagonal or block tridiagonal systems it is somewhat slower than desired. The second option is to 'transpose' the flow and geometry variables as part of the time-stepping process: Start with x-lines of data in-processor. Form explicit terms in x, then transpose so y-lines of data are in-processor. Form explicit terms in y, then transpose so z-lines are in processor. Form explicit terms in z, then solve linear systems in the z-direction. Transpose to the y-direction, then solve linear systems in the y-direction. Finally transpose to the x direction and solve linear systems in the x-direction. This strategy avoids inter-processor communication when differencing and solving linear systems, but requires a large amount of communication when doing the transposes. The transpose method is more efficient than the non-transpose strategy when dealing with scalar pentadiagonal or block tridiagonal systems. For handling geometrically complex problems the chimera strategy was adopted. For multiple zone cases we compute on each zone sequentially (using the whole parallel machine), then send the chimera interpolation data to a distributed data structure (array) laid out over the whole machine. This information transfer implies an irregular communication pattern, and is the second possible barrier to an efficient algorithm. We have implemented these ideas on the CM-5 using CMF (Connection Machine Fortran), a data parallel language which combines elements of Fortran 90 and certain extensions, and which bears a strong similarity to High Performance Fortran. We make use of the Connection Machine Scientific Software Library (CMSSL) for the linear solver and array transpose operations.

Jespersen, Dennis C.↗

DOE OSTI2025

Ensemble Simulation Techniques and Fast Randomized Algorithms

The major goals of the project were to develop and analyze new ensemble simulation techniques, including trajectory stratification and preconditioned MCMC techniques, as well as develop fast numerical linear algebra techniques closely related to ensemble simulation ideas. The trajectory stratification techniques involve simulating in parallel short trajectory fragments of a Markov process confined to a specific region of space‐time and then patching together the statistics gathered to assemble estimates of very general dynamical properties. We have also developed this approach for rare event simulation and extended the techniques to applications requiring a more general framework (such as electronic structure calculations). The preconditioned MCMC techniques involve simulating multiple Markov chains in parallel and then using information from the ensemble to speed the mixing of each individual chain. The fast randomized linear algebra methods are motivated by the diffusion Monte Carlo technique, but are applicable to finding the dominant eigenvalue of (almost) general matrices. For most non‐negative matrices, the schemes result in an error (compared to the power method) that is constant in the dimension of the problem. For more general matrices, we see a very clear sublinear cost trend in computational tests.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗

DOE OSTI2025

Priority-BF: A Task Manager for Priority-Based Scheduling

The increasing demand for computational resources, particularly in High-Performance Computing environments, necessitates to rethink how we handle job scheduling strategies. This work addresses the challenge of managing concurrent jobs with differing priorities on overloaded parallel systems, where strict QoS constraints are often difficult for users to define. Our solution relies on a qualitative description of priorities and pulls from two key approaches: the Easy-BF algorithm and the Conservative Backfilling algorithms. This solution improves the response time for high-priority jobs by 50% without affecting the overall system utilization. We show its applicability in several critical scenarios such as High-Performance Computing (HPC) resource management and in-situ computing.

Gainaru, Ana [ORNL]↗

NASA NTRS1980

A polymorphic reconfigurable emulator for parallel simulation

Microprocessor and arithmetic support chip technology was applied to the design of a reconfigurable emulator for real time flight simulation. The system developed consists of master control system to perform all man machine interactions and to configure the hardware to emulate a given aircraft, and numerous slave compute modules (SCM) which comprise the parallel computational units. It is shown that all parts of the state equations can be worked on simultaneously but that the algebraic equations cannot (unless they are slowly varying). Attempts to obtain algorithms that will allow parellel updates are reported. The word length and step size to be used in the SCM's is determined and the architecture of the hardware and software is described.

Parrish, E. A., Jr.↗

NASA NTRS1990

Electronic Neural Networks

Viewgraphs on electronic neural networks for space station are presented. Topics covered include: electronic neural networks; electronic implementations; VLSI/thin film hybrid hardware for neurocomputing; computations with analog parallel processing; features of neuroprocessors; applications of neuroprocessors; neural network hardware for terrain trafficability determination; a dedicated processor for path planning; neural network system interface; neural network for robotic control; error backpropagation algorithm for learning; resource allocation matrix; global optimization neuroprocessor; and electrically programmable read only thin-film synaptic array.

Thakoor, Anil↗

NASA NTRS1992

Adding dynamic rules to self-organizing fuzzy systems

This paper develops a Dynamic Self-Organizing Fuzzy System (DSOFS) capable of adding, removing, and/or adapting the fuzzy rules and the fuzzy reference sets. The DSOFS background consists of a self-organizing neural structure with neuron relocation features which will develop a map of the input-output behavior. The relocation algorithm extends the topological ordering concept. Fuzzy rules (neurons) are dynamically added or released while the neural structure learns the pattern. The DSOFS advantages are the automatic synthesis and the possibility of parallel implementation. A high adaptation speed and a reduced number of neurons is needed in order to keep errors under some limits. The computer simulation results are presented in a nonlinear systems modelling application.

Buhusi, Catalin V.↗

NASA NTRS2007

Simulation of a Periodic Jet in a Crossflow with a RANS Solver Using an Unstructured Grid

A second-order unstructured-grid code, developed and used primarily for steady aerodynamic simulations, is applied to the synthetic jet in a cross flow. The code, FUN3D, is a vertex-centered finite-volume method originally developed by Anderson[1, 2], and is currently supported by members of the Fast Adaptive Aerospace Tools team at NASA Langley. Used primarily for design[3] and analysis[4] of steady aerodynamic configurations, FUN3D incorporates a discrete adjoint capability, and supports parallel computations using MPI. A detailed description of the FUN3D code can be found in the references given above. The code is under continuous development and contains a variety of flux splitting algorithms for the inviscid terms, two methods for computing gradients, several turbulence models, and several solution methodologies; all in varying states of development. Only the most robust and reliable components, based on experiences with steady aerodynamic simulations, were employed in this work. As applied in this work, FUN3D solves the Reynolds averaged Navier-Stokes equations using the one equation turbulence model of Spalart and Allmaras[5]. The spatial discretization is formed on unstructured meshes using a vertex-centered approach. The inviscid terms are evaluated by a flux-difference splitting formulation using least-squares reconstruction and Roe-type approximate Riemann fluxes. Green-Gauss gradient evaluations are used for viscous and turbulence modeling terms. The discrete spatial operator is combined with a backward time operator which is then solved iteratively using point or line Gauss-Seidel and local time stepping in a pseudo time. For steady flows, the physical time step is set to infinity and the pseudo time step is ramped up with the iteration count. A second-order backward in time operator is used for time accurate flows with 20 to 50 steps in the pseudo time applied at each physical time step. For this effort, FUN3D was modified to support spatially varying boundary and initial conditions, and unsteady boundary conditions. Also, a specialized in/out flow boundary condition was implemented to model the action of the diaphragm. This boundary condition is described below in more detail. The grids were generated using the internally developed codes GridEX[6] for meshing the surfaces and inviscid regions of the domain, and for CAD access; and MesherX[7] for meshing the viscous regions. Grid spacing in on the surfaces and in the inviscid regions are indirectly controlled by specifying sources. The viscous layers are generated using an advancing layer technique. MeshersX allows the user to control the spatial variation of the first step off the surface, growth rates, and the termination criterion by providing small problem dependent subroutines.

Atkins, H. L.↗