Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Computer 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,225 records · Page 68
All sourcesNASA NTRSDOE OSTI
DOE OSTI2024

Application of performance portability solutions for GPUs and many-core CPUs to track reconstruction kernels

Next generation High-Energy Physics (HEP) experiments are presented with significant computational challenges, both in terms of data volume and processing power. Using compute accelerators, such as GPUs, is one of the promising ways to provide the necessary computational power to meet the challenge. The current programming models for compute accelerators often involve using architecture-specific programming languages promoted by the hardware vendors and hence limit the set of platforms that the code can run on. Developing software with platform restrictions is especially unfeasible for HEP communities as it takes significant effort to convert typical HEP algorithms into ones that are efficient for compute accelerators. Multiple performance portability solutions have recently emerged and provide an alternative path for using compute accelerators, which allow the code to be executed on hardware from different vendors. We apply several portability solutions, such as Kokkos, SYCL, C++17 std::execution::par, Alpaka, and OpenMP/OpenACC, on two mini-apps extracted from the mkFit project: p2z and p2r. These apps include basic kernels for a Kalman filter track fit, such as propagation and update of track parameters, for detectors at a fixed z or fixed r position, respectively. The two mini-apps explore different memory layout formats. We report on the development experience with different portability solutions, as well as their performance on GPUs and many-core CPUs, measured as the throughput of the kernels from different GPU and CPU vendors such as NVIDIA, AMD and Intel.

Kwok, Ka Hei Martin↗
DOE OSTI2024

Application of performance portability solutions for GPUs and many-core CPUs to track reconstruction kernels

Next generation High-Energy Physics (HEP) experiments are presented with significant computational challenges, both in terms of data volume and processing power. Using compute accelerators, such as GPUs, is one of the promising ways to provide the necessary computational power to meet the challenge. The current programming models for compute accelerators often involve using architecture-specific programming languages promoted by the hardware vendors and hence limit the set of platforms that the code can run on. Developing software with platform restrictions is especially unfeasible for HEP communities as it takes significant effort to convert typical HEP algorithms into ones that are efficient for compute accelerators. Multiple performance portability solutions have recently emerged and provide an alternative path for using compute accelerators, which allow the code to be executed on hardware from different vendors. We apply several portability solutions, such as Kokkos, SYCL, C++17 std::execution::par and Alpaka, on two mini-apps extracted from the mkFit project: p2z and p2r. These apps include basic kernels for a Kalman filter track fit, such as propagation and update of track parameters, for detectors at a fixed z or fixed r position, respectively. The two mini-apps explore different memory layout formats. We report on the development experience with different portability solutions, as well as their performance on GPUs and many-core CPUs, measured as the throughput of the kernels from different GPU and CPU vendors such as NVIDIA, AMD and Intel.

Kwok, Ka Martin↗
DOE OSTI2021

Scalable Approaches to Selecting Key Entities in Large Networked Infrastructure Systems

This work aims at bringing advances in discrete optimization algorithms to solving practical engineering problems at scale. Often times, in many engineering design problems, there is a need to select a small set of influential or representative elements from a large ground set of entities in an optimal fashion. Submodular optimization provides for a formal way to solve such problems. Common examples with infrastructure systems involve sensor placement and identification of key entities with certain objectives. However, scaling these approaches to large infrastructure systems can be challenging because of the high computational complexity of the overall framework that include the optimization algorithms as well as high-complexity compute-oracles that provide the necessary objective function values. In this work, we explore a well-studied and widely-applicable paradigm, namely leader-selection in a multi-agent networked setting in the context of scalable methodologies. We demonstrate novel frameworks that utilize variations of accelerated submodular optimization algorithms along with linear-algebraic methods that can help accelerate the oracle computations. We further explore this combination in conjunction with graph partitioning paradigms to take advantage of the accelerated algorithms in a distributed setting. Finally we demonstrate the key findings on a practical problem in an operational setting. For this, we leverage an example road network with approximately 18k nodes and 27k edges in a traffic control application, where we seek a limited number of k=200 key intersections. This problem can be solved in a serial setting in just under 5 hours providing more than 2 orders of magnitude speed-up over methods that do not consider acceleration techniques.

Visweswara Sathanur, Arun↗
DOE OSTI2023

BitGNN: Unlocking the Performance Potential of Binary Graph Neural Networks on GPUs

Graph Neural Networks (GNNs) have shown compelling results in many graph-based learning tasks. They are, however, time-consuming. Recent work has shown a promising direction in improving GNN speed and shrinking the size — network binarization, which binarizes network values and operations. Prior work, however, mainly focused on algorithm designs, leaving it open on how to fully materialize the performance potential. This work fills the gap by proposing techniques to best map binary GNNs and their computations to fit the nature of bit manipulations, optimizations and algorithms to maximize BSpMM kernel efficiency, and solutions to other factors influencing the end-to-end time on GPUs. Results on real-world graphs show that the proposed techniques outperform state of-the-art binary GNN implementations by 21-67× with little accuracy loss.

Chen, Jou-An↗
DOE OSTI2024

Alternating Direction Decomposition with Strong Bounding and Convexification (ADDSBC) for Solving Security Constrained AC Unit Commitment Problems

This project aims to develop efficient and robust computational methods for solving the security-constrained unit commitment and alternating current optimal power flow problem (SC-UC-ACOPF). The SC-UC-ACOPF problem is at the center of the short-term operation of the U.S. Power Grid. It is solved every week, every day, and every 10 minutes to plan for the optimal action of electricity generation and consumption by minimizing the generation cost and maintaining power system reliability against potential disruptions of equipment failures. In mathematical terms, SC-UC-ACOPF is a challenging large-scale mixed-integer nonlinear optimization model. This means that the decisions involve both discrete variables, e.g. the turning on and off of generators and switching of transmission lines and transformers, and continuous decisions, e.g. the amount of energy generated by each generator and the power flows in the power grid. The physics of the power flow is described by nonlinear equations involving real and reactive power and bus voltages. Another key feature is the large number of contingencies, i.e. the system needs to stay reliable in face of failure of any one equipment, such as transmission lines and generators. The U.S. power grids are extremely complicated and large scale with more than 5,000 generators, 50,000 buses, and 100,000 high-voltage transmission lines, making the SC-UC-ACOPF a very large-scale computation challenge. The research developed in this project aims to solve the SC-UC-ACOPF problems in the three timescales, i.e. weekly, daily, and every 10-min. The proposed computational methods are built on a principled algorithmic approach of decomposition and penalization. More specifically, the algorithm develops spatial and temporal decomposition by exploiting the strong temporal coupling and weak spatial coupling of the UC problem and the complementary feature, i.e. weak temporal coupling and strong spatial coupling of the ACOPF problem. The algorithm also leverages recent progresses in strong convex relaxation of ACOPF. A unique feature of the proposed approach is that it generates a valid, global upper bound on the optimal maximum profit. In this way, a global optimality gap is available to measure the quality of the solution. To further speed up computation, the research team has developed a plethora of effective heuristics to strengthen the iterative penalty-based decomposition framework. For instance, a heuristic is developed to construct inner approximations of the time coupling constraints within the time decoupled problems. Contingencies are pre-screened and low-rank matrix computation is exploited to find the almost unique solution to each contingency. A novel heuristic for line switching is proposed and tested with positive impacts on instances where line switching is beneficial. Taking a systematic approach and carefully handling every detail of the problem pays off. The TIM-GO’s performance throughout the trials and the final event was stellar. TIM-GO garnered the second highest total prize money and is ranked in the top three positions across all categories of comparison.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

A multilayer multi-configurational approach to efficiently simulate large-scale circuit-based quantum computers on classical machines

Here, a multilayer multi-configurational theory framework is adapted to simulate circuit-based quantum computers. Quantum addition of superpositions of an exponential number of summands is performed in polynomial time with high accuracy. We demonstrate numerically accurate calculations including up to one million qubits for entangling benchmarks. Simulation cost can be assessed by entropy-based entanglement measures. For the considered systems, we show that the entanglement only grows weakly with the system size. The present simulations demonstrate how quantum algorithms in low-entropy regimes can be used efficiently on classically simulated quantum computers.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

The Case for Strong Scaling in Deep Learning: Training Large 3D CNNs with Hybrid Parallelism

Here, we present scalable hybrid-parallel algorithms for training large-scale 3D convolutional neural networks. Deep learning-based emerging scientific workflows often require model training with large, high-dimensional samples, which can make training much more costly and even infeasible due to excessive memory usage. We solve these challenges by extensively applying hybrid parallelism throughout the end-to-end training pipeline, including both computations and I/O. Our hybrid-parallel algorithm extends the standard data parallelism with spatial parallelism, which partitions a single sample in the spatial domain, realizing strong scaling beyond the mini-batch dimension with a larger aggregated memory capacity. We evaluate our proposed training algorithms with two challenging 3D CNNs, CosmoFlow and 3D U-Net. Our comprehensive performance studies show that good weak and strong scaling can be achieved for both networks using up to 2K GPUs. More importantly, we enable training of CosmoFlow with much larger samples than previously possible, realizing an order-of-magnitude improvement in prediction accuracy.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

A novel framework for hosting capacity analysis with spatio-temporal probabilistic voltage sensitivity analysis

Smart grids are envisioned to accommodate high penetration of distributed photovoltaic (PV) generation, which may cause adverse grid impacts in terms of voltage violations. Therefore, PV Hosting capacity is being used as a planning tool to determine the maximum PV installation capacity that causes the first voltage violation and above which would require infrastructure upgrades. Additionally, traditional methods of Hosting capacity analysis are scenario based and computationally complex as they rely on iterative load flow algorithms that require investigating a large number of scenarios for accurate assessment of PV impacts. Therefore, this paper presents a computationally efficient analytical approach to compute the probability distribution of voltage change due to random behavior of randomly located multiple distributed PVs. The proposed approach is based on Spatio-temporal probabilistic voltage sensitivity analysis that exploits both spatial and temporal uncertainties associated with PV injections. Thereafter, the derived distribution is used to quantify voltage violations for various PV penetration levels and subsequently determine the hosting capacity of the system without the need to examine large number of scenarios. Results of the proposed framework are validated via conventional load flow based simulation approach on the IEEE 37 and IEEE 123 node test systems.

42 ENGINEERING↗
DOE OSTI2023

Sampling frequency thresholds for the quantum advantage of the quantum approximate optimization algorithm

We compare the performance of the Quantum Approximate Optimization Algorithm (QAOA) with state-of-the-art classical solvers Gurobi and MQLib to solve the MaxCut problem on 3-regular graphs. We identify the minimum noiseless sampling frequency and depth p required for a quantum device to outperform classical algorithms. There is potential for quantum advantage on hundreds of qubits and moderate depth with a sampling frequency of 10 kHz. We observe, however, that classical heuristic solvers are capable of producing high-quality approximate solutions in linear time complexity. In order to match this quality for large graph sizes N, a quantum device must support depth p > 11. Additionally, multi-shot QAOA is not efficient on large graphs, indicating that QAOA p ≤ 11 does not scale with N. These results limit achieving quantum advantage for QAOA MaxCut on 3-regular graphs. Other problems, such as different graphs, weighted MaxCut, and 3-SAT, may be better suited for achieving quantum advantage on near-term quantum devices.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2023

A Practical Approach to Wave Function Propagation, Hopping Probabilities, and Time Steps in Surface Hopping Calculations

We compare several established approaches for propagating wave functions and calculating hopping probabilities within the fewest switches surface hopping (FSSH) algorithm for difficult cases with many electronic states and many trivial crossings. If only a single time step (Δt c ) is employed, we find that no published approach can accurately capture the dynamics correctly unless Δt c → 0 (which is not computationally feasible). If multiple time steps are employed, for a fixed classical time step (Δt c ), a robust scheme can be found for dynamically choosing quantum time steps (δt q1 and δt q2 ) and calculating hopping probabilities so that one can systematically reduce all errors and achieve maximally efficient accuracy; scattering calculations confirm that one can choose a fairly large classical time step. Furthermore, the robust scheme presented here uses both the “local diabatic” and adiabatic interpolation and thus borrows elements from both the Granucci/Persico and Meek/Levine algorithms. Our findings should be broadly applicable in the future.

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

Two-dimensional materials for bio-realistic neuronal computing networks

Two-dimensional (2D) van der Waals materials have found broad utility in a diverse range of applications including electronics, optoelectronics, renewable energy, and quantum information technologies. Meanwhile, exponentially growing digital data coupled with the ubiquity of artificial intelligence algorithms have generated significant interest in edge neuromorphic computing as an alternative to centralized cloud computing. The drive to incorporate neuroscience principles into computing hardware is motivated by the low power consumption, parallel processing, and reconfigurability of the human brain. The diverse library of 2D materials with atomic-level thicknesses, exceptional electrostatic tunability, and integration versatility is particularly well-suited for realizing bio-realistic synaptic and neuronal functionality. Here, we summarize past and present work in this field and outline the frontier challenges that have not yet been overcome. Here we also delineate potential solutions and suggest that the neuroscience principles of criticality and synchrony have the potential to inspire breakthrough applications of 2D materials in neuronal computing networks.

36 MATERIALS SCIENCE↗
DOE OSTI2024

Extracting and Interpreting Electrochemical Impedance Spectra (EIS) from Physics-Based Models of Lithium-Ion Batteries

This paper implements a highly efficient algorithm to extract electrochemical impedance spectra (EIS) from physics-based battery models (e.g., a P2D model). The mathematical approach is different from how EIS is practiced experimentally. Experimentally, the voltage (current) is harmonically perturbed over a wide range of frequencies and the amplitude and phase shift of the corresponding current (voltage) is measured. The experimental approach can be implemented in simulation software, but is computationally expensive. The approach here is to determine locally linear state-space models from the full physical model. The four Jacobian matrices that are the basis of the state-space models can be derived by numerical differentiation of the physical model. The EIS is then extracted from the state-space model using computationally efficient matrix-manipulation techniques. The algorithm can evaluate the full EIS at an instant in time during a transient, independent of whether the battery is in a stationary state. The approach is also able to separate the full-cell impedance to evaluate partial EIS, such as for a battery anode alone. Although such partial EIS is difficult to measure experimentally, the partial EIS provides valuable insights in interpreting the full-cell EIS.

25 ENERGY STORAGE↗
DOE OSTI2023

Tools for analysis of optimization models

The software is code for analyzing, debugging, and solving optimization models. The code implements several algorithms and provides convenient APIs to apply these algorithms to optimization models. The algorithms are primarily based on graph theory. They compute well-known partitions of graphs, and use these partitions to provide the user information about their optimization model, including diagnosing certain types of structural modeling errors. Some algorithms may be used as a subroutine to solve an optimization problem, and may call an optimization solver to facilitate this. Well-known linear algebra routines are called to provide further diagnostics. The software contains no data and no models other than toy models used for testing.

Parker, Robert↗
DOE OSTI2023

Compression of tokamak boundary plasma simulation data using a maximum volume algorithm for matrix skeleton decomposition

This report demonstrates satisfactory data compression of SOLPS-ITER simulation output ranging from 2D fields, 1D profiles, and 0D scalar variables with a novel matrix decomposition approach. The singular value decomposition (SVD) scales poorly for large matrix sizes and is unsuited to the application on high dimensional data common to fusion plasma physics simulation. In this work, we employ the columns-submatrix-rows (CUR) matrix factorization technique in order to compute a low-rank approximation up to two orders of magnitude faster than the SVD, but within a nominal L2-norm relative error of ε = 10 –2 . In addition, the CUR approach maintains the original format of the data, in its extracted columns and rows, allowing for interpretable data storage at the original resolution of the simulation. We utilize an iterative algorithm to compute the CUR decomposition of simulation output by maximizing the volume, or linearly independent information content, of a low-rank submatrix contained within the data. Experiments over $\textit{n} × \textit{n}$ randomized test matrices with embedded rank-deficient features show that this maximum volume implementation of CUR matrix approximation has reduced asymptotic computational complexity on the order of n compared to the SVD, which scales approximately as $n^3$. These results show that the CUR technique can be used to effectively select time step snapshots (columns) of over 140 SOLPS-ITER output variables and the associated discretized coordinate timeseries (rows) allowing for reconstruction of the complete simulation dynamics.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗
DOE OSTI2022

An Evolutionary Algorithm to Personalize Stool-Based Colorectal Cancer Screening

Fecal immunochemical testing (FIT) is an established method for colorectal cancer (CRC) screening. Measured FIT-concentrations are associated with both present and future risk of CRC, and may be used for personalized screening. However, evaluation of personalized screening is computationally challenging. In this study, a broadly applicable algorithm is presented to efficiently optimize personalized screening policies that prescribe screening intervals and FIT-cutoffs, based on age and FIT-history. We present a mathematical framework for personalized screening policies and a bi-objective evolutionary algorithm that identifies policies with minimal costs and maximal health benefits. The algorithm is combined with an established microsimulation model (MISCAN-Colon), to accurately estimate the costs and benefits of generated policies, without restrictive Markov assumptions. The performance of the algorithm is demonstrated in three experiments. In Experiment 1, a relatively small benchmark problem, the optimal policies were known. The algorithm approached the maximum feasible benefits with a relative difference of 0.007%. Experiment 2 optimized both intervals and cutoffs, Experiment 3 optimized cutoffs only. Optimal policies in both experiments are unknown. Compared to policies recently evaluated for the USPSTF, personalized screening increased health benefits up to 14 and 4.3%, for Experiments 2 and 3, respectively, without adding costs. Generated policies have several features concordant with current screening recommendations. The method presented in this paper is flexible and capable of optimizing personalized screening policies evaluated with computationally-intensive but established simulation models. It can be used to inform screening policies for CRC or other diseases. For CRC, more debate is needed on what features a policy needs to exhibit to make it suitable for implementation in practice.

60 APPLIED LIFE SCIENCES↗
DOE OSTI2023

Privacy-preserving federated learning: Application to behind-the-meter solar photovoltaic generation forecasting

Here, the growing usage of decentralized renewable energy sources has made accurate estimation of their aggregated generation crucial for maintaining grid flexibility and reliability. However, the majority of distributed photovoltaic (PV) systems are behind-the-meter (BTM) and invisible to utilities, leading to three challenges in obtaining an accurate forecast of their aggregated output. Firstly, traditional centralized prediction algorithms used in previous studies may not be appropriate due to privacy concerns. There is therefore a need for decentralized forecasting methods, such as federated learning (FL), to protect privacy. Secondly, there has been no comparison between localized, centralized, and decentralized forecasting methods for BTM PV production, and the trade-off between prediction accuracy and privacy has not been explored. Lastly, the computational time of data-driven prediction algorithms has not been examined. This article presents a FL power forecasting method for PVs, which uses federated learning as a decentralized collaborative modeling approach to train a single model on data from multiple BTM sites. The machine learning network used to design this FL-based BTM PV forecasting model is a multi-layered perceptron, which ensures privacy and security of the data. Comparing the suggested FL forecasting model to non-private centralized and entirely private localized models revealed that it has a high level of accuracy, with an RMSE that is 18.17% lower than localized models and 9.9% higher than centralized models.

14 SOLAR ENERGY↗
DOE OSTI2021

Optimization and supervised machine learning methods for fitting numerical physics models without derivatives

Here, we address the calibration of a computationally expensive nuclear physics model for which derivative information with respect to the fit parameters is not readily available. Of particular interest is the performance of optimization-based training algorithms when dozens, rather than millions or more, of training data are available and when the expense of the model places limitations on the number of concurrent model evaluations that can be performed. As a case study, we consider the Fayans energy density functional model, which has characteristics similar to many model fitting and calibration problems in nuclear physics. We analyze hyperparameter tuning considerations and variability associated with stochastic optimization algorithms and illustrate considerations for tuning in different computational settings.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Reducing Communication in Graph Neural Network Training

Graph Neural Networks (GNNs) are powerful and flexible neural networks that use the naturally sparse connectivity information of the data. GNNs represent this connectivity as sparse matrices, which have lower arithmetic intensity and thus higher communication costs compared to dense matrices, making GNNs harder to scale to high concurrencies than convolutional or fully-connected neural networks. Here, we introduce a family of parallel algorithms for training GNNs and show that they can asymptotically reduce communication compared to previous parallel GNN training methods. We implement these algorithms, which are based on 1D, 1. 5D, 2D, and 3D sparse-dense matrix multiplication, using torch.distributed on GPU-equipped clusters. Our algorithms optimize communication across the full GNN training pipeline. We train GNNs on over a hundred GPUs on multiple datasets, including a protein network with over a billion edges.

97 MATHEMATICS AND COMPUTING↗