SEARCH · Engineering Papers

Results for “distributed 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.

SourceResearch connectionFrom yearThrough year

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

At least 91 records · Page 5

All sources NASA NTRS DOE OSTI

NASA NTRS2007

Integrated Hardware and Software for No-Loss Computing

When an algorithm is distributed across multiple threads executing on many distinct processors, a loss of one of those threads or processors can potentially result in the total loss of all the incremental results up to that point. When implementation is massively hardware distributed, then the probability of a hardware failure during the course of a long execution is potentially high. Traditionally, this problem has been addressed by establishing checkpoints where the current state of some or part of the execution is saved. Then in the event of a failure, this state information can be used to recompute that point in the execution and resume the computation from that point. A serious problem arises when one distributes a problem across multiple threads and physical processors is that one increases the likelihood of the algorithm failing due to no fault of the scientist but as a result of hardware faults coupled with operating system problems. With good reason, scientists expect their computing tools to serve them and not the other way around. What is novel here is a unique combination of hardware and software that reformulates an application into monolithic structure that can be monitored in real-time and dynamically reconfigured in the event of a failure. This unique reformulation of hardware and software will provide advanced aeronautical technologies to meet the challenges of next-generation systems in aviation, for civilian and scientific purposes, in our atmosphere and in atmospheres of other worlds. In particular, with respect to NASA s manned flight to Mars, this technology addresses the critical requirements for improving safety and increasing reliability of manned spacecraft.

James, Mark↗

NASA NTRS1984

Numerical algorithm conjugating steady and transient, separated, compressible flow and a solid body having arbitrarily distributed heat sources

A numerical algorithm that is second-order accurate in time has been developed for the conjugated problem of a separated, compressible flow field and a conductive solid body. The full two-dimensional time-dependent Navier-Stokes equations are coupled with the time-dependent energy equation for the solid body and are solved simultaneously. using implicit algorithms. The energy equation for the solid body may include arbitrarily distributed heat sources. The algorithm has been exmined for the case of two-dimensional supersonic compression-corner interaction, with a heat source embedded in the wall in the vicinity of the separation bubble and the attached boundary layer. The effect of the heat source on the flow field is studied for steady and transient cases.

Degani, D.↗

NASA NTRS2003

An Agent Inspired Reconfigurable Computing Implementation of a Genetic Algorithm

Many software systems have been successfully implemented using an agent paradigm which employs a number of independent entities that communicate with one another to achieve a common goal. The distributed nature of such a paradigm makes it an excellent candidate for use in high speed reconfigurable computing hardware environments such as those present in modem FPGA's. In this paper, a distributed genetic algorithm that can be applied to the agent based reconfigurable hardware model is introduced. The effectiveness of this new algorithm is evaluated by comparing the quality of the solutions found by the new algorithm with those found by traditional genetic algorithms. The performance of a reconfigurable hardware implementation of the new algorithm on an FPGA is compared to traditional single processor implementations.

Weir, John M.↗

NASA NTRS1993

Mapping robust parallel multigrid algorithms to scalable memory architectures

The convergence rate of standard multigrid algorithms degenerates on problems with stretched grids or anisotropic operators. The usual cure for this is the use of line or plane relaxation. However, multigrid algorithms based on line and plane relaxation have limited and awkward parallelism and are quite difficult to map effectively to highly parallel architectures. Newer multigrid algorithms that overcome anisotropy through the use of multiple coarse grids rather than relaxation are better suited to massively parallel architectures because they require only simple point-relaxation smoothers. In this paper, we look at the parallel implementation of a V-cycle multiple semicoarsened grid (MSG) algorithm on distributed-memory architectures such as the Intel iPSC/860 and Paragon computers. The MSG algorithms provide two levels of parallelism: parallelism within the relaxation or interpolation on each grid and across the grids on each multigrid level. Both levels of parallelism must be exploited to map these algorithms effectively to parallel architectures. This paper describes a mapping of an MSG algorithm to distributed-memory architectures that demonstrates how both levels of parallelism can be exploited. The result is a robust and effective multigrid algorithm for distributed-memory machines.

Overman, Andrea↗

NASA NTRS1992

Parallel computational fluid dynamics - Implementations and results

The present volume on parallel CFD discusses implementations on parallel machines, numerical algorithms for parallel CFD, and performance evaluation and computer science issues. Attention is given to a parallel algorithm for compressible flows through rotor-stator combinations, a massively parallel Euler solver for unstructured grids, a fast scheme to analyze 3D disk airflow on a parallel computer, and a block implicit multigrid solution of the Euler equations. Topics addressed include a 3D ADI algorithm on distributed memory multiprocessors, clustered element-by-element computations for fluid flow, hypercube FFT and the Fourier pseudospectral method, and an investigation of parallel iterative algorithms for CFD. Also discussed are fluid dynamics using interface methods on parallel processors, sorting for particle flow simulation on the connection machine, a large grain mapping method, and efforts toward a Teraflops capability for CFD.

Simon, Horst D.↗

NASA NTRS2002

Intelligent Systems for Power Management and Distribution

The motivation behind an advanced technology program to develop intelligent power management and distribution (PMAD) systems is described. The program concentrates on developing digital control and distributed processing algorithms for PMAD components and systems to improve their size, weight, efficiency, and reliability. Specific areas of research in developing intelligent DC-DC converters and distributed switchgear are described. Results from recent development efforts are presented along with expected future benefits to the overall PMAD system performance.

Button, Robert M.↗

NASA NTRS2002

Intelligent Systems for Power Management and Distribution

Button, Robert M.↗

NASA NTRS1982

A generalization of algebraic surface drawing

An implicit surface mathematical description of three-dimensional space is defined in terms of all points which satisfy some equation F(x, y, z) equals 0. This form is ideal for space-shaded picture drawing, where the coordinates are substituted for x and y and the equation is solved for z. A new algorithm is presented which is applicable to functional forms other than those of first- and second-order polynomial functions, such as the summation of several Gaussian density distributions. The algorithm was created in order to model electron density maps of molecular structures, but is shown to be capable of generating shapes of esthetic interest.

Blinn, J. F.↗

NASA NTRS1987

Parallel discrete event simulation: A shared memory approach

With traditional event list techniques, evaluating a detailed discrete event simulation model can often require hours or even days of computation time. Parallel simulation mimics the interacting servers and queues of a real system by assigning each simulated entity to a processor. By eliminating the event list and maintaining only sufficient synchronization to insure causality, parallel simulation can potentially provide speedups that are linear in the number of processors. A set of shared memory experiments is presented using the Chandy-Misra distributed simulation algorithm to simulate networks of queues. Parameters include queueing network topology and routing probabilities, number of processors, and assignment of network nodes to processors. These experiments show that Chandy-Misra distributed simulation is a questionable alternative to sequential simulation of most queueing network models.

Reed, Daniel A.↗

NASA NTRSDate not supplied

Design of Safe Separation Bounds for Temporally Deconflicted Trajectories Under Bounded Uncertainties

This paper explores the derivation of safe separation bounds for a heterogeneous group of~$n$ Uncrewed Aerial Systems (UAS) that are assigned temporally deconflicted trajectories. Compared to spatially deconflicted trajectories, temporal deconfliction can lead to higher traffic capacities and a more efficient use of the available airspace. One challenge with this type of deconfliction is that collisions can occur if some cooperating UAS are behind or ahead of schedule. To overcome this risk, this paper derives a lower bound on the safety distance between two heterogeneous UAS in the presence of bounded uncertainties. This safety distance can be leveraged to inform trajectory generation algorithms. The proposed bound establishes a rigorous safety margin when the fleet deviates from the planned trajectories, both temporally and spatially. For its derivation the paper assumes the UAS implement a distributed coordination algorithm that allows the fleet to maintain their schedules synchronized within a bounded temporal error, and a path-following algorithm that lets the vehicles track a target that moves along the planned trajectory with a bounded spatial error.

autonomy↗

NASA NTRS1990

Execution time support for scientific programs on distributed memory machines

Optimizations are considered that are required for efficient execution of code segments that consists of loops over distributed data structures. The PARTI (Parallel Automated Runtime Toolkit at ICASE) execution time primitives are designed to carry out these optimizations and can be used to implement a wide range of scientific algorithms on distributed memory machines. These primitives allow the user to control array mappings in a way that gives an appearance of shared memory. Computations can be based on a global index set. Primitives are used to carry out gather and scatter operations on distributed arrays. Communications patterns are derived at runtime, and the appropriate send and receive messages are automatically generated.

Berryman, Harry↗

NASA NTRS1993

Mapping robust parallel multigrid algorithms to scalable memory architectures

The convergence rate of standard multigrid algorithms degenerates on problems with stretched grids or anisotropic operators. The usual cure for this is the use of line or plane relaxation. However, multigrid algorithms based on line and plane relaxation have limited and awkward parallelism and are quite difficult to map effectively to highly parallel architectures. Newer multigrid algorithms that overcome anisotropy through the use of multiple coarse grids rather than line relaxation are better suited to massively parallel architectures because they require only simple point-relaxation smoothers. The parallel implementation of a V-cycle multiple semi-coarsened grid (MSG) algorithm or distributed-memory architectures such as the Intel iPSC/860 and Paragon computers is addressed. The MSG algorithms provide two levels of parallelism: parallelism within the relaxation or interpolation on each grid and across the grids on each multigrid level. Both levels of parallelism must be exploited to map these algorithms effectively to parallel architectures. A mapping of an MSG algorithm to distributed-memory architectures that demonstrate how both levels of parallelism can be exploited is described. The results is a robust and effective multigrid algorithm for distributed-memory machines.

Overman, Andrea↗

NASA NTRS2009

Use of Fuzzycones for Sun-Only Attitude Determination: THEMIS Becomes ARTEMIS

In order for two THEMIS probes to successfully transition to ARTEMIS it will be necessary to determine attitudes with moderate accuracy using Sun sensor data only. To accomplish this requirement, an implementation of the Fuzzycones maximum likelihood algorithm was developed. The effect of different measurement uncertainty models on Fuzzycones attitude accuracy was investigated and a bin-transition technique was introduced to improve attitude accuracy using data with uniform error distributions. The algorithm was tested with THEMIS data and in simulations. The analysis results show that the attitude requirements can be met using Fuzzycones and data containing two bin-transitions.

Hashmall, Joseph A.↗

NASA NTRS2018

A Fault-Tolerant Clock Synchronization and Geometry Determination Protocol

A fault-tolerant distributed protocol (algorithm) is presented that achieves optimum timing precision (clock synchronization) among the nodes and, simultaneously, determines the network's geometry (shape) - locations and distances of the nodes relative to each other - in a wireless distributed system. This protocol is based on the assumption of initial coarse synchrony of nodes' local clocks. The proposed solution assumes no prior knowledge of the nodes' locations, the distances between the nodes, or network's geometry, but assumes an ordered geometry where nodes have unique identifiers. This protocol accommodates large variations in the communication latencies among the nodes; thus, it applies equally to both wireless and wired networks.

Malekpour, Mahyar R.↗

NASA NTRS2003

Computation of Domain-Averaged Shortwave Irradiance by a One-Dimensional Algorithm Incorporating Correlations between Optical Thickness and Direct Incident Radiation

A one-dimensional radiative transfer algorithm that accounts for correlations between the optical thickness and the incident direct solar radiation is developed to compute the domain-averaged shortwave irradiance profile. It divides the direct irradiance into four components and treats the direct irradiance in two separate, clear and cloudy columns to account for the fact that clouds attenuate the direct irradiance more than clear-sky. The horizontal inhomogeneity of clouds in the cloudy column is treated by the gamma weighted two-stream approximation, which assumes that the optical thickness of clouds follows a gamma distribution. The algorithm inputs the cloud fraction, cumulative cloud fraction as a function of height, and a parameter expressing the shape of the probability density function of the cloud optical thickness distribution in addition to inputs required for a two-stream radiative transfer model. These cloud property inputs can be obtained using ground- and satellite-based instruments. Therefore, the algorithm can treat realistic cloud overlap features and horizontal inhomogeneity of clouds in a framework of one- dimensional radiative transfer. Heating rates computed by the algorithm using cloud fields generated by cloud resolving models agree with those computed with a Monte Carlo model. If optical properties in computational layers that divide a vertically extensive cloud are correlated, the irradiance profile computed by the algorithm further improves.

Kato, S.↗

NASA NTRS1988

Parallel discrete event simulation using shared memory

With traditional event-list techniques, evaluating a detailed discrete-event simulation-model can often require hours or even days of computation time. By eliminating the event list and maintaining only sufficient synchronization to ensure causality, parallel simulation can potentially provide speedups that are linear in the numbers of processors. A set of shared-memory experiments, using the Chandy-Misra distributed-simulation algorithm, to simulate networks of queues is presented. Parameters of the study include queueing network topology and routing probabilities, number of processors, and assignment of network nodes to processors. These experiments show that Chandy-Misra distributed simulation is a questionable alternative to sequential-simulation of most queueing network models.

Reed, Daniel A.↗

NASA NTRS1984

On Estimating the Phase of Periodic Waveform in Additive Gaussian Noise, Part 2

Motivated by advances in signal processing technology that support more complex algorithms, a new look is taken at the problem of estimating the phase and other parameters of a periodic waveform in additive Gaussian noise. The general problem was introduced and the maximum a posteriori probability criterion with signal space interpretation was used to obtain the structures of optimum and some suboptimum phase estimators for known constant frequency and unknown constant phase with an a priori distribution. Optimal algorithms are obtained for some cases where the frequency is a parameterized function of time with the unknown parameters and phase having a joint a priori distribution. In the last section, the intrinsic and extrinsic geometry of hypersurfaces is introduced to provide insight to the estimation problem for the small noise and large noise cases.

Rauch, L. L.↗

NASA NTRS1992

Simulator for concurrent processing data flow architectures

A software simulator capability of simulating execution of an algorithm graph on a given system under the Algorithm to Architecture Mapping Model (ATAMM) rules is presented. ATAMM is capable of modeling the execution of large-grained algorithms on distributed data flow architectures. Investigating the behavior and determining the performance of an ATAMM based system requires the aid of software tools. The ATAMM Simulator presented is capable of determining the performance of a system without having to build a hardware prototype. Case studies are performed on four algorithms to demonstrate the capabilities of the ATAMM Simulator. Simulated results are shown to be comparable to the experimental results of the Advanced Development Model System.

Malekpour, Mahyar R.↗