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

Fast Parallel Tensor Times Same Vector for Hypergraphs

Hypergraphs are a popular paradigm to rep- resent complex real-world networks exhibiting multi-way relationships of varying sizes. Mining centrality in hyper- graphs via symmetric adjacency tensors has only recently become computationally feasible for large and complex datasets. To enable scalable computation of these and related hypergraph analytics, here we focus on the Sparse Symmetric Tensor Times Same Vector (S3TTVC) oper- ation. We introduce the Compound Compressed Sparse Symmetric (CCSS) format, an extension of the compact CSS format for hypergraphs of varying hyperedge sizes and present a shared-memory parallel algorithm to compute S3TTVC. We experimentally show S3TTVC computation using the CCSS format achieves better performance than the naive baseline, and is subsequently more performant for hypergraph H-eigenvector centrality.

Shivakumar, Shruti↗

Distributed Data-Driven Optimization for Voltage Regulation in Distribution Systems

Here, this paper proposes a distributed data-driven optimization framework for voltage regulation in distribution systems. The recursive kernel regression and alternating direction method of multipliers (ADMM) are selected to cover the system learning and distributed optimization tasks. The proposed distributed data-driven framework is capable of having a rapid response to system or load changes while considering the operation optimality. Besides, the distributed algorithm parallels the computation tasks and reduces the computational expense of a single agent. To validate the performance of the proposed method, a hypothetical 7-Bus system and the IEEE 123-Bus system are selected to show the effectiveness of the proposed data-driven framework. According to the numerical study results, the proposed method offers great flexibility for selecting customized kernel models for different regions and can effectively improve the system voltage profile in a distributed manner.

24 POWER TRANSMISSION AND DISTRIBUTION↗

SU-E-I-93: Improved Imaging Quality for Multislice Helical CT Via Sparsity Regularized Iterative Image Reconstruction Method Based On Tensor Framelet

Purpose: Inspired by compressive sensing, sparsity regularized iterative reconstruction method has been extensively studied. However, its utility pertinent to multislice helical 4D CT for radiotherapy with respect to imaging quality, dose, and time has not been thoroughly addressed. As the beginning of such an investigation, this work carries out the initial comparison of reconstructed imaging quality between sparsity regularized iterative method and analytic method through static phantom studies using a state-of-art 128-channel multi-slice Siemens helical CT scanner. Methods: In our iterative method, tensor framelet (TF) is chosen as the regularization method for its superior performance from total variation regularization in terms of reduced piecewise-constant artifacts and improved imaging quality that has been demonstrated in our prior work. On the other hand, X-ray transforms and its adjoints are computed on-the-fly through GPU implementation using our previous developed fast parallel algorithms with O(1) complexity per computing thread. For comparison, both FDK (approximate analytic method) and Katsevich algorithm (exact analytic method) are used for multislice helical CT image reconstruction. Results: The phantom experimental data with different imaging doses were acquired using a state-of-art 128-channel multi-slice Siemens helical CT scanner. The reconstructed image quality was compared between TF-based iterative method, FDK and Katsevich algorithm with the quantitative analysis for characterizing signal-to-noise ratio, image contrast, and spatial resolution of high-contrast and low-contrast objects. Conclusion: The experimental results suggest that our tensor framelet regularized iterative reconstruction algorithm improves the helical CT imaging quality from FDK and Katsevich algorithm for static experimental phantom studies that have been performed.

60 APPLIED LIFE SCIENCES↗

Simulation of Magnetic Systems in the Domain with a Corner

Numerical simulation of magnetic systems having corner points is considered. The literature on this topic is reviewed. A method of encapsulating the function behavior near corner points in the difference scheme is proposed for numerical solution of the 2D magnetostatic problem in the iron domain. For the 3D magnetostatic problem in the iron/vacuum domain, the increase in the magnetic field near the corner point is estimated, and a method for construction of an adaptive mesh is proposed. A parallel algorithm is implemented on the graphics-processing unit (GPU) architecture for faster search for the numerical solution of the magnetostatic problem. Numerical simulation is performed for the magnetic system of the SPD detector to be used at the NICA complex (JINR, Dubna).

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

Parallel Computation of Persistent Homology using the Blowup Complex

We describe a parallel algorithm that computes persistent homology, an algebraic descriptor of a filtered topological space. Our algorithm is distinguished by operating on a spatial decomposition of the domain, as opposed to a decomposition with respect to the filtration. We rely on a classical construction, called the Mayer--Vietoris blowup complex, to glue global topological information about a space from its disjoint subsets. We introduce an efficient algorithm to perform this gluing operation, which may be of independent interest, and describe how to process the domain hierarchically. We report on a set of experiments that help assess the strengths and identify the limitations of our method.

97 MATHEMATICS AND COMPUTING↗

Brief announcement: Hypergraph parititioning for parallel sparse matrix-matrix multiplication

The performance of parallel algorithms for sparse matrix-matrix multiplication is typically determined by the amount of interprocessor communication performed, which in turn depends on the nonzero structure of the input matrices. In this paper, we characterize the communication cost of a sparse matrix-matrix multiplication algorithm in terms of the size of a cut of an associated hypergraph that encodes the computation for a given input nonzero structure. Obtaining an optimal algorithm corresponds to solving a hypergraph partitioning problem. Furthermore, our hypergraph model generalizes several existing models for sparse matrix-vector multiplication, and we can leverage hypergraph partitioners developed for that computation to improve application-specific algorithms for multiplying sparse matrices.

97 MATHEMATICS AND COMPUTING↗

Spherical Region Queries on Multicore Architectures

In this short paper, we report the performance of multiple thread-parallel algorithms for spherical region queries on multicore architectures motivated by a challenging data analytics application in materials science. Performances of two tree-based algorithms and a naive algorithm are compared to identify the length scales at which these approaches perform optimally. The optimal algorithm is then used to scale the driving materials science application, which is shown to deliver over 17X speedup using 32 OpenMP threads on data sets containing many millions of atoms.

Lu, Hao↗

Toward Large-Scale Image Segmentation on Summit

Semantic segmentation of images is an important computer vision task that emerges in a variety of application domains such as medical imaging, robotic vision and autonomous vehicles to name a few. While these domain-specific image analysis tasks involve relatively small image sizes (~ 10 2 × 10 2 ), there are many applications that need to train machine learning models on image data with extents that are orders of magnitude larger (~10 4 × 10 4 ). Training deep neural network (DNN) models on large extent images is extremely memory-intensive and often exceeds the memory limitations of a single graphical processing unit, a hardware accelerator of choice for computer vision workloads. Here, an efficient, sample parallel approach to train U-Net models on large extent image data sets is presented. Its advantages and limitations are analyzed and near-linear strong-scaling speedup demonstrated on 256 nodes (1536 GPUs) of the Summit supercomputer. Using a single node of the Summit supercomputer, an early evaluation of a recently released model parallel framework called GPipe is demonstrated to deliver ~ 2X speedup in executing a U-Net model with an order of magnitude larger number of trainable parameters than reported before. Performance bottlenecks for pipelined training of U-Net models are identified and mitigation strategies to improve the speedups are discussed. Together, these results open up the possibility of combining both approaches into a unified scalable pipelined and data parallel algorithm to efficiently train U-Net models with very large receptive fields on data sets of ultra-large extent images.

Seal, Sudip↗

Brief Announcement: Communication Optimal Sparse LU Factorization for Planar Matrices

We introduce a new parallel algorithm for solving sparse LU factorization of planar matrices, which commonly arise in the finite element method for 2D PDEs. Existing scalable methods, such as the multifrontal approach with subtree-to-subcube mapping by Gupta et al. [1] and right-looking with 3D mapping by Sao et al. [2] fail to achieve optimal communication costs for these matrices. Our new algorithm combines 3D mapping and subtree-to-subcube mapping to minimize communication costs while allowing trade-offs between extra memory and reduced communication. We demonstrate that our proposed algorithm attains the communication lower bound up to a factor of O(log log n) in the memory-optimal case and up to a factor of O(log P) in the memory-independent case for an n-dimensional planar sparse matrix on P processors.

Sao, Piyush↗

DIMPLES: Distributed Influence Maximization for Pandemic pLanning on Exascale Systems

We study exascale parallel algorithms for the selection of intervention or monitoring strategies in massive realistic socio-technical networks through scalable Influence Maximization (InfMax) algorithms. We employ novel techniques to enable efficient scaling on up to 8k nodes of OLCF Frontier, with 65k AMD GPUs and 458k AMD CPU cores. Current state-of-the-art InfMax tools are limited to networks with only a few million actors (vertices) and a few hundred million interactions (edges). By overcoming these limitations, we show that our approach is capable of processing a realistic social contact network of the United States with 285 million nodes and about 8 billion edges. This two orders-of-magnitude improvement over the previous state-of-the-art is obtained by leveraging algorithmic advancements for the InfMax problem and designing several problem-specific approaches to overlap communication with computation, improve GPU efficiency, and lower the application’s memory requirements. We evaluate strong scaling for computing 10k most influential seeds using up to 8k nodes of an exascale system, and weak scaling from 128 to 8k system nodes for seed sets ranging from 625 to 40k seeds. We achieve the fastest-known runtime of 25 minutes while performing 48 million diffusion simulations totaling 2.31 petabytes to identify 40k influential seeds using 8k nodes, and take 5.75 minutes to identify 10k seeds while using 4k nodes.

Minutoli, Marco [Pacific Northwest National Labora↗

ECP-ExaGraph/Submodular-b-matching

A b-MATCHING is a subset of edges M such that at most b(v) edges in M are incident on each vertex v, where b(v) is specified. We present a distributed-memory parallel algorithm, b-SUITOR, that computes a b-MATCHING with more than half the maximum weight in a graph with weights on the edges

Ferdous, S M↗

Multiscale Ecosystem for solving Maxwell-Schrodinger equations of open quantum systems (OpenMS)

Light-matter interactions play an important role in many branches of physics, chemistry, energy, and materials science. In the strong coupling regime, light-matter interactions are able to tune the materials properties via the formation of new quasiparticles, such as plasmons and polaritons. However, theoretical and numerical modeling of the light-matter interaction-mediated processes remain a big challenge because light-matter interactions are fundamentally multiscale and multiphysics problems involving multiple interactions between electrons, nuclei, and photons at different time/length scales. In the current community, light-matter interactions were treated at different levels of theoretical complexity in quantum chemistry and quantum optics. In quantum optics or quantum photonics, the matter is usually simplified as a few-level system, and the light is treated quantum-mechanically. On the other hand, quantum chemistry explores first-principles methods, including both single-particle and many-body-based techniques, to describe the electronic properties of matter in detail. However, light is usually prescribed as a classical electromagnetic field, and the light-matter interaction is taken into account as an external potential via classical approximations. This software is designed to fill current modeling shortcomings by delivering a first-ever scalable multiscale platform for simulating light-matter interactions in realistic electromagnetic environments. The software solves Maxwell and Schrodinger equations self-consistent on the heterogeneous platforms. It implements HF/DFT, TDDFT, and coupled-cluster counterparts for light-matter interactions and adopts modular programming to offload massively parallel algorithms on a large number of CPU/GPUs.

Zhang, Yu↗

Tycho 2: A Proxy Application for Kinetic Transport Sweeps

Tycho 2 is a proxy application that implements discrete ordinates (SN) kinetic transport sweeps on unstructured, 3D, tetrahedral meshes. It has been designed to be small and require minimal dependencies to make collaboration and experimentation as easy as possible. Tycho 2 has been released as open source software. The software is currently in a beta release with plans for a stable release (version 1.0) before the end of the year. The code is parallelized via MPI across spatial cells and OpenMP across angles. Currently, several parallelization algorithms are implemented.

97 MATHEMATICS AND COMPUTING↗

Milestone Completion Report WBS 1.3.5.05 ECP/VTK-m FY17Q3 [MS-17/02] Faceted Surface Normals STDA05-3.

The FY17Q3 milestone of the ECP/VTK-m project includes the completion of a VTK-m filter that computes normal vectors for surfaces. Normal vectors are those that point perpendicular to the surface and are an important direction when rendering the surface. The implementation includes the parallel algorithm itself, a filter module to simplify integrating it into other software, and documentation in the VTK-m Users’ Guide. With the completion of this milestone, we are able to necessary information to rendering systems to provide appropriate shading of surfaces. This milestone also feeds into subsequent milestones that progressively improve the approximation of surface direction.

99 GENERAL AND MISCELLANEOUS↗

Asynchronous Navier-Stokes Solver on 3D Unstructured Grids for the Exascale Era

This project has developed multiple fluid dynamics solvers for complex 3D flows using fully asynchronous distributed-memory task-parallel algorithms on top of the Charm++ runtime system. The algorithms solve the Euler or Navier-Stokes equations of compressible flows using unstructured tetrahedron meshes with optional solution-adaptive mesh-, and polynomial-order refinement. We have demonstrated excellent strong scaling up 50K compute cores and the benefits of Charm++’s automatic load balancing.

97 MATHEMATICS AND COMPUTING↗

AEOLUS: Advances in Experimental Design, Optimal Control, and Learning for Uncertain Complex Systems

Sustained advances in the mathematics of modeling and simulation have resulted in the capability today for routine simulation of a number of large scale complex DOE-relevant systems. As remarkable as this capability for solving the so-called forward problem is, it is typically only the first step-an inner loop within an outer loop that explores the simulation model's parameter space and decision space to characterize uncertainty in the model's predictions, learn unknown model parameters from data, design the most informative experiments, determine optimal control strategies, and create optimal designs. Broadly, what unifies all of these outer loop problems is that they are, in one form or another, optimization problems over parameter/control/design space that are constrained by complex uncertain models. To fully realize the power of scientific simulation as a basis for scientific discovery, technological innovation, and rational decision-making, it is imperative to move beyond simulation to tackle the outer loop of optimization for learning from data, experimental design, and control with complex uncertain models. When the models under consideration are large-scale and complex, and when the optimization variable and uncertain parameter spaces are high (or infinite) dimensional, this constitutes a grand challenge of the highest order, and is intractable with conventional methods. To overcome these challenges, the AEOLUS Center was established to develop a unified mathematical, computational, and statistical framework for (1) Learning predictive models from complex data via Bayesian inference and optimization, and (2) Optimizing experiments, processes, and designs using the resulting uncertain models. These problems are intractable with conventional methods, for several reasons: (1) The simulation problems that govern the inner loops of the optimization problems are expensive to execute (due to severe nonlinearity, heterogeneity, multiphysics/multiscale coupling); (2) The optimization variable and uncertain parameter spaces are high dimensional, often stemming from discretizations of infinite dimensional fields such as initial conditions, sources, or material properties. We argue that the key to overcoming these challenges is to develop new mathematical, computational, and statistical methods that exploit the structure of the Bayesian inference and optimization problems mediated by their underlying complex uncertain models. This structure includes the regularity, sparsity, geometry, low intrinsic dimensionality, and multifidelity nature of the maps from uncertain parameter/optimization variable spaces to the specific objectives targeted: Bayesian inference, optimal experimental design, and optimal control design. Black box methods developed as generic tools are incapable of exploiting this structure. To be successful, we must create, integrate, and cross-fertilize ideas across multiple areas of applied math--including approximation theory, Bayesian inference, data science, experimental design, information theory, machine learning, model reduction, optimal control theory, parallel algorithms, PDE-constrained optimization, randomized algorithms, stochastic optimization, and uncertainty quantification--all while exploiting the structure of the problems at hand. With this goal in mind, we have marshaled a team of leading authorities in these areas. While the methods we develop will be broadly applicable across a wide spectrum of DOE problems in which experiments inform models and the systems those models describe must be optimized under uncertainty, we have chosen a specific area, advanced manufacturing and materials, to drive our work. AMM is characterized by complex models across multiple scales, and is a rich source of challenging problems in inference, experimental design, and optimal control, requiring multifaceted and integrated advances in applied mathematics. As such, AMM serves as an excellent vehicle to motivate and demonstrate the advances in applied mathematics developed by our center.

97 MATHEMATICS AND COMPUTING↗

Systematic errors in low-latency gravitational wave parameter estimation impact electromagnetic follow-up observations

Among the most eagerly anticipated opportunities made possible by Advanced LIGO/Virgo are multimessenger observations of compact mergers. Optical counterparts may be short-lived so rapid characterization of gravitational wave (GW) events is paramount for discovering electromagnetic signatures. One way to meet the demand for rapid GW parameter estimation is to trade off accuracy for speed, using waveform models with simplified treatment of the compact objects’ spin. We report on the systematic errors in GW parameter estimation suffered when using different spin approximations to recover generic signals. Component mass measurements can be biased by >5σ using simple-precession waveforms and in excess of 20σ when non-spinning templates are employed. This suggests that electromagnetic observing campaigns should not take a strict approach to selecting which LIGO/Virgo candidates warrant follow-up observations based on low-latency mass estimates. For sky localization, we find that searched areas are up to a factor of ∼2 larger for non-spinning analyses, and are systematically larger for any of the simplified waveforms considered in our analysis. Distance biases for the non-precessing waveforms can be in excess of 100% and are largest when the spin angular momenta are in the orbital plane of the binary. We confirm that spin-aligned waveforms should be used for low-latency parameter estimation at the minimum. Including simple precession, though more computationally costly, mitigates biases except for signals with extreme precession effects. Our results shine a spotlight on the critical need for development of computationally inexpensive precessing waveforms and/or massively parallel algorithms for parameter estimation.

79 ASTRONOMY AND ASTROPHYSICS↗

Chandra Follow-up of the SDSS DR8 Redmapper Catalog Using the MATCha Pipeline

In order to place constraints on cosmology through optical surveys of galaxy clusters, one must first understand the properties of those clusters. To this end, we introduce the Mass Analysis Tool for Chandra (MATCha), a pipeline that uses a parallellized algorithm to analyze archival Chandra data. MATCha simultaneously calculates X-ray temperatures and luminosities and performs centering measurements for hundreds of potential galaxy clusters using archival X-ray exposures. We run MATCha on the redMaPPer SDSS DR8 cluster catalog and use MATCha's output X-ray temperatures and luminosities to analyze the galaxy cluster temperature–richness, luminosity–richness, luminosity–temperature, and temperature–luminosity scaling relations. We detect 447 clusters and determine 246 r 2500 temperatures across all redshifts. Within 0.1 < z < 0.35, we find that r 2500 T X scales with optical richness (λ) as $\mathrm{ln}\left(\tfrac{{k}_{B}{T}_{{\rm{X}}}}{1.0\,\mathrm{keV}}\right)=(0.52\pm 0.05)\mathrm{ln}\left(\tfrac{\lambda }{70}\right)+(1.85\pm 0.03)$ with an intrinsic scatter of $0.27\pm 0.02$ ($1\sigma $). We investigate the distribution of offsets between the X-ray center and redMaPPer center within 0.1 < z < 0.35, finding that 68%.3 ± 6.5% of clusters are well-centered. However, we find a broad tail of large offsets in this distribution, and we explore some of the causes of redMaPPer miscentering.

79 ASTRONOMY AND ASTROPHYSICS↗