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 973 records · Page 54
All sourcesNASA NTRSDOE OSTI
DOE OSTI2019

Extreme Scale De Novo Metagenome Assembly

Metagenome assembly is the process of transforming a set of short, overlapping, and potentially erroneous DNA segments from environmental samples into the accurate representation of the underlying microbiomes's genomes. State-of-the-art tools require big shared memory machines and cannot handle contemporary metagenome datasets that exceed Terabytes in size. In this paper, we introduce the MetaHipMer pipeline, a high-quality and high-performance metagenome assembler that employs an iterative de Bruijn graph approach. MetaHipMer leverages a specialized scaffolding algorithm that produces long scaffolds and accommodates the idiosyncrasies of metagenomes. MetaHipMer is end-to-end parallelized using the Unified Parallel C language and therefore can run seamlessly on shared and distributed-memory systems. Experimental results show that MetaHipMer matches or outperforms the state-of-the-art tools in terms of accuracy. Ultimately, MetaHipMer scales efficiently to large concurrencies and is able to assemble previously intractable grand challenge metagenomes. We demonstrate the unprecedented capability of MetaHipMer by computing the first full assembly of the Twitchell Wetlands dataset, consisting of 7.5 billion reads - size 2.6 TBytes.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2015

Iterative stability analysis of spatial domain decomposition based on block Jacobi algorithm for the diamond-difference scheme

Here, we study convergence of the integral transport matrix method (ITMM) based on a parallel block Jacobi (PBJ) iterative strategy for solving particle transport problems. The ITMM is a spatial domain decomposition method proposed for massively parallel computations. AFourier analysis of the PBJ-based iterations applied to SN diamond-difference equations in 1D slab and 2D Cartesian geometries is performed. It is carried out for infinite-medium problems with homogeneous material properties. To analyze the performance of the ITMM with the PBJ algorithm and evaluate its potential in scalability we consider a limiting case of one spatial cell per subdomain. The analysis shows that in such limit the spectral radius of the iteration method is one without regard to values of the scattering ratio and optical thickness of the spatial cells. This implies lack of convergence in infinite medium. Numerical results of finite-medium problems are presented. They demonstrate effects of finite size of spatial domain on the performance of the iteration algorithm as well as its asymptotic behavior when the extent of the spatial domain increases. Finally, these numerical experiments also show that for finite domains iterative convergence to a finite criterion is achievable in a multiple of the sum of number of cells in each dimension.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2022

Estimating the randomness of quantum circuit ensembles up to 50 qubits

Random quantum circuits have been utilized in the contexts of quantum supremacy demonstrations, variational quantum algorithms for chemistry and machine learning, and blackhole information. The ability of random circuits to approximate any random unitaries has consequences on their complexity, expressibility, and trainability. To study this property of random circuits, we develop numerical protocols for estimating the frame potential, the distance between a given ensemble and the exact randomness. Our tensor-network-based algorithm has polynomial complexity for shallow circuits and is high-performing using CPU and GPU parallelism. We study 1. local and parallel random circuits to verify the linear growth in complexity as stated by the Brown–Susskind conjecture, and; 2. hardware-efficient ansätze to shed light on its expressibility and the barren plateau problem in the context of variational algorithms. Our work shows that large-scale tensor network simulations could provide important hints toward open problems in quantum information science.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2016

SU-G-TeP1-15: Toward a Novel GPU Accelerated Deterministic Solution to the Linear Boltzmann Transport Equation

Purpose: To develop a Graphic Processor Unit (GPU) accelerated deterministic solution to the Linear Boltzmann Transport Equation (LBTE) for accurate dose calculations in radiotherapy (RT). A deterministic solution yields the potential for major speed improvements due to the sparse matrix-vector and vector-vector multiplications and would thus be of benefit to RT. Methods: In order to leverage the massively parallel architecture of GPUs, the first order LBTE was reformulated as a second order self-adjoint equation using the Least Squares Finite Element Method (LSFEM). This produces a symmetric positive-definite matrix which is efficiently solved using a parallelized conjugate gradient (CG) solver. The LSFEM formalism is applied in space, discrete ordinates is applied in angle, and the Multigroup method is applied in energy. The final linear system of equations produced is tightly coupled in space and angle. Our code written in CUDA-C was benchmarked on an Nvidia GeForce TITAN-X GPU against an Intel i7-6700K CPU. A spatial mesh of 30,950 tetrahedral elements was used with an S4 angular approximation. Results: To avoid repeating a full computationally intensive finite element matrix assembly at each Multigroup energy, a novel mapping algorithm was developed which minimized the operations required at each energy. Additionally, a parallelized memory mapping for the kronecker product between the sparse spatial and angular matrices, including Dirichlet boundary conditions, was created. Atomicity is preserved by graph-coloring overlapping nodes into separate kernel launches. The one-time mapping calculations for matrix assembly, kronecker product, and boundary condition application took 452±1ms on GPU. Matrix assembly for 16 energy groups took 556±3s on CPU, and 358±2ms on GPU using the mappings developed. The CG solver took 93±1s on CPU, and 468±2ms on GPU. Conclusion: Three computationally intensive subroutines in deterministically solving the LBTE have been formulated on GPU, resulting in two orders of magnitude speedup. Funding support from Natural Sciences and Engineering Research Council and Alberta Innovates Health Solutions. Dr. Fallone is a co-founder and CEO of MagnetTx Oncology Solutions (under discussions to license Alberta bi-planar linac MR for commercialization).

60 APPLIED LIFE SCIENCES↗
DOE OSTI2019

A communication-avoiding 3D algorithm for sparse LU factorization on heterogeneous systems

We propose a new algorithm to improve the strong scalability of right-looking sparse LU factorization on distributed memory systems. Our 3D algorithm for sparse LU uses a three-dimensional MPI process grid, exploits elimination tree parallelism, and trades off increased memory for reduced per-process communication. We also analyze the asymptotic improvements for planar graphs (e.g., those arising from 2D grid or mesh discretizations) and certain non-planar graphs (specifically for 3D grids and meshes). For a planar graph with $n$ vertices, our algorithm reduces communication volume asymptotically in $n$ by a factor of $\mathscr{O}$ $\Big(\sqrt{log \ n}\Big)$ and latency by a factor of $\mathscr{O}$ $(log \ n)$. For nonplanar cases, our algorithm can reduce the per-process communication volume by 3× and latency by $\mathscr{O}$ $\Big(n^\frac13\Big)$ times. In all cases, the memory needed to achieve these gains is a constant factor. We implemented our algorithm by extending the 2D data structure used in SuperLU_DIST. Our new 3D code achieves empirical speedups up to 27× for planar graphs and up to 3.3× for non-planar graphs over the baseline 2D SuperLU_DIST when run on 24,000 cores of a Cray XC30. We extend the 3D algorithm for heterogeneous architectures by adding the Highly Asynchronous Lazy Offload (Halo) algorithm for co-processor offload. On 4096 nodes of a Cray XK7 with 32,768 CPU cores and 4096 Nvidia K20x GPUs, the 3D algorithm achieves empirical speedups up to 24× for planar graphs and 3.5× for non-planar graphs over the baseline 2D SuperLU_DIST with co-processor acceleration.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2015

A method for data handling numerical results in parallel OpenFOAM simulations

Parallel computational fluid dynamics simulations produce vast amount of numerical result data. This paper introduces a method for reducing the size of the data by replaying the interprocessor traffic. The results are recovered only in certain regions of interest configured by the user. A known test case is used for several mesh partitioning scenarios using the OpenFOAM toolkit{sup ®}[1]. The space savings obtained with classic algorithms remain constant for more than 60 Gb of floating point data. Our method is most efficient on large simulation meshes and is much better suited for compressing large scale simulation results than the regular algorithms.

42 ENGINEERING↗
DOE OSTI2025

Practical Implementation of GPU-based Computing at the Grid Edge for Resilience Scenarios

This paper presents a practical implementation of GPU-accelerated computing at the grid edge to enhance power system resilience through next-generation smart meters. Advanced Metering Infrastructure (AMI) systems rely predominantly on centralized processing architectures, which limit real-time response capabilities during grid disturbances. This work proposes the integration of GPU-enabled computational platforms directly within smart meter to enable local execution support for power system analytics, fault detection algorithms, and optimization routines. The proposed framework uses the Julia programming language to leverage highperformance parallel computing capabilities while maintaining code portability and development efficiency. We use two experimental scenarios to benchmark the computational feasibility of this approach: sparse linear system solutions representative of power flow analyses, and multi-stage production cost simulations incorporating unit commitment and economic dispatch operations. Results demonstrate that computationally intensive power system algorithms, such as those supporting resilience scenario calculations, can be effectively executed at the distribution edge using commercially available embedded GPU hardware. Keywords—GPU acceleration, edge computing, smart meters, grid resilience, AMI, resilience.

De Souza, Reubun [School of Electrical Engineering↗
DOE OSTI2025

Quantum Simulators and Applications on Quantum Framework

Simulating quantum circuits is essential for validating quantum algorithms. However, no single simulator consistently performs best - efficiency depends on circuit structure, entanglement, and depth. In this work, we integrate Qiskit-Aer (state-vector and matrix product state) and QTensor, a tree-tensor-network based simulator, into the Quantum Framework (QFw), a modular platform that supports multiple quantum backends via a unified interface. We also enable distributed quantum approximate optimization algorithm (DQAOA) application compatibility with QFw, allowing sub-problems to be solved in parallel at scale. We then benchmark DQAOA and TFIM (transverse field Ising model) circuits across supported simulators, showing how performance varies significantly with problem type. All simulations are deployed on the Frontier supercomputer using QFw's MPI-based orchestration for distributed, multinode execution. These results underscore the need for simulatoragnostic infrastructure to enable systematic evaluation and highperformance scaling of quantum workloads. QFw provides a practical and extensible path toward reproducible quantum algorithm development across diverse application domains.

Chundury, Srikar [ORNL] (ORCID:0009000183359259)↗
DOE OSTI2020

PySpawn: Software for Nonadiabatic Quantum Molecular Dynamics

The ab initio multiple spawning (AIMS) method enables nonadiabatic quantum molecular dynamics simulations in an arbitrary number of dimensions, with potential energy surfaces provided by electronic structure calculations performed on-the-fly. However, the intricacy of the AIMS algorithm complicates software development, deployment on modern shared computer resources, and post-simulation data analysis. PySpawn is a nonadiabatic molecular dynamics software package that addresses these issues. Here, the program is designed to be easily interfaced with electronic structure software, and an interface to the TeraChem software package is described here. PySpawn introduces a task-based reorganization of the AIMS algorithm, allowing fine-grained restart capability and setting the stage for efficient parallelization in a future release. PySpawn includes a user-friendly and interactive Python analysis module that will enable novice users to painlessly adopt AIMS. As a demonstration of PySpawn’s simulation capability and analysis module, we report complete active space self-consistent field–based AIMS simulations of the 1,2- dithienyl-1,2-dicyanoethene molecule, a promising molecular photoswitch.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2018

Reduced Free Energy Perturbation/Hamiltonian Replica Exchange Molecular Dynamics Method with Unbiased Alchemical Thermodynamic Axis

We report that replica-exchange molecular dynamics (REMD) has been proven to efficiently improve the convergence of free energy perturbation (FEP) calculations involving considerable reorganization of their surrounding. We previously introduced the FEP/(λ,H)-REMD algorithm for ligand binding, in which replicas along the alchemical thermodynamic coupling axis λ were expanded as a series of Hamiltonian boosted replicas along a second axis to form a two-dimensional (2D) replica-exchange exchange map [Jiang, W.; Roux, B., J. Chem. Theory Comput. 2010, 6 (9), 2559-2565]. Aiming to achieve a similar performance at a lower computational cost, we propose here a modified version of this algorithm in which only the end-states along the alchemical axis are augmented by boosted replicas. The reduced FEP/(λ,H)-REMD method with one-dimensional (1D) unbiased alchemical thermodynamic coupling axis λ is implemented on the basis of generic multiple copy algorithm (MCA) module of the biomolecular simulation program NAMD. The flexible MCA framework of NAMD enables a user to design customized replica-exchange patterns through Tcl scripting in the context of a highly parallelized simulation program without touching the source code. Two Hamiltonian tempering boosting scheme were examined with the new algorithm: a first one based on potential energy rescaling of a pre-identified “solute”, and a second one via the introduction of flattening torsional free energy barriers. As two illustrative examples with reliable experiment data, the absolute binding free energies of pxylene and n-butylbenzene to the nonpolar cavity of the L99A mutant of T4 lysozyme were calculated. Lastly, the tests demonstrate that the new protocol efficiently enhances the sampling of torsional motions for backbone and side chains around the binding pocket and accelerates the convergence of the free energy computations.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2020

C-SAW: a framework for graph sampling and random walk on GPUs

Many applications require to learn, mine, analyze and visualize large-scale graphs. These graphs are often too large to be addressed efficiently using conventional graph processing technologies. Fortunately, recent research efforts find out graph sampling and random walk, which significantly reduce the size of original graphs, can benefit the tasks of learning, mining, analyzing and visualizing large graphs by capturing the desirable graph properties. This paper introduces C-SAW, the first framework that accelerates Sampling and Random Walk framework on GPUs. Particularly, C-SAW makes three contributions: First, our framework provides a generic API which allows users to implement a wide range of sampling and random walk algorithms with ease. Second, offloading this framework on GPU, we introduce warp-centric parallel selection, and two novel optimizations for collision migration. Third, towards supporting graphs that exceed the GPU memory capacity, we introduce efficient data transfer optimizations for out-of-memory and multi-GPU sampling, such as workload-aware scheduling and batched multi-instance sampling. Taken together, our framework constantly outperforms the state of the art projects in addition to the capability of supporting a wide range of sampling and random walk algorithms.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

A supernodal all-pairs shortest path algorithm

We show how to exploit graph sparsity in the Floyd-Warshall algorithm for the all-pairs shortest path (Apsp) problem. Floyd-Warshall is an attractive choice for Apsp on high-performing systems due to its structural similarity to solving dense linear systems and matrix multiplication. However, if sparsity of the input graph is not properly exploited, Floyd-Warshall will perform unnecessary asymptotic work and thus may not be a suitable choice for many input graphs. To overcome this limitation, the key idea in our approach is to use the known algebraic relationship between Floyd-Warshall and Gaussian elimination, and import several algorithmic techniques from sparse Cholesky factorization, namely, fill-in reducing ordering, symbolic analysis, supernodal traversal, and elimination tree parallelism. When combined, these techniques reduce computation, improve locality and enhance parallelism. We implement these ideas in an efficient shared memory parallel prototype that is orders of magnitude faster than an efficient multi-threaded baseline Floyd-Warshall that does not exploit sparsity. Our experiments suggest that the Floyd-Warshall algorithm can compete with Dijkstra's algorithm (the algorithmic core of Johnson's algorithm) for several classes sparse graphs.

Sao, Piyush↗
DOE OSTI2016

SU-C-207A-01: A Novel Maximum Likelihood Method for High-Resolution Proton Radiography/proton CT

Purpose: Multiple Coulomb scattering is the largest contributor to blurring in proton imaging. Here we tested a maximum likelihood least squares estimator (MLLSE) to improve the spatial resolution of proton radiography (pRad) and proton computed tomography (pCT). Methods: The object is discretized into voxels and the average relative stopping power through voxel columns defined from the source to the detector pixels is optimized such that it maximizes the likelihood of the proton energy loss. The length spent by individual protons in each column is calculated through an optimized cubic spline estimate. pRad images were first produced using Geant4 simulations. An anthropomorphic head phantom and the Catphan line-pair module for 3-D spatial resolution were studied and resulting images were analyzed. Both parallel and conical beam have been investigated for simulated pRad acquisition. Then, experimental data of a pediatric head phantom (CIRS) were acquired using a recently completed experimental pCT scanner. Specific filters were applied on proton angle and energy loss data to remove proton histories that underwent nuclear interactions. The MTF10% (lp/mm) was used to evaluate and compare spatial resolution. Results: Numerical simulations showed improvement in the pRad spatial resolution for the parallel (2.75 to 6.71 lp/cm) and conical beam (3.08 to 5.83 lp/cm) reconstructed with the MLLSE compared to averaging detector pixel signals. For full tomographic reconstruction, the improved pRad were used as input into a simultaneous algebraic reconstruction algorithm. The Catphan pCT reconstruction based on the MLLSE-enhanced projection showed spatial resolution improvement for the parallel (2.83 to 5.86 lp/cm) and conical beam (3.03 to 5.15 lp/cm). The anthropomorphic head pCT displayed important contrast gains in high-gradient regions. Experimental results also demonstrated significant improvement in spatial resolution of the pediatric head radiography. Conclusion: The proposed MLLSE shows promising potential to increase the spatial resolution (up to 244%) in proton imaging.

60 APPLIED LIFE SCIENCES↗
DOE OSTI2017

Scaling Up Data-Parallel Analytics Platforms: Linear Algebraic Operation Cases

Linear algebraic operations such as matrix manipulations form the kernel of many machine learning and other crucial algorithms. Scaling up as well as scaling out such algorithms are key to supporting large scale data analysis that require efficient processing over millions of data samples. To this end, we present, ARION, a hardware acceleration based approach for scaling-up individual tasks of Spark, a popular data-parallel analytics platform. We support both linear algebraic operations of between two dense matrices, and between sparse and dense matrices in distributed environments. ARION provides a flexible control of acceleration according to matrix density, along with efficient scheduling based on runtime resource utilization. We demonstrate the benefit of our approach for general matrix multiplication operations over large matrices with up to four billion elements by using Gramian matrix computation that is commonly used in machine learning. Experiments show that our approach achieves more than 2× and 1.5× end-to-end performance speedups for dense and sparse matrices, respectively, and up to 57.04× faster computation compared to MLlib, a state of the art Spark-based implementation. This work is sponsored in part by the NSF under the grants: CNS-1565314, CNS-1405697, and CNS-1615411. The manuscript has been authored by UT-Battelle, LLC under Contract No. DE-AC05-00OR22725 with the U.S. Department of Energy. The United States Government retains and the publisher, by accepting the article for publication, acknowledges that the United States Government retains a non-exclusive, paid-up, irrevocable, world-wide license to publish or reproduce the published form of this manuscript, or allow others to do so, for United States Government purposes. The Department of Energy will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan (http://energy.gov/downloads/doe-public-access-plan). This research used resources of the Oak Ridge Leadership Computing Facility at the Oak Ridge National Laboratory, which is supported by the Office of Science of the U.S. Department of Energy under Contract No. DE-AC05-00OR22725.

Xu, Luna↗
DOE OSTI2016

An S N Algorithm for Modern Architectures

LANL discrete ordinates transport packages are required to perform large, computationally intensive time-dependent calculations on massively parallel architectures, where even a single such calculation may need many months to complete. While KBA methods scale out well to very large numbers of compute nodes, we are limited by practical constraints on the number of such nodes we can actually apply to any given calculation. Instead, we describe a modified KBA algorithm that allows realization of the reductions in solution time offered by both the current, and future, architectural changes within a compute node.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Grain structure and texture selection regimes in metal powder bed fusion

Additive manufacturing (AM) offers opportunities to produce complex part geometries not possible with conventional processing and in some cases even improve part performance. However, adoption has been slowed by difficulties assessing microstructure variability and there is no straightforward approach to relate processing to grain structure characteristics. In this study, datasets from AdditiveFOAM heat transport simulations of laser powder bed fusion (LPBF) are used to drive ExaCA simulations of grain structure. The GPU utilization of ExaCA and an algorithmic update for modeling melt pool overlap region solidification enabled rapid and parallel simulation across a wider range of process conditions than previously explored with cellular automata-based solidification models. A texture selection angle $θ_s$ is defined based on melt pool overlap geometry, and the range of $θ_s$ over which a commonly observed texture transition occurs in characterized AM builds was well-reproduced by ExaCA simulations over a wide range of melt pool shape, hatch spacing, and layer height. ExaCA simulations with 90 degree rotation of the scan direction on every other layer reproduced a number of trends from the AM literature including grain refinement, the dominance of layers with larger melt pools on the final grain structure, and the weakening or strengthening of texture depending on odd and even layer melt pool overlap geometry. EBSD data from a benchmark AM part is used to validate the simulated mechanism of a layer rotation-induced texture strengthening effect. Importantly, these results expand the understanding of the mechanisms for texture selection in alloys with cubic crystal symmetry and offer an approach to easily evaluate processing conditions. With this new understanding, these modeling tools will enable anticipation of previously unexpected variations in grain structure and target specific microstructures and properties.

36 MATERIALS SCIENCE↗
DOE OSTI2017

Large-scale atomistic calculations of clusters in intense x-ray pulses

Here, we present the methodology of our recently developed Monte-Carlo/ Molecular-Dynamics method for studying the fundamental ultrafast dynamics induced by high-fluence, high-intensity x-ray free electron laser (XFEL) pulses in clusters. The quantum nature of the initiating ionization process is accounted for by a Monte Carlo method to calculate probabilities of electronic transitions, including photo absorption, inner-shell relaxation, photon scattering, electron collision and recombination dynamics, and thus track the transient electronic configurations explicitly. The freed electrons and ions are followed by classical particle trajectories using a molecular dynamics algorithm. These calculations reveal the surprising role of electron-ion recombination processes that lead to the development of nonuniform spatial charge density profiles in x-ray excited clusters over femtosecond timescales. In the high-intensity limit, it is important to include the recombination dynamics in the calculated scattering response even for a 2- fs pulse. We also demonstrate that our numerical codes and algorithms can make e!cient use of the computational power of massively parallel supercomputers to investigate the intense-field dynamics in systems with increasing complexity and size at the ultrafast timescale and in non-linear x-ray interaction regimes. In particular, picosecond trajectories of XFEL clusters with attosecond time resolution containing millions of particles can be e!ciently computed on upwards of 262,144 processes.

74 ATOMIC AND MOLECULAR PHYSICS↗