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 739 records · Page 41

EXAGRAPH: Graph and combinatorial methods for enabling exascale applications

Combinatorial algorithms in general and graph algorithms in particular play a critical enabling role in numerous scientific applications. However, the irregular memory access nature of these algorithms makes them one of the hardest algorithmic kernels to implement on parallel systems. With tens of billions of hardware threads and deep memory hierarchies, the exascale computing systems in particular pose extreme challenges in scaling graph algorithms. The codesign center on combinatorial algorithms, ExaGraph, was established to design and develop methods and techniques for efficient implementation of key combinatorial (graph) algorithms chosen from a diverse set of exascale applications. Algebraic and combinatorial methods have a complementary role in the advancement of computational science and engineering, including playing an enabling role on each other. In this paper, we survey the algorithmic and software development activities performed under the auspices of ExaGraph from both a combinatorial and an algebraic perspective. In particular, we detail our recent efforts in porting the algorithms to manycore accelerator (GPU) architectures. We also provide a brief survey of the applications that have benefited from the scalable implementations of different combinatorial algorithms to enable scientific discovery at scale. We believe that several applications will benefit from the algorithmic and software tools developed by the ExaGraph team.

97 MATHEMATICS AND COMPUTING↗

Extracting SIMD Parallelism from Recursive Task-Parallel Programs

The pursuit of computational efficiency has led to the proliferation of throughput-oriented hardware, from GPUs to increasingly wide vector units on commodity processors and accelerators. This hardware is designed to efficiently execute data-parallel computations in a vectorized manner. However, many algorithms are more naturally expressed as divide-and-conquer, recursive, task-parallel computations. In the absence of data parallelism, it seems that such algorithms are not well suited to throughput-oriented architectures. This paper presents a set of novel code transformations that expose the data parallelism latent in recursive, task- parallel programs. These transformations facilitate straightforward vectorization of task-parallel programs on commodity hardware. We also present scheduling policies that maintain high utilization of vector resources while limiting space usage. Across several task-parallel benchmarks, we demonstrate both efficient vector resource utilization and substantial speedup on chips using Intel’s SSE4.2 vector units, as well as accelerators using Intel’s AVX512 units. We then show through rigorous sampling that, in practice, our vectorization techniques are effective for a much larger class of programs.

Recursive Programs, task parallelism, vectorizatio↗

Efficient Execution of Recursive Programs on Commodity Vector Hardware

The pursuit of computational efficiency has led to the proliferation of throughput-oriented hardware, from GPUs to increasingly-wide vector units on commodity processors and accelerators. This hardware is designed to efficiently execute data-parallel computations in a vectorized manner. However, many algorithms are more naturally expressed as divide-and-conquer, recursive, task-parallel computations; in the absence of data parallelism, it seems that such algorithms are not well-suited to throughput-oriented architectures. This paper presents a set of novel code transformations that expose the data-parallelism latent in recursive, task-parallel programs. These transformations facilitate straightforward vectorization of task-parallel programs on commodity hardware. We also present scheduling policies that maintain high utilization of vector resources while limiting space usage. Across several task-parallel benchmarks, we demonstrate both efficient vector resource utilization and substantial speedup on chips using Intel's SSE4.2 vector units as well as accelerators using Intel's AVX512 units.

resursion↗

A non-destructive method for crack quantification in photovoltaic backsheets under accelerated and real-world exposures

The long-term durability of photovoltaic modules is paramount for the continued growth of the industry. Polymer backsheets are of particular concern since they provide electrical insulation and an environmental barrier. In this paper, 23 freestanding, multilayer backsheets with nine unique material combinations underwent four different weathering exposures under accelerated and real-world conditions. Besides changes in color and gloss, the induced degradation included parallel or mudflat cracks on 11 backsheets, sometimes in combination with delamination or blistering. Similar degradation has been observed in previous studies and is concerning since cracks compromise the mechanical integrity and electrical safety of backsheets. Quantitative parameters are desirable to reliably classify categories of cracks and supply unbiased features for statistical analysis in predictive lifetime models. We developed an analysis technique that utilizes surface profilometry data to quantify the depth, width, area, spacing, and number of cracks. Parameters are automatically extracted from the raw data by an algorithm running on a high performance distributed computing cluster. Our algorithm excelled at characterizing parallel cracks with minimal de-adhesion, and only an estimated 4% of crack detections were false positives. The addition of humidity and temperature variation formed up to three times as many cracks on a photodose basis compared to dry, constant temperature exposures. Cracks in real-world and accelerated exposures propagated to similar depths with equivalent photodoses; however, the number of cracks formed in accelerated exposures was far greater on a photodose basis. Of samples that cracked, the best performing backsheet configuration was polyvinyl fluoride/poly (ethylene-terephthalate)/polyethylene (PVF/PET/PE) while the least durable was PET/PET/ethylene-vinyl acetate. Finally, none of the six PVF/PET/PVF backsheets cracked in any of the exposures.

14 SOLAR ENERGY↗

GronOR: Massively Parallel and GPU-Accelerated Non-Orthogonal Configuration Interaction for Large Molecular Systems

GronOR is a program package for non-orthogonal configuration interaction calculations for an electronic wave function built in terms of anti-symmetrized products of multi-configuration molecular fragment wave functions. The two-electron integrals that have to be processed may be expressed in terms of atomic orbitals or in terms of an orbital basis determined from the molecular orbitals of the fragments. The code has been specifically designed for execution on distributed memory massively parallel and Graphics Processing Unit (GPU)-accelerated computer architectures, using an MPI+OpenACC/OpenMP programming approach. The task-based execution model used in the implementation allows for linear scaling with the number of nodes on the largest pre-exascale architectures available, provides hardware fault resiliency, and enables effective execution on systems with distinct central processing unit-only and GPU-accelerated partitions. The code interfaces with existing multi-configuration electronic structure codes that provide optimized molecular fragment orbitals, configuration interaction coefficients, and the required integrals. Algorithm and implementation details, parallel and accelerated performance benchmarks, and an analysis of the sensitivity of the accuracy of results and computational performance to thresholds used in the calculations are presented.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Planar Collisionless Shock Simulations with the Semi-implicit Particle-in-cell Model FLEKS

This study investigates the applicability of the semi-implicit particle-in-cell code FLexible Exascale Kinetic Simulator (FLEKS) to heliospheric shock simulations. We examine one- and two-dimensional local planar shock simulations, initialized using MHD states with upstream conditions representative of plasmas in the hypersonic, β ∼ 1 regime, for both quasi-perpendicular and quasi-parallel configurations. The refined algorithm in FLEKS proves robust, enabling accurate shock simulations with a grid resolution on the order of the electron inertial length d e . Our simulations successfully capture key shock features, including shock structures (foot, ramp, overshoot, and undershoot), upstream and downstream waves (fast magnetosonic, whistler, Alfvén ion-cyclotron, and mirror modes), and non-Maxwellian particle distributions. Crucially, we find that at least two spatial dimensions are critical for accurately reproducing downstream-wave physics in quasi-perpendicular shocks and capturing the complex dynamics of quasi-parallel shocks, including surface rippling, shocklets, short, large-amplitude magnetic structures, magnetic reconnection, and jets. Furthermore, our parameter studies demonstrate the impact of mass ratio and grid resolution on shock physics. This work provides valuable guidance for selecting appropriate physical and numerical parameters for shock simulations using a semi-implicit PIC method, paving the way for incorporating kinetic shock processes into large-scale collisionless plasma simulations with the MHD-AEPIC model.

plasma astrophysics↗

An Evaluation of Database Solutions to Spatial Object Association

Object association is a common problem encountered in many applications. Spatial object association, also referred to as crossmatch of spatial datasets, is the problem of identifying and comparing objects in two datasets based on their positions in a common spatial coordinate system--one of the datasets may correspond to a catalog of objects observed over time in a multi-dimensional domain; the other dataset may consist of objects observed in a snapshot of the domain at a time point. The use of database management systems to the solve the object association problem provides portability across different platforms and also greater flexibility. Increasing dataset sizes in today's applications, however, have made object association a data/compute-intensive problem that requires targeted optimizations for efficient execution. In this work, we investigate how database-based crossmatch algorithms can be deployed on different database system architectures and evaluate the deployments to understand the impact of architectural choices on crossmatch performance and associated trade-offs. We investigate the execution of two crossmatch algorithms on (1) a parallel database system with active disk style processing capabilities, (2) a high-throughput network database (MySQL Cluster), and (3) shared-nothing databases with replication. We have conducted our study in the context of a large-scale astronomy application with real use-case scenarios.

99 GENERAL AND MISCELLANEOUS↗

Class network routing

Class network routing is implemented in a network such as a computer network comprising a plurality of parallel compute processors at nodes thereof. Class network routing allows a compute processor to broadcast a message to a range (one or more) of other compute processors in the computer network, such as processors in a column or a row. Normally this type of operation requires a separate message to be sent to each processor. With class network routing pursuant to the invention, a single message is sufficient, which generally reduces the total number of messages in the network as well as the latency to do a broadcast. Class network routing is also applied to dense matrix inversion algorithms on distributed memory parallel supercomputers with hardware class function (multicast) capability. This is achieved by exploiting the fact that the communication patterns of dense matrix inversion can be served by hardware class functions, which results in faster execution times.

97 MATHEMATICS AND COMPUTING↗

A Highly Parallel Implementation of K-Means for Multithreaded Architecture

We present a parallel implementation of the popular k-means clustering algorithm for massively multithreaded computer systems, as well as a parallelized version of the KKZ seed selection algorithm. We demonstrate that as system size increases, sequential seed selection can become a bottleneck. We also present an early attempt at parallelizing k-means that highlights critical performance issues when programming massively multithreaded systems. For our case studies, we used data collected from electric power simulations and run on the Cray XMT.

99 GENERAL AND MISCELLANEOUS↗

8th International Special Session on Current Trends in Numerical Simulation for Parallel Engineering Environments

In today's world, the use of parallel programming and architectures is essential for simulating practical problems in engineering and related disciplines. Significant progress in CPU architecture (multi- and many-core CPUs, SMT, transactional memory, virtualization support, shared caches etc.) system scalability, and interconnect technology, continues to provide new opportunities, as well as new challenges for both system architects and software developers. These trends are paralleled by progress in algorithms, simulation techniques, and software integration from multiple disciplines. In its 8th year, ParSim continues to build a bridge between application disciplines and computer science and to help fostering closer cooperations between these fields. Since its successful introduction in 2002, ParSim has established itself as an integral part of the EuroPVM/MPI conference series. In contrast to traditional conferences, emphasis is put on the presentation of up-to-date results with a short turn-around time. We believe that this offers a unique opportunity to present new aspects in this dynamic field and discuss them with a wide, interdisciplinary audience. The EuroPVM/MPI conference series, as one of the prime events in parallel computation, serves as an ideal surrounding for ParSim. This combination enables participants to present and discuss their work within the scope of both the session and the host conference. This year, five papers from authors in five countries were submitted to Par-Sim, and we selected three of them. They cover a range of different application fields including mechanical engineering, material science, and structural engineering simulations. We are confident that this resulted in an attractive special session and that this will be an informal setting for lively discussions as well as for fostering new collaborations. Several people contributed to this event. Thanks go to Jack Dongarra, the EuroPVM/MPI general chair, and to Jan Westerholm, Juha Fagerholm and Jussi Heikonen, the PC chairs, for their encouragement and support to continue the ParSim series at EuroPVM/MPI 2009. We would also like to thank the numerous reviewers, who provided us with their reviews in such a short amount of time (in most cases in just a few days) and thereby helped us to maintain the tight schedule. Last, but certainly not least, we would like to thank all those who took the time to submit papers and hence made this event possible in the first place. We are confident that this session will fulfill its purpose to provide new insights from both the engineering and the computer science side and encourages interdisciplinary exchange of ideas and cooperations, and that this will continue ParSim's tradition at EuroPVM/MPI.

99 GENERAL AND MISCELLANEOUS↗

Block-Iterative Methods for 3D Constant-Coefficient Stencils on GPUs and Multicore CPUs

Block iterative methods are extremely important as smoothers for multigrid methods, as preconditioners for Krylov methods, and as solvers for diagonally dominant linear systems. Developing robust and efficient smoother algorithms suitable for current and evolving GPU and multicore CPU systems is a significant challenge. We address this issue in the case of constant-coefficient stencils arising in the solution of elliptic partial differential equations on structured 3D uniform and adaptively refined block structured grids. Robust, highly parallel implementations of block Jacobi and chaotic block Gauss-Seidel algorithms with exact inversion of the blocks are developed using different parallelization techniques. Experimental results for NVIDIA Fermi/Kepler GPUs and AMD multicore systems are presented.

97 MATHEMATICS AND COMPUTING↗

Parallel simulated annealing with embedded machine learning and multifidelity models for reactor core design

This paper presents extensions to a penalty-free, parallel simulated annealing (SA) algorithm for multi-constrained combinatorial optimization with the aim of embedding multi-fidelity physics models into the annealing procedure. The method uses a low-fidelity, quickly executing model for rapid design space exploration and a high-fidelity model for detailed constraint resolution and on-the-fly bias correction. Machine learning models updated within the annealing procedure were used to bridge the gap between the multi-fidelity models, which led to accurate rapid exploration and efficient detailed constraint resolution. A software implementation of the new multi-fidelity optimization methods, called ML-PSA, was demonstrated on a continuous multi-fidelity optimization problem and a constrained combinatorial PWR lattice design problem. These problems demonstrate some of the features, parallel performance characteristics, and extensible nature of the multi-fidelity SA methods. This paper shows that the developed software and procedure are a general optimization tool that can be applied to a wide variety of scientific and engineering design optimization applications. (authors)

22 GENERAL STUDIES OF NUCLEAR REACTORS↗

Ab Initio Computation of Rotationally-Averaged Pump–Probe X-ray and Electron Diffraction Signals

We develop a new algorithm for the computation of the rotationally averaged elastic molecular diffraction signal for the cases of perpendicular or parallel pump–probe geometries. The algorithm first collocates the charge density from an arbitrary ab initio wave function onto a Becke quadrature grid [A. Becke, J. Chem. Phys. 1988, 88, 2457], providing a high-fidelity multiresolution representation of the charge density. A double sum is then performed over the Becke grid points, and the interaction between points computed using the scattering kernels of Williamson and Zewail [J. C. Williamson and A. H. Zewail, J. Phys. Chem. 1994, 98, 2766]. These kernels analytically average over the molecular orientations with the cos 2 γ selection factor appropriate for one-photon dipole absorption in a perpendicular pump–probe geometry. We demonstrate that the method is converged with small grids containing <500 points/atom. We implement the algorithm on a GPU for increased efficiency and emonstrate the algorithm for molecules with up to a few dozen atoms. We explore the accuracy of the independent atom model (IAM) by comparison with our new and more accurate method. We also investigate the possibility of detecting signatures of electronic transitions in polyatomic pump–probe diffraction experiments.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Iterative diagonalization in augmented plane wave based methods in electronic structure calculations

Due to the increased computer power and advanced algorithms, quantum mechanical calculations based on Density Functional Theory are more and more widely used to solve real materials science problems. In this context large nonlinear generalized eigenvalue problems must be solved repeatedly to calculate the electronic ground state of a solid or molecule. Due to the nonlinear nature of this problem, an iterative solution of the eigenvalue problem can be more efficient provided it does not disturb the convergence of the self-consistent-field problem. The blocked Davidson method is one of the widely used and efficient schemes for that purpose, but its performance depends critically on the preconditioning, i.e. the procedure to improve the search space for an accurate solution. For more diagonally dominated problems, which appear typically for plane wave based pseudopotential calculations, the inverse of the diagonal of (H - ES) is used. However, for the more efficient 'augmented plane wave + local-orbitals' basis set this preconditioning is not sufficient due to large off-diagonal terms caused by the local orbitals. We propose a new preconditioner based on the inverse of (H - {lambda}S) and demonstrate its efficiency for real applications using both, a sequential and a parallel implementation of this algorithm into our WIEN2k code.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

High-Level Synthesis of Irregular Applications: A Case Study on Influence Maximization

The Influence Maximization problem is the problem of identifying a small cohort of actors from a broader population that, when initially activated in a diffusion process, are expected to result in a large number of activations in the population. While the problem is known to be NP-hard, several approximation algorithms have been devised by leveraging its submodular structure. While these algorithms are theoretically efficient, they are computationally very expensive in practice. This work advances the current state-of-the-art parallelization scheme for the IMM algorithm by devising the adoption of custom hardware accelerators implemented on FPGAs by leveraging High Level Synthesis from OpenCL. We study the performance of our proposed approach by exploring optimizations tailored at improving the parallel efficiency of the accelerators and highlight their effects and limitations in accelerating complex graph analytic applications. Our experimental evaluation shows that FPGA acceleration can improve the performance of the LT diffusion model up to 1.72x for the entire application and up to 2.90x for its most important kernel with respect to a CPU only parallel execution. The FPGA acceleration of the LT model shows also a 1.54x reduction in energy consumption when compared to a parallel CPU only run.

Neff, Reece W.↗

Parallel DTFE Surface Density Field Reconstruction

We improve the interpolation accuracy and efficiency of the Delaunay tessellation field estimator (DTFE) for surface density field reconstruction by proposing an algorithm that takes advantage of the adaptive triangular mesh for line-of-sight integration. The costly computation of an intermediate 3D grid is completely avoided by our method and only optimally chosen interpolation points are computed, thus, the overall computational cost is significantly reduced. The algorithm is implemented as a parallel shared-memory kernel for large-scale grid rendered field reconstructions in our distributed-memory framework designed for N-body gravitational lensing simulations in large volumes. We also introduce a load balancing scheme to optimize the efficiency of processing a large number of field reconstructions. Our results show our kernel outperforms existing software packages for volume weighted density field reconstruction, achieving ~ 10x speedup, and our load balancing algorithm gains an additional ~ 3.6x speedup at scales with ~ 16k processes.

97 MATHEMATICS AND COMPUTING↗

Benchmark Comparison for a Multi-Processing Ion Mobility Calculator in the Free Molecular Regime

A benchmark comparison between two ion mobility and collision cross-section (CCS) calculators, MOBCAL and IMoS, is presented here as a standard to test the efficiency and performance of both programs. Utilizing 47 organic ions, results are in excellent agreement between IMoS and MOBCAL in He and N{sub 2,} when both programs use identical input parameters. Due to a more efficiently written algorithm and to its parallelization, IMoS is able to calculate the same CCS (within 1%) with a speed around two orders of magnitude faster than its MOBCAL counterpart when seven cores are used. Due to the high computational cost of MOBCAL in N{sub 2}, reaching tens of thousands of seconds even for small ions, the comparison between IMoS and MOBCAL is stopped at 70 atoms. Large biomolecules (>10000 atoms) remain computationally expensive when IMoS is used in N{sub 2} (even when employing 16 cores). Approximations such as diffuse trajectory methods (DHSS, TDHSS) with and without partial charges and projected area approximation corrections can be used to reduce the total computational time by several folds without hurting the accuracy of the solution. These latter methods can in principle be used with coarse-grained model structures and should yield acceptable CCS results. .

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

Recommended direct simulation Monte Carlo collision model parameters for modeling ionized air transport processes

A systematic approach for calibrating the direct simulation Monte Carlo (DSMC) collision model parameters to achieve consistency in the transport processes is presented. The DSMC collision cross section model parameters are calibrated for high temperature atmospheric conditions by matching the collision integrals from DSMC against ab initio based collision integrals that are currently employed in the Langley Aerothermodynamic Upwind Relaxation Algorithm (LAURA) and Data Parallel Line Relaxation (DPLR) high temperature computational fluid dynamics solvers. The DSMC parameter values are computed for the widely used Variable Hard Sphere (VHS) and the Variable Soft Sphere (VSS) models using the collision-specific pairing approach. The recommended best-fit VHS/VSS parameter values are provided over a temperature range of 1000-20 000 K for a thirteen-species ionized air mixture. Use of the VSS model is necessary to achieve consistency in transport processes of ionized gases. The agreement of the VSS model transport properties with the transport properties as determined by the ab initio collision integral fits was found to be within 6% in the entire temperature range, regardless of the composition of the mixture. The recommended model parameter values can be readily applied to any gas mixture involving binary collisional interactions between the chemical species presented for the specified temperature range.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗