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,459 records · Page 81
All sourcesNASA NTRSDOE OSTI
DOE OSTI2017

Parallel Multivariate Spatio-Temporal Clustering of Large Ecological Datasets on Hybrid Supercomputers

A proliferation of data from vast networks of remote sensing platforms (satellites, unmanned aircraft systems (UAS), airborne etc.), observational facilities (meteorological, eddy covariance etc.), state-of-the-art sensors, and simulation models offer unprecedented opportunities for scientific discovery. Unsupervised classification is a widely applied data mining approach to derive insights from such data. However, classification of very large data sets is a complex computational problem that requires efficient numerical algorithms and implementations on high performance computing (HPC) platforms. Additionally, increasing power, space, cooling and efficiency requirements has led to the deployment of hybrid supercomputing platforms with complex architectures and memory hierarchies like the Titan system at Oak Ridge National Laboratory. The advent of such accelerated computing architectures offers new challenges and opportunities for big data analytics in general and specifically, large scale cluster analysis in our case. Although there is an existing body of work on parallel cluster analysis, those approaches do not fully meet the needs imposed by the nature and size of our large data sets. Moreover, they had scaling limitations and were mostly limited to traditional distributed memory computing platforms. We present a parallel Multivariate Spatio-Temporal Clustering (MSTC) technique based on k-means cluster analysis that can target hybrid supercomputers like Titan. We developed a hybrid MPI, CUDA and OpenACC implementation that can utilize both CPU and GPU resources on computational nodes. We describe performance results on Titan that demonstrate the scalability and efficacy of our approach in processing large ecological data sets.

Sreepathi, Sarat↗
DOE OSTI2013

HipGISAXS : a high-performance computing code for simulating grazing-incidence X-ray scattering data

This article describes the development of a flexible grazing-incidence small-angle X-ray scattering (GISAXS) simulation code in the framework of the distorted wave Born approximation that effectively utilizes the parallel processing power provided by graphics processors and multicore processors. The code, entitled High-Performance GISAXS , computes the GISAXS image for any given superposition of user-defined custom shapes or morphologies in a material and for various grazing-incidence angles and sample orientations. These capabilities permit treatment of a wide range of possible sample structures, including multilayered polymer films and nanoparticles on top of or embedded in a substrate or polymer film layers. In cases where the material displays regions of significant refractive index contrast, an algorithm has been implemented to perform a slicing of the sample and compute the averaged refractive index profile to be used as the reference geometry of the unperturbed system. A number of case studies are presented, which demonstrate good agreement with the experimental data for a variety of polymer and hybrid polymer/nanoparticle composite materials. The parallelized simulation code is well suited for addressing the analysis efforts required by the increasing amounts of GISAXS data being produced by high-speed detectors and ultrafast light sources.

Chemistry↗
DOE OSTI2014

Hierarchical computation in the SPMD programming model

Large-scale parallel machines are programmed mainly with the single program, multiple data (SPMD) model of parallelism. While this model has advantages of scalability and simplicity, it does not fit well with divide-and-conquer parallelism or hierarchical machines that mix shared and distributed memory. In this paper, we define the recursive single program, multiple data model (RSPMD) that extends SPMD with a hierarchical team mechanism to support hierarchical algorithms and machines. We implement this model in the Titanium language and describe how to eliminate a class of deadlocks by ensuring alignment of collective operations. We present application case studies evaluating the RSPMD model, showing that it enables divide-and-conquer algorithms such as sorting to be elegantly expressed and that team collective operations increase performance of conjugate gradient by up to a factor of two. The model also facilitates optimizations for hierarchical machines, improving scalability of particle in cell by 8x and performance of sorting and a stencil code by up to 40% and 14%, respectively.

Kamil, A↗
DOE OSTI2014

Robust and efficient overset grid assembly for partitioned unstructured meshes

This paper presents a method to perform efficient and automated Overset Grid Assembly (OGA) on a system of overlapping unstructured meshes in a parallel computing environment where all meshes are partitioned into multiple mesh-blocks and processed on multiple cores. The main task of the overset grid assembler is to identify, in parallel, among all points in the overlapping mesh system, at which points the flow solution should be computed (field points), interpolated (receptor points), or ignored (hole points). Point containment search or donor search, an algorithm to efficiently determine the cell that contains a given point, is the core procedure necessary for accomplishing this task. Donor search is particularly challenging for partitioned unstructured meshes because of the complex irregular boundaries that are often created during partitioning. Another challenge arises because of the large variation in the type of mesh-block overlap and the resulting large load imbalance on multiple processors. Desirable traits for the grid assembly method are efficiency (requiring only a small fraction of the solver time), robustness (correct identification of all point types), and full automation (no user input required other than the mesh system). Additionally, the method should be scalable, which is an important challenge due to the inherent load imbalance. This paper describes a fully-automated grid assembly method, which can use two different donor search algorithms. One is based on the use of auxiliary grids and Exact Inverse Maps (EIM), and the other is based on the use of Alternating Digital Trees (ADT). The EIM method is demonstrated to be more efficient than the ADT method, while retaining robustness. An adaptive load re-balance algorithm is also designed and implemented, which considerably improves the scalability of the method.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2017

The HEP.TrkX Project: deep neural networks for HL-LHC online and offline tracking

Particle track reconstruction in dense environments such as the detectors of the High Luminosity Large Hadron Collider (HL-LHC) is a challenging pattern recognition problem. Traditional tracking algorithms such as the combinatorial Kalman Filter have been used with great success in LHC experiments for years. However, these state-of-the-art techniques are inherently sequential and scale poorly with the expected increases in detector occupancy in the HL-LHC conditions. The HEP.TrkX project is a pilot project with the aim to identify and develop cross-experiment solutions based on machine learning algorithms for track reconstruction. Machine learning algorithms bring a lot of potential to this problem thanks to their capability to model complex non-linear data dependencies, to learn effective representations of high-dimensional data through training, and to parallelize easily on high-throughput architectures such as GPUs. This contribution will describe our initial explorations into this relatively unexplored idea space. Furthermore, we will discuss the use of recurrent (LSTM) and convolutional neural networks to find and fit tracks in toy detector data.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗
DOE OSTI2018

The HEP.TrkX Project: Deep Learning for Particle Tracking

Charged particle reconstruction in dense environments, such as the detectors of the High Luminosity Large Hadron Collider (HL-LHC) is a challenging pattern recognition problem. Traditional tracking algorithms, such as the combinatorial Kalman Filter, have been used with great success in HEP experiments for years. However, these state-of-the-art techniques are inherently sequential and scale quadratically or worse with increased detector occupancy. The HEP.TrkX project is a pilot project with the aim to identify and develop cross-experiment solutions based on machine learning algorithms for track reconstruction. Machine learning algorithms bring a lot of potential to this problem thanks to their capability to model complex non-linear data dependencies, to learn effective representations of high-dimensional data through training, and to parallelize easily on high-throughput architectures such as FPGAs or GPUs. In this paper we present the evolution and performance of our recurrent (LSTM) and convolutional neural networks moving from basic 2D models to more complex models and the challenges of scaling up to realistic dimensionality/sparsity.

Tsaris, Aristeidis↗
DOE OSTI2020

3D fault architecture controls the dynamism of earthquake swarms

The vibrant evolutionary patterns made by earthquake swarms are incompatible with standard, effectively two-dimensional (2D) models for general fault architecture. Here we leverage advances in earthquake monitoring with a deep-learning algorithm to image a fault zone hosting a 4-year-long swarm in southern California. We infer that fluids are naturally injected into the fault zone from below and diffuse through strike-parallel channels while triggering earthquakes. A permeability barrier initially limits up-dip swarm migration but ultimately is circumvented. This enables fluid migration within a shallower section of the fault with fundamentally different mechanical properties. Our observations provide high-resolution constraints on the processes by which swarms initiate, grow, and arrest. These findings illustrate how swarm evolution is strongly controlled by 3D variations in fault architecture.

58 GEOSCIENCES↗
DOE OSTI2026

Integral Kernel Methods for Nonlinear Parabolic-Elliptic Systems

Nonlinear parabolic-elliptic systems arise in many physical, biological, and chemical phenomena such as chemotaxis, ion transport, self-gravitating particles, and Brownian vortices. Existing methods struggle with the strong coupling and high nonlinearity and nonlocality of some of these systems, especially the ill-conditioned, convection-dominated problems. To overcome numerical difficulties, current approaches rely on initial guesses, preconditioning, or iterative techniques with no convergence guarantees. They might suffer from poor scalability, large memory usage, and difficulty to parallelize. Inspired by the connection of parabolic-elliptic systems to stochastic processes, we introduce a novel meshless, monolithic, and fully explicit method that naturally encapsulates the elliptic and parabolic operators into a single step which updates each node deterministically with global information. By being fully quadrature-based, it avoids solving systems of discretized equations and does not utilize initial guesses or preconditioning, while requiring little memory and being easy to parallelize. We first derive the method in an integral kernel formulation with quadratic complexity in the number of integration nodes and then leverage kernel-independent fast multipole methods (FMM) to present a scalable algorithm with linear complexity. We provide numerical examples for the Poisson-Nernst-Planck equations in one, two, and three dimensions, together with the derivation of the integral kernel for each case. Furthermore, the examples demonstrate the fast convergence and scalability of the FMM-accelerated algorithm, as well as its suitability for convection-dominated problems, making it competitive against traditional PDE solvers.

PDE systems↗
DOE OSTI2016

Livermore Big Artificial Neural Network Toolkit

LBANN is a toolkit that is designed to train artificial neural networks efficiently on high performance computing architectures. It is optimized to take advantages of key High Performance Computing features to accelerate neural network training. Specifically it is optimized for low-latency, high bandwidth interconnects, node-local NVRAM, node-local GPU accelerators, and high bandwidth parallel file systems. It is built on top of the open source Elemental distributed-memory dense and spars-direct linear algebra and optimization library that is released under the BSD license. The algorithms contained within LBANN are drawn from the academic literature and implemented to work within a distributed-memory framework.

Essen, BrianVan↗
DOE OSTI2016

Livermore Big Artificial Neural Network Toolkit

LBANN is a toolkit that is designed to train artificial neural networks efficiently on high performance computing architectures. It is optimized to take advantages of key High Performance Computing features to accelerate neural network training. Specifically it is optimized for low-latency, high bandwidth interconnects, node-local NVRAM, node-local GPU accelerators, and high bandwidth parallel file systems. It is built on top of the open source Elemental distributed-memory dense and spars-direct linear algebra and optimization library that is released under the BSD license. The algorithms contained within LBANN are drawn from the academic literature and implemented to work within a distributed-memory framework.

Essen, Brian Van↗
DOE OSTI2025

Implementation of a Mesh refinement algorithm into the quasi-static PIC code QuickPIC

Plasma-based acceleration (PBA) has emerged as a promising candidate for the accelerator technology used to build a future linear collider and/or an advanced light source. In PBA, a trailing or witness particle beam is accelerated in the plasma wave wakefield (WF) created by a laser or particle beam driver. The WF is often nonlinear and involves the crossing of plasma particle trajectories in real space and thus particle-in-cell methods are used. The distance over which the drive beam evolves is several orders of magnitude larger than the wake wavelength. This large disparity in length scales is amenable to the quasi-static approach. Three-dimensional (3D), quasi-static (QS), particle-in-cell (PIC) codes, e.g., QuickPIC, have been shown to provide high fidelity simulation capability with 2-4 orders of magnitude speedup over 3D fully explicit PIC codes. In PBA, the witness beam needs to be matched to the focusing forces of the WF to reduce the emittance growth. In some linear collider designs, the matched spot size of the witness beam can be 2 to 3 orders of magnitude smaller than the spot size (and wavelength) of the wakefield. Such an additional disparity in length scales is ideal for mesh refinement where the WF within the witness beam is described on a finer mesh than the rest of the WF. A mesh refinement scheme is described that has been implemented into the 3D QS PIC code, QuickPIC. Very fine (high) resolution is used in a small spatial region that includes the witness beam and progressively coarser resolutions in the rest of the simulation domain. A fast multigrid Poisson solver has been implemented for the field solve on the refined meshes and a Fast Fourier Transform (FFT) based Poisson solver is used for the coarse mesh. The code has been parallelized with both MPI and OpenMP, and the parallel scalability has also been improved by using pipelining. A preliminary adaptive mesh refinement technique is described to optimize the computational time for simulations with an evolving witness beam size. Several test problems are used to verify that the mesh refinement algorithm provides accurate results. Additionally, the results are benchmarked against highly resolved simulations exhibiting near-azimuthal symmetry, performed using QPAD—a novel hybrid QS PIC code that uses a PIC description in the coordinates (r, ct – z) and a gridless description in the azimuthal angle, Φ.

Linear collider↗
DOE OSTI2026

FullWave — A Full Wave Parallel Code for Modeling RF Fields in Hot Tokamak Plasma

FullWave is a computer code that simulates how radio-frequency (RF) waves travel and deposit energy in the hot plasma inside a fusion reactor. RF waves are used to heat the plasma and drive electrical current, which is essential for sustaining fusion reactions. The code uses a new algorithm that can handle much finer spatial detail than previous codes — more than 100 times finer — while running efficiently on national supercomputers. It incorporates a detailed physics model that captures subtle kinetic effects important for accurate prediction of wave behavior. Under this project, FullWave was extended to cover multiple RF frequency ranges relevant to present and future tokamaks, and validated against experimental parameters from the DIII-D tokamak at General Atomics. Results were published in peer-reviewed journal articles.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗
DOE OSTI2020

ELSI — An open infrastructure for electronic structure solvers

Routine applications of electronic structure theory to molecules and periodic systems need to compute the electron density from given Hamiltonian and, in case of non-orthogonal basis sets, overlap matrices. System sizes can range from few to thousands or, in some examples, millions of atoms. Different discretization schemes (basis sets) and different system geometries (finite non-periodic vs. infinite periodic boundary conditions) yield matrices with different structures. The ELectronic Structure Infrastructure (ELSI) project provides an open-source software interface to facilitate the implementation and optimal use of high-performance solver libraries covering cubic scaling eigensolvers, linear scaling density-matrix-based algorithms, and other reduced scaling methods in between. In this paper, we present recent improvements and developments inside ELSI, mainly covering (1) new solvers connected to the interface, (2) matrix layout and communication adapted for parallel calculations of periodic and/or spin-polarized systems, (3) routines for density matrix extrapolation in geometry optimization and molecular dynamics calculations, and (4) general utilities such as parallel matrix I/O and JSON output. The ELSI interface has been integrated into four electronic structure code projects (DFTB+, DGDFT, FHI-aims, SIESTA), allowing us to rigorously benchmark the performance of the solvers on an equal footing. Based on results of a systematic set of large-scale benchmarks performed with Kohn–Sham density-functional theory and density-functional tight-binding theory, we identify factors that strongly affect the efficiency of the solvers, and propose a decision layer that assists with the solver selection process. As a result, we describe a reverse communication interface encoding matrix-free iterative solver strategies that are amenable, e.g., for use with planewave basis sets.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2018

A comparative study of shear band tracking strategies in three-dimensional finite elements with embedded weak discontinuities

We present a computational framework for the treatment of shear localization in metallic materials under dynamic loading, based on the integration of a shear band tracking strategy into an explicit 3D finite element formulation with embedded weak discontinuities. Within this computational framework, an embedded shear band’s mid-surface is represented by an iso-surface of a level set function, which is obtained by solving a heatconduction type boundary value problem (BVP). The solution of this BVP is carried out either globally over the entire problem domain, or locally at the level of individual elements in the mesh. In this paper, we present a detailed comparison of these global and local algorithmic implementations of the shear band tracking strategy. Numerical results obtained using these two implementations, and using a simplified formulation without shear band tracking, are presented and compared. Moreover, we compare the computational efficiency and parallel scaling performance of the local and global implementations. This comparative study shows that both implementations can simulate the initiation of two independent shear bands and their propagation past each other without merging, whereas only the global implementation can successfully simulate the merging of two branches of a single shear band. This study also confirms that the global implementation is more computationally intensive, since it requires a global system of linear equations associated with the level set BVP to be solved at each time step. Both implementations exhibit very good scalability in domain decomposition-based parallel simulations.

36 MATERIALS SCIENCE↗
DOE OSTI2015

Collective I/O Tuning Using Analytical and Machine-Learning Models

The ever larger demand of scientific applications for computation and data is currently driving a continuous increase in scale of parallel computers. The inherent complexity of scaling up a computing systems in terms of both hardware and software stack exposes an increasing number of factors impacting the performance and complicating the process of optimization. In particular, the optimization of parallel I/O has become increasingly challenging due to increasing storage hierarchy and well known performance variability of shared storage systems. This paper focuses on model-based autotuning of the two-phase collective I/O algorithm from a popular MPI distribution on the Blue Gene/Q architecture. We propose a novel hybrid model, constructed as a composition of analytical models for communication and storage operations and black-box models for the performance of the individual operations. We perform an in-depth study of the complexity involved in performance modeling including architecture, software stack and noise. In particular we address this challenges of modeling the performance of shared storage systems by building a benchmark that helps synthesizing factors such as topology, file caching, and noise. The experimental results show that the hybrid approach produces significantly better results than state-of-the-art machine learning approaches and shows a higher robustness to noise, at the cost of a higher modeling complexity

I/O performance modeling↗
DOE OSTI2020

Population Count on Intel® CPU, GPU, and FPGA

Population count is a primitive used in many applications. Commodity processors have dedicated instructions for achieving high-performance population count. Motivated by the productivity of high-level synthesis and the importance of population count, in this paper we investigated the OpenCL implementations of population count algorithms, and evaluated their performance and resource utilizations on an FPGA. Based on the results, we select the most efficient implementation. Then we derived a reduction pattern from a representative application of population count. We parallelized the reduction with atomic functions, and optimized it with vectorized memory accesses, tree reduction, and compute-unit duplication. We evaluated the performance of the reduction kernel on an Intel (R) Xeon (R) CPU and an Intel (R) IrisT Pro integrated GPU, and an FPGA card that features an Intel (R) Arria (R) 10 FPGA. When DRAM memory bandwidth is comparable on the three computing platforms, the FPGA can achieve the highest kernel performance for large workload. On the other hand, we described performance bottlenecks on the FPGA. To make FPGAs more competitive in raw performance compared to high-performant CPU and GPU platforms, it is important to increase external memory bandwidth, minimize data movement between a host and a device, and reduce OpenCL runtime overhead on an FPGA.

heterogeneous computing↗