Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “parallel data structures”

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 181 records · Page 10

A comparative study of serial and parallel aeroelastic computations of wings

A procedure for computing the aeroelasticity of wings on parallel multiple-instruction, multiple-data (MIMD) computers is presented. In this procedure, fluids are modeled using Euler equations, and structures are modeled using modal or finite element equations. The procedure is designed in such a way that each discipline can be developed and maintained independently by using a domain decomposition approach. In the present parallel procedure, each computational domain is scalable. A parallel integration scheme is used to compute aeroelastic responses by solving fluid and structural equations concurrently. The computational efficiency issues of parallel integration of both fluid and structural equations are investigated in detail. This approach, which reduces the total computational time by a factor of almost 2, is demonstrated for a typical aeroelastic wing by using various numbers of processors on the Intel iPSC/860.

Byun, Chansup↗

cuTS: Scaling Subgraph Isomorphism on Distributed Multi-GPUSystems Using Trie Based Data Structure

Subgraph isomorphism is a pattern-matching algorithm widely used in many domains such as chem-informatics, bioinformatics, databases, and social network analysis. It is computationally expensive and is a proven NP-hard problem. The massive parallelism offered by the GPU hardware is well suited for solving the subgraph isomorphism. However, current GPU implementations are far from the achievable performance. Moreover, the enormous memory requirement of current approaches limits the problem size that can be handled. This work analyzes the fundamental challenges associated with processing the subgraph isomorphism on GPUs and develops an efficient GPU hardware-aware implementation. We also develop a new GPU-friendly trie-based data structure to drastically reduce the intermediate storage space requirement. Hence, our approach runs larger benchmarks than the competitors. We also develop the first distributed sub-graph isomorphism algorithm for GPUs. Our experimental evaluation section demonstrates the efficacy of our approach by comparing the execution time and number of cases that we can handle against the state-of-the-art GPU implementations.

Xiang, Lizhi↗

Scaling Structured Multigrid to 500K+ Cores Through Coarse-Grid Redistribution

The effcient solution of sparse, linear systems resulting from the discretization of partial differential equations is crucial to the performance of many physics-based simulations. The algorithmic optimality of multilevel approaches for common discretizations makes them a good candidate for an efficient parallel solver. Yet, modern architectures for high-performance computing systems continue to challenge the parallel scalability of multilevel solvers. While algebraic multigrid methods are robust for solving a variety of problems, the increasing importance of data locality and cost of data movement in modern architectures motivates the need to carefully exploit structure in the problem. Robust logically structured variational multigrid methods, such as Black Box Multigrid (BoxMG), maintain structure throughout the multigrid hierarchy. This avoids indirection and increased coarse- grid communication costs typical in parallel algebraic multigrid. Nevertheless, the parallel scalability of structured multigrid is challenged by coarse-grid problems where the overhead in communication dominates computation. In this paper, an algorithm is introduced for redistributing coarse-grid problems through incremental agglomeration. Guided by a predictive performance model, this algorithm provides robust redistribution decisions for structured multilevel solvers. A two-dimensional diffusion problem is used to demonstrate the significant gain in performance of this algorithm over the previous approach that used agglomeration to one processor. In addition, the parallel scalability of this approach

97 MATHEMATICS AND COMPUTING↗

ELECTRONIC STRUCTURE METHODS AND PROTOCOLS WITH APPLICATION TO DYNAMICS, KINETICS AND THERMOCHEMISTRY

Hydrocarbon combustion involves the reaction dynamics of a tremendous number of species beginning with many-component fuel mixtures and proceeding via a complex system of intermediates to form primary and secondary products. Combustion conditions corresponding to new advanced engines and/or alternative fuels rely increasingly on autoignition and low-temperature-combustion chemistry. In these regimes various transient radical species such as HO2, ROO·, ·QOOH, HCO, NO2, HOCO, and Criegee intermediates play important roles in determining the detailed as well as more general dynamics. A clear understanding and accurate representation of these processes is needed for effective modeling. Given the difficulties associated with making reliable experimental measurements of these systems, computation can play an important role in developing these energy technologies. Accurate calculations have their own challenges since even within the simplest dynamical approximations such as transition state theory, the rates depend exponentially on critical barrier heights and these may be sensitive to the level of quantum chemistry. Moreover, it is well-known that in many cases it is necessary to go beyond statistical theories and consider the dynamics. Quantum tunneling, resonances, radiative transitions, and non-adiabatic effects governed by spin-orbit or derivative coupling can be determining factors in those dynamics. Building upon progress made during a period of prior support through the DOE Early Career Program, this project combines developments in the areas of potential energy surface (PES) fitting and multistate multireference quantum chemistry to allow spectroscopically and dynamically/kinetically accurate investigations of key molecular systems (such as those mentioned above), many of which are radicals with strong multireference character and have the possibility of multiple electronic states contributing to the observed dynamics. An ongoing area of investigation is to develop general strategies for robustly convergent electronic structure theory for global multichannel reactive surfaces including diabatization of energy and other relevant surfaces such as dipole transition. Combining advances in ab initio methods with automated interpolative PES fitting allows the construction of high-quality PESs (incorporating thousands of high-level data) to be done rapidly through parallel processing on high-performance computing (HPC) clusters. In addition, new methods and approaches to electronic structure theory will be developed and tested through applications. This project will explore limitations in traditional multireference calculations (e.g., MRCI) such as those imposed by internal contraction, lack of high-order correlation treatment and poor scaling. Methods such as DMRG-based extended active-space CASSCF and various Quantum Monte Carlo (QMC) methods will be applied (including VMC/DMC and FCIQMC). Insight into the relative significance of different orbital spaces and the robustness of application of these approaches on leadership class computing architectures will be gained. Synergy with other components of this research program such as automated PES fitting and multireference quantum chemistry will be used to address challenges encountered by the standard approaches to computational thermochemistry (those being single-reference quantum chemistry and perturbative treatments of the anharmonic vibrational energy, which break down for some cases of electronic structure or floppy strongly coupled vibrational modes).

74 ATOMIC AND MOLECULAR PHYSICS↗

TGE: Machine Learning Based Task Graph Embedding for Large-Scale Topology Mapping

Task mapping is an important problem in parallel and distributed computing. The goal in task mapping is to find an optimal layout of the processes of an application (or a task) onto a given network topology. We target this problem in the context of staging applications. A staging application consists of two or more parallel applications (also referred to as staging tasks) which run concurrently and exchange data over the course of computation. Task mapping becomes a more challenging problem in staging applications, because not only data is exchanged between the staging tasks, but also the processes of a staging task may exchange data with each other. We propose a novel method, called Task Graph Embedding (TGE), that harnesses the observable graph structures of parallel applications and network topologies. TGE employs a machine learning based algorithm to find the best representation of a graph, called an embedding, onto a space in which the task-to-processor mapping problem can be solved. We evaluate and demonstrate the effectiveness of TGE experimentally with the communication patterns extracted from runs of XGC, a large-scale fusion simulation code, on Titan.

Choi, Jong Youl↗

3D Navier-Stokes Time Accurate Solutions Using Multipartitioning Parallel Computation Methodology

A parallel CFD code solving 3D time accurate Navier-Stokes equations with multipartitioning parallel Methodology is being developed in collaboration with Ohio State University within the Air Vehicle Directorate, at Wright Patterson Air Force Base. The advantage of the multipartitioning parallel method is that the domain decomposition will not introduce domain boundaries for the implicit operators. A ring structure data communication is employed so that the implicit time accurate method can be implemented for multi-processors with the same accuracy as for the single processor. No sub-iteration is needed at the domain boundaries. The code has been validated for some typical unsteady flows, which include Coutte Flow, flow passing a cylinder. The code now is being employed for a large scale time accurate wall jet transient flow computation. 'ne preliminary results are promising. The mesh has been refined to capture more details of the flow field. The mesh refinement computation is in progress and would be difficult to successfully implement without the parallel computation techniques used. A modified version of the code with more efficient inversion of the diagonalized block matrix is currently being tested.

Zha, Ge-Cheng↗

Two Carrier Analysis of Persistent Photoconductivity in Modulation-Doped Structures

A simultaneous fit of Hall and conductivity data gives quantitative results on the carrier concentration and mobility in both the quantum well and the parallel conduction channel. In this study this method was applied to reveal several new findings on the effect of persistent photoconductivity (PPC) on free-carrier concentrations and mobilities. The increase in the two-dimensional electron-gas (2DEG) concentration is significantly smaller than the apparent one derived from single carrier analysis of the Hall coefficient. In the two types of structures investigated, delta doped and continuously doped barrier, the apparent concentration almost doubles following illumination, while analysis reveals an increase of about 20% in the 2DEG. The effect of PPC on mobility depends on the structure. For the sample with a continuously doped barrier the mobility in the quantum well more than doubles. This increase is attributed to the effective screening of the ionized donors by the large electron concentration in the barrier. In the delta doped barrier sample the mobility is reduced by almost a factor of 2. This decrease is probably caused by strong coupling between the two wells, as is demonstrated by self-consistent analysis.

Schacham, S. E.↗

Run-time scheduling and execution of loops on message passing machines

Sparse system solvers and general purpose codes for solving partial differential equations are examples of the many types of problems whose irregularity can result in poor performance on distributed memory machines. Often, the data structures used in these problems are very flexible. Crucial details concerning loop dependences are encoded in these structures rather than being explicitly represented in the program. Good methods for parallelizing and partitioning these types of problems require assignment of computations in rather arbitrary ways. Naive implementations of programs on distributed memory machines requiring general loop partitions can be extremely inefficient. Instead, the scheduling mechanism needs to capture the data reference patterns of the loops in order to partition the problem. First, the indices assigned to each processor must be locally numbered. Next, it is necessary to precompute what information is needed by each processor at various points in the computation. The precomputed information is then used to generate an execution template designed to carry out the computation, communication, and partitioning of data, in an optimized manner. The design is presented for a general preprocessor and schedule executer, the structures of which do not vary, even though the details of the computation and of the type of information are problem dependent.

Crowley, Kay↗

Run-time scheduling and execution of loops on message passing machines

Sparse system solvers and general purpose codes for solving partial differential equations are examples of the many types of problems whose irregularity can result in poor performance on distributed memory machines. Often, the data structures used in these problems are very flexible. Crucial details concerning loop dependences are encoded in these structures rather than being explicitly represented in the program. Good methods for parallelizing and partitioning these types of problems require assignment of computations in rather arbitrary ways. Naive implementations of programs on distributed memory machines requiring general loop partitions can be extremely inefficient. Instead, the scheduling mechanism needs to capture the data reference patterns of the loops in order to partition the problem. First, the indices assigned to each processor must be locally numbered. Next, it is necessary to precompute what information is needed by each processor at various points in the computation. The precomputed information is then used to generate an execution template designed to carry out the computation, communication, and partitioning of data, in an optimized manner. The design is presented for a general preprocessor and schedule executer, the structures of which do not vary, even though the details of the computation and of the type of information are problem dependent.

Saltz, Joel↗

Enabling Parallel Execution of System-level Simulations in SAM

This report summarizes the recent code updates related to “element ghosting” in SAM to enable the parallel execution of system-level simulations using multiple processors/cores. Unlike typical MOOSE-based applications, for system-level simulations, SAM mostly deals with a collection of discrete small pieces of meshes, and the connection of physics on these meshes are realized by using “connector” types of components/code structures, such as conjugate heat transfer and flow junctions. The required code implementation is to correctly mark the necessary ghost elements for each type of such components/code structures; thus, the lower-level libraries can correctly perform the necessary data transfer between processors (CPUs) when executed in parallel mode. After the code updates, SAM can now run system-level simulations in the parallel mode. The parallel execution capability was then tested with an ABTR input model with 23k DOFs. Significant speedup was demonstrated when the optimal number of CPUs were used in parallel mode. Future systematic studies on parallelization performance using additional test cases covering different physics/scenarios will be needed to provide additional insights into the scalability of SAM parallelization.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗

NavP: Structured and Multithreaded Distributed Parallel Programming

We present Navigational Programming (NavP) -- a distributed parallel programming methodology based on the principles of migrating computations and multithreading. The four major steps of NavP are: (1) Distribute the data using the data communication pattern in a given algorithm; (2) Insert navigational commands for the computation to migrate and follow large-sized distributed data; (3) Cut the sequential migrating thread and construct a mobile pipeline; and (4) Loop back for refinement. NavP is significantly different from the current prevailing Message Passing (MP) approach. The advantages of NavP include: (1) NavP is structured distributed programming and it does not change the code structure of an original algorithm. This is in sharp contrast to MP as MP implementations in general do not resemble the original sequential code; (2) NavP implementations are always competitive with the best MPI implementations in terms of performance. Approaches such as DSM or HPF have failed to deliver satisfying performance as of today in contrast, even if they are relatively easy to use compared to MP; (3) NavP provides incremental parallelization, which is beyond the reach of MP; and (4) NavP is a unifying approach that allows us to exploit both fine- (multithreading on shared memory) and coarse- (pipelined tasks on distributed memory) grained parallelism. This is in contrast to the currently popular hybrid use of MP+OpenMP, which is known to be complex to use. We present experimental results that demonstrate the effectiveness of NavP.

navigational programming (NavP)↗

Memory access optimization for particle operations in computational fluid dynamics-discrete element method simulations

Computational Fluid Dynamics - Discrete Element Method is used to model gas-solid systems in several applications in energy, pharmaceutical and petrochemical industries. Computational performance bottlenecks often limit the problem sizes that can be simulated at industrial scale. The data structures used to store several millions of particles in such large-scale simulations have a large memory footprint that does not fit into the processor cache hierarchies on current high-performance-computing platforms, leading to reduced computational performance. This paper specifically addresses this aspect of memory access bottlenecks in industrial scale simulations. The use of space-filling curves to improve memory access patterns is described and their impact on computational performance is quantified in both shared and distributed memory parallelization paradigms. The Morton space filling curve applied to uniform grids and k-dimensional tree partitions are used to reorder the particle data-structure thus improving spatial and temporal locality in memory. The performance impact of these techniques when applied to two benchmark problems, namely the homogeneous-cooling-system and a fluidized-bed, are presented. We report these optimization techniques lead to approximately two-fold performance improvement in particle focused operations such as neighbor-list creation and data-exchange, with ~ 1.5 times overall improvement in a fluidization simulation with 1.27 million particles.

97 MATHEMATICS AND COMPUTING↗

SHAD: the Scalable High-performance Algorithms and Data-structures Library

The unprecedented amount of data that needs to be processed in emerging data analytics applications poses novel challenges to industry and academia. Scalability and high performance become more than a desirable feature because, due to the scale and the nature of the problems, they draw the line between what is achievable and what is unfeasible. In this paper, we propose SHAD, the Scalable High-performance Algorithms and Data-structures library. SHAD adopts a modular design that confines low level details and promotes reuse. SHAD's core is built on an Abstract Runtime Interface which enhances portability and identifies the minimal set of features of the underlying system required by the framework. The core library includes common data-structures such as: Array, Vector, Map and Set. These are designed to accommodate significant amount of data which can be accessed in massively parallel environments, and used as building blocks for SHAD extensions, i.e. higher level software libraries. We have validated and evaluated our design with a performance and scalability study of the core components of the library. We have validated the design flexibility by proposing a Graph Library as an example of SHAD extension, which implements two different graph data-structures; we evaluate their performance with a set of graph applications. Experimental results show that the approach is promising in terms of both performance and scalability. On a distributed system with 320 cores, SHAD Arrays are able to sustain a throughput of 65 billion operations per second, while SHAD Maps sustain 1 billion of operations per second. Algorithms implemented using the Graph Library exhibit performance and scalability comparable to a custom solution, but with smaller development effort.

Castellana, Vito G.↗

Phase transformation path in Aluminum under ramp compression; simulation and experimental study

Abstract We present a framework based on non-equilibrium molecular dynamics (NEMD) to reproduce the phase transformation event of Aluminum under ramp compression loading. The simulated stress-density response, virtual x-ray diffraction patterns, and structure analysis are compared against the previously observed experimental laser-driven ramp compression in-situ x-ray diffraction data. The NEMD simulations show the solid–solid phase transitions are consistent to experimental observations with a close-packed face-centered cubic (fcc) (111), hexagonal close-packed (hcp) structure (002), and body-centered cubic bcc (110) planes remaining parallel. The atomic-level analysis of NEMD simulations identifiy the exact phase transformation pathway happening via Bain transformation while the previous in situ x-ray diffraction data did not provide sufficient information for deducing the exact phase transformation path.

36 MATERIALS SCIENCE↗

Parallel Randomized Tucker Decomposition Algorithms

The Tucker tensor decomposition is a natural extension of the singular value decomposition (SVD) to multiway data. Here, we propose to accelerate Tucker tensor decomposition algorithms by using randomization and parallelization. We present two algorithms that scale to large data and many processors, significantly reduce both computation and communication cost compared to previous deterministic and randomized approaches, and obtain nearly the same approximation errors. The key idea in our algorithms is to perform randomized sketches with Kronecker-structured random matrices, which reduces computation compared to unstructured matrices and can be implemented using a fundamental tensor computational kernel. We provide probabilistic error analysis of our algorithms and implement a new parallel algorithm for the structured randomized sketch. Our experimental results demonstrate that our combination of randomization and parallelization achieves accurate Tucker decompositions much faster than alternative approaches. We observe up to a 16X speedup over the fastest deterministic parallel implementation on 3D simulation data.

Tucker decompositions↗

PETSc/TAO Users Manual V.3.21

This manual describes the use of the Portable, Extensible Toolkit for Scientific Computation (PETSc) and the Toolkit for Advanced Optimization (TAO) for the numerical solution of partial differential equations (PDEs) and related problems on high-performance computers. PETSc/TAO is a suite of data structures and routines that provide the building blocks for implementing large-scale application codes on parallel (and serial) computers. PETSc uses the MPI standard for all distributed memory communication. PETSc/TAO includes a large suite of parallel linear solvers, nonlinear solvers, time integrators, and optimizers that may be used in application codes written in Fortran, C, C++, and Python (via petsc4py; see Getting Started ). The library is organized hierarchically, enabling users to employ the abstraction level most appropriate for a particular problem. By using techniques of object-oriented programming, PETSc provides enormous flexibility for users.

97 MATHEMATICS AND COMPUTING↗

PETSc/TAO Users Manual Revision 3.22

This manual describes the use of the Portable, Extensible Toolkit for Scientific Computation (PETSc) and the Toolkit for Advanced Optimization (TAO) for the numerical solution of partial differential equations (PDEs) and related problems on high-performance computers. PETSc/TAO is a suite of data structures and routines that provide the building blocks for implementing large-scale application codes on parallel (and serial) computers. PETSc uses the MPI standard for all distributed memory communication.

97 MATHEMATICS AND COMPUTING↗

PETSc/TAO Users Manual Revision 3.23

This manual describes the use of the Portable, Extensible Toolkit for Scientific Computation (PETSc) and the Toolkit for Advanced Optimization (TAO) for the numerical solution of partial differential equations (PDEs) and related problems on high-performance computers. PETSc/TAO is a suite of data structures and routines that provide the building blocks for implementing large-scale application codes on parallel (and serial) computers. PETSc uses the MPI standard for all distributed memory communication.

97 MATHEMATICS AND COMPUTING↗