SEARCH · Engineering Papers

Results for “pipeline”

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 109 records · Page 6

All sources NASA NTRS DOE OSTI

NASA NTRS1983

A parallel-pipeline architecture of the fast polynomial transform for computing a two-dimensional cyclic convolution

It is pointed out that the two-dimensional cyclic convolution is a useful tool for many two-dimensional digital signal processing applications. Two important applications are related to spaceborne high-resolution synthetic aperture radar (SAR) processing and image processing. Nussbaumer and Quandalle (1978) showed that a radix-2 polynomial transform analogous to the conventional radix-2 FFT algorithm can be used to compute a two-dimensional cyclic convolution. On the basis of results reported by Arambepola and Rayner (1979), a radix-2 polynomial transform can be defined to compute a multidimensional cyclic convolution. Truong et al. (1981) used the considered ideas together with the Chinese Theorem to further reduce the complexity of the radix-2 fast polynomial transform (FPT). Reed et al. (1981) demonstrated that such a new FPT algorithm is significantly faster than the FFT algorithm for computing a two-dimensional convolution. In the present investigation, a parallel-pipeline architecture is considered for implementing the FPT developed by Truong et al.

Truong, T. K.↗

NASA NTRS1984

A Systolic VLSI Design of a Pipeline Reed-solomon Decoder

A pipeline structure of a transform decoder similar to a systolic array was developed to decode Reed-Solomon (RS) codes. An important ingredient of this design is a modified Euclidean algorithm for computing the error locator polynomial. The computation of inverse field elements is completely avoided in this modification of Euclid's algorithm. The new decoder is regular and simple, and naturally suitable for VLSI implementation.

Shao, H. M.↗

NASA NTRS1984

Pipelined digital SAR azimuth correlator using hybrid FFT-transversal filter

A synthetic aperture radar system (SAR) having a range correlator is provided with a hybrid azimuth correlator which utilizes a block-pipe-lined fast Fourier transform (FFT). The correlator has a predetermined FFT transform size with delay elements for delaying SAR range correlated data so as to embed in the Fourier transform operation a corner-turning function as the range correlated SAR data is converted from the time domain to a frequency domain. The azimuth correlator is comprised of a transversal filter to receive the SAR data in the frequency domain, a generator for range migration compensation and azimuth reference functions, and an azimuth reference multiplier for correlation of the SAR data. Following the transversal filter is a block-pipelined inverse FFT used to restore azimuth correlated data in the frequency domain to the time domain for imaging.

Wu, C.↗

NASA NTRS1983

Parallelism and pipelining in high-speed digital simulators

The attainment of high computing speed as measured by the computational throughput is seen as one of the most challenging requirements. It is noted that high speed is cardinal in several distinct classes of applications. These classes are then discussed; they comprise (1) the real-time simulation of dynamic systems , (2) distributed parameter systems, and (3) mixed lumped and distributed systems. From the 1950s on, the quest for high speed in digital simulators concentrated on overcoming the limitations imposed by the so-called von Neumann bottleneck. Two major architectural approaches have made ig possible to circumvent this bottleneck and attain high speeds. These are pipelining and parallelism. Supercomputers, peripheral array processors, and microcomputer networks are then discussed.

Karplus, W. J.↗

NASA NTRS1985

A VLSI design of a pipeline Reed-Solomon decoder

Shao, H. M.↗

NASA NTRS1985

PIFEX: An advanced programmable pipelined-image processor

PIFEX is a pipelined-image processor being built in the JPL Robotics Lab. It will operate on digitized raster-scanned images (at 60 frames per second for images up to about 300 by 400 and at lesser rates for larger images), performing a variety of operations simultaneously under program control. It thus is a powerful, flexible tool for image processing and low-level computer vision. It also has applications in other two-dimensional problems such as route planning for obstacle avoidance and the numerical solution of two-dimensional partial differential equations (although its low numerical precision limits its use in the latter field). The concept and design of PIFEX are described herein, and some examples of its use are given.

Gennery, D. B.↗

NASA NTRS1985

Partitioning problems in parallel, pipelined and distributed computing

The problem of optimally assigning the modules of a parallel program over the processors of a multiple computer system is addressed. A Sum-Bottleneck path algorithm is developed that permits the efficient solution of many variants of this problem under some constraints on the structure of the partitions. In particular, the following problems are solved optimally for a single-host, multiple satellite system: partitioning multiple chain structured parallel programs, multiple arbitrarily structured serial programs and single tree structured parallel programs. In addition, the problems of partitioning chain structured parallel programs across chain connected systems and across shared memory (or shared bus) systems are also solved under certain constraints. All solutions for parallel programs are equally applicable to pipelined programs. These results extend prior research in this area by explicitly taking concurrency into account and permit the efficient utilization of multiple computer architectures for a wide range of problems of practical interest.

Bokhari, S.↗

NASA NTRS1986

A reliable pipelining protocol for the message service of the Mobile Satellite Experiment

This paper describes and analyzes a pipelining protocol for the data message communications of MSAT-X, a proposed experimental satellite-based mobile communications network. A demand assigned multiple access protocol using pure ALOHA for making reservation requests has been developed for MSAT-X under error-free assumptions. Preliminary propagation studies indicate that the short term bit error rate of satellite channels in a mobile environment can be as high as 0.001. Therefore, error-control schemes must be developed to ensure reliable transmissions. A retransmission scheme using selective repeat to minimize the end-to-end delay is proposed. Slotted ALOHA for making reservation requests is used to increase the overall system throughput. Since the number of channels available for reservation and data channels is essentially fixed for a given voice call blocking probability and a fixed call arrival rate, the analysis presented in this paper is also applicable to the integrated voice and data services of MSAT-X. Various operational scenarios have been investigated.

Li, V. O. K.↗

NASA NTRS1988

Partitioning problems in parallel, pipelined, and distributed computing

The problem of optimally assigning the modules of a parallel program over the processors of a multiple-computer system is addressed. A sum-bottleneck path algorithm is developed that permits the efficient solution of many variants of this problem under some constraints on the structure of the partitions. In particular, the following problems are solved optimally for a single-host, multiple-satellite system: partitioning multiple chain-structured parallel programs, multiple arbitrarily structured serial programs, and single-tree structured parallel programs. In addition, the problem of partitioning chain-structured parallel programs across chain-connected systems is solved under certain constraints. All solutions for parallel programs are equally applicable to pipelined programs. These results extend prior research in this area by explicitly taking concurrency into account and permit the efficient utilization of multiple-computer architectures for a wide range of problems of practical interest.

Bokhari, Shahid H.↗

NASA NTRS1988

Programmable pipelined image processor

A pipelined image processor selectively interconnects modules in a column of a two-dimensional array to modules of the next column of the array of modules 1,1 through M,N, where M is the number of modules in one dimension and N is the number of modules in the other direction. Each module includes two input selectors for A and B inputs, two convolvers, a binary function operator, a neighborhood comparison operator which produces an A output and an output selector which may select as a B output the output of any one of the components in the module, including the A output of the neighborhood comparison operator. Each module may be connected to as many as eight modules in the next column, preferably with the majority always in a different row that is up (or down) in the array for a generally spiral data path around the torus thus formed. The binary function operator is implemented as a look-up table addressed by the most significant 8 bits of each 12-bit argument. The table output includes a function value and the slopes for interpolation of the two arguments by multiplying the 4 least significant bits in multipliers and adding the products to the function value through adders.

Donald B Gennery↗

NASA NTRS1991

Video Pipeline Tree For Scan Conversion Of Triangles

Scenes containing many polygons generated in real time. Video pipeline subsystem having branched structure performs scan conversion of polygons in images generated by computers. New subsystem divides polygons into triangles, each of which processed rapidly in parallel, modular fashion and merged into image.

Robinett, Warren↗

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

Improved algorithms for mapping pipelined and parallel computations

Recent work on the problem of mapping pipelined or parallel computations onto linear array, shared memory, and host-satellite systems is extended. It is shown how these problems can be solved even more efficiently when computation module execution times are bounded from below, intermodule communication times are bounded from above, and the processors satisfy certain homogeneity constraints. The improved algorithms have significantly lower time and space complexities than the more general algorithms: in one case, an O(nm3) time algorithm for mapping m modules onto n processors is replaced with an O(nm log m) time algorithm, and the space requirements are reduced from O(nm2) to O(m). Run-time complexity is reduced further with parallel mapping algorithms based on these improvements, which run on the architectures for which they create mappings.

Nicol, David M.↗

NASA NTRS1991

Optimal processor assignment for pipeline computations

The availability of large scale multitasked parallel architectures introduces the following processor assignment problem for pipelined computations. Given a set of tasks and their precedence constraints, along with their experimentally determined individual responses times for different processor sizes, find an assignment of processor to tasks. Two objectives are of interest: minimal response given a throughput requirement, and maximal throughput given a response time requirement. These assignment problems differ considerably from the classical mapping problem in which several tasks share a processor; instead, it is assumed that a large number of processors are to be assigned to a relatively small number of tasks. Efficient assignment algorithms were developed for different classes of task structures. For a p processor system and a series parallel precedence graph with n constituent tasks, an O(np2) algorithm is provided that finds the optimal assignment for the response time optimization problem; it was found that the assignment optimizing the constrained throughput in O(np2log p) time. Special cases of linear, independent, and tree graphs are also considered.

Nicol, David M.↗

NASA NTRS1990

Pipeline issues

The declining pool of graduates, the lack of rigorous preparation in science and mathematics, and the declining interest in science and engineering careers at the precollege level promises a shortage of technically educated personnel at the college level for industry, government, and the universities in the next several decades. The educational process, which starts out with a large number of students at the elementary level, but with an ever smaller number preparing for science and engineering at each more advanced educational level, is in a state of crisis. These pipeline issues, so called because the educational process is likened to a series of ever smaller constrictions in a pipe, were examined in a workshop at the Space Grant Conference and a summary of the presentations and the results of the discussion, and the conclusions of the workshop participants are reported.

Eisley, Joe T.↗

NASA NTRS1990

High performance pipelined multiplier with fast carry-save adder

A high-performance pipelined multiplier is described. Its high performance results from the fast carry-save adder basic cell which has a simple structure and is suitable for the Gate Forest semi-custom environment. The carry-save adder computes the sum and carry within two gate delay. Results show that the proposed adder can operate at 200 MHz for a 2-micron CMOS process; better performance is expected in a Gate Forest realization.

Wu, Angus↗

NASA NTRS1993

Storage media pipelining: Making good use of fine-grained media

This paper proposes a new high-performance paradigm for accessing removable media such as tapes and especially magneto-optical disks. In high-performance computing the striping of data across multiple devices is a common means of improving data transfer rates. Striping has been used very successfully for fixed magnetic disks improving overall system reliability as well as throughput. It has also been proposed as a solution for providing improved bandwidth for tape and magneto-optical subsystems. However, striping of removable media has shortcomings, particularly in the areas of latency to data and restricted system configurations, and is suitable primarily for very large I/Os. We propose that for fine-grained media, an alternative access method, media pipelining, may be used to provide high bandwidth for large requests while retaining the flexibility to support concurrent small requests and different system configurations. Its principal drawback is high buffering requirements in the host computer or file server. This paper discusses the possible organization of such a system including the hardware conditions under which it may be effective, and the flexibility of configuration. Its expected performance is discussed under varying workloads including large single I/O's and numerous smaller ones. Finally, a specific system incorporating a high-transfer-rate magneto-optical disk drive and autochanger is discussed.

Vanmeter, Rodney↗

NASA NTRS1994

Maglev crude oil pipeline

This maglev crude oil pipeline consists of two conduits guiding an endless stream of long containers. One conduit carries loaded containers and the other empty returns. The containers are levitated by permanent magnets in repulsion and propelled by stationary linear induction motors. The containers are linked to each other in a manner that allows them, while in continuous motion, to be folded into side by side position at loading and unloading points. This folding causes a speed reduction in proportion to the ratio of container diameter to container length. While in side by side position, containers are opened at their ends to be filled or emptied. Container size and speed are elected to produce a desired carrying capacity.

Knolle, Ernst G.↗