Search NASA⌕ Search

SEARCH · Search NASA

Results for “data parallel algorithms”

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

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

At least 505 records · Page 28
All sourcesNASA NTRSDOE OSTI
NASA NTRS1980

A design study of a signal detection system

A system is described which can aid in the search for radio signals from extraterrestrial sources, or in other applications characterized by low signal-to-noise ratios and very high data rates. The system follows a multichannel (16 million bin) spectrum analyzer, and has critical processing, system control, and memory fuctions. The design includes a moderately rich set of algorithms to be used in parallel to detect signals of unknown form. A multi-threshold approach is used to obtain high and low signal sensitivities. Relatively compact and transportable memory systems are specified.

Healy, T. J.↗
NASA NTRS1986

Modular VLSI Reed-Solomon Decoder

Proposed Reed-Solomon (RS) decoder assembled from very-large-scale integrated-circuit (VLSI) building blocks. Decoder exploits recursive forms in RS decoding algorithms. RS codes capable of correcting random or burst errors in telemetry and other data-communication signals. Because of small size and low power consumption, advantageous to employ several such decoders in parallel-processing scheme to increase decoding speed.

Liu, K. Y.↗
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 NTRS1995

Parallel volume ray-casting for unstructured-grid data on distributed-memory architectures

As computing technology continues to advance, computational modeling of scientific and engineering problems produces data of increasing complexity: large in size and unstructured in shape. Volume visualization of such data is a challenging problem. This paper proposes a distributed parallel solution that makes ray-casting volume rendering of unstructured-grid data practical. Both the data and the rendering process are distributed among processors. At each processor, ray-casting of local data is performed independent of the other processors. The global image composing processes, which require inter-processor communication, are overlapped with the local ray-casting processes to achieve maximum parallel efficiency. This algorithm differs from previous ones in four ways: it is completely distributed, less view-dependent, reasonably scalable, and flexible. Without using dynamic load balancing, test results on the Intel Paragon using from two to 128 processors show, on average, about 60% parallel efficiency.

Ma, Kwan-Liu↗
NASA NTRS2005

The Effect of Approximating Some Molecular Integrals in Coupled-Cluster Calculations: Fundamental Frequencies and Rovibrational Spectroscopic Constants of Cyclopropenylidene

The singles and doubles coupled-cluster method that includes a perturbational estimate of connected triple excitations, denoted CCSD(T), has been used, in conjunction with approximate integral techniques, to compute highly accurate rovibrational spectroscopic constants of cyclopropenylidene, C3H2. The approximate integral technique was proposed in 1994 by Rendell and Lee in order to avoid disk storage and input/output bottlenecks, and today it will also significantly aid in the development of algorithms for distributed memory, massively parallel computer architectures. It is shown in this study that use of approximate integrals does not impact the accuracy of CCSD(T) calculations. In addition, the most accurate spectroscopic data yet for C3H2 is presented based on a CCSD(T)/cc-pVQZ quartic force field that is modified to include the effects of core-valence electron correlation. Cyclopropenylidene is of great astronomical and astrobiological interest because it is the smallest aromatic ringed compound to be positively identified in the interstellar medium, and is thus involved in the prebiotic processing of carbon and hydrogen. The singles and doubles coupled-cluster method that includes a perturbational estimate of

Lee, Timothy J.↗
NASA NTRS2012

GPU Lossless Hyperspectral Data Compression System for Space Applications

On-board lossless hyperspectral data compression reduces data volume in order to meet NASA and DoD limited downlink capabilities. At JPL, a novel, adaptive and predictive technique for lossless compression of hyperspectral data, named the Fast Lossless (FL) algorithm, was recently developed. This technique uses an adaptive filtering method and achieves state-of-the-art performance in both compression effectiveness and low complexity. Because of its outstanding performance and suitability for real-time onboard hardware implementation, the FL compressor is being formalized as the emerging CCSDS Standard for Lossless Multispectral & Hyperspectral image compression. The FL compressor is well-suited for parallel hardware implementation. A GPU hardware implementation was developed for FL targeting the current state-of-the-art GPUs from NVIDIA(Trademark). The GPU implementation on a NVIDIA(Trademark) GeForce(Trademark) GTX 580 achieves a throughput performance of 583.08 Mbits/sec (44.85 MSamples/sec) and an acceleration of at least 6 times a software implementation running on a 3.47 GHz single core Intel(Trademark) Xeon(Trademark) processor. This paper describes the design and implementation of the FL algorithm on the GPU. The massively parallel implementation will provide in the future a fast and practical real-time solution for airborne and space applications.

Graphic Processor Units↗
NASA NTRS2007

Efficient Mosaicking of Spitzer Space Telescope Images

A parallel version of the MOPEX software, which generates mosaics of infrared astronomical images acquired by the Spitzer Space Telescope, extends the capabilities of the prior serial version. In the parallel version, both the input image space and the output mosaic space are divided among the available parallel processors. This is the only software that performs the point-source detection and the rejection of spurious imaging effects of cosmic rays required by Spitzer scientists. This software includes components that implement outlier-detection algorithms that can be fine-tuned for a particular set of image data by use of a number of adjustable parameters. This software has been used to construct a mosaic of the Spitzer Infrared Array Camera Shallow Survey, which comprises more than 17,000 exposures in four wavelength bands from 3.6 to 8 m and spans a solid angle of about 9 square degrees. When this software was executed on 32 nodes of the 1,024-processor Cosmos cluster computer at NASA s Jet Propulsion Laboratory, a speedup of 8.3 was achieved over the serial version of MOPEX. The performance is expected to improve dramatically once a true parallel file system is installed on Cosmos.

Jacob, Joseph↗
DOE OSTI2023

cuAlign: Scalable Network Alignment on GPU Accelerators

Given two graphs, the objective of network alignment is to find the best one-to-one mapping of vertices in one graph (??) to vertices in the other (??), such that the number of overlaps is maximized. We say that edges(??, ??) ???and(??', ??') ??? are overlapped if ?? is mapped to ??' and ?? is mapped to??'. Network alignment is an important optimization problem with several applications in bioinformatics, computer vision and ontology matching. Since it is an NP-hard problem, efficient heuristics and scalable implementations are necessary. In this work, we introduce a new framework that combines the concepts of intra-network proximity using vertex embedding,Belief Propagation (BP) and approximate weighted matching, and provides qualitative improvements up to22%over state-of-the-art approaches. We also provide scalable implementations on GPU accelerators, demonstrating up to19×speedup for Belief Propagation and 3× speedup for approximate weighted matching relative to previous multithreaded implementation. A combination of combinatorial and algebraic kernels within the network alignment algorithm poses significant hurdles for parallelization. Load imbalance and irregular DRAM traffic limit achievable performance on GPUs. Our novel approach identifies and exploits unique structural proper-ties of the BP-based algorithm and employs code fusion to reduce data movement between different steps of the algorithm. Using a diverse set of inputs, we demonstrate qualitative improvements of our algorithms, and performance gains of our GPU-accelerated implementation. We believe that our work will enable algorithmic improvements and practical applications of network alignment.

Xiang, Lizhi↗
NASA NTRS1985

A decentralized square root information filter/smoother

A number of developments has recently led to a considerable interest in the decentralization of linear least squares estimators. The developments are partly related to the impending emergence of VLSI technology, the realization of parallel processing, and the need for algorithmic ways to speed the solution of dynamically decoupled, high dimensional estimation problems. A new method is presented for combining Square Root Information Filters (SRIF) estimates obtained from independent data sets. The new method involves an orthogonal transformation, and an information matrix filter 'homework' problem discussed by Schweppe (1973) is generalized. The employed SRIF orthogonal transformation methodology has been described by Bierman (1977).

Bierman, G. J.↗
NASA NTRS1987

Image reconstruction from multiple 1-D scans using filtered localized projection

The spatial resolution that can be attained using scanning linear arrays (consisting of discrete IR solid-state detectors) for image acquisition is considered, and a filtered local projection (FLP) method is described which efficiently combines all available scan information into one rectangular grid without the need for explicit interpolation. Mathematically, the FLP algorithm consists of a localized summation followed by an inverse-filter operation, and it has application to nonlinear restoring techniques. The present method is applied, using a linear array, to simulated data for staggered parallel scans and to multiple scan directions. Noise effects and limitations of the technique are also considered.

Frieden, B. Roy↗
NASA NTRS1989

Memory management in traceback Viterbi decoders

The new Viterbi decoder for long constraint length codes, under development for the Deep Space Network, stores path information according to an algorithm called traceback. The details of a particular implementation of this algorithm, based on three memory buffers, are described. The penalties in increased storage requirement and longer decoding delay are offset by the reduced amount of data that needs to be exchanged between processors, in a parallel architecture decoder.

Collins, O.↗
DOE OSTI2020

Machine Committee Framework for Power Grid Disturbances Analysis Using Synchrophasors Data

Events detection is a key challenge in power grid frequency disturbances analysis. Accurate detection of events is crucial for situational awareness of the power system. In this paper, we study the problem of events detection in power grid frequency disturbance analysis using synchrophasors data streams. Current events detection approaches for power grid rely on individual detection algorithm. This study integrates some of the existing detection algorithms using the concept of machine committee to develop improved detection approaches for grid disturbance analysis. Specifically, we propose two algorithms—an Event Detection Machine Committee (EDMC) algorithm and a Change-Point Detection Machine Committee (CPDMC) algorithm. Both algorithms use parallel architecture to fuse detection knowledge of its individual methods to arrive at an overall output. The EDMC algorithm combines five individual event detection methods, while the CPDMC algorithm combines two change-point detection methods. Each method performs the detection task separately. The overall output of each algorithm is then computed using a voting strategy. The proposed algorithms are evaluated using three case studies of actual power grid disturbances. Compared with the individual results of the various detection methods, we found that the EDMC algorithm is a better fit for analyzing synchrophasors data; it improves the detection accuracy; and it is suitable for practical scenarios.

24 POWER TRANSMISSION AND DISTRIBUTION↗
NASA NTRS1997

Visual Computing Environment

The Visual Computing Environment (VCE) is a NASA Lewis Research Center project to develop a framework for intercomponent and multidisciplinary computational simulations. Many current engineering analysis codes simulate various aspects of aircraft engine operation. For example, existing computational fluid dynamics (CFD) codes can model the airflow through individual engine components such as the inlet, compressor, combustor, turbine, or nozzle. Currently, these codes are run in isolation, making intercomponent and complete system simulations very difficult to perform. In addition, management and utilization of these engineering codes for coupled component simulations is a complex, laborious task, requiring substantial experience and effort. To facilitate multicomponent aircraft engine analysis, the CFD Research Corporation (CFDRC) is developing the VCE system. This system, which is part of NASA's Numerical Propulsion Simulation System (NPSS) program, can couple various engineering disciplines, such as CFD, structural analysis, and thermal analysis. The objectives of VCE are to (1) develop a visual computing environment for controlling the execution of individual simulation codes that are running in parallel and are distributed on heterogeneous host machines in a networked environment, (2) develop numerical coupling algorithms for interchanging boundary conditions between codes with arbitrary grid matching and different levels of dimensionality, (3) provide a graphical interface for simulation setup and control, and (4) provide tools for online visualization and plotting. VCE was designed to provide a distributed, object-oriented environment. Mechanisms are provided for creating and manipulating objects, such as grids, boundary conditions, and solution data. This environment includes parallel virtual machine (PVM) for distributed processing. Users can interactively select and couple any set of codes that have been modified to run in a parallel distributed fashion on a cluster of heterogeneous workstations. A scripting facility allows users to dictate the sequence of events that make up the particular simulation.

Lawrence, Charles↗
DOE OSTI2019

Computational Strategies for Scalable Genomics Analysis

The revolution in next-generation DNA sequencing technologies is leading to explosive data growth in genomics, posing a significant challenge to the computing infrastructure and software algorithms for genomics analysis. Various big data technologies have been explored to scale up/out current bioinformatics solutions to mine the big genomics data. In this review, we survey some of these exciting developments in the applications of parallel distributed computing and special hardware to genomics. We comment on the pros and cons of each strategy in the context of ease of development, robustness, scalability, and efficiency. Although this review is written for an audience from the genomics and bioinformatics fields, it may also be informative for the audience of computer science with interests in genomics applications.

59 BASIC BIOLOGICAL SCIENCES↗
NASA NTRS1994

The design and development of signal-processing algorithms for an airborne x-band Doppler weather radar

Improved measurements of precipitation will aid our understanding of the role of latent heating on global circulations. Spaceborne meteorological sensors such as the planned precipitation radar and microwave radiometers on the Tropical Rainfall Measurement Mission (TRMM) provide for the first time a comprehensive means of making these global measurements. Pre-TRMM activities include development of precipitation algorithms using existing satellite data, computer simulations, and measurements from limited aircraft campaigns. Since the TRMM radar will be the first spaceborne precipitation radar, there is limited experience with such measurements, and only recently have airborne radars become available that can attempt to address the issue of the limitations of a spaceborne radar. There are many questions regarding how much attenuation occurs in various cloud types and the effect of cloud vertical motions on the estimation of precipitation rates. The EDOP program being developed by NASA GSFC will provide data useful for testing both rain-retrieval algorithms and the importance of vertical motions on the rain measurements. The purpose of this report is to describe the design and development of real-time embedded parallel algorithms used by EDOP to extract reflectivity and Doppler products (velocity, spectrum width, and signal-to-noise ratio) as the first step in the aforementioned goals.

Nicholson, Shaun R.↗
NASA NTRS1996

Hierarchical and Parallelizable Direct Volume Rendering for Irregular and Multiple Grids

A general volume rendering technique is described that efficiently produces images of excellent quality from data defined over irregular grids having a wide variety of formats. Rendering is done in software, eliminating the need for special graphics hardware, as well as any artifacts associated with graphics hardware. Images of volumes with about one million cells can be produced in one to several minutes on a workstation with a 150 MHz processor. A significant advantage of this method for applications such as computational fluid dynamics is that it can process multiple intersecting grids. Such grids present problems for most current volume rendering techniques. Also, the wide range of cell sizes (by a factor of 10,000 or more), which is typical of such applications, does not present difficulties, as it does for many techniques. A spatial hierarchical organization makes it possible to access data from a restricted region efficiently. The tree has greater depth in regions of greater detail, determined by the number of cells in the region. It also makes it possible to render useful 'preview' images very quickly (about one second for one-million-cell grids) by displaying each region associated with a tree node as one cell. Previews show enough detail to navigate effectively in very large data sets. The algorithmic techniques include use of a kappa-d tree, with prefix-order partitioning of triangles, to reduce the number of primitives that must be processed for one rendering, coarse-grain parallelism for a shared-memory MIMD architecture, a new perspective transformation that achieves greater numerical accuracy, and a scanline algorithm with depth sorting and a new clipping technique.

Wilhelms, Jane↗
NASA NTRS2011

The Goes-R Geostationary Lightning Mapper (GLM)

The Geostationary Operational Environmental Satellite (GOES-R) is the next series to follow the existing GOES system currently operating over the Western Hemisphere. Superior spacecraft and instrument technology will support expanded detection of environmental phenomena, resulting in more timely and accurate forecasts and warnings. Advancements over current GOES capabilities include a new capability for total lightning detection (cloud and cloud-to-ground flashes) from the Geostationary Lightning Mapper (GLM), and improved storm diagnostic capability with the Advanced Baseline Imager. The GLM will map total lightning activity (in-cloud and cloud-to-ground lighting flashes) continuously day and night with near-uniform spatial resolution of 8 km with a product refresh rate of less than 20 sec over the Americas and adjacent oceanic regions. This will aid in forecasting severe storms and tornado activity, and convective weather impacts on aviation safety and efficiency. In parallel with the instrument development, a GOES-R Risk Reduction Team and Algorithm Working Group Lightning Applications Team have begun to develop the Level 2 algorithms, cal/val performance monitoring tools, and new applications. Proxy total lightning data from the NASA Lightning Imaging Sensor on the Tropical Rainfall Measuring Mission (TRMM) satellite and regional test beds are being used to develop the pre-launch algorithms and applications, and also improve our knowledge of thunderstorm initiation and evolution. In this paper we will report on new Nowcasting and storm warning applications being developed and evaluated at various NOAA Testbeds.

Goodman, Steven J.↗