Engineering Papers⌕ Search

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.

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

At least 1,333 records · Page 74
All sourcesNASA NTRSDOE OSTI
NASA NTRS1991

A parallel-pipelined architecture for a multi carrier demodulator

Analog devices have been used for processing the information on board the satellites. Presently, digital devices are being used because they are economical and flexible as compared to their analog counterparts. Several schemes of digital transmission can be used depending on the data rate requirement of the user. An economical scheme of transmission for small earth stations uses single channel per carrier/frequency division multiple access (SCPC/FDMA) on the uplink and time division multiplexing (TDM) on the downlink. This is a typical communication service offered to low data rate users in commercial mass market. These channels usually pertain to either voice or data transmission. An efficient digital demodulator architecture is provided for a large number of law data rate users. A demodulator primarily consists of carrier, clock, and data recovery modules. This design uses principles of parallel processing, pipelining, and time sharing schemes to process large numbers of voice or data channels. It maintains the optimum throughput which is derived from the designed architecture and from the use of high speed components. The design is optimized for reduced power and area requirements. This is essential for satellite applications. The design is also flexible in processing a group of a varying number of channels. The algorithms that are used are verified by the use of a computer aided software engineering (CASE) tool called the Block Oriented System Simulator. The data flow, control circuitry, and interface of the hardware design is simulated in C language. Also, a multiprocessor approach is provided to map, model, and simulate the demodulation algorithms mainly from a speed view point. A hypercude based architecture implementation is provided for such a scheme of operation. The hypercube structure and the demodulation models on hypercubes are simulated in Ada.

Kwatra, S. C.↗
NASA NTRS1991

Mapping implicit spectral methods to distributed memory architectures

Spectral methods were proven invaluable in numerical simulation of PDEs (Partial Differential Equations), but the frequent global communication required raises a fundamental barrier to their use on highly parallel architectures. To explore this issue, a 3-D implicit spectral method was implemented on an Intel hypercube. Utilization of about 50 percent was achieved on a 32 node iPSC/860 hypercube, for a 64 x 64 x 64 Fourier-spectral grid; finer grids yield higher utilizations. Chebyshev-spectral grids are more problematic, since plane-relaxation based multigrid is required. However, by using a semicoarsening multigrid algorithm, and by relaxing all multigrid levels concurrently, relatively high utilizations were also achieved in this harder case.

Overman, Andrea L.↗
NASA NTRS1997

Computation of Reacting Flows in Combustion Processes

The main objective of this research was to develop an efficient three-dimensional computer code for chemically reacting flows. The main computer code developed is ALLSPD-3D. The ALLSPD-3D computer program is developed for the calculation of three-dimensional, chemically reacting flows with sprays. The ALL-SPD code employs a coupled, strongly implicit solution procedure for turbulent spray combustion flows. A stochastic droplet model and an efficient method for treatment of the spray source terms in the gas-phase equations are used to calculate the evaporating liquid sprays. The chemistry treatment in the code is general enough that an arbitrary number of reaction and species can be defined by the users. Also, it is written in generalized curvilinear coordinates with both multi-block and flexible internal blockage capabilities to handle complex geometries. In addition, for general industrial combustion applications, the code provides both dilution and transpiration cooling capabilities. The ALLSPD algorithm, which employs the preconditioning and eigenvalue rescaling techniques, is capable of providing efficient solution for flows with a wide range of Mach numbers. Although written for three-dimensional flows in general, the code can be used for two-dimensional and axisymmetric flow computations as well. The code is written in such a way that it can be run in various computer platforms (supercomputers, workstations and parallel processors) and the GUI (Graphical User Interface) should provide a user-friendly tool in setting up and running the code.

Keith, Theo G., Jr.↗
NASA NTRS2003

Evaluation of Cache-based Superscalar and Cacheless Vector Architectures for Scientific Computations

The growing gap between sustained and peak performance for scientific applications has become a well-known problem in high performance computing. The recent development of parallel vector systems offers the potential to bridge this gap for a significant number of computational science codes and deliver a substantial increase in computing capabilities. This paper examines the intranode performance of the NEC SX6 vector processor and the cache-based IBM Power3/4 superscalar architectures across a number of key scientific computing areas. First, we present the performance of a microbenchmark suite that examines a full spectrum of low-level machine characteristics. Next, we study the behavior of the NAS Parallel Benchmarks using some simple optimizations. Finally, we evaluate the perfor- mance of several numerical codes from key scientific computing domains. Overall results demonstrate that the SX6 achieves high performance on a large fraction of our application suite and in many cases significantly outperforms the RISC-based architectures. However, certain classes of applications are not easily amenable to vectorization and would likely require extensive reengineering of both algorithm and implementation to utilize the SX6 effectively.

Oliker, Leonid↗
NASA NTRS1989

Adaptive Strategies for Controls of Flexible Arms

An adaptive controller for a modern manipulator has been designed based on asymptotical stability via the Lyapunov criterion with the output error between the system and a reference model used as the actuating control signal. Computer simulations were carried out to test the design. The combination of the adaptive controller and a system vibration and mode shape estimator show that the flexible arm should move along a pre-defined trajectory with high-speed motion and fast vibration setting time. An existing computer-controlled prototype two link manipulator, RALF (Robotic Arm, Large Flexible), with a parallel mechanism driven by hydraulic actuators was used to verify the mathematical analysis. The experimental results illustrate that assumed modes found from finite element techniques can be used to derive the equations of motion with acceptable accuracy. The robust adaptive (modal) control is implemented to compensate for unmodelled modes and nonlinearities and is compared with the joint feedback control in additional experiments. Preliminary results show promise for the experimental control algorithm.

Yuan, Bau-San↗
NASA NTRS1991

A Large-Grain Mapping Approach for Multiprocessor Systems Through Data Flow Model Ph.D. Thesis

A large-grain level mapping method is presented of numerical oriented applications onto multiprocessor systems. The method is based on the large-grain data flow representation of the input application and it assumes a general interconnection topology of the multiprocessor system. The large-grain data flow model was used because such representation best exhibits inherited parallelism in many important applications, e.g., CFD models based on partial differential equations can be presented in large-grain data flow format, very effectively. A generalized interconnection topology of the multiprocessor architecture is considered, including such architectural issues as interprocessor communication cost, with the aim to identify the 'best matching' between the application and the multiprocessor structure. The objective is to minimize the total execution time of the input algorithm running on the target system. The mapping strategy consists of the following: (1) large-grain data flow graph generation from the input application using compilation techniques; (2) data flow graph partitioning into basic computation blocks; and (3) physical mapping onto the target multiprocessor using a priority allocation scheme for the computation blocks.

Kim, Hwa-Soo↗
NASA NTRS2012

Airborne Precision Spacing (APS) Dependent Parallel Arrivals (DPA)

The Airborne Precision Spacing (APS) team at the NASA Langley Research Center (LaRC) has been developing a concept of operations to extend the current APS concept to support dependent approaches to parallel or converging runways along with the required pilot and controller procedures and pilot interfaces. A staggered operations capability for the Airborne Spacing for Terminal Arrival Routes (ASTAR) tool was developed and designated as ASTAR10. ASTAR10 has reached a sufficient level of maturity to be validated and tested through a fast-time simulation. The purpose of the experiment was to identify and resolve any remaining issues in the ASTAR10 algorithm, as well as put the concept of operations through a practical test.

Smith, Colin L.↗
NASA NTRS2011

Fault-Tolerant, Radiation-Hard DSP

Commercial digital signal processors (DSPs) for use in high-speed satellite computers are challenged by the damaging effects of space radiation, mainly single event upsets (SEUs) and single event functional interrupts (SEFIs). Innovations have been developed for mitigating the effects of SEUs and SEFIs, enabling the use of very-highspeed commercial DSPs with improved SEU tolerances. Time-triple modular redundancy (TTMR) is a method of applying traditional triple modular redundancy on a single processor, exploiting the VLIW (very long instruction word) class of parallel processors. TTMR improves SEU rates substantially. SEFIs are solved by a SEFI-hardened core circuit, external to the microprocessor. It monitors the health of the processor, and if a SEFI occurs, forces the processor to return to performance through a series of escalating events. TTMR and hardened-core solutions were developed for both DSPs and reconfigurable field-programmable gate arrays (FPGAs). This includes advancement of TTMR algorithms for DSPs and reconfigurable FPGAs, plus a rad-hard, hardened-core integrated circuit that services both the DSP and FPGA. Additionally, a combined DSP and FPGA board architecture was fully developed into a rad-hard engineering product. This technology enables use of commercial off-the-shelf (COTS) DSPs in computers for satellite and other space applications, allowing rapid deployment at a much lower cost. Traditional rad-hard space computers are very expensive and typically have long lead times. These computers are either based on traditional rad-hard processors, which have extremely low computational performance, or triple modular redundant (TMR) FPGA arrays, which suffer from power and complexity issues. Even more frustrating is that the TMR arrays of FPGAs require a fixed, external rad-hard voting element, thereby causing them to lose much of their reconfiguration capability and in some cases significant speed reduction. The benefits of COTS high-performance signal processing include significant increase in onboard science data processing, enabling orders of magnitude reduction in required communication bandwidth for science data return, orders of magnitude improvement in onboard mission planning and critical decision making, and the ability to rapidly respond to changing mission environments, thus enabling opportunistic science and orders of magnitude reduction in the cost of mission operations through reduction of required staff. Additional benefits of COTS-based, high-performance signal processing include the ability to leverage considerable commercial and academic investments in advanced computing tools, techniques, and infra structure, and the familiarity of the science and IT community with these computing environments.

Czajkowski, David↗
NASA NTRS1990

Real-time image processing II; Proceedings of the Meeting, Orlando, FL, Apr. 16-18, 1990

The present conference discusses topics in the fields of feature extraction and implementation, filter and correlation algorithms, optical correlators, high-level algorithms, and digital image processing for ranging and remote driving. Attention is given to a nonlinear filter derived from topological image features, IR image segmentation through iterative thresholding, orthogonal subspaces for correlation masking, composite filter trees and image recognition via binary search, and features of matrix-coherent optical image processing. Also discussed are multitarget tracking via hybrid joint transform correlator, binary joint Fourier transform correlator considerations, global image processing operations on parallel architectures, real-time implementation of a differential range finder, and real-time binocular stereo range and motion detection.

Juday, Richard D.↗
NASA NTRS1998

Bell-Curve Based Evolutionary Optimization Algorithm

The paper presents an optimization algorithm that falls in the category of genetic, or evolutionary algorithms. While the bit exchange is the basis of most of the Genetic Algorithms (GA) in research and applications in America, some alternatives, also in the category of evolutionary algorithms, but use a direct, geometrical approach have gained popularity in Europe and Asia. The Bell-Curve Based Evolutionary Algorithm (BCB) is in this alternative category and is distinguished by the use of a combination of n-dimensional geometry and the normal distribution, the bell-curve, in the generation of the offspring. The tool for creating a child is a geometrical construct comprising a line connecting two parents and a weighted point on that line. The point that defines the child deviates from the weighted point in two directions: parallel and orthogonal to the connecting line, the deviation in each direction obeying a probabilistic distribution. Tests showed satisfactory performance of BCB. The principal advantage of BCB is its controllability via the normal distribution parameters and the geometrical construct variables.

Sobieszczanski-Sobieski, J.↗
NASA NTRS1980

Application of finite-element-techniques to the interaction of conduction and radiation in an absorbing, scattering and emitting medium

In this paper, the authors demonstrate that a Galerkin finite element method of analysis, utilizing isoparametric elements, offers a viable means of solving continuum thermal radiation problems with conduction in a participating medium. The participating medium was considered to be a gray radiation medium exhibiting isotropic absorption, emission, and scattering characteristics and optical properties that are independent of temperature. The medium was considered to be bounded by infinite parallel opaque, gray surfaces with diffuse emission and reflection characteristics. In solving this problem, a finite element formulation was developed to describe a system in radiative equilibrium. Then the results of this first analysis were linked with a second finite element model which incorporated conduction into the analysis. The results of this study were found to be in good agreement with existing published data. The model offers the following advantageous features: geometric generality, a computational algorithm which is 'convenient' and 'computable', and a functional basis for extension of the radiation model to higher order approximation.

Wu, S. T.↗
NASA NTRS1994

On k-ary n-cubes: Theory and applications

Many parallel processing networks can be viewed as graphs called k-ary n-cubes, whose special cases include rings, hypercubes and toruses. In this paper, combinatorial properties of k-ary n-cubes are explored. In particular, the problem of characterizing the subgraph of a given number of nodes with the maximum edge count is studied. These theoretical results are then used to compute a lower bounding function in branch-and-bound partitioning algorithms and to establish the optimality of some irregular partitions.

Mao, Weizhen↗
NASA NTRS1990

Partitioning sparse matrices with eigenvectors of graphs

The problem of computing a small vertex separator in a graph arises in the context of computing a good ordering for the parallel factorization of sparse, symmetric matrices. An algebraic approach for computing vertex separators is considered in this paper. It is shown that lower bounds on separator sizes can be obtained in terms of the eigenvalues of the Laplacian matrix associated with a graph. The Laplacian eigenvectors of grid graphs can be computed from Kronecker products involving the eigenvectors of path graphs, and these eigenvectors can be used to compute good separators in grid graphs. A heuristic algorithm is designed to compute a vertex separator in a general graph by first computing an edge separator in the graph from an eigenvector of the Laplacian matrix, and then using a maximum matching in a subgraph to compute the vertex separator. Results on the quality of the separators computed by the spectral algorithm are presented, and these are compared with separators obtained from other algorithms for computing separators. Finally, the time required to compute the Laplacian eigenvector is reported, and the accuracy with which the eigenvector must be computed to obtain good separators is considered. The spectral algorithm has the advantage that it can be implemented on a medium-size multiprocessor in a straightforward manner.

Pothen, Alex↗
NASA NTRS2003

TOMS and SBUV Data: Comparison to 3D Chemical-Transport Model Results

We have updated our merged ozone data (MOD) set using the TOMS data from the new version 8 algorithm. We then analyzed these data for contributions from solar cycle, volcanoes, QBO, and halogens using a standard statistical time series model. We have recently completed a hindcast run of our 3D chemical-transport model for the same years. This model uses off-line winds from the finite-volume GCM, a full stratospheric photochemistry package, and time-varying forcing due to halogens, solar uv, and volcanic aerosols. We will report on a parallel analysis of these model results using the same statistical time series technique as used for the MOD data.

Stolarski, Richard S.↗
NASA NTRS1991

Lunar rovers and local positioning system

Telerobotic rovers equipped with adequate actuators and sensors are clearly necessary for extraterrestrial construction. They will be employed as substitutes for humans, to perform jobs like surveying, sensing, signaling, manipulating, and the handling of small materials. Important design criteria for these rovers include versatility and robustness. They must be easily programmed and reprogrammed to perform a wide variety of different functions, and they must be robust so that construction work will not be jeopardized by parts failures. The key qualities and functions necessary for these rovers to achieve the required versatility and robustness are modularity, redundancy, and coordination. Three robotic rovers are being built by CSC as a test bed to implement the concepts of modularity and coordination. The specific goal of the design and construction of these robots is to demonstrate the software modularity and multirobot control algorithms required for the physical manipulation of constructible elements. Each rover consists of a transporter platform, bus manager, simple manipulator, and positioning receivers. These robots will be controlled from a central control console via a radio-frequency local area network (LAN). To date, one prototype transporter platform frame was built with batteries, motors, a prototype single-motor controller, and two prototype internal LAN boards. Software modules were developed in C language for monitor functions, i/o, and parallel port usage in each computer board. Also completed are the fabrication of half of the required number of computer boards, the procurement of 19.2 Kbaud RF modems for inter-robot communications, and the simulation of processing requirements for positioning receivers. In addition to the robotic platform, the fabrication of a local positioning system based on infrared signals is nearly completed. This positioning system will make the rovers into a moving reference system capable of performing site surveys. In addition, a four degree mechanical manipulator especially suited for coordinated teleoperation was conceptually designed and is currently being analyzed. This manipulator will be integrated into the rovers as their end effector. Twenty internal LAN cards fabricated by a commercial firm are being used, a prototype manipulator and a range finder for a positioning system were built, a prototype two-motor controller was designed, and one of the robots is performing its first telerobotic motion. In addition, the robots' internal LAN's were coordinated and tested, hardware design upgrades based on fabrication and fit experience were completed, and the positioning system is running. The rover system is able to perform simple tasks such as sensing and signaling; coordination systems which allow construction tasks to begin were established, and soon coordinated teams of robots in the laboratory will be able to manipulate common objects.

Avery, James↗
NASA NTRS1989

Towards real-time simulation of large space structures: Stabilization of fluid/thermal/structure interactions and implementation on high performance supercomputers

Within the Center for Space Construction, the SIMSTRUC project's objectives center around the development of simulation tools for the realistic analysis of large space structures. The word 'tools' is the broad sense; it designates mathematical models, finite element/finite difference formulations, computational algorithms, implementations on advanced computer architectures, and visualization capabilities. The results of our activities during the first year within the SIMSTRUC project are reported. On the modeling side, an alternative approach to fluid/thermal/structure interaction analysis that is a departure from the 'loosely coupled' and 'unified' approaches that are being currently practiced are described. The advantages of our approach both in terms of accuracy and computational efficiency were demonstrated. On the computational side, a software architecture for parallel/vector and massively parallel supercomputers that speeds up finite element and finite difference computations by several orders of magnitude is presented. As an example, the simulation of the deployment of a space structure that used to require over six hours of a workstation using a conventional finite element software, now runs on a multiprocessor using a parallel computation strategy in less than three seconds. In order to promote the physical understanding of the simulation behavior, a real-time visualization capability on the Connection Machine, which allows the analyst to watch the graphical animation of the results at the same time these are generated, was also developed. It is believed that by combining efficient analytical formulations with the state-of-the-art high performance computer implementations and superfast visualization capabilities, SIMSTRUC is moving fast towards the real-time simulation of large space structures. The designers as well as the researchers will certainly benefit from this technology.

Farhat, C.↗
NASA NTRS2000

Development of a Wake Vortex Spacing System for Airport Capacity Enhancement and Delay Reduction

The Terminal Area Productivity project has developed the technologies required (weather measurement, wake prediction, and wake measurement) to determine the aircraft spacing needed to prevent wake vortex encounters in various weather conditions. The system performs weather measurements, predicts bounds on wake vortex behavior in those conditions, derives safe wake spacing criteria, and validates the wake predictions with wake vortex measurements. System performance to date indicates that the potential runway arrival rate increase with Aircraft VOrtex Spacing System (AVOSS), considering common path effects and ATC delivery variance, is 5% to 12% depending on the ratio of large and heavy aircraft. The concept demonstration system, using early generation algorithms and minimal optimization, is performing the wake predictions with adequate robustness such that only 4 hard exceedances have been observed in 1235 wake validation cases. This performance demonstrates the feasibility of predicting wake behavior bounds with multiple uncertainties present, including the unknown aircraft weight and speed, weather persistence between the wake prediction and the observations, and the location of the weather sensors several kilometers from the approach location. A concept for the use of the AVOSS system for parallel runway operations has been suggested, and an initial study at the JFK International Airport suggests that a simplified AVOSS system can be successfully operated using only a single lidar as both the weather sensor and the wake validation instrument. Such a selfcontained AVOSS would be suitable for wake separation close to the airport, as is required for parallel approach concepts such as SOIA.

Hinton, David A.↗
NASA NTRS2010

Reconfigurable Hardware for Compressing Hyperspectral Image Data

High-speed, low-power, reconfigurable electronic hardware has been developed to implement ICER-3D, an algorithm for compressing hyperspectral-image data. The algorithm and parts thereof have been the topics of several NASA Tech Briefs articles, including Context Modeler for Wavelet Compression of Hyperspectral Images (NPO-43239) and ICER-3D Hyperspectral Image Compression Software (NPO-43238), which appear elsewhere in this issue of NASA Tech Briefs. As described in more detail in those articles, the algorithm includes three main subalgorithms: one for computing wavelet transforms, one for context modeling, and one for entropy encoding. For the purpose of designing the hardware, these subalgorithms are treated as modules to be implemented efficiently in field-programmable gate arrays (FPGAs). The design takes advantage of industry- standard, commercially available FPGAs. The implementation targets the Xilinx Virtex II pro architecture, which has embedded PowerPC processor cores with flexible on-chip bus architecture. It incorporates an efficient parallel and pipelined architecture to compress the three-dimensional image data. The design provides for internal buffering to minimize intensive input/output operations while making efficient use of offchip memory. The design is scalable in that the subalgorithms are implemented as independent hardware modules that can be combined in parallel to increase throughput. The on-chip processor manages the overall operation of the compression system, including execution of the top-level control functions as well as scheduling, initiating, and monitoring processes. The design prototype has been demonstrated to be capable of compressing hyperspectral data at a rate of 4.5 megasamples per second at a conservative clock frequency of 50 MHz, with a potential for substantially greater throughput at a higher clock frequency. The power consumption of the prototype is less than 6.5 W. The reconfigurability (by means of reprogramming) of the FPGAs makes it possible to effectively alter the design to some extent to satisfy different requirements without adding hardware. The implementation could be easily propagated to future FPGA generations and/or to custom application-specific integrated circuits.

Aranki, Nazeeh↗