SEARCH · Engineering Papers

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,369 records · Page 76

All sources NASA NTRS DOE OSTI

NASA NTRS1987

Mapping a battlefield simulation onto message-passing parallel architectures

Perhaps the most critical problem in distributed simulation is that of mapping: without an effective mapping of workload to processors the speedup potential of parallel processing cannot be realized. Mapping a simulation onto a message-passing architecture is especially difficult when the computational workload dynamically changes as a function of time and space; this is exactly the situation faced by battlefield simulations. This paper studies an approach where the simulated battlefield domain is first partitioned into many regions of equal size; typically there are more regions than processors. The regions are then assigned to processors; a processor is responsible for performing all simulation activity associated with the regions. The assignment algorithm is quite simple and attempts to balance load by exploiting locality of workload intensity. The performance of this technique is studied on a simple battlefield simulation implemented on the Flex/32 multiprocessor. Measurements show that the proposed method achieves reasonable processor efficiencies. Furthermore, the method shows promise for use in dynamic remapping of the simulation.

Nicol, David M.↗

NASA NTRS1989

Algorithmic considerations of integrated design for CSI on a hypercube architecture

An approach is presented to the integrated design problem for actively controlled large, flexible mechanical systems for which Control Structure Interaction (CSI) problems are of concern. The two coupled design problems were identified as the optimal Structural Design problem the optimal Controller Design problem. These two problems can be addressed within a decision making loop that would consider each separately, and then sequentially analyze the effects of one on the other. Embedded in such a loop would be the simulation and coordination tasks as part of the decision tools required in a total (software) package. All of the above are compute-intensive tasks. In any such task, possible decompositions and gains due to the inherent parallelism have to be exploited. The problems under consideration, as applied to large flexible mechanical structures, are particularly suited to be mapped onto multicomputer systems in a hypercube topology.

Oezguener, UE.↗

NASA NTRS1986

Dynamic remapping of parallel computations with varying resource demands

A large class of computational problems is characterized by frequent synchronization, and computational requirements which change as a function of time. When such a problem must be solved on a message passing multiprocessor machine, the combination of these characteristics lead to system performance which decreases in time. Performance can be improved with periodic redistribution of computational load; however, redistribution can exact a sometimes large delay cost. We study the issue of deciding when to invoke a global load remapping mechanism. Such a decision policy must effectively weigh the costs of remapping against the performance benefits. We treat this problem by constructing two analytic models which exhibit stochastically decreasing performance. One model is quite tractable; we are able to describe the optimal remapping algorithm, and the optimal decision policy governing when to invoke that algorithm. However, computational complexity prohibits the use of the optimal remapping decision policy. We then study the performance of a general remapping policy on both analytic models. This policy attempts to minimize a statistic W(n) which measures the system degradation (including the cost of remapping) per computation step over a period of n steps. We show that as a function of time, the expected value of W(n) has at most one minimum, and that when this minimum exists it defines the optimal fixed-interval remapping policy. Our decision policy appeals to this result by remapping when it estimates that W(n) is minimized. Our performance data suggests that this policy effectively finds the natural frequency of remapping. We also use the analytic models to express the relationship between performance and remapping cost, number of processors, and the computation's stochastic activity.

Nicol, D. M.↗

NASA NTRS1986

Negative base encoding in optical linear algebra processors

In the digital multiplication by analog convolution algorithm, the bits of two encoded numbers are convolved to form the product of the two numbers in mixed binary representation; this output can be easily converted to binary. Attention is presently given to negative base encoding, treating base -2 initially, and then showing that the negative base system can be readily extended to any radix. In general, negative base encoding in optical linear algebra processors represents a more efficient technique than either sign magnitude or 2's complement encoding, when the additions of digitally encoded products are performed in parallel.

Perlee, C.↗

NASA NTRS2003

Geoscience Laser Altimeter System (GLAS) on the ICESat Mission: Initial Science Measurement Performance

The Geoscience Laser Altimeter System is the space lidar on the NASA ICESat mission. Its design combines an altimeter with 5 cm precision with a laser pointing angle determination system and a dual wavelength cloud and aerosol lidar. GLAS measures the range to the Earth s surface with 1064 nm laser pulses. Each laser pulse produces a precision pointing measurement from the stellar reference system (SRS) and an echo pulse waveform, which permits range determination and waveform spreading analysis. The single shot ranging accuracy is < 10 cm for ice surfaces with slopes < 2 degrees. GLAS also measures atmospheric backscatter profiles at both 1064 and 532 nm. The 1064 nm measurements use an analog Si APD detector and measure the height and profile the backscatter signal from thicker clouds. The measurements at 532 nm use photon counting detectors, and will measure the vertical height distributions of optically thin clouds and aerosol layers Before launch, the measurement performance of GLAS was evaluated using a lidar test instrument called the Bench Check Equipment (BCE). The BCE was developed in parallel with GLAS and served as an inverse altimeter, inverse lidar and a stellar source simulator. It was used to simulate the range of expected optical inputs to the GLAS receiver by illuminating its telescope with simulated background light as well as laser echoes with known powers, energy levels, widths and delay times. The BCE also allowed monitoring of the transmitted laser energy, the angle measurements of the SRS, the co-alignment of the transmitted laser beam to the receiver line of sight, and performance of the flight science algorithms. Performance was evaluated during the GLAS development, before and after environmental tests, and after delivery to the spacecraft. The ICESat observatory was launched into a 94 degree inclination, 590 km altitude circular polar orbit on January 12,2003. Beginning in early February, GLAS was powered on tested in stages. Its 1064 nm optical receiver was evaluated in a several tests using both solar background light and an internal test source. Laser 1 was activated on February 20,2003. GLAS operated with Laser 1 for 38 continuous days on orbit using its 1064 nm receiver channel, producing over 130 million individual laser measurements of the Earth s surface and atmosphere. These nadir-pointed measurements fell along the ICESat s ground track, and spanned more than 4 cycles of the initial 8-day ICESat repeat orbit. The initial GLAS measurement set shows strong echo pulses from ranging to the surface topography, oceans, ice sheets and cloud tops, as well as profiles of clouds and aerosols. The GLAS measurements have unprecedented vertical and angular resolution, and show nearly continuous height profiles of ice, land and ocean surfaces or cloud tops, as well profiles of backscatter from thin clouds and aerosol layers. Examples of these GLAS measurements and an initial assessment of its science measurement performance will be presented.

Abshire, James B.↗

NASA NTRS1987

Optimal mapping of irregular finite element domains to parallel processors

Mapping the solution domain of n-finite elements into N-subdomains that may be processed in parallel by N-processors is an optimal one if the subdomain decomposition results in a well-balanced workload distribution among the processors. The problem is discussed in the context of irregular finite element domains as an important aspect of the efficient utilization of the capabilities of emerging multiprocessor computers. Finding the optimal mapping is an intractable combinatorial optimization problem, for which a satisfactory approximate solution is obtained here by analogy to a method used in statistical mechanics for simulating the annealing process in solids. The simulated annealing analogy and algorithm are described, and numerical results are given for mapping an irregular two-dimensional finite element domain containing a singularity onto the Hypercube computer.

Flower, J.↗

NASA NTRS2004

Fast-Acquisition/Weak-Signal-Tracking GPS Receiver for HEO

A report discusses the technical background and design of the Navigator Global Positioning System (GPS) receiver -- . a radiation-hardened receiver intended for use aboard spacecraft. Navigator is capable of weak signal acquisition and tracking as well as much faster acquisition of strong or weak signals with no a priori knowledge or external aiding. Weak-signal acquisition and tracking enables GPS use in high Earth orbits (HEO), and fast acquisition allows for the receiver to remain without power until needed in any orbit. Signal acquisition and signal tracking are, respectively, the processes of finding and demodulating a signal. Acquisition is the more computationally difficult process. Previous GPS receivers employ the method of sequentially searching the two-dimensional signal parameter space (code phase and Doppler). Navigator exploits properties of the Fourier transform in a massively parallel search for the GPS signal. This method results in far faster acquisition times [in the lab, 12 GPS satellites have been acquired with no a priori knowledge in a Low-Earth-Orbit (LEO) scenario in less than one second]. Modeling has shown that Navigator will be capable of acquiring signals down to 25 dB-Hz, appropriate for HEO missions. Navigator is built using the radiation-hardened ColdFire microprocessor and housing the most computationally intense functions in dedicated field-programmable gate arrays. The high performance of the algorithm and of the receiver as a whole are made possible by optimizing computational efficiency and carefully weighing tradeoffs among the sampling rate, data format, and data-path bit width.

Wintemitz, Luke↗

NASA NTRS1984

Numerical simulation of the interaction of a vortex with stationary airfoil in transonic flow

A perturbation form of an implicit conservative, noniterative numerical algorithm for the two-dimensional thin layer Navier-Stokes and Euler equations is used to compute the interaction flow-field of a vortex with stationary airfoil. A Lamb-like analytical vortex having a finite core is chosen to interact with a thick (NACA 0012) and a thin (NACA 64A006) airfoil independently in transonic flow. Two different configurations of vortex interaction are studied, viz., (1) when the vortex is fixed at one location in the flowfield, and (2) when the vortex is convecting past the airfoil at freestream velocity. Parallel computations of this interacting flowfield are also done using a version of the Transonic Small Disturbance Code (ATRAN2). A special treatment of the leading edge region for thin airfoils is included in this code. With this, the three methods gave qualitatively similar results for the weaker interactions considered in this study. However, the strongest interactions considered proved to be beyond the capabilities of the small disturbance code. The results also show a far greater influence of the vortex on the airfoil flowfield when the vortex is stationary than when it is convecting with the flow.

Srinivasan, G. R.↗

NASA NTRS1999

On the Fast Evaluation Method of Temperature and Gas Mixing Ratio Weighting Functions for Remote Sensing of Planetary Atmospheres in Thermal IR and Microwave

Evaluation of weighting functions in the atmospheric remote sensing is usually the most computer-intensive part of the inversion algorithms. We present an analytic approach to computations of temperature and mixing ratio weighting functions that is based on our previous results but the resulting expressions use the intermediate variables that are generated in computations of observable radiances themselves. Upwelling radiances at the given level in the atmosphere and atmospheric transmittances from space to the given level are combined with local values of the total absorption coefficient and its components due to absorption of atmospheric constituents under study. This makes it possible to evaluate the temperature and mixing ratio weighting functions in parallel with evaluation of radiances. This substantially decreases the computer time required for evaluation of weighting functions. Implications for the nadir and limb viewing geometries are discussed.

Ustinov, E. A.↗

NASA NTRS2004

An Initial Analysis of the Pixel-Level Uncertainties in Global MODIS Cloud Optical Thickness and Effective Particle Size Retrievals

Moderate Resolution Imaging Spectroradiometer (MODIS) retrievals of cloud optical thickness and effective particle radius employ well-known solar reflectance techniques using pre-calculated reflectance look-up tables. We evaluate the quantitative uncertainty in simultaneous retrievals of cloud optical thickness and particle size for this type of algorithm. The technique uses sensitivity calculations derived from the reflectance look-up tables, coupled with estimates for the effect of various error terms on the uncertainty in inferring the actual cloud-top reflectance. The error terms include the effects of instrument calibration, surface spectral albedo, and atmospheric corrections on both water and ice cloud retrievals. Because particle shapes in ice clouds are highly variable, the effect of particle shape is analyzed separately with a more approximate method. Results will deal exclusively with pixel-level uncertainties associated with plane-parallel clouds; real-world radiative departures from a plane-parallel model are an additional consideration. While we demonstrate the uncertainty technique with operational 1 km MODIS retrievals from the Terra and Aqua satellite platforms, the technique is applicable to any reflectance-based satellite- or air-borne sensor retrieval using similar spectral channels.

Platnick, S.↗

NASA NTRS1997

Constrained Multipoint Aerodynamic Shape Optimization Using an Adjoint Formulation and Parallel Computers

An aerodynamic shape optimization method that treats the design of complex aircraft configurations subject to high fidelity computational fluid dynamics (CFD), geometric constraints and multiple design points is described. The design process will be greatly accelerated through the use of both control theory and distributed memory computer architectures. Control theory is employed to derive the adjoint differential equations whose solution allows for the evaluation of design gradient information at a fraction of the computational cost required by previous design methods. The resulting problem is implemented on parallel distributed memory architectures using a domain decomposition approach, an optimized communication schedule, and the MPI (Message Passing Interface) standard for portability and efficiency. The final result achieves very rapid aerodynamic design based on a higher order CFD method. In order to facilitate the integration of these high fidelity CFD approaches into future multi-disciplinary optimization (NW) applications, new methods must be developed which are capable of simultaneously addressing complex geometries, multiple objective functions, and geometric design constraints. In our earlier studies, we coupled the adjoint based design formulations with unconstrained optimization algorithms and showed that the approach was effective for the aerodynamic design of airfoils, wings, wing-bodies, and complex aircraft configurations. In many of the results presented in these earlier works, geometric constraints were satisfied either by a projection into feasible space or by posing the design space parameterization such that it automatically satisfied constraints. Furthermore, with the exception of reference 9 where the second author initially explored the use of multipoint design in conjunction with adjoint formulations, our earlier works have focused on single point design efforts. Here we demonstrate that the same methodology may be extended to treat complete configuration designs subject to multiple design points and geometric constraints. Examples are presented for both transonic and supersonic configurations ranging from wing alone designs to complex configuration designs involving wing, fuselage, nacelles and pylons.

Reuther, James↗

NASA NTRS2014

GPU Lossless Hyperspectral Data Compression System

Hyperspectral imaging systems onboard aircraft or spacecraft can acquire large amounts of data, putting a strain on limited downlink and storage resources. Onboard data compression can mitigate this problem but may require a system capable of a high throughput. In order to achieve a high throughput with a software compressor, a graphics processing unit (GPU) implementation of a compressor was developed targeting the current state-of-the-art GPUs from NVIDIA(R). The implementation is based on the fast lossless (FL) compression algorithm reported in "Fast Lossless Compression of Multispectral-Image Data" (NPO- 42517), NASA Tech Briefs, Vol. 30, No. 8 (August 2006), page 26, which operates on hyperspectral data and achieves excellent compression performance while having low complexity. The FL compressor uses an adaptive filtering method and achieves state-of-the-art performance in both compression effectiveness and low complexity. The new Consultative Committee for Space Data Systems (CCSDS) Standard for Lossless Multispectral & Hyperspectral image compression (CCSDS 123) is based on the FL compressor. The software makes use of the highly-parallel processing capability of GPUs to achieve a throughput at least six times higher than that of a software implementation running on a single-core CPU. This implementation provides a practical real-time solution for compression of data from airborne hyperspectral instruments.

Aranki, Nazeeh I.↗

NASA NTRS2015

DRAGONS-A Micrometeoroid and Orbital Debris Impact Sensor on the ISS

The Debris Resistive/Acoustic Grid Orbital Navy-NASA Sensor (DRAGONS) is intended to be a large area impact sensor for in situ measurements of micrometeoroids and orbital debris (MMOD) in the sub-millimeter to millimeter size regime in the near Earth space environment. These MMOD particles are too small to be detected by ground-based radars and optical telescopes, but still large enough to be a serious threat to human space activities and robotic missions in the low Earth orbit (LEO) region. The nominal detection area of DRAGONS is 1 sq m, consisting of four 0.5 m × 0.5 m independent panels, but the dimensions of the panels can easily be modified to accommodate different payload constraints. The approach of the DRAGONS design is to combine three particle impact detection concepts to maximize information that can be extracted from each detected impact. The first is a resistive grid consisting of 75-micrometer-wide resistive lines, coated in parallel and separated by 75 micrometer gaps on a 25-micrometer thin film. When a particle a few hundred micrometers or larger strikes the grid, it would penetrate the film and sever some resistive lines. The size of the damage area can be estimated from the increased resistance. The second concept is based on polyvinylidene fluoride (PVDF) acoustic impact sensors. Multiple PVDF sensors are attached to the thin film to provide the impact timing information. From the different signal arrival times at different acoustic sensors, the impact location can be calculated via triangulation algorithms. The third concept employs a dual-layer film system where a second 25-micrometer film is placed 15 cm behind the resistive-grid film. Multiple PVDF acoustic sensors are also attached to the second film. The combination of impact timing and location information from the two films allows for direct measurements of the impact direction and speed. The DRAGONS technology development has been funded by several NASA organizations since 2002, first by the NASA Science Mission Directorate and the NASA Exploration Systems Mission Directorate, then by the NASA JSC Innovative Research and Development Program and the NASA Orbital Debris Program Office. The NASA Orbital Debris Program Office leads the effort with collaboration from the U.S. Naval Academy, Naval Research Laboratory, University of Kent at Canterbury in Great Britain, and Virginia Tech. The project recently reached a major milestone when DRAGONS was approved for a technology demonstration mission by the International Space Station (ISS) Program in October 2014. The plan is to deploy a 1 sq m DRAGONS on the ISS with the detection surface facing the ram-direction for 2 to 3 years. The tentative launch schedule is in early 2017. This mission will collect data on orbital debris in the sub-millimeter size regime to better define the small orbital debris environment at the ISS altitude. The mission will also advance the DRAGONS Technology Readiness Level to 9 and greatly enhance the opportunities to deploy DRAGONS on other spacecraft to high LEO orbits in the future.

Liou, J.-C.↗

NASA NTRS2016

Benchmark Comparison of Cloud Analytics Methods Applied to Earth Observations

Cloud computing has the potential to bring high performance computing capabilities to the average science researcher. However, in order to take full advantage of cloud capabilities, the science data used in the analysis must often be reorganized. This typically involves sharding the data across multiple nodes to enable relatively fine-grained parallelism. This can be either via cloud-based file systems or cloud-enabled databases such as Cassandra, Rasdaman or SciDB. Since storing an extra copy of data leads to increased cost and data management complexity, NASA is interested in determining the benefits and costs of various cloud analytics methods for real Earth Observation cases. Accordingly, NASA's Earth Science Technology Office and Earth Science Data and Information Systems project have teamed with cloud analytics practitioners to run a benchmark comparison on cloud analytics methods using the same input data and analysis algorithms. We have particularly looked at analysis algorithms that work over long time series, because these are particularly intractable for many Earth Observation datasets which typically store data with one or just a few time steps per file. This post will present side-by-side cost and performance results for several common Earth observation analysis operations.

science data management↗

NASA NTRS2007

The Plane-parallel Albedo Bias of Liquid Clouds from MODIS Observations

In our most advanced modeling tools for climate change prediction, namely General Circulation Models (GCMs), the schemes used to calculate the budget of solar and thermal radiation commonly assume that clouds are horizontally homogeneous at scales as large as a few hundred kilometers. However, this assumption, used for convenience, computational speed, and lack of knowledge on cloud small scale variability, leads to erroneous estimates of the radiation budget. This paper provides a global picture of the solar radiation errors at scales of approximately 100 km due to warm (liquid phase) clouds only. To achieve this, we use cloud retrievals from the instrument MODIS on the Terra and Aqua satellites, along with atmospheric and surface information, as input into a GCM-style radiative transfer algorithm. Since the MODIS product contains information on cloud variability below 100 km we can run the radiation algorithm both for the variable and the (assumed) homogeneous clouds. The difference between these calculations for reflected or transmitted solar radiation constitutes the bias that GCMs would commit if they were able to perfectly predict the properties of warm clouds, but then assumed they were homogeneous for radiation calculations. We find that the global average of this bias is approx.2-3 times larger in terms of energy than the additional amount of thermal energy that would be trapped if we were to double carbon dioxide from current concentrations. We should therefore make a greater effort to predict horizontal cloud variability in GCMs and account for its effects in radiation calculations.

Oreopoulos, Lazaros↗

NASA NTRS2018

The Convergence of Analysis Produced by Overlapping Assimilation Streams

When conducting a reanalysis for a long period, it is common to do so using multiple, parallel computational schemes. A period of overlap is included to foster continuity between successive streams. At the GMAO, the overlap period is one year. By the end of that period, the time mean anlysis for corresponding overlapped months are almost identical, as desired. The variances of differences at corresponding analysis times within each month, however, do not converge to zero. Instead their monthly variances converge to values that are a significant fraction of the the estimated variances of analysis errors. This occurs although the overlapping streams use the same observations, assimilation model, and assimilation algorithm, differing only in the background applied information applied at the beginning of the overlap period.

Errico, Ronald M.↗

NASA NTRS2021

PatchworkWave: A Multipatch Infrastructure for Multiphysics/Multiscale/Multiframe/Multimethod Simulations at Arbitrary Order

We present an extension of the PatchworkMHD code [1], itself an MHD-capable extension of thePatch-workcode [2], for which several algorithms presented here were co-developed. Its purpose is to create a“multipatch” scheme compatible with numerical simulations of arbitrary equations of motion at any dis-cretization order in space and time. In thePatchworkframework, the global simulation is comprised of anarbitrary number of moving, local meshes, or “patches”, which are free to employ their own resolution, co-ordinate system/topology, physics equations, reference frame, and in our new approach, numerical method.Each local patch exchanges boundary data with a single global patch on which all other patches residethrough a client-router-server parallelization model. In generalizingPatchworkto be compatible witharbitrary order time integration,PatchworkMHDandPatchworkWavehave significantly improved theinterpatch interpolation accuracy by removing an interpolation of interpolated data feedback present in theoriginalPatchworkcode. Furthermore, we extendPatchworkto bemultimethodby allowing multiplestate vectors to be updated simultaneously, with each state vector providing its own interpatch interpolationand transformation procedures. As such, our scheme is compatible with nearly any set of hyperbolic partialdifferential equations. We demonstrate our changes through the implementation of a scalar wave toy-modelthat is evolved on arbitrary, time dependent patch configurations at 4th order accuracy.

Dennis B Bowen↗

NASA NTRS2004

Evolutionary computing for the design search and optimization of space vehicle power subsystems

Evolutionary computing has proven to be a straightforward and robust approach for optimizing a wide range of difficult analysis and design problems. This paper discusses the application of these techniques to an existing space vehicle power subsystem resource and performance analysis simulation in a parallel processing environment. Out preliminary results demonstrate that this approach has the potential to improve the space system trade study process by allowing engineers to statistically weight subsystem goals of mass, cost and performance then automatically size power elements based on anticipated performance of the subsystem rather than on worst-case estimates.

power↗