Engineering Papers⌕ Search

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.

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

At least 1,729 records · Page 96

Simulations of transition and turbulence on the Navier-Stokes computer

The Navier-Stokes Computer (NSC) consists of multiple local memory parallel processors interconnected in a hypercube network. Efficient implementation of algorithms on the NSC thus requires the effective utilization of both the coarse and fine grain paralelism inherent in the architectural design. The basic approach to implementing an algorithm on the NSC is presented herein. The particular finite-difference algorithm considered was developed for performing transition and turbulence simulations by direct solution of the time-dependent incompressible Navier-Stokes equations. The suitability of this algorithm for performing simulations of the isotropic turbulence problem is verified from computations performed on a Cray 2. Projected timing results for the algorithm on the NSC itself are presented for both the isotropic turbulence and laminar turbulent transition problems.

Krist, S. E.↗

Introduction to a system for implementing neural net connections on SIMD architectures

Neural networks have attracted much interest recently, and using parallel architectures to simulate neural networks is a natural and necessary application. The SIMD model of parallel computation is chosen, because systems of this type can be built with large numbers of processing elements. However, such systems are not naturally suited to generalized communication. A method is proposed that allows an implementation of neural network connections on massively parallel SIMD architectures. The key to this system is an algorithm permitting the formation of arbitrary connections between the neurons. A feature is the ability to add new connections quickly. It also has error recovery ability and is robust over a variety of network topologies. Simulations of the general connection system, and its implementation on the Connection Machine, indicate that the time and space requirements are proportional to the product of the average number of connections per neuron and the diameter of the interconnection network.

Tomboulian, Sherryl↗

A parallel Householder tridiagonalization stratagem using scattered square decomposition

The parallel stratagem in this paper uses scattered square decomposition, introduced by Fox (1985), for its data assignment and then exploits parallelism in the solution steps of the sequential Householder tridiagonalization algorithm. One may condense a real symmetric full matrix A of order n into a tridiagonal form by the stratagem in concurrent machines where N(=D-squared) processors are used. Expressions for efficiency and speedup are given for the evaluation of the stratagem. An alternative stratagem which requires less data transmission but more computations is also discussed. The results shown that the Householder method of tridiagonalization may be implemented on a concurrent machine efficiently by scattered square decomposition provided that the number of matrix elements contained in each processor is much larger than the number of processors of the concurrent machine, and the ratio of the time to transmit one data item from one processor to any other processor to the time to perform a floating-point arithmetic operation is small enough.

Chang, H. Y.↗

Introduction to a system for implementing neural net connections on SIMD architectures

Neural networks have attracted much interest recently, and using parallel architectures to simulate neural networks is a natural and necessary application. The SIMD model of parallel computation is chosen, because systems of this type can be built with large numbers of processing elements. However, such systems are not naturally suited to generalized elements. A method is proposed that allows an implementation of neural network connections on massively parallel SIMD architectures. The key to this system is an algorithm permitting the formation of arbitrary connections between the neurons. A feature is the ability to add new connections quickly. It also has error recovery ability and is robust over a variety of network topologies. Simulations of the general connection system, and its implementation on the Connection Machine, indicate that the time and space requirements are proportional to the product of the average number of connections per neuron and the diameter of the interconnection network.

Tomboulian, Sherryl↗

Optimizing Input/Output Using Adaptive File System Policies

Parallel input/output characterization studies and experiments with flexible resource management algorithms indicate that adaptivity is crucial to file system performance. In this paper we propose an automatic technique for selecting and refining file system policies based on application access patterns and execution environment. An automatic classification framework allows the file system to select appropriate caching and pre-fetching policies, while performance sensors provide feedback used to tune policy parameters for specific system environments. To illustrate the potential performance improvements possible using adaptive file system policies, we present results from experiments involving classification-based and performance-based steering.

Madhyastha, Tara M.↗

Balancing Contention and Synchronization on the Intel Paragon

The Intel Paragon is a mesh-connected distributed memory parallel computer. It uses an oblivious and deterministic message routing algorithm: this permits us to develop highly optimized schedules for frequently needed communication patterns. The complete exchange is one such pattern. Several approaches are available for carrying it out on the mesh. We study an algorithm developed by Scott. This algorithm assumes that a communication link can carry one message at a time and that a node can only transmit one message at a time. It requires global synchronization to enforce a schedule of transmissions. Unfortunately global synchronization has substantial overhead on the Paragon. At the same time the powerful interconnection mechanism of this machine permits 2 or 3 messages to share a communication link with minor overhead. It can also overlap multiple message transmission from the same node to some extent. We develop a generalization of Scott's algorithm that executes complete exchange with a prescribed contention. Schedules that incur greater contention require fewer synchronization steps. This permits us to tradeoff contention against synchronization overhead. We describe the performance of this algorithm and compare it with Scott's original algorithm as well as with a naive algorithm that does not take interconnection structure into account. The Bounded contention algorithm is always better than Scott's algorithm and outperforms the naive algorithm for all but the smallest message sizes. The naive algorithm fails to work on meshes larger than 12 x 12. These results show that due consideration of processor interconnect and machine performance parameters is necessary to obtain peak performance from the Paragon and its successor mesh machines.

Bokhari, Shahid H.↗

Genetically Engineered Microelectronic Infrared Filters

A genetic algorithm is used for design of infrared filters and in the understanding of the material structure of a resonant tunneling diode. These two components are examples of microdevices and nanodevices that can be numerically simulated using fundamental mathematical and physical models. Because the number of parameters that can be used in the design of one of these devices is large, and because experimental exploration of the design space is unfeasible, reliable software models integrated with global optimization methods are examined The genetic algorithm and engineering design codes have been implemented on massively parallel computers to exploit their high performance. Design results are presented for the infrared filter showing new and optimized device design. Results for nanodevices are presented in a companion paper at this workshop.

Cwik, Tom↗

Perspectives on the Future of CFD

This viewgraph presentation gives an overview of the future of computational fluid dynamics (CFD), which in the past has pioneered the field of flow simulation. Over time CFD has progressed as computing power. Numerical methods have been advanced as CPU and memory capacity increases. Complex configurations are routinely computed now and direct numerical simulations (DNS) and large eddy simulations (LES) are used to study turbulence. As the computing resources changed to parallel and distributed platforms, computer science aspects such as scalability (algorithmic and implementation) and portability and transparent codings have advanced. Examples of potential future (or current) challenges include risk assessment, limitations of the heuristic model, and the development of CFD and information technology (IT) tools.

Kwak, Dochan↗

Molecular Simulations in Astrobiology

One of the main goals of astrobiology is to understand the origin of cellular life. In the absence of any record of the earliest ancestors of contemporary cells, protocells, the most direct way to test our understanding of their characteristics is to construct laboratory models of protocells. Such efforts, currently underway in the NASA Astrobiology Program, are accompanied by computational studies aimed at explaining self-organization of simple molecules into ordered structures and developing designs of molecules that are capable of performing protocellular functions. Many of these functions, such as importing nutrients, capturing and storing energy, and responding to changes in the environment, are carried out by proteins bound to membranes. We use computer simulations to address the following, questions about these proteins: (1) How do small proteins (peptides) organize themselves into ordered structures at water-membrane interfaces and insert into membranes? (2) How do peptides aggregate to form membrane-spannin(y structures (e.g., channels)? (3) By what mechanisms do such aggregates perform their functions? The simulations are performed using the molecular dynamics (MD) method. In this method, Newton's equations of motion for each atom in the system are solved iteratively. At each time step, the forces exerted on each atom by the remaining atoms are evaluated by dividing them into two parts. Short-range forces are calculated directly in real space while long-range forces are evaluated in reciprocal space, usually using a particle-mesh algorithm which is of order O(NlnN). Currently, a time step of 2 femtoseconds is typically used, thereby making studies of problems occurring on multi-nanosecond time scales (10(exp 6) - 10(exp 8) time steps) accessible. To address a broader range of problems, simulations need to be extended by three orders of magnitude. Such an extension requires both algorithmic improvements and codes scalable to a large number of parallel processors. Work in this direction is in progress. Two specific series of simulations that demonstrate how peptides self-organize and function in membranes are discussed. In one series of simulations, it was shown that nonpolar peptides, disordered in water, translocate to the nonpolar interior of the membrane and, simultaneously, fold into two different helical structures, which remain in equilibrium. Once in the membrane, the peptides can readily change their orientation, especially in response to local electric fields. This structural and orientational flexibility of peptides with changing conditions may have provided a mechanism of transmitting signals between the environment and the interior of the protocell. In another series of simulations, the mechanism by which a simple protein channel efficiently mediates proton transport across membranes was investigated. This process is a key step in cellular bioenergetics. In the channel under study, proton transport is gated by four histidines that occlude the channel pore. The simulations demonstrate that protons move through the gate by a "shuttle" mechanism, wherein one histidine is protonated on the extracellular side and, subsequently, the proton bound on the opposite side is released.

Pohorille, Andrew↗

Toward GEOS-6, A Global Cloud System Resolving Atmospheric Model

NASA is committed to observing and understanding the weather and climate of our home planet through the use of multi-scale modeling systems and space-based observations. Global climate models have evolved to take advantage of the influx of multi- and many-core computing technologies and the availability of large clusters of multi-core microprocessors. GEOS-6 is a next-generation cloud system resolving atmospheric model that will place NASA at the forefront of scientific exploration of our atmosphere and climate. Model simulations with GEOS-6 will produce a realistic representation of our atmosphere on the scale of typical satellite observations, bringing a visual comprehension of model results to a new level among the climate enthusiasts. In preparation for GEOS-6, the agency's flagship Earth System Modeling Framework [JDl] has been enhanced to support cutting-edge high-resolution global climate and weather simulations. Improvements include a cubed-sphere grid that exposes parallelism; a non-hydrostatic finite volume dynamical core, and algorithm designed for co-processor technologies, among others. GEOS-6 represents a fundamental advancement in the capability of global Earth system models. The ability to directly compare global simulations at the resolution of spaceborne satellite images will lead to algorithm improvements and better utilization of space-based observations within the GOES data assimilation system

Putman, William M.↗

Futility

The Futility package contains the following: 1) Definition of the size of integers and real numbers; 2) A generic Unit test harness; 3) Definitions for some basic extensions to the Fortran language: arbitrary length strings, a parameter list construct, exception handlers, command line processor, timers; 4) Geometry definitions: point, line, plane, box, cylinder, polyhedron; 5) File wrapper functions: standard Fortran input/output files, Fortran binary files, HDF5 files; 6) Parallel wrapper functions: MPI, and Open MP abstraction layers, partitioning algorithms; 7) Math utilities: BLAS, Matrix and Vector definitions, Linear Solver methods and wrappers for other TPLs (PETSC, MKL, etc), preconditioner classes; 8) Misc: random number generator, water saturation properties, sorting algorithms.

Collins, Benjamin S.↗

Tusas: A fully implicit parallel approach for coupled phase-field equations

In this study, we develop a fully-coupled, fully-implicit approach for phase-field modeling of solidification in metals and alloys. Predictive simulation of solidification in pure metals and metal alloys remains a significant challenge in the field of materials science, as microstructure formation during the solidification process plays a critical role in the properties and performance of the solid material. Our simulation approach consists of a finite element spatial discretization of the fully-coupled nonlinear system of partial differential equations at the microscale, which is treated implicitly in time with a preconditioned Jacobian-free Newton-Krylov method. The approach is algorithmically scalable as well as efficient due to an effective preconditioning strategy based on algebraic multigrid and block factorization. We implement this approach in the open-source Tusas framework, which is a general, flexible tool developed in C++ for solving coupled systems of nonlinear partial differential equations. The performance of our approach is analyzed in terms of algorithmic scalability and efficiency, while the computational performance of Tusas is presented in terms of parallel scalability and efficiency on emerging heterogeneous architectures. We demonstrate that modern algorithms, discretizations, and computational science, and heterogeneous hardware provide a robust route for predictive phase-field simulation of microstructure evolution during additive manufacturing.

97 MATHEMATICS AND COMPUTING↗

Parallel membership queries on very large scientific data sets using bitmap indexes

© 2019 John Wiley & Sons, Ltd. Many scientific applications produce very large amounts of data as advances in hardware fuel computing and experimental facilities. Managing and analyzing massive quantities of scientific data is challenging as data are often stored in specific formatted files, such as HDF5 and NetCDF, which do not offer appropriate search capabilities. In this research, we investigated a special class of search capability, called membership query, to identify whether queried elements of a set are members of an attribute. Attributes that naturally have classification values appear frequently in scientific domains such as category and object type as well as in daily life such as zip code and occupation. Because classification attribute values are discrete and require random data access, performing a membership query on a large scientific data set creates challenges. We applied bitmap indexing and parallelization to membership queries to overcome these challenges. Bitmap indexing provides high performance not only for low cardinality attributes but also for high cardinality attributes, such as floating-point variables, electric charge, or momentum in a particle physics data set, due to compression algorithms such as Word-Aligned Hybrid. We conducted experiments, in a highly parallelized environment, on data obtained from a particle accelerator model and a synthetic data set.

Yildiz, Beytullah↗

Exploring MPI Communication Models for Graph Applications Using Graph Matching as a Case Study

Traditional implementations of parallel graph operations on distributed memory platforms are written using Message Passing Interface (MPI) point to point communication primitives such as Send-Recv (blocking and nonblocking). Apart from this classical model, the MPI community has over the years added other communication models; however, their suitability for handling the irregular traffic workloads typical of graph operations remain comparatively less explored. Our aim in this paper is to study these relatively underutilized communication models of MPI for graph applications. More specifically, we evaluate MPI’s one-sided programming, or Remote Memory Access (RMA), and nearest neighborhood collectives using a process graph topology. There are features in these newer models that are intended to better map to irregular communication patterns, as exemplified in graph algorithms. As a concrete application for our case study, we use distributed memory implementations of a weighted graph matching algorithm to investigate performances of MPI-3 RMA and neighborhood collective operations compared to nonblocking Send- Recv. A matching in a graph is a subset of edges such that no two matched edges are incident on the same vertex. A maximum weight matching is a matching of maximum weight computed as the sum of the weights of matched edges. Algorithms for optimal matching have quadratic complexity and are difficult to parallelize. More importantly, execution of graph matching is dominated by high volume of irregular memory accesses, making it an ideal candidate for studying the effects of various MPI communication models on graph applications at scale. Our neighborhood collectives and RMA implementations yields up to 6× speedup over traditional optimized nonblocking Send-Recv implementations, on thousands of cores of the NERSC Cori supercomputer. We believe the lessons learned from this case study can be adopted to benefit a wider range of graph application codes.

Ghosh, Sayan↗

High-Throughput Discovery Illuminates Design Principles and Limits for Long-Lived Charged Species in Organic Electrolytes

The chemical stability of charged molecules in all-organic redox flow batteries (RFBs) is required for the prolonged operation of these devices. Molecular engineering and electrolyte optimization are used to mitigate parasitic reactions and extend the lifetimes of the charge carriers. However, how much can structural variation extend the lifetime? To probe this query, we designed a high-throughput kinetic study of the radical cation of N-methylphenothiazinium, guided by statistical sampling and learning algorithms. Using Argonne’s autonomous discovery facility, we conducted over 6,000 kinetic experiments with robotic sample preparation, parallel kinetic measurements, and machine learning inputs, testing 188 solvent molecules selected from a space of over 540 candidates from 11 chemical classes. Algorithmic selections guided us to stable solvent candidates, which were further tested in high concentration with and without supporting electrolyte. Our findings reveal the inherent difficulty of exceeding the current state of the art through solvent variation. The desired stability is statistically rare and poorly predictable. Among the many tested, only three solvents significantly outperformed our baseline, acetonitrile─and none by more than a factor of 3─suggesting a general challenge in achieving the necessary techno-economic targets. Furthermore, we suggest that self-discharge through solvent homolysis is the cause of the observed limitations. Several structural motifs contribute to >1,000 h half-life stability including molecular simplicity, symmetry, oxidation complement, and strategic fluorination. Importantly, this workflow establishes effective assays for diagnosing and predicting oxidative stress for highly stable liquid electrolytes in all batteries.

Batteries↗

Real-time dynamics and control strategies for space operations of flexible structures

This project (NAG9-574) was meant to be a three-year research project. However, due to NASA's reorganizations during 1992, the project was funded only for one year. Accordingly, every effort was made to make the present final report as if the project was meant to be for one-year duration. Originally, during the first year we were planning to accomplish the following: we were to start with a three dimensional flexible manipulator beam with articulated joints and with a linear control-based controller applied at the joints; using this simple example, we were to design the software systems requirements for real-time processing, introduce the streamlining of various computational algorithms, perform the necessary reorganization of the partitioned simulation procedures, and assess the potential speed-up realization of the solution process by parallel computations. The three reports included as part of the final report address: the streamlining of various computational algorithms; the necessary reorganization of the partitioned simulation procedures, in particular the observer models; and an initial attempt of reconfiguring the flexible space structures.

Park, K. C.↗

Bit-parallel arithmetic in a massively-parallel associative processor

A simple but powerful new architecture based on a classical associative processor model is presented. Algorithms for performing the four basic arithmetic operations both for integer and floating point operands are described. For m-bit operands, the proposed architecture makes it possible to execute complex operations in O(m) cycles as opposed to O(m exp 2) for bit-serial machines. A word-parallel, bit-parallel, massively-parallel computing system can be constructed using this architecture with VLSI technology. The operation of this system is demonstrated for the fast Fourier transform and matrix multiplication.

Scherson, Isaac D.↗

Parallel Climate Data Assimilation PSAS Package

We have designed and implemented a set of highly efficient and highly scalable algorithms for an unstructured computational package, the PSAS data assimilation package, as demonstrated by detailed performance analysis of systematic runs on up to 512node Intel Paragon. The equation solver achieves a sustained 18 Gflops performance. As the results, we achieved an unprecedented 100-fold solution time reduction on the Intel Paragon parallel platform over the Cray C90. This not only meets and exceeds the DAO time requirements, but also significantly enlarges the window of exploration in climate data assimilations.

PSAS data scalable algorithms Intel Paragon 512nod↗