Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “algorithms scalability”

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 307 records · Page 17

Reduced Hardware NOrec: A Safe and Scalable Hybrid Transactional Memory

Because of hardware TM limitations, software fallbacks are the only way to make TM algorithms guarantee progress. Nevertheless, all known software fallbacks to date, from simple locks to sophisticated versions of the NOrec Hybrid TM algorithm, have either limited scalability or weakened semantics. We propose a novel reduced-hardware (RH) version of the NOrec HyTM algorithm. Instead of an all-software slow path, in our RH NOrec the slow-path is a "mix" of hardware and software: one short hardware transaction executes a maximal amount of initial reads in the hardware, and the second executes all of the writes. Furthermore, this novel combination of the RH approach and the NOrec algorithm delivers the first Hybrid TM that scales while fully preserving the hardware's original semantics of opacity and privatization. Our GCC implementation of RH NOrec is promising in that it shows improved performance relative to all prior methods, at the concurrency levels we could test today.

97 MATHEMATICS AND COMPUTING↗

Multigraph-based Routing in Delay Tolerant Networks: An Alternative to Contact Graph Routing

Satellites are leaving the realms of niche use, extending our day-to-day networked infrastructure to space – thereby forcing a generalization of network architectures. The Delay Tolerant Networking (DTN) protocol is being developed to give rise to this new Solar System Internet. Predominantly, DTNs in space use globally-distributed contact tables to compute routes. In this paper, we propose and analyze a novel optimized approach for route computations that improves upon traditional approaches. As the general DTN will always include some scheduled links, our new algorithm enables greater scalability and practicality of DTN routing. These contact tables include windows when two nodes can communicate and were classically organized into a contact graph, where the vertices represent contact opportunities. Because the complexity of a contact graph grows with the number of contacts, pathfinding on it does not scale. A new structure using multigraphs with the same data is proposed. We show that a multigraph-based approach, which we call contact multigraph routing, exhibits performance superior to routing based on contact graphs, allowing greater scaling to schedule-based routing. In this paper, the multigraph-based algorithm is detailed and a proof is included showing it outperforms the previous algorithm given the same input. Pseudocode is included, as are simulation results. We conclude with suggested future work.

Delay Tolerant Networking↗

Hierarchical Distributed Voltage Regulation in Networked Autonomous Grids

We propose a novel algorithm to solve optimal power flow (OPF) that aims at dispatching controllable distributed energy resources (DERs) for voltage regulation at minimum cost. The proposed algorithm features unprecedented scalability to large distribution networks by utilizing an information structure based on networked autonomous grids (AGs). Specifically, each AG is a subtree of a large distribution network that has a tree topology. The topology and line parameters of each AG are known only to a regional coordinator (RC) that is responsible for communicating with and dispatching the DERs within this AG. The reduced network, where each AG is treated as a node, is managed by a central coordinator (CC), which knows the topology and line parameters of the reduced network only and communicates with all the RCs. We jointly explore this information structure and the structure of the linearized distribution power flow (LinDistFlow) model to derive a hierarchical, distributed implementation of the primal-dual gradient algorithm that solves the OPF. The proposed implementation significantly reduces the computation burden compared to the centrally coordinated implementation of the primal-dual algorithm. Numerical results on a 4,521-node test feeder show that the proposed hierarchical distributed algorithm can achieve an improvement of more than tenfold in the speed of convergence compared to the centrally coordinated primal-dual algorithm.

Zhou, Xinyang↗

Hierarchical Distributed Voltage Regulation in Networked Autonomous Grids: Preprint

We propose a novel algorithm to solve optimal power flow (OPF) that aims at dispatching controllable distributed energy resources (DERs) for voltage regulation at minimum cost. The proposed algorithm features unprecedented scalability to large distribution networks by utilizing an information structure based on networked autonomous grids (AGs). Specifically, each AG is a subtree of a large distribution network that has a tree topology. The topology and line parameters of each AG are known only to a regional coordinator (RC) that is responsible for communicating with and dispatching the DERs within this AG. The reduced network, where each AG is treated as a node, is managed by a central coordinator (CC), which knows the topology and line parameters of the reduced network only and communicates with all the RCs. We jointly explore this information structure and the structure of the linearized distribution power flow (LinDistFlow) model to derive a hierarchical, distributed implementation of the primal-dual gradient algorithm that solves OPF. The proposed implementation significantly reduces the computation burden compared to the centrally coordinated implementation of the primal-dual algorithm. Numerical results on a 4,521-node test feeder show that the proposed hierarchical distributed algorithm can achieve more than 10-fold improvement in the speed of convergence compared to the centrally coordinated primal-dual algorithm.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Hierarchical Distributed Voltage Regulation in Networked Autonomous Grids

We propose a novel algorithm to solve optimal power flow (OPF) that aims at dispatching controllable distributed energy resources (DERs) for voltage regulation at minimum cost. The proposed algorithm features unprecedented scalability to large distribution networks by utilizing an information structure based on networked autonomous grids (AGs). Specifically, each AG is a subtree of a large distribution network that has a tree topology. The topology and line parameters of each AG are known only to a regional coordinator (RC) that is responsible for communicating with and dispatching the DERs within this AG. The reduced network, where each AG is treated as a node, is managed by a central coordinator (CC), which knows the topology and line parameters of the reduced network only and communicates with all the RCs. We jointly explore this information structure and the structure of the linearized distribution power flow (LinDistFlow) model to derive a hierarchical, distributed implementation of the primal-dual gradient algorithm that solves the OPF. The proposed implementation significantly reduces the computation burden compared to the centrally coordinated implementation of the primal-dual algorithm. Numerical results on a 4,521-node test feeder show that the proposed hierarchical distributed algorithm can achieve an improvement of more than tenfold in the speed of convergence compared to the centrally coordinated primal-dual algorithm.

24 POWER TRANSMISSION AND DISTRIBUTION↗

How to estimate the 3D power spectrum of the Lyman-α forest

Here, we derive and numerically implement an algorithm for estimating the 3D power spectrum of the Lyman-α (Lyα) forest flux fluctuations. The algorithm exploits the unique geometry of Lyα forest data to efficiently measure the cross-spectrum between lines of sight as a function of parallel wavenumber, transverse separation and redshift. We start by approximating the global covariance matrix as block-diagonal, where only pixels from the same spectrum are correlated. We then compute the eigenvectors of the derivative of the signal covariance with respect to cross-spectrum parameters, and project the inverse-covariance-weighted spectra onto them. This acts much like a radial Fourier transform over redshift windows. The resulting cross-spectrum inference is then converted into our final product, an approximation of the likelihood for the 3D power spectrum expressed as second order Taylor expansion around a fiducial model. We demonstrate the accuracy and scalability of the algorithm and comment on possible extensions. Our algorithm will allow efficient analysis of the upcoming Dark Energy Spectroscopic Instrument dataset.

79 ASTRONOMY AND ASTROPHYSICS↗

Trigger Detection for Adaptive Scientific Workflows Using Percentile Sampling

The increasing complexity of both scientific simulations and high-performance computing system architectures are driving the need for adaptive workflows, in which the composition and execution of computational and data manipulation steps dynamically depend on the evolutionary state of the simulation itself. Consider, for example, the frequency of data storage. Critical phases of the simulation should be captured with high frequency and with high fidelity for postanalysis; however, we cannot afford to retain the same frequency for the full simulation due to the high cost of data movement. We can instead look for triggers, indicators that the simulation will be entering a critical phase, and adapt the workflow accordingly. In this paper, we present a methodology for detecting triggers and demonstrate its use in the context of direct numerical simulations of turbulent combustion using S3D. We show that chemical explosive mode analysis (CEMA) can be used to devise a noise-tolerant indicator for rapid increase in heat release. However, exhaustive computation of CEMA values dominates the total simulation, and thus is prohibitively expensive. To overcome this computational bottleneck, we propose a quantile sampling approach. Our sampling-based algorithm comes with provable error/confidence bounds, as a function of the number of samples. Most importantly, the number of samples is independent of the problem size, and thus our proposed sampling algorithm offers perfect scalability. Our experiments on homogeneous charge compression ignition and reactivity controlled compression ignition simulations show that the proposed method can detect rapid increases in heat release, and its computational overhead is negligible. Our results will be used to make dynamic workflow decisions regarding data storage and mesh resolution in future combustion simulations.

97 MATHEMATICS AND COMPUTING↗

Evaluating a quantum-classical quantum Monte Carlo algorithm with Matchgate shadows

Solving the electronic structure problem of molecules and solids to high accuracy is a major challenge in quantum chemistry and condensed matter physics. The rapid emergence and development of quantum computers offer a promising route to systematically tackle this problem. Recent work by [Huggins et al ., Nature (London) 603 , 416 (2022)] proposed a hybrid quantum-classical quantum Monte Carlo (QC-QMC) algorithm using Clifford shadows to determine the ground state of a Fermionic Hamiltonian. This approach displayed inherent noise resilience and the potential for improved accuracy compared to its purely classical counterpart. Nevertheless, the use of Clifford shadows introduces an exponentially scaling postprocessing cost. In this work, we investigate an improved QC-QMC scheme utilizing the recently developed Matchgate shadows technique [Commun. Math. Phys. 404 , 629 (2023)], which removes the aforementioned exponential bottleneck. We observe from experiments on quantum hardware that the use of Matchgate shadows in QC-QMC is inherently noise robust. We show that this noise resilience has a more subtle origin than in the case of Clifford shadows. Nevertheless, we find that classical postprocessing, while asymptotically efficient, requires hours of runtime on thousands of classical CPUs for even the smallest chemical systems, presenting a major challenge to the scalability of the algorithm.

Monte Carlo methods↗

Mesh-free data transfer algorithms for partitioned multiphysics problems: Conservation, accuracy, and parallelism

In this study we analyze and extend mesh-free algorithms for three-dimensional data transfer problems in partitioned multiphysics simulations. We first provide a direct comparison between a mesh-based weighted residual method using the common-refinement scheme and two mesh-free algorithms leveraging compactly supported radial basis functions: one using a spline interpolation and one using a moving least square reconstruction. Through the comparison we assess both the conservation and accuracy of the data transfer obtained from each of the methods. We do so for a varying set of geometries with and without curvature and sharp features and for functions with and without smoothness and with varying gradients. Our results show that the mesh-based and mesh-free algorithms are complementary with cases where each was demonstrated to perform better than the other. We then focus on the mesh-free methods by developing a set of algorithms to parallelize them based on sparse linear algebra techniques. This includes a discussion of fast parallel radius searching in point clouds and restructuring the interpolation algorithms to leverage data structures and linear algebra services designed for large distributed computing environments. The scalability of our new algorithms is demonstrated on a leadership class computing facility using a set of basic scaling studies. Finally, these scaling studies show that for problems with reasonable load balance, our new algorithms for both spline interpolation and moving least square reconstruction demonstrate both strong and weak scalability using more than 100,000 MPI processes with billions of degrees of freedom in the data transfer operation.

97 MATHEMATICS AND COMPUTING↗

Geotagging one hundred million Twitter accounts with total variation minimization

Geographically annotated social media is extremely valuable for modern information retrieval. However, when researchers can only access publicly-visible data, one quickly finds that social media users rarely publish location information. In this work, we provide a method which can geolocate the overwhelming majority of active Twitter users, independent of their location sharing preferences, using only publicly-visible Twitter data. Our method infers an unknown user's location by examining their friend's locations. We frame the geotagging problem as an optimization over a social network with a total variation-based objective and provide a scalable and distributed algorithm for its solution. Furthermore, we show how a robust estimate of the geographic dispersion of each user's ego network can be used as a per-user accuracy measure which is effective at removing outlying errors. Leave-many-out evaluation shows that our method is able to infer location for 101, 846, 236 Twitter users at a median error of 6.38 km, allowing us to geotag over 80% of public tweets.

Compton, Ryan↗

A Novel Multithreaded Algorithm For Extracting Maximal Chordal Subgraphs

Chordal graphs are triangulated graphs where any cycle larger than three is bisected by a chord. Many combinatorial optimization problems such as computing the minimum fill-in, the size of the maximum clique and the chromatic number are NP-hard on general graphs but have polynomial time solutions on chordal graphs. In this paper, we present a novel multithreaded algorithm to extract a maximal chordal subgraph from a general graph. Our algorithm is based on an iterative approach where each thread can asynchronously update a subset of edges that are dynamically assigned to it. We implement our algorithm on two different multithreaded architectures – Cray XMT, a massively multithreaded platform, and AMD Magny-Cours, a shared memory multicore platform. In addition to the proof of correctness, we present the performance of our algorithm using a testset of carefully generated synthetical graphs with up to half-a-billion edges and real world networks from gene correlation studies. We demonstrate that our algorithm achieves high scalability for all inputs on both types of architectures.

Halappanavar, Mahantesh↗

Rapid Small-Signal Stability Assessment and Enhancement Following Changes in Topology

The paper proposes a scalable and tractable algorithm for dynamic topology optimization of power systems involving changes in branch on/off status, while respecting small-signal stability (SSS) constraints. A procedure for fast updates of the system matrices (in descriptor form) and without additional full matrix inversions is proposed. To additionally reduce the computation time, only critical eigenvalues (right-most or those in a specified damping ratio and frequency range) are calculated. A quadratic optimization approach is proposed for optimized generation re-dispatch to satisfy SSS constraints. The approach is applied to two (medium- and large-scale) real-world test power systems.

Saric, AT↗

FIRE: A Failure-Adaptive RL Framework for Edge Computing Migrations

In edge computing, users' service profiles are migrated between edge servers due to user mobility. Reinforcement Learning (RL) frameworks have been proposed to do so, often trained on simulated data. However, existing RL frameworks overlook occasional server failures, which although rare, impact latency-sensitive applications like AR/VR and real- time obstacle detection. These rare failures, being not adequately represented in historical training data, pose a challenge for data-driven RL algorithms. We introduce FIRE, a framework that adapts to rare events by training a RL policy in an edge computing digital twin environment. We propose FIRE-ImRE, an importance sampling-based Q-learning algorithm, which samples rare events proportionally to their impact on the value function. FIRE considers delay, migration, failure, and backup placement costs across individual and shared service profiles. We prove FIRE-ImRE's boundedness and convergence to optimality. Next, we introduce novel deep Q-learning (FIRE-ImDQL) and actor critic (FIRE-ImACRE) versions of our algorithm to enhance scalability. Here, we extend our framework to accommodate users with varying risk tolerances of rare failure events. Through trace-driven experiments, we show that FIRE reduces edge computing costs compared to vanilla RL and the greedy baseline in the event of failures.

Edge computing↗

A Fast Scalable Quasi-Static Time Series Analysis Method for PV Impact Studies Using Linear Sensitivity Model

Understanding the impact of distributed photovoltaic (PV) resources on various elements of the distribution feeder is imperative for their cost effective integration. A year-long quasi-static time series (QSTS) simulation at 1-second granularity is often necessary to fully study these impacts. However, the significant computational burden associated with running QSTS simulations is a major challenge to their adoption. In this paper, we propose a fast scalable QSTS simulation algorithm that is based on a linear sensitivity model for estimating voltage-related PV impact metrics of a three-phase unbalanced, nonradial distribution system with various discrete step control elements including tap changing transformers and capacitor banks. Here, the algorithm relies on computing voltage sensitivities while taking into account all the effects of discrete controllable elements in the circuit. Consequently, the proposed sensitivity model can accurately estimate the state of controllers at each time step and the number of control actions throughout the year. For the test case of a real distribution feeder with 2969 buses (5469 nodes), 6 load/PV time series power profiles, and 9 voltage regulating elements including controller delays, the proposed algorithm demonstrates a dramatic time reduction, more than 180 times faster than traditional QSTS techniques.

14 SOLAR ENERGY↗

Efficient Neural Network Approaches for Conditional Optimal Transport with Applications in Bayesian Inference

In this work, we present two neural network approaches that approximate the solutions of static and dynamic conditional optimal transport (COT) problems. Both approaches enable conditional sampling and conditional density estimation, which are core tasks in Bayesian inference—particularly in the simulation-based (“likelihood-free”) setting. Our methods represent the target conditional distribution as a transformation of a tractable reference distribution. Obtaining such a transformation, chosen here to be an approximation of the COT map, is computationally challenging even in moderate dimensions. To improve scalability, our numerical algorithms use neural networks to parameterize candidate maps and further exploit the structure of the COT problem. Our static approach approximates the map as the gradient of a partially input convex neural network. It uses a novel numerical implementation to increase computational efficiency compared to state-of-the-art alternatives. Our dynamic approach approximates the conditional optimal transport via the flow map of a regularized neural ODE; compared to the static approach, it is slower to train but offers more modeling choices and can lead to faster sampling. We demonstrate both algorithms numerically, comparing them with competing state-of-the-art approaches, using benchmark datasets and simulation-based Bayesian inverse problems.

97 MATHEMATICS AND COMPUTING↗

HotSpots: Failure Cascades on Heterogeneous Critical Infrastructure Networks

Critical Infrastructure Systems such as transportation, water and power grid systems are vital to our national security, economy, and public safety. Recent events, like the 2012 hurricane Sandy, show how the interdependencies among different CI networks lead to catastrophic failures among the whole system. Hence, analyzing these CI networks, and modeling failure cascades on them becomes a very important problem. However, traditional models either do not take multiple CIs or the dynamics of the system into account, or model it simplistically. In this paper, we study this problem using a heterogeneous network viewpoint. We first construct heterogeneous CI networks with multiple components using national-level datasets. Then we study novel failure maximization problems on these networks, to compute critical nodes in such systems. We then provide HotSpots, a scalable and effective algorithm for these problems, based on careful transformations. Finally, we conduct extensive experiments on real CIS data from multiple US states, and show that our method HotSpots outperforms non-trivial baselines, gives meaningful results and that our approach gives immediate benefits in providing situational-awareness during large-scale failures.

Chen, Liangzhe↗

Master-Slave Control Scheme in Electric Vehicle Smart Charging Infrastructure

WINSmartEV is a software based plug-in electric vehicle (PEV) monitoring, control, and management system. It not only incorporates intelligence at every level so that charge scheduling can avoid grid bottlenecks, but it also multiplies the number of PEVs that can be plugged into a single circuit. This paper proposes, designs, and executes many upgrades to WINSmartEV. These upgrades include new hardware that makes the level 1 and level 2 chargers faster, more robust, and more scalable. It includes algorithms that provide a more optimal charge scheduling for the level 2 (EVSE) and an enhanced vehicle monitoring/identification module (VMM) system that can automatically identify PEVs and authorize charging.

42 ENGINEERING↗

TagDigger: user-friendly extraction of read counts from GBS and RAD-seq data

In genotyping-by-sequencing (GBS) and restriction site-associated DNA sequencing (RAD-seq), read depth is important for assessing the quality of genotype calls and estimating allele dosage in polyploids. However, existing pipelines for GBS and RAD-seq do not provide read counts in formats that are both accurate and easy to access. Additionally, although existing pipelines allow previously-mined SNPs to be genotyped on new samples, they do not allow the user to manually specify a subset of loci to examine. Pipelines that do not use a reference genome assign arbitrary names to SNPs, making meta-analysis across projects difficult. We created the software TagDigger, which includes three programs for analyzing GBS and RAD-seq data. The first script, tagdigger_interactive.py, rapidly extracts read counts and genotypes from FASTQ files using user supplied sets of barcodes and tags. Input and output is in CSV format so that it can be opened by spreadsheet software. Tag sequences can also be imported from the Stacks, TASSEL-GBSv2, TASSEL-UNEAK, or pyRAD pipelines, and a separate file can be imported listing the names of markers to retain. A second script, tag_manager.py, consolidates marker names and sequences across multiple projects. A third script, barcode_splitter.py, assists with preparing FASTQ data for deposit in a public archive by splitting FASTQ files by barcode and generating MD5 checksums for the resulting files. TagDigger is open-source and freely available software written in Python 3. It uses a scalable, rapid search algorithm that can process over 100 million FASTQ reads per hour. TagDigger will run on a laptop with any operating system, does not consume hard drive space with intermediate files, and does not require programming skill to use.

59 BASIC BIOLOGICAL SCIENCES↗