SEARCH · Engineering Papers

Results for “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.

SourceResearch connectionFrom yearThrough year

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

At least 343 records · Page 19

All sources NASA NTRS DOE OSTI

NASA NTRS1986

Experimental Parallel-Processing Computer

Master processor supervises slave processors, each with its own memory. Computer with parallel processing serves as inexpensive tool for experimentation with parallel mathematical algorithms. Speed enhancement obtained depends on both nature of problem and structure of algorithm used. In parallel-processing architecture, "bank select" and control signals determine which one, if any, of N slave processor memories accessible to master processor at any given moment. When so selected, slave memory operates as part of master computer memory. When not selected, slave memory operates independently of main memory. Slave processors communicate with each other via input/output bus.

Mcgregor, J. W.↗

NASA NTRS1987

Parallel image compression

A parallel compression algorithm for the 16,384 processor MPP machine was developed. The serial version of the algorithm can be viewed as a combination of on-line dynamic lossless test compression techniques (which employ simple learning strategies) and vector quantization. These concepts are described. How these concepts are combined to form a new strategy for performing dynamic on-line lossy compression is discussed. Finally, the implementation of this algorithm in a massively parallel fashion on the MPP is discussed.

Reif, John H.↗

NASA NTRS1989

A Computational Fluid Dynamics Algorithm on a Massively Parallel Computer

The discipline of computational fluid dynamics is demanding ever-increasing computational power to deal with complex fluid flow problems. We investigate the performance of a finite-difference computational fluid dynamics algorithm on a massively parallel computer, the Connection Machine. Of special interest is an implicit time-stepping algorithm; to obtain maximum performance from the Connection Machine, it is necessary to use a nonstandard algorithm to solve the linear systems that arise in the implicit algorithm. We find that the Connection Machine ran achieve very high computation rates on both explicit and implicit algorithms. The performance of the Connection Machine puts it in the same class as today's most powerful conventional supercomputers.

Jespersen, Dennis C.↗

NASA NTRS1995

Parallel rendering

This article provides a broad introduction to the subject of parallel rendering, encompassing both hardware and software systems. The focus is on the underlying concepts and the issues which arise in the design of parallel rendering algorithms and systems. We examine the different types of parallelism and how they can be applied in rendering applications. Concepts from parallel computing, such as data decomposition, task granularity, scalability, and load balancing, are considered in relation to the rendering problem. We also explore concepts from computer graphics, such as coherence and projection, which have a significant impact on the structure of parallel rendering algorithms. Our survey covers a number of practical considerations as well, including the choice of architectural platform, communication and memory requirements, and the problem of image assembly and display. We illustrate the discussion with numerous examples from the parallel rendering literature, representing most of the principal rendering methods currently used in computer graphics.

Crockett, Thomas W.↗

NASA NTRS1997

Computational Issues in Damping Identification for Large Scale Problems

Two damping identification methods are tested for efficiency in large-scale applications. One is an iterative routine, and the other a least squares method. Numerical simulations have been performed on multiple degree-of-freedom models to test the effectiveness of the algorithm and the usefulness of parallel computation for the problems. High Performance Fortran is used to parallelize the algorithm. Tests were performed using the IBM-SP2 at NASA Ames Research Center. The least squares method tested incurs high communication costs, which reduces the benefit of high performance computing. This method's memory requirement grows at a very rapid rate meaning that larger problems can quickly exceed available computer memory. The iterative method's memory requirement grows at a much slower pace and is able to handle problems with 500+ degrees of freedom on a single processor. This method benefits from parallelization, and significant speedup can he seen for problems of 100+ degrees-of-freedom.

Pilkey, Deborah L.↗

NASA NTRS1996

Parallel Newton-Krylov-Schwarz algorithms for the transonic full potential equation

We study parallel two-level overlapping Schwarz algorithms for solving nonlinear finite element problems, in particular, for the full potential equation of aerodynamics discretized in two dimensions with bilinear elements. The overall algorithm, Newton-Krylov-Schwarz (NKS), employs an inexact finite-difference Newton method and a Krylov space iterative method, with a two-level overlapping Schwarz method as a preconditioner. We demonstrate that NKS, combined with a density upwinding continuation strategy for problems with weak shocks, is robust and, economical for this class of mixed elliptic-hyperbolic nonlinear partial differential equations, with proper specification of several parameters. We study upwinding parameters, inner convergence tolerance, coarse grid density, subdomain overlap, and the level of fill-in in the incomplete factorization, and report their effect on numerical convergence rate, overall execution time, and parallel efficiency on a distributed-memory parallel computer.

Cai, Xiao-Chuan↗

DOE OSTI2020

Parallel performance of algebraic multigrid domain decomposition

Algebraic multigrid (AMG) is a widely used scalable solver and preconditioner for large-scale linear systems resulting from the discretization of a wide class of elliptic PDEs. While AMG has optimal computational complexity, the cost of communication has become a significant bottleneck that limits its scalability as processor counts continue to grow on modern machines. This article examines the design, implementation, and parallel performance of a novel algorithm, algebraic multigrid domain decomposition (AMG-DD), designed specifically to limit communication. The goal of AMG-DD is to provide a low-communication alternative to standard AMG V-cycles by trading some additional computational overhead for a significant reduction in communication cost. Numerical results show that AMG-DD achieves superior accuracy per communication cost compared with AMG, and speedup over AMG is demonstrated on a large GPU cluster.

97 MATHEMATICS AND COMPUTING↗

NASA NTRS1998

Globalized Newton-Krylov-Schwarz Algorithms and Software for Parallel Implicit CFD

Implicit solution methods are important in applications modeled by PDEs with disparate temporal and spatial scales. Because such applications require high resolution with reasonable turnaround, "routine" parallelization is essential. The pseudo-transient matrix-free Newton-Krylov-Schwarz (Psi-NKS) algorithmic framework is presented as an answer. We show that, for the classical problem of three-dimensional transonic Euler flow about an M6 wing, Psi-NKS can simultaneously deliver: globalized, asymptotically rapid convergence through adaptive pseudo- transient continuation and Newton's method-, reasonable parallelizability for an implicit method through deferred synchronization and favorable communication-to-computation scaling in the Krylov linear solver; and high per- processor performance through attention to distributed memory and cache locality, especially through the Schwarz preconditioner. Two discouraging features of Psi-NKS methods are their sensitivity to the coding of the underlying PDE discretization and the large number of parameters that must be selected to govern convergence. We therefore distill several recommendations from our experience and from our reading of the literature on various algorithmic components of Psi-NKS, and we describe a freely available, MPI-based portable parallel software implementation of the solver employed here.

Gropp, W. D.↗

DOE OSTI2023

Massively-parallel Lagrangian particle code and applications

Massively-parallel, distributed-memory algorithms for the Lagrangian particle hydrodynamic method (Samulyak et al., 2018) have been developed, verified, and implemented. The key component of parallel algorithms is a particle management module that includes a parallel construction of octree databases, dynamic adaptation and refinement of octrees, and particle migration between parallel subdomains. The particle management module is based on the p4est (parallel forest of k-trees) library. The massively-parallel Lagrangian particle code has been applied to a variety of fundamental science and applied problems. A summary of Lagrangian particle code applications to the injection of impurities into thermonuclear fusion devices and to the simulation of supersonic hydrogen jets in support of laser-plasma wakefield acceleration research has also been presented.

97 MATHEMATICS AND COMPUTING↗

NASA NTRS1998

Parallelization of the Pipelined Thomas Algorithm

In this study the following questions are addressed. Is it possible to improve the parallelization efficiency of the Thomas algorithm? How should the Thomas algorithm be formulated in order to get solved lines that are used as data for other computational tasks while processors are idle? To answer these questions, two-step pipelined algorithms (PAs) are introduced formally. It is shown that the idle processor time is invariant with respect to the order of backward and forward steps in PAs starting from one outermost processor. The advantage of PAs starting from two outermost processors is small. Versions of the pipelined Thomas algorithms considered here fall into the category of PAs. These results show that the parallelization efficiency of the Thomas algorithm cannot be improved directly. However, the processor idle time can be used if some data has been computed by the time processors become idle. To achieve this goal the Immediate Backward pipelined Thomas Algorithm (IB-PTA) is developed in this article. The backward step is computed immediately after the forward step has been completed for the first portion of lines. This enables the completion of the Thomas algorithm for some of these lines before processors become idle. An algorithm for generating a static processor schedule recursively is developed. This schedule is used to switch between forward and backward computations and to control communications between processors. The advantage of the IB-PTA over the basic PTA is the presence of solved lines, which are available for other computations, by the time processors become idle.

Povitsky, A.↗

NASA NTRS2013

Experiments with a Parallel Multi-Objective Evolutionary Algorithm for Scheduling

Evolutionary multi-objective algorithms have great potential for scheduling in those situations where tradeoffs among competing objectives represent a key requirement. One challenge, however, is runtime performance, as a consequence of evolving not just a single schedule, but an entire population, while attempting to sample the Pareto frontier as accurately and uniformly as possible. The growing availability of multi-core processors in end user workstations, and even laptops, has raised the question of the extent to which such hardware can be used to speed up evolutionary algorithms. In this paper we report on early experiments in parallelizing a Generalized Differential Evolution (GDE) algorithm for scheduling long-range activities on NASA's Deep Space Network. Initial results show that significant speedups can be achieved, but that performance does not necessarily improve as more cores are utilized. We describe our preliminary results and some initial suggestions from parallelizing the GDE algorithm. Directions for future work are outlined.

scheduling↗

DOE OSTI2021

ParChain: a framework for parallel hierarchical agglomerative clustering using nearest-neighbor chain

This paper studies the hierarchical clustering problem, where the goal is to produce a dendrogram that represents clusters at varying scales of a data set. We propose the ParChain framework for designing parallel hierarchical agglomerative clustering (HAC) algorithms, and using the framework we obtain novel parallel algorithms for the complete linkage, average linkage, and Ward's linkage criteria. Compared to most previous parallel HAC algorithms, which require quadratic memory, our new algorithms require only linear memory, and are scalable to large data sets. ParChain is based on our parallelization of the nearest-neighbor chain algorithm, and enables multiple clusters to be merged on every round. We introduce two key optimizations that are critical for efficiency: a range query optimization that reduces the number of distance computations required when finding nearest neighbors of clusters, and a caching optimization that stores a subset of previously computed distances, which are likely to be reused. Experimentally, we show that our highly-optimized implementations using 48 cores with two-way hyper-threading achieve 5.8--110.1x speedup over state-of-the-art parallel HAC algorithms and achieve 13.75--54.23x self-relative speedup. Compared to state-of-the-art algorithms, our algorithms require up to 237.3x less space. Our algorithms are able to scale to data set sizes with tens of millions of points, which existing algorithms are not able to handle.

Computer Science↗

NASA NTRS1995

A Parallel Incompressible Navier-Stokes Solver With a Parallel Multigrid Elliptic Kernal

The paper describes numerical algorithms and parallel implementations of a time-dependent, incompressible Navier-Stokes flow solver and a multigrid elliptic solver, which is also used as a computation kernal in the flow solver. The implemented solvers are numerically stable and computationally efficient, and they scale well to a large number of processors for problems with moderate granularity.

solver Navier-Stokes solver multigrid elliptic sol↗

NASA NTRS1987

Algorithmic commonalities in the parallel environment

The ultimate aim of this project was to analyze procedures from substantially different application areas to discover what is either common or peculiar in the process of conversion to the Massively Parallel Processor (MPP). Three areas were identified: molecular dynamic simulation, production systems (rule systems), and various graphics and vision algorithms. To date, only selected graphics procedures have been investigated. They are the most readily available, and produce the most visible results. These include simple polygon patch rendering, raycasting against a constructive solid geometric model, and stochastic or fractal based textured surface algorithms. Only the simplest of conversion strategies, mapping a major loop to the array, has been investigated so far. It is not entirely satisfactory.

Mcanulty, Michael A.↗

DOE OSTI2025

A GPU‐Accelerated Generative Adversarial Model for Causal Inference

We develop a GPU-accelerated machine learning generative adversarial model designed to facilitate causal inferences from observational data. Our model's theoretical framework is conceptualized in a manner that is amenable to being operable and scalable for high-performance computing platforms. We leverage GPU acceleration to develop a parallel evolutionary algorithm to achieve large-scale parallel computation of the model within a now widely accessible computing platform. This capability both enhances computational speedup and efficiency and also extends the use of the model to a broader range of substantive research domains while maintaining the underlying theoretical properties of the model.

GPU↗

DOE OSTI2023

Semantic embedding for quantum algorithms

The study of classical algorithms is supported by an immense understructure, founded in logic, type, and category theory, that allows an algorithmist to reason about the sequential manipulation of data irrespective of a computation’s realizing dynamics. As quantum computing matures, a similar need has developed for an assurance of the correctness of high-level quantum algorithmic reasoning. Parallel to this need, many quantum algorithms have been unified and improved using quantum signal processing (QSP) and quantum singular value transformation (QSVT), which characterize the ability, by alternating circuit ansätze, to transform the singular values of sub-blocks of unitary matrices by polynomial functions. However, while the algebraic manipulation of polynomials is simple (e.g., compositions and products), the QSP/QSVT circuits realizing analogous manipulations of their embedded polynomials are non-obvious. This work constructs and characterizes the runtime and expressivity of QSP/QSVT protocols where circuit manipulation maps naturally to the algebraic manipulation of functional transforms (termed semantic embedding). In this way, QSP/QSVT can be treated and combined modularly, purely in terms of the functional transforms they embed, with key guarantees on the computability and modularity of the realizing circuits. We also identify existing quantum algorithms whose use of semantic embedding is implicit, spanning from distributed search to proofs of soundness in quantum cryptography. The methods used, based in category theory, establish a theory of semantically embeddable quantum algorithms, and provide a new role for QSP/QSVT in reducing sophisticated algorithmic problems to simpler algebraic ones.

Physics↗

NASA NTRS1987

Real-time collision avoidance manipulator transfer movements

Collision free robot manipulator maneuvers for transferring a payload from one location to another in the presence of obstacles are discussed. Such maneuvers are executed by means of two algorithms running in parallel. The first algorithm performs an on-line, one step ahead acceleration optimization, with an adaptive N-step ahead precaution measure to prevent overshooting the specified forbidden joint coordinates. The second algorithm, an on-line planning algorithm, at the same time, selects the current target state and the current forbidden joint coordinates for the first algorithm. Since the task is a point to point transfer movement, the problem is dealt in robot joint space directly and the kinematic problem can be bypassed completely. A simulation example using a 2 degree-of-freedom planner robot is given.

Chen, N.↗

NASA NTRS1993

Use of networked workstations for parallel nonlinear structural dynamic simulations of rotating bladed-disk assemblies

The principal objective of this research is to investigate, develop and demonstrate coarse-grained, parallel-processing strategies for nonlinear dynamic simulations for rotating bladed-disk assemblies. The parallel -processing strategies addressed include numerical algorithms for parallel nonlinear solutions and techniques to effect load balancing among processors. The parallel environment employed is a distributed-memory, coarse-grained one consisting of networked workstations. A parallel explicit time integration method has been implemented for transient nonlinear solutions of rotationg bladed-disk assemblies. Automatic domain partitioning techniques have been investigated for load balancing among processors. Advanced computing environments, data structures and interactive computer graphics all contribute to an integrated parallel finite element analysis system to facilitate more efficient and powerful dynamic simulations.

Hsieh, Shang-Hsien↗