Search NASA⌕ Search

SEARCH · Search NASA

Results for “Shared-Memory Parallel”

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 19 records
All sourcesNASA NTRSDOE OSTI
NASA NTRS1993

Dynamic programming on a shared-memory multiprocessor

Three new algorithms for solving dynamic programming problems on a shared-memory parallel computer are described. All three algorithms attempt to balance work load, while keeping synchronization cost low. In particular, for a multiprocessor having p processors, an analysis of the best algorithm shows that the arithmetic cost is O(n-cubed/6p) and that the synchronization cost is O(absolute value of log sub C n) if p much less than n, where C = (2p-1)/(2p + 1) and n is the size of the problem. The low synchronization cost is important for machines where synchronization is expensive. Analysis and experiments show that the best algorithm is effective in balancing the work load and producing high efficiency.

Edmonds, Phil↗
NASA NTRS1992

Hypercluster Parallel Processor

Hypercluster computer system includes multiple digital processors, operation of which coordinated through specialized software. Configurable according to various parallel-computing architectures of shared-memory or distributed-memory class, including scalar computer, vector computer, reduced-instruction-set computer, and complex-instruction-set computer. Designed as flexible, relatively inexpensive system that provides single programming and operating environment within which one can investigate effects of various parallel-computing architectures and combinations on performance in solution of complicated problems like those of three-dimensional flows in turbomachines. Hypercluster software and architectural concepts are in public domain.

Blech, Richard A.↗
NASA NTRS1988

Parafrase restructuring of FORTRAN code for parallel processing

Parafrase transforms a FORTRAN code, subroutine by subroutine, into a parallel code for a vector and/or shared-memory multiprocessor system. Parafrase is not a compiler; it transforms a code and provides information for a vector or concurrent process. Parafrase uses a data dependency to reveal parallelism among instructions. The data dependency test distinguishes between recurrences and statements that can be directly vectorized or parallelized. A number of transformations are required to build a data dependency graph.

Wadhwa, Atul↗
NASA NTRS1991

T on the Cray X/MP

This research was aimed at porting the T programming language, a dialect of LISP, to the Cray X/MP computer. The effort involved research into systems engineering and software engineering problems related not only to compiler design and implementation, but also to parallel computation, the X/MP being a shared-memory multiprocessor. Porting also involved the sub-tasks of retargeting the assembler, code-generator, and run-time system. A reasonably effective porting methodology that is relatively straight forward, although more difficult than table-driven approaches, has been developed. The run-time system was not ported, and thus the T programs cannot be run without explicit linking of the required run-time support. The run-time performance gain achieved in generated code was found to be disappointing. Recommendations for the achievement of higher performance are given.

Hudak, Paul↗
NASA NTRS1989

The FORCE - A highly portable parallel programming language

This paper explains why the FORCE parallel programming language is easily portable among six different shared-memory multiprocessors, and how a two-level macro preprocessor makes it possible to hide low-level machine dependencies and to build machine-independent high-level constructs on top of them. These FORCE constructs make it possible to write portable parallel programs largely independent of the number of processes and the specific shared-memory multiprocessor executing them.

Jordan, Harry F.↗
NASA NTRS1991

Experimental evaluation of multiprocessor cache-based error recovery

Several variations of cache-based checkpointing for rollback error recovery in shared-memory multiprocessors have been recently developed. By modifying the cache replacement policy, these techniques use the inherent redundancy in the memory hierarchy to periodically checkpoint the computation state. Three schemes, different in the manner in which they avoid rollback propagation, are evaluated. By simulation with address traces from parallel applications running on an Encore Multimax shared-memory multiprocessor, the performance effect of integrating the recovery schemes in the cache coherence protocol are evaluated. The results indicate that the cache-based schemes can provide checkpointing capability with low performance overhead but uncontrollable high variability in the checkpoint interval.

Janssens, Bob↗
NASA NTRS1989

The FORCE: A highly portable parallel programming language

Here, it is explained why the FORCE parallel programming language is easily portable among six different shared-memory microprocessors, and how a two-level macro preprocessor makes it possible to hide low level machine dependencies and to build machine-independent high level constructs on top of them. These FORCE constructs make it possible to write portable parallel programs largely independent of the number of processes and the specific shared memory multiprocessor executing them.

Jordan, Harry F.↗
NASA NTRS1991

Implementation of a partitioned algorithm for simulation of large CSI problems

The implementation of a partitioned numerical algorithm for determining the dynamic response of coupled structure/controller/estimator finite-dimensional systems is reviewed. The partitioned approach leads to a set of coupled first and second-order linear differential equations which are numerically integrated with extrapolation and implicit step methods. The present software implementation, ACSIS, utilizes parallel processing techniques at various levels to optimize performance on a shared-memory concurrent/vector processing system. A general procedure for the design of controller and filter gains is also implemented, which utilizes the vibration characteristics of the structure to be solved. Also presented are: example problems; a user's guide to the software; the procedures and algorithm scripts; a stability analysis for the algorithm; and the source code for the parallel implementation.

Alvin, Kenneth F.↗
NASA NTRS1992

Address tracing of parallel systems via TRAPEDS

Trace-driven simulation is an important aid in performance analysis of computer systems. Capturing address traces to use in these simulations, however, is a difficult problem for parallel processor architectures. A technique termed TRAPEDS modifies executable code (at the assembly language level) to dynamically collect the address trace from executing code. TRAPEDS has recently been implemented on both a hypercube multicomputer and a shared-memory multiprocessor. Particular attention is focused on strategies for efficiently and accurately collecting traces from both classes of parallel machines. The iPSC/2 hypercube multicomputer implementation traces both user and system code, and performs simulation on-the-fly to avoid large storage costs. Strategies are detailed for mitigating address trace distortion when collecting operating system traces. The Encore Multimax multiprocessor implementation uses a timer-based approach to reflect the interleaving of the processor traces and stores the traces to disc. Time and space overhead results are presented for both TRAPEDS implementations. Experimental cache simulation results derived from iPSC/2 address traces are presented to illustrate the importance of tracing operating system references.

Stunkel, Craig B.↗
NASA NTRS1988

Parallel discrete event simulation using shared memory

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

Reed, Daniel A.↗
NASA NTRS1992

A simple modern correctness condition for a space-based high-performance multiprocessor

A number of U.S. national programs, including space-based detection of ballistic missile launches, envisage putting significant computing power into space. Given sufficient progress in low-power VLSI, multichip-module packaging and liquid-cooling technologies, we will see design of high-performance multiprocessors for individual satellites. In very high speed implementations, performance depends critically on tolerating large latencies in interprocessor communication; without latency tolerance, performance is limited by the vastly differing time scales in processor and data-memory modules, including interconnect times. The modern approach to tolerating remote-communication cost in scalable, shared-memory multiprocessors is to use a multithreaded architecture, and alter the semantics of shared memory slightly, at the price of forcing the programmer either to reason about program correctness in a relaxed consistency model or to agree to program in a constrained style. The literature on multiprocessor correctness conditions has become increasingly complex, and sometimes confusing, which may hinder its practical application. We propose a simple modern correctness condition for a high-performance, shared-memory multiprocessor; the correctness condition is based on a simple interface between the multiprocessor architecture and a high-performance, shared-memory multiprocessor; the correctness condition is based on a simple interface between the multiprocessor architecture and the parallel programming system.

Probst, David K.↗
NASA NTRS1990

A parallel algorithm for global routing

A Parallel Hierarchical algorithm for Global Routing (PHIGURE) is presented. The router is based on the work of Burstein and Pelavin, but has many extensions for general global routing and parallel execution. Main features of the algorithm include structured hierarchical decomposition into separate independent tasks which are suitable for parallel execution and adaptive simplex solution for adding feedthroughs and adjusting channel heights for row-based layout. Alternative decomposition methods and the various levels of parallelism available in the algorithm are examined closely. The algorithm is described and results are presented for a shared-memory multiprocessor implementation.

Brouwer, Randall J.↗
NASA NTRS1991

Modeling and measuring multiprogramming and system overheads on a shared-memory multiprocessor - Case study

The present discussion of methods for quantifying multiprogramming (MP) overhead on a computer system illustrates two such techniques, respectively for quantifying MP overheads' lower bound and determining the MP overload of real workloads, in light of the percentage of parallel processing time that is consumed by MP overhead on Alliant multiprocessors. Kernel lock spinning is found to be a major factor in MP overhead, which accounts for more than half of total system overhead. It is noted that parallel environments' MP overhead is not statistically dependent on the number of parallel jobs undergoing multiprogramming.

Dimpsey, Robert T.↗
NASA NTRS1990

Concurrent Finite-Element Analysis On Hypercube Computers

Improved approach to execution of finite-element codes on hypercube and similar concurrent data processors increases efficiency of computation for many different types of problems. Based on flexible general model of computation on, and communication among, large-node parallel processors. Hybrid combining direct methods within subdomains and preconditioned-conjugate-gradient (PCG) iteration on remaining boundary system to obtain method of solution both robust and efficient. Preserves general structure and function of conventional sequential finite-element-method software. Generalized to both distributed- and shared-memory multicomputers, eliminating degree of machine specificity restricting general usefulness.

Lyzenga, G. A.↗
NASA NTRS1989

Initial operating capability for the hypercluster parallel-processing test bed

The NASA Lewis Research Center is investigating the benefits of parallel processing to applications in computational fluid and structural mechanics. To aid this investigation, NASA Lewis is developing the Hypercluster, a multi-architecture, parallel-processing test bed. The initial operating capability (IOC) being developed for the Hypercluster is described. The IOC will provide a user with a programming/operating environment that is interactive, responsive, and easy to use. The IOC effort includes the development of the Hypercluster Operating System (HYCLOPS). HYCLOPS runs in conjunction with a vendor-supplied disk operating system on a Front-End Processor (FEP) to provide interactive, run-time operations such as program loading, execution, memory editing, and data retrieval. Run-time libraries, that augment the FEP FORTRAN libraries, are being developed to support parallel and vector processing on the Hypercluster. Special utilities are being provided to enable passage of information about application programs and their mapping to the operating system. Communications between the FEP and the Hypercluster are being handled by dedicated processors, each running a Message-Passing Kernel, (MPK). A shared-memory interface allows rapid data exchange between HYCLOPS and the communications processors. Input/output handlers are built into the HYCLOPS-MPK interface, eliminating the need for the user to supply separate I/O support programs on the FEP.

Cole, Gary L.↗
NASA NTRS1991

A parallel vectorized implementation of triple excitations in CCSD(T) - Application to the binding energies of the AlH3, AlH2F, AlHF2 and AlF3 dimers

An efficient method for various noniterative estimates of connected triple excitations in coupled-cluster theory is outlined and related to a similar expression occurring in Moller-Plesset perturbation theory. The method is highly vectorized and capable of utilizing multiple processors on a shared-memory machine, leading to computational rates in excess of one billion floating-point operations per second on four processors of a CRAY Y-MP. Using the new procedure, the binding energies of the D(2h) diborane-type dimers of AlH3, AlH2F, AlHF2, and AlF3 have been determined to be 32, 40, 20, and 47 kcal/mol, respectively. For Al2F6, the correlation procedure includes 232 molecular orbitals and over 1.5 x 10 to the 6th single and double coupled-cluster amplitudes, effectively accounting for over 2 x 10 to the 9th connected triple excitations.

Rendell, Alistair P.↗
NASA NTRS1991

Parallel computation of aerodynamic influence coefficients for aeroelastic analysis on a transputer network

Aeroelastic analysis is mult-disciplinary and computationally expensive. Hence, it can greatly benefit from parallel processing. As part of an effort to develop an aeroelastic analysis capability on a distributed-memory transputer network, a parallel algorithm for the computation of aerodynamic influence coefficients is implemented on a network of 32 transputers. The aerodynamic influence coefficients are calculated using a three-dimensional unsteady aerodynamic model and a panel discretization. Efficiencies up to 85 percent are demonstrated using 32 processors. The effects of subtask ordering, problem size and network topology are presented. A comparison to results on a shared-memory computer indicates that higher speedup is achieved on the distributed-memory system.

Janetzke, D. C.↗
NASA NTRS1987

Analysis of a parallelized nonlinear elliptic boundary value problem solver with application to reacting flows

A parallelized finite difference code based on the Newton method for systems of nonlinear elliptic boundary value problems in two dimensions is analyzed in terms of computational complexity and parallel efficiency. An approximate cost function depending on 15 dimensionless parameters is derived for algorithms based on stripwise and boxwise decompositions of the domain and a one-to-one assignment of the strip or box subdomains to processors. The sensitivity of the cost functions to the parameters is explored in regions of parameter space corresponding to model small-order systems with inexpensive function evaluations and also a coupled system of nineteen equations with very expensive function evaluations. The algorithm was implemented on the Intel Hypercube, and some experimental results for the model problems with stripwise decompositions are presented and compared with the theory. In the context of computational combustion problems, multiprocessors of either message-passing or shared-memory type may be employed with stripwise decompositions to realize speedup of O(n), where n is mesh resolution in one direction, for reasonable n.

Keyes, David E.↗