Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “algorithmic efficiency”

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,135 records · Page 63

MAESTRO: AN ADAPTIVE LOW MACH NUMBER HYDRODYNAMICS ALGORITHM FOR STELLAR FLOWS

Many astrophysical phenomena are highly subsonic, requiring specialized numerical methods suitable for long-time integration. In a series of earlier papers we described the development of MAESTRO, a low Mach number stellar hydrodynamics code that can be used to simulate long-time, low-speed flows that would be prohibitively expensive to model using traditional compressible codes. MAESTRO is based on an equation set derived using low Mach number asymptotics; this equation set does not explicitly track acoustic waves and thus allows a significant increase in the time step. MAESTRO is suitable for two- and three-dimensional local atmospheric flows as well as three-dimensional full-star flows. Here, we continue the development of MAESTRO by incorporating adaptive mesh refinement (AMR). The primary difference between MAESTRO and other structured grid AMR approaches for incompressible and low Mach number flows is the presence of the time-dependent base state, whose evolution is coupled to the evolution of the full solution. We also describe how to incorporate the expansion of the base state for full-star flows, which involves a novel mapping technique between the one-dimensional base state and the Cartesian grid, as well as a number of overall improvements to the algorithm. We examine the efficiency and accuracy of our adaptive code, and demonstrate that it is suitable for further study of our initial scientific application, the convective phase of Type Ia supernovae.

79 ASTRONOMY AND ASTROPHYSICS↗

Application of the TITAN Hybrid Deterministic Transport Code to Medical Physics - Paper 118

The TITAN code is a 3-dimensional parallel deterministic transport code that solves the linear Boltzmann equation. The TITAN code has hybrid algorithms that are ideal for medical physics applications: i) SN and characteristics method and ii) SN with a fictitious quadrature set and ray-tracing. These hybrid algorithms have been used in the simulation of computed tomography (CT) and single photon emission computed tomography (SPECT) In this paper, the hybrid algorithms developed for medical physics applications in the TITAN code are discussed. First, the TITAN code's block-oriented approach for utilizing SN and characteristic solvers for CT is presented and results for a simple test case are given. Second, the paper describes a hybrid formulation for SPECT with an SN solver in the phantom, a fictitious quadrature set for directions from the phantom surface passing through the collimator, and a simplified ray-tracing algorithm for particle transport to the detector. Finally, ongoing work is described and concluding remarks are given. The TITAN code's hybrid algorithms allow it to efficiently solve problems with low-scatter regions, which are frequently found in medical physics applications. The TITAN code has been used to solve a simplified CT problem and generate projection images for SPECT simulations. The WCOS technique was developed to improve the TITAN code's collimator representation. For these applications, the TITAN code was shown to require significantly less computation time than MCNP5. Work is currently underway to implement an iterative image reconstruction algorithm in the TITAN code. A script that calls the TITAN code to complete the forward projection step in SPECT has already been used to reconstruction a 2-dimensional phantom. The ability of TITAN to fully model particle transport in the patient in short computation times is expected to be a great advantage to iterative reconstruction. (authors)

61 RADIATION PROTECTION AND DOSIMETRY↗

Variable Precision Computing

This report summarizes the activities and major accomplishments of the Variable Precision Computing Strategic Initiative project. The overarching goal of this project was to initiate and promote a new paradigm in High Performance Computing (HPC) that would fundamentally change how we represent and make use of representations of real numbers in finite precision and that would establish Lawrence Livermore National Laboratory (LLNL) as a leader in precision-related research for HPC. We pursued three integrated and concurrent research thrusts: new, more dynamic data representations to address data motion and capacity limitations; improved mixed precision algorithms to accelerate computation and to leverage new hardware; and new tools to help developers reason about precision and to automate code transformations. Within these thrust areas, we made significant advances in the use of compressed array data types in numerical calculations, in the theoretical justification, in improved performance, and in the prospects of hardware implementation; in the development of metrics to significantly reduce the storage needs of molecular dynamics simulations; in the development and analysis of efficient mixed-precision algorithms for time-dependent partial differential equations and for orthogonal factorization; and in the capability of tools that can analyze sensitivity of computed results to choices in precision and that can make automated code transformations based on such analysis. We established that there are definite opportunities to realize significant improvements in HPC above and beyond the 2x limits of traditional mixed precision using the technologies we have developed. The project produced numerous papers, presentations, and posters in important venues as well as open-source software contributions to the community, and many of the new capabilities have initiated or are being leveraged in ongoing projects.

97 MATHEMATICS AND COMPUTING↗

Scalable Algorithms for Distributed-Memory Adaptive Mesh Refinement

This paper presents scalable algorithms and data structures for adaptive mesh refinement computations. We describe a novel mesh restructuring algorithm for adaptive mesh refinement computations that uses a constant number of collectives regardless of the refinement depth. To further increase scalability, we describe a localized hierarchical coordinate-based block indexing scheme in contrast to traditional linear numbering schemes, which incur unnecessary synchronization. In contrast to the existing approaches which take O(P) time and storage per process, our approach takes only constant time and has very small memory footprint. With these optimizations as well as an efficient mapping scheme, our algorithm is scalable and suitable for large, highly-refined meshes. We present strong-scaling experiments up to 2k ranks on Cray XK6, and 32k ranks on IBM Blue Gene/Q.

Langer, Akhil↗

3D Coded SUMMA: Communication-Efficient and Robust Parallel Matrix Multiplication

In this paper, we propose a novel fault-tolerant parallel matrix multiplication algorithm called 3D Coded SUMMA that achieves higher failure-tolerance than replication-based schemes for the same amount of redundancy. This work bridges the gap between recent developments in coded computing and fault-tolerance in high-performance computing (HPC). The core idea of coded computing is the same as algorithm-based fault-tolerance (ABFT), which is weaving redundancy in the computation using error-correcting codes. In particular, we show that MatDot codes, an innovative code construction for parallel matrix multiplications, can be integrated into three-dimensional SUMMA (Scalable Universal Matrix Multiplication Algorithm [30]) in a communication-avoiding manner. To tolerate any two node failures, the proposed 3D Coded SUMMA requires ~50% less redundancy than replication, while the overhead in execution time is only about 5–10%.

97 MATHEMATICS AND COMPUTING↗

Searching for Clues for a Matter Dominated Universe in Liquid Argon Time Projection Chambers

Liquid Argon Time Projection Chambers (LArTPCs) represent one of the most widely utilized neutrino detection techniques in neutrino experiments, for instance, in the Short Baseline Neutrino (SBN) program and the future large-scale LArTPC: Deep Underground Neutrino Experiment (DUNE). The high-end technique, facilitating excellent spatial and calorimetric reconstruction resolution, also enables testing exotic Beyond Standard Model (BSM) theories, such as baryon number violation (BNV) processes (e.g., proton-decay, neutron-antineutron oscillation). At the same time, Machine Learning (ML) techniques have demonstrated their ubiquitous use in recent decades; ML techniques have also become some of the most powerful tools in high-energy physics (HEP) analyses. Furthermore, the development of algorithms to cater to the needs of problems in HEP (i.e., triggering, reconstruction, improving sensitivity, etc.) has also become an active area of research. By developing a combined approach using Convolutional Neural Network (CNN) and Boosted Decision Tree (BDT) techniques, the sensitivity of neutron-antineutron oscillation in DUNE is evaluated for a projected exposure of 400kton·years. Additionally, to meet the triggering requirement to select such rare events in DUNE, such a search is only supported with highly efficient self-triggering algorithms. An ML-based self-triggering scheme for large-scale LArTPCs, such as DUNE, is also developed with the intention of implementation on field-programmable gate arrays (FPGAs). The ML-based approach for searching for neutron-antineutron oscillation can be demonstrated and validated on the current LArTPC MicroBooNE. The analysis in MicroBooNE represents the first-ever search for neutron-antineutron oscillation in a LArTPC. DUNE's projected 90% C.L. sensitivity to the neutron antineutron oscillation lifetime is 6.45×10³² years, assuming 1.327×10³⁵ neutron·years, equivalent to 10 years of DUNE far detector exposure (400kton·years). For MicroBooNE, assuming 372 seconds of exposure (equivalent to 3.13×10³⁶ neutron·years), the 90% C.L. lifetime sensitivity is found at 3.07×10²⁵ yrs, after accounting for Monte-Carlo statistical uncertainty and systematic uncertainty from detector effects.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

The adaptive mesh method based on HOC difference scheme for convection diffusion equations with boundary layers

In this paper, an adaptive mesh method is proposed to generate orthogonal nonuniform mesh for 2D rectangular computational domain. The algorithm adopts the dimension split idea which redistribute the mesh on each direction sequently. This approach efficiently decreases the difficultly of algorithm and enables the adapted mesh to be orthogonal. The adaptive mesh method can redistribute the mesh based on the solution without specifying the location of the boundary layer or the grid distribution function to generate the nonuniform mesh in advance. To verify the effectiveness and robustness of the algorithm, the presented method combined with the HOC difference scheme on nonuniform grid is used to solve the 1D and 2D convection diffusion problems with boundary layers. Besides, the multigrid method is used to accelerate the iterative convergence speed. The numerical solutions of adaptive mesh is more flexible than uniform or nonuniform grids methods if the location of the boundary layers is unknown in advance.

97 MATHEMATICS AND COMPUTING↗

Distributed-Memory Fast Maximal Independent Set

The Maximal Independent Set (MIS) graph problem arises in many applications such as computer vision, information theory, molecular biology, and process scheduling. The growing scale of MIS problems suggests the use of distributed-memory hardware as a cost-effective approach to providing necessary compute and memory resources. Luby proposed four randomized algorithms to solve the MIS problem. All those algorithms are designed focusing on shared-memory machines and are analyzed using the PRAM model. These algorithms do not have direct efficient distributed-memory implementations. In this paper, we extend two of Luby’s seminal MIS algorithms, “Luby(A)” and “Luby(B),” to distributed-memory execution, and we evaluate their performance. We compare our results with the “Filtered MIS” implementation in the Combinatorial BLAS library for two types of synthetic graph inputs.

distributed memory parallel↗

A novel quark-field creation operator construction for hadronic physics in lattice QCD

A new quark-field smearing algorithm is defined which enables efficient calculations of a broad range of hadron correlation functions. The technique applies a low-rank operator to define smooth fields, that are to be used in hadron creation operators. The resulting space of smooth fields is small enough that all elements of the reduced quark propagator can be computed exactly at reasonable computational cost. Correlations between arbitrary sources, including multi-hadron operators can be computed {\em a posteriori} without requiring new lattice Dirac operator inversions. The method is tested on realistic lattice sizes with light dynamical quarks.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Efficient Measurement-Driven Eigenenergy Estimation with Classical Shadows

Quantum algorithms exploiting real-time evolution under a target Hamiltonian have demonstrated remarkable efficiency in extracting key spectral information. However, the broader potential of these methods, particularly beyond ground-state calculations, is underexplored. In this work, we introduce the framework of multiobservable dynamic mode decomposition (MODMD), which combines the observable dynamic mode decomposition (DMD), a measurement-driven eigensolver tailored for near-term implementation, with classical shadow tomography. MODMD leverages random scrambling in the classical shadow technique to construct, with exponentially reduced resource requirements, a signal subspace that encodes rich spectral information. Notably, we replace typical Hadamard-test circuits with a protocol designed to predict low-rank observables, thereby broadening the use of classical shadow tomography for predicting many low-rank observables. We establish theoretical guarantees on the spectral approximation from MODMD, taking into account distinct sources of error. In the ideal case, we prove that the spectral error scales as exp (−Δ⁢𝐸⁢𝑡 max ), where Δ⁢𝐸 is the Hamiltonian spectral gap and 𝑡 max is the maximal simulation time. This analysis provides a rigorous justification of the rapid convergence observed across simulations. To demonstrate the utility of our framework, we consider its application to fundamental tasks, such as determining the low-lying, i.e., ground or excited, energies of representative many-body systems. Our work paves the path for efficient designs of measurement-driven algorithms on near-term and early fault-tolerant quantum devices.

quantum algorithms & computation↗

Performance evaluation of cosmic ray muon trajectory estimation algorithms

Muons, being elementary particles with minimal interaction with nuclear materials and abundant at sea level, have sparked interest in utilizing them for imaging various applications, such as mining [Borselli et al., Sci. Rep. 12, 22329 (2022)], volcano imaging [Nagamine et al., Nucl. Instrum. Meth. A, 356, 585(1995)], and underground tunnel detection [Guardincerri et al., Pure Appl. Geophys. 174, 2133 (2017)]. Recently, their use in nuclear nonproliferation and safeguard verification has gained attention, particularly in cargo screening for nuclear waste smuggling [Baesso et al., J. Instrum. 9, C10041 (2014)], source localization [L. J. Schultz et al., Nucl. Instrum. Meth. A 519, 687 (2004)], and locating nuclear fuel debris in reactors [Borozdin et al., Phys. Rev. Let. 109, 152501 (2012)]. However, the resolution of muon image reconstruction techniques is limited due to multiple Coulomb scattering (MCS) within the target object. To achieve robust muon tomography, it is crucial to develop efficient and flexible physics-based algorithms that can model the MCS process accurately and estimate the most probable trajectory of muons as they pass through the target object. To address this limitation, in this study, a novel algorithmic approach utilizing the Bayesian probability theory and Gaussian approximation of MCS is chosen. Different energy levels, materials, and target sizes were considered in the evaluations. The results demonstrate that the Generalized Muon Trajectory Estimation (GMTE) algorithm offers significant improvements over currently used algorithms. Across all test scenarios, the GMTE algorithm demonstrated ~50% and 38% increase in precision compared to Straight Line Path (SLP) and Point of Closest Approach (PoCA) algorithms, respectively. Furthermore, it exhibited 10%–35% and 10%–15% increases in muon flux utilization for high and medium Z materials, respectively, compared to the PoCA algorithm. In conclusion, the extensive simulations confirm the enhanced performance and efficiency of the GMTE algorithm, offering improved resolution and reduced measurement time for cosmic ray muon imaging compared to the current SLP and PoCA algorithms.

79 ASTRONOMY AND ASTROPHYSICS↗

Advanced time integration algorithms for dislocation dynamics simulations of work hardening

Efficient time integration is a necessity for dislocation dynamics simulations of work hardening to achieve experimentally relevant strains. In this work, an efficient time integration scheme using a high order explicit method with time step subcycling and a newly-developed collision detection algorithm are evaluated. First, time integrator performance is examined for an annihilating Frank–Read source, showing the effects of dislocation line collision. The integrator with subcycling is found to significantly out-perform other integration schemes. The performance of the time integration and collision detection algorithms is then tested in a work hardening simulation. The new algorithms show a 100-fold speed-up relative to traditional schemes. As a result, subcycling is shown to improve efficiency significantly while maintaining an accurate solution, and the new collision algorithm allows an arbitrarily large time step size without missing collisions.

97 MATHEMATICS AND COMPUTING↗

Designing Topology-Aware Collective Communication Algorithms for Large Scale InfiniBand Clusters: Case Studies with Scatter and Gather

Modern high performance computing systems are being increasingly deployed in a hierarchical fashion with multi-core computing platforms forming the base of the hierarchy. These systems are usually comprised of multiple racks, with each rack consisting of a finite number of chassis, with each chassis having multiple compute nodes or blades, based on multi-core architectures. The networks are also hierarchical with multiple levels of switches. Message exchange operations between processes that belong to different racks involve multiple hops across different switches and this directly affects the performance of collective operations. In this paper, we take on the challenges involved in detecting the topology of large scale InfiniBand clusters and leveraging this knowledge to design efficient topology-aware algorithms for collective operations. We also propose a communication model to analyze the communication costs involved in collective operations on large scale supercomputing systems. We have analyzed the performance characteristics of two collectives, MPI_Gather and MPI_Scatter on such systems and we have proposed topology-aware algorithms for these operations. Our experimental results have shown that the proposed algorithms can improve the performance of these collective operations by almost 54% at the micro-benchmark level.

97 MATHEMATICS AND COMPUTING↗

Numerical eigen-spectrum slicing, accurate orthogonal eigen-basis, and mixed-precision eigenvalue refinement using OpenMP data-dependent tasks and accelerator offload

Performing a variety of numerical computations efficiently and, at the same time, in a portable fashion requires both an overarching design followed by a number of implementation strategies. All of these are exemplified below as we present transitioning the PLASMA numerical library from relying on dependence-driven large tasks to achieving utilization of fine grain tasking and offload to hardware accelerators while keeping its core dependence sets: OpenMP source code pragmas and runtime for most system-level functionality and basic low-level numerical kernels provided directly by hardware vendors or open source projects with vendor contributions. We also present new algorithmic methods and their efficient parallel implementations including fine grained tasking for eigen-spectrum slicing and offload for mixed-precision eigenvalue refinement. We provide performance, scaling, and numerical results showing sizable gains over the available solutions from either the open source and vendor-provided packages.

Luszczek, Piotr↗

Highly scalable distributed-memory sparse triangular solution algorithms.

This paper presents a highly efficient distributed-memory parallel sparse triangular solver. The triangular solution phase is often performed following factorization phase in the sparse linear solvers and has become increasingly computa­tionally expensive for direct solvers with many right hand sides (RHSs) or preconditioned iterative solvers. However, the low arithmetic intensity and sequential nature of the triangular solve algorithm pose performance challenges for its large-scale distributed-memory parallelization. In this work, we propose several strategies to enhance scalability of an algorithm with 2D block cyclic process layout. First, an asynchronous binary-tree-based communication scheme implemented via non-blocking MPI functions is leveraged to broadcast partial solutions and reduce partial updates among a subset of processes for each block column and row of the triangular matrix, respectively. This scheme reduces message latency, improves communication load balance and significantly accelerates asynchronous execution of the triangular solve. In addition, efficient BLAS operations and threading implementations are exploited to accelerate local computations and further reduce process idle time. The proposed strategies are implemented in SuperLU_DIST and numerical experiments show up to 4.4x improvement with one right-hand side and up to 6.1x improvement with 50 right- hand sides on 4096 processes, compared to the current release. This is the first time that sparse triangular solution is demonstrated strong scaling on more than 4000 cores.

Liu, Yang↗

Continuous thermostat setpoint monitoring and correction (Thermostat setpoint correction) v1.0

The Continuous Thermostat Setpoint Monitoring and Correction software is a set of fault detection and correction algorithms that can be implemented in thermostats with two-way OpenAPIs. It is written in the Python language. The algorithms aim to detect the most common and impactful efficiency problems associated with thermostat setpoints - overly aggressive heating or cooling setpoints, incorrect schedules/setbacks, and overly narrow deadbands. These algorithms can automatically detect faults, and implement associated corrective actions to bring the system back to a state of efficient operation. The algorithms can run remotely in the cloud, and directly implemented by connected thermostat manufacturers, or by third party service providers. The software enables a lightweight cost-effective energy management strategy for HVAC systems. The solution is specially viable for small and medium sized commercial buildings, where a full scale building automation system and fault detection and diagnostic tools are often unavailable.

Granderson, Jessica↗

Applicability of available Li-ion battery degradation models for system and control algorithm design

Within electrified vehicle powertrains, lithium-ion battery performance degrades with aging and usage, resulting in a loss in both energy and power capacity. As a result, models used for system design and control algorithm development would ideally capture the impact of those efforts on battery capacity degradation, be computationally efficient, and simple enough to be used for algorithm development. This paper provides an assessment of the state-of-the-art in lithium-ion battery degradation models, including accuracy, computational complexity, and amenability to control algorithm development. Various aging and degradation models have been studied in the literature, including physics-based electrochemical models, semi-empirical models, and empirical models. Some of these models have been validated with experimental data; however, comparisons of pre-existing degradation models across multiple experimental data sets have not been previously published. Three representative models, a 1-d electrochemical model (a combination of performance model and degradation model), a semi-empirical degradation model (the performance is predicted by an equivalent circuit model) and an empirical degradation model (the performance is predicted by an equivalent circuit model), are compared against four published experimental data sets for a 2.3-Ah commercial graphite/LiFePO 4 cell. Based on simulation results and comparisons to experimental data, the key differences in the aging factors captured by each of the models are summarized. Here the results show that the physics-based model is best able to capture results across all four representative data sets with an error less than 10%, but is 20x slower than the empirical model, and 134x slower than the semi-empirical model, making it unsuitable for powertrain system design and model-based algorithm development. Despite being computationally efficient, the semi-empirical and empirical models, when used under conditions that lie outside the calibration data set, exhibit up to 71% error in capacity loss prediction. Such models require expensive experimental data collection to recalibrate for every new application. Thus, in the author’s opinion, there exists a need for a physically-based model that generalizes well across operating conditions, is computationally efficient for model-based design, and simple enough for control algorithm development.

25 ENERGY STORAGE↗

Improved-efficiency DSMC collision-partner selection schemes.

The effect of collision-partner selection schemes on the accuracy and the efficiency of the Direct Simulation Monte Carlo (DSMC) method of Bird is investigated. Several schemes to reduce the total discretization error as a function of the mean collision separation and the mean collision time are examined. These include the historically first sub-cell scheme, the more recent nearest-neighbor scheme, and various near-neighbor schemes, which are evaluated for their effect on the thermal conductivity for Fourier flow. Their convergence characteristics as a function of spatial and temporal discretization and the number of simulators per cell are compared to the convergence characteristics of the sophisticated and standard DSMC algorithms. Improved performance is obtained if the population from which possible collision partners are selected is an appropriate fraction of the population of the cell.

99 GENERAL AND MISCELLANEOUS↗