Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Graphs”

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,477 records · Page 82
All sourcesNASA NTRSDOE OSTI
DOE OSTI2022

Neural Lyapunov Differentiable Predictive Control

We present a learning-based predictive control methodology using the differentiable programming framework with sufficient Lyapunov-based guarantees. The neural Lyapunov differentiable predictive control (NLDPC) learns the policy by constructing a computational graph encompassing the system dynamics, state, and input constraints, and the necessary Lyapunov certification constraints, and thereafter using the automatic differentiation to update the neural policy parameters. In conjunction, our approach jointly learns a Lyapunov function that certifies the regions of state-space with stable dynamics. We also provide an initial condition sampling-based statistical guarantee for the training of NLDPC. Our offline training approach provides a computationally efficient and scalable alternative to classical model predictive control solutions, which now directly comes with Lyapunov based guarantees as shown in this paper. We substantiate the advantages of the proposed approach with simulations to stabilize the double integrator model and on an example of controlling an aircraft model.

Mukherjee, Sayak↗
DOE OSTI2020

DeepClone: Lightweight State Replication of Deep Learning Models for Data Parallel Training

Training modern deep neural network (DNN) models involves complex workflows triggered by model exploration, sensitivity analysis, explainability, etc. A key primitive in this context is the ability to clone a model training instance, i.e. “fork” the training process in a potentially different direction, which enables comparisons of different evolution paths using variations of training data and model parameters. However, in a quest improve the training throughput, a mix of data parallel, model parallel, pipeline parallel and layer-wise parallel approaches are making the problem of cloning highly complex. In this paper, we explore the problem of efficient cloning under such circumstances. To this end, we leverage several properties of data-parallel training and layer-wise parallelism to design DeepClone, a cloning approach based on augmenting the execution graph to gain direct access to tensors, which are then sharded and reconstructed asynchronously in order to minimize runtime overhead, standby duration, readiness duration. Compared with state-of-art approaches, DeepClone shows orders of magnitude improvement for several classes of DNN models.

data-parallel training↗
DOE OSTI2023

Fast Parallel Tensor Times Same Vector for Hypergraphs

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

Shivakumar, Shruti↗
DOE OSTI2021

A Survey: Handling Irregularities in Neural Network Acceleration with FPGAs

In the last decade, Artificial Intelligence (AI) through Deep Neural Networks (DNNs) has penetrated virtually every aspect of science, technology, and business. Many types of DNNs have been and continue to be developed, including Convolutional Neural Networks (CNNs), Recurrent Neural Net- works (RNNs), and Graph Neural Networks (GNNs). The overall problem for all of these Neural Networks (NNs) is that their target applications generally pose stringent constraints on latency and throughput, while also having strict accuracy requirements. There have been many previous efforts in creating hardware to accelerate NNs. The problem designers face is that optimal NN models typically have significant irregularities, making them hardware-unfriendly. In this paper, we first define the problems in NN acceleration by characterizing common irregularities in NN processing into 4 types; then we summarize the existing works that handle the four types of irregularities efficiently using hardware, especially FPGAs; finally, we provide a new vision of next-generation FPGA-based NN acceleration: that the emerging heterogeneity in the next-generation FPGAs is the key to achieving higher performance.

Geng, Tong↗
DOE OSTI2024

Distributed-Memory Sparse Deep Neural Network Inference Using Global Arrays

Partitioned Global Address Space (PGAS) models exhibit tremendous promise in developing efficient and productive distributed-memory parallel applications. They have been used extensively in scientific computations due to conveniently offering a ``shared-memory''-like model and convenient interfaces that separate communication with synchronization. Traditionally, PGAS communication models have been applied to dense/contiguously distributed data, but most modern applications depict varied levels of sparsity. Existing PGAS models require certain adaptations to support distributed sparse computations, since associated computations often require matrix arithmetic, in addition to data movement. The Global Arrays toolkit from Pacific Northwest National Laboratory (PNNL) is one of the earliest PGAS models to combine one-sided data communication and distributed matrix operations and is still used in the popular NWChem quantum chemistry suite. Recently, we have expanded the Global Arrays toolkit to support common sparse operations, like sparse matrix-dense matrix multiplies (SpMM), sparse matrix-sparse matrix multiplication (SpGEMM) and Sampled Dense-Dense Matrix Multiplication (SDDMM). As it turns out, these operations are the bedrock of sparse Deep Learning (DL); sparse deep neural networks and Graph Neural Networks (GNNs) have gained increasing attention recently in achieving speedups on training and inference with reduced memory footprints. Unlike scientific applications in High Performance Computing (HPC), modern (distributed-memory capable) DL toolkits often rely on non-standardized and closed-source vendor software optimizations, creating challenges in software-hardware co-design at scale. Our goal is to support a variety of distributed-memory sparse matrix operations and helper functions in the newly created Sparse Global Arrays (SGA), such that it is possible to build portable and productive Machine Learning scenarios for algorithm/software and hardware codesign purposes. Contemporary data-parallel schemes for training/inference are undergoing a major overhaul since model replication limits scalability and causes resource inefficiencies. As such, we have adopted tensor parallelism in decomposing the model and inputs, to mitigate memory issues. Current implementation is built on top of MPI and uses CPUs to maximize the portability across the platforms.

Distributed computing, machine learning↗
DOE OSTI2021

Optimizing FPGA-based Accelerator Design for Large-Scale Molecular Similarity Search (Special Session Paper)

Molecular similarity search has been widely used in drug discovery to rapidly identify structurally similar compounds from large molecular databases. With the increasing size of chemical libraries, there is growing interest in the efficient ac- celeration of large-scale similarity search. Existing works mainly focus on CPU and GPU to accelerate the computation of Tatimoto coefficient in measuring the pairwise similarity between different molecular fingerprints. In this paper, we propose and optimize an FPGA-based accelerator design on exhaustive and approximate search algorithms. On exhaustive search using BitBound & fold- ing, we analyze the similarity cutoff and folding level relationship with search speedup and accuracy, and propose a scalable on- the-fly query engine on FPGAs to reduce the resource utilization and pipeline interval. We achieve a 450 million compounds-per- second processing throughput for a single query engine. On approximate search using hierarchical navigable small world (HNSW), a popular algorithm with high recall and query speed, we propose an FPGA-based graph traversal engine to utilize high throughput register array based priority queue and fine- grained distance calculation engine to increase the processing capability. Experimental results show that the proposed FPGA- based HNSW implementation achieves a 35× speedup than existing works on CPU. To the best of our knowledge, our FPGA- based implementation is the first attempt to accelerate molecular similarity search on FPGA and has the highest performance among existing approaches.

Peng, Hongwu↗
DOE OSTI2021

Optimized Quantum Program Execution Ordering to Mitigate Errors in Simulations of Quantum Systems

Simulating the time evolution of a physical system at quantum mechanical levels of detail - known as Hamiltonian Simulation (HS) - is an important and interesting problem across physics and chemistry. For this task, algorithms that run on quantum computers are known to be exponentially faster than classical algorithms; in fact, this application motivated Feynman to propose the construction of quantum computers. Nonetheless, there are challenges in reaching this performance potential. Prior work has focused on compiling circuits (quantum programs) for HS with the goal of maximizing either accuracy or gate cancellation. Our work proposes a compilation strategy that simultaneously advances both goals. At a high level, we use classical optimizations such as graph coloring and travelling salesperson to order the execution of quantum programs. Specifically, we group together mutually commuting terms in the Hamiltonian (a matrix characterizing the quantum mechanical system) to improve the accuracy of the simulation. We then rearrange the terms within each group to maximize gate cancellation in the final quantum circuit. Furthermore, these optimizations work together to improve HS performance and result in an average 40% reduction in circuit depth. This work advances the frontier of HS which in turn can advance physical and chemical modeling in both basic and applied sciences.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

A Novel Framework to Quantify Power Grid Resilience

The quantification of an operating power grid’s resilience is highly significant today, given its criticality as an enabler of other infrastructures, complexity, and the threat it faces due to a wide range of detrimental events, from extreme climate to cyber attacks. Currently, there exist no standardized definitions and metrics for measuring the resilience of an operating grid. In this paper, we introduce a novel resilience quantification framework and demonstrate a method to measure the flexibility towards topological/structural changes due to potential failures in the power grid to assess operational resilience. We start with the state estimation data from a large utility and use the graph analysis methods and power flow simulation tools to compute the identified resilience parameters.

Yoginath, Srikanth↗
DOE OSTI2020

Computing Bottleneck Structures at Scale for High-Precision Network Performance Analysis

The Theory of Bottleneck Structures is a recently-developed framework for studying the performance of data networks. It describes how local perturbations in one part of the network propagate and interact with others. This framework is a powerful analytical tool that allows network operators to make accurate predictions about network behavior and thereby optimize performance. Previous work implemented a software package for bottleneck structure analysis, but applied it only to toy examples. In this work, we introduce the first software package capable of scaling bottleneck structure analysis to production-size networks. Here, we benchmark our system using logs from ESnet, the Department of Energy's high-performance data network that connects research institutions in the U.S. Using the previously published tool as a baseline, we demonstrate that our system achieves vastly improved performance, constructing the bottleneck structure graphs in 0.21 s and calculating link derivatives in 0.09 s on average. We also study the asymptotic complexity of our core algorithms, demonstrating good scaling properties and strong agreement with theoretical bounds. These results indicate that our new software package can maintain its fast performance when applied to even larger networks. They also show that our software is efficient enough to analyze rapidly changing networks in real time. Overall, we demonstrate the feasibility of applying bottleneck structure analysis to solve practical problems in large, real-world data networks.

benchmark↗
DOE OSTI2020

GPU-Based Static Data-Flow Analysis for Fast and Scalable Android App Vetting

Many popular vetting tools for Android applications use static code analysis techniques. In particular, Interprocedural Data-Flow Graph (IDFG) construction is the computation at the core of Android static data-flow analysis and consumes most of the analysis time. Many analysis tools use a worklist algorithm, an iterative fixed-point approach, to construct the IDFG. In this paper, we observe that a straightforward GPU parallelization of the worklist algorithm leads to significant underutilization of the GPU resources. We identify four performance bottlenecks, namely, frequent dynamic memory allocations, high branch divergence, workload imbalance, and irregular memory access patterns. Accordingly, we propose GDroid, a GPU-based worklist algorithm implementation with multiple fine-grained optimizations tailored to common characteristics of Android applications. The optimizations considered are: matrix-based data structure, memory access-based node grouping, and worklist merging. Our experimental evaluation, performed on 1000 Android applications, shows that the proposed optimizations are beneficial to performance, and GDroid can achieve up to 128X speedups against a plain GPU implementation.

Android security↗
DOE OSTI2026

LibraryX: A Framework for Cross-Library-Call Optimization

Scientific applications utilize performance libraries as a software engineering concept: these libraries encapsulate important and well-understood (mathematical) operations, allow for reuse, and are implemented and tuned by experts. Domain scientists then implement complex algorithms based on these domainspecific libraries. While individual library calls are optimized, larger performance gains across sequences of calls—sometimes spanning multiple libraries—are often unrealized, forcing a trade-off between performance and implementation complexity.To overcome this issue, we propose LibraryX, an approach and a system that allows for cross-library-call optimization even when library calls stem from multiple performance libraries. LibraryX annotates library calls with semantic information and optimizes entire directed acyclic graphs (DAGs) of calls dynamically using the SPIRAL code generation system. We demonstrate its effectiveness across a range of memory bound workloads, achieving significant speedups on Nvidia, AMD, and Intel accelerators compared to code using native libraries without cross-call optimization.

Rao, Sanil [Carnegie Mellon University,Department ↗
DOE OSTI2024

eCC++ : A Compiler Construction Framework for Embedded Domain-Specific Languages

eCC++ is a new compiler construction framework for embedding domain-specific programming languages within C++. That is, the host language is C++, the guest language is the DSL to be embedded in C++, and eCC++ is the tool that enables the embedding. The eCC++ framework is composed of three main components: a front-end, an API for program verification based on a functional and declarative intermediate representation (IR), and a Multi-Level Intermediate Representation (MLIR) code generator. The eCC++ front-end consists of a library of C++ classes and operators that can be used to define the guest language. Guest sources are compiled with any standard C++ compiler, and when run, the resulting executable generates an eCC++ IR representation of the program, which can be verified within the eCC++ framework. Finally, eCC++ allows for high-level and domain-specific optimizations before generating MLIR. In summary, eCC++ aims to act as a generic front-end that enables embedding guest languages into C++, and provides necessary compiler technology for program verification, targeting the existing capabilities in the MLIR infrastructure. The paper evaluates the eCC++ expressiveness and usability describing the process of embedding GraphIt, a high-performance graph language in C++.

Gonzalez Tallada, Marc↗
DOE OSTI2023

Smart Data Mapping for Connecting Power System Model and Geospatial Data

Knowing the geospatial locations of power system model elements is the foundation for analyzing system vulnerability to natural hazards and connecting loads with end users and their communities. However, power system models and geospatial data for power grid assets may have been developed asynchronously without close coordination. Creating a direct mapping between the two may be a challenging task, considering heterogeneous data structures, target uses, historical legacies, and human errors. This work aims to build an automatic data mapping workflow to connect power system model elements and geospatial data for transmission network, and to support energy grid resilience studies for Puerto Rico. The primary steps in this workflow include constructing graphs using geospatial data, and aligning them to the transmission networks defined in the power system data. The results have been evaluated against existing manual mapping practices for part of the Puerto Rico Power Grid model to illustrate the performance of such auto-mapping solutions.

Resilience, geospatial data, grid transmission net↗
DOE OSTI2022

Mass Detection for Heavy-Duty Vehicles using Gaussian Belief Propagation

Predicting vehicle mass is critical to accurately estimate energy use and emissions of commercial trucks. However, data from vehicle telematics is often not at sufficient temporal resolution or accuracy for use in model-based detection methods. In this work, a new statistical mass prediction technique is described for heavy-duty vehicles that incorporates the use Gaussian Belief Propagation (GBP) for probabilistic inference. Similar to Bayesian inference models, the GBP model typically requires less labeled training data than other contemporary machine learning techniques. First, a factor graph is constructed, and a set of Gaussian belief nodes with associated means and variances are fitted to the training data. To better handle noisy input data, the GBP mass prediction model utilizes a k-nearest factors (kNF) algorithm for probabilistic inference on unseen testing data. The proposed method is compared with a classical weighted k-nearest neighbors (kNN) regressor. This statistical kNF-GBP model works even with low-quantity, low-quality initial training data, while being capable of realtime mass estimation. Unlike the kNN regressor, the GBP model produces a measure of uncertainty with its predictions. The proposed method is validated using curve-sampled driving data collected from multiple cloud-connected Class 8 regional haul diesel trucks. Both the kNN regressor and the kNF-GBP mass prediction model were able to predict payload mass with coefficients of determination above 0.97 with minimal data preprocessing.

29 ENERGY PLANNING, POLICY, AND ECONOMY↗
DOE OSTI2022

CPES-QSM: A Quantitative Method Towards the Secure Operation of Cyber-Physical Energy Systems

Power systems are evolving into cyber-physical energy systems (CPES) mainly due to the integration of modern communication and Internet-of-Things (IoT) devices. CPES security evaluation is challenging since the physical and cyber layers are often not considered holistically. Existing literature focuses on only optimizing the operation of either the physical or cyber layer while ignoring the interactions between them. This paper proposes a metric, the Cyber-Physical Energy System Quantitative Security Metric (CPES-QSM), that quantifies the interaction between the cyber and physical layers across three domains: electrical, cyber-risk, and network topology. A method for incorporating the proposed cyber-metric into operational decisions is also proposed by formulating a cyber-constrained AC optimal power flow (C-ACOPF) that considers the status of all the CPES layers. The C-ACOPF considers the vulnerabilities of physical and cyber networks by incorporating factors such as voltage stability, contingencies, graph-theory, and IoT cyber risks, while using a multi-criteria decision-making technique. We note that simulation studies are conducted using standard IEEE test systems to evaluate the effectiveness of the proposed metric and the C-ACOPF formulation.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2024

Miniaturized Magnetoelastic Sensor System

This article describes the design, assembly, and implementation of a hand-held, magnetic-field-based sensor system that can be adapted for a variety of sensing applications. The miniaturized system is based on Chemical Identification by Magneto-Elastic Sensing (ChIMES) technology, which uses three concentric solenoid coils to wirelessly interrogate a sensor body comprised of a response material coupled to a magnetoelastic wire. The response material expands when it encounters a target, imposing mechanical stress on the wire and altering its magnetic permeability. The sensor bodies are passive, requiring no external power source, and they are small, measuring about 15 mm in length and 3.0 mm in diameter. Up to four sensor bodies can be configured as an evenly-spaced linear array. The sensor system operates by applying a low-frequency, current-stabilized, filtered triangle wave to a uniform-density excitation coil to switch the magnetic domains within the wire. Further, the responses from the sensors are picked up by a detection coil as stress-induced changes in the Faraday voltage, and the strong magnetic field induced by the excitation coil in the detection coil is nullified by a cancellation coil reverse-wound in series with the detection coil. The responses of the sensors in an array are separated in time by a linear gradient dc biasing coil. The sensors can be interrogated through metallic and nonmetallic barriers. The signals from the detection coil and the excitation coil are digitized by a pair of bipolar analog-to-digital converters (ADCs). A Raspberry Pi single-board computer (SBC) and associated software perform data acquisition and control all aspects of the sensor system hardware. The program allows the user to select the number of sensors in the array, the type of signal that is being collected, and the number of samples to take. The program also allows for signal processing of the sensor data, such as baseline correction. The program can differentiate sensor peaks from each other and calculate the magnitude of each sensor response with less than 1% error. The data are then displayed along with a graph of the signal.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗
DOE OSTI2024

Measurement-Based Approach for Inertia-Trend Analysis of the US Western Interconnection

Rising deployment of inverter-based resources (IBRs), characterized by a lack of rotating mass, is decreasing the total inertia of the system. This can lead to an increased Rate of Change of Frequency (RoCoF) during the disturbance and false activation of protective devices. There is a need to assess the inertia over the past decade amidst the evolving landscape of renewable energy sources to develop strategies for integrating energy storage, enhancing resilience measures, and ensuring the stable and reliable operation of the grid. Therefore, a realistic assessment of the inertia trend using a measurement-based approach that addresses the limitations of existing models is proposed. An inertia study of the Western Interconnection in the United States is performed utilizing the data from 2013 to 2022, obtained from FNET/ GridEye network. The three-second RoCoF time window is chosen for the study as it showed an optimum balance between a strong correlation with the power imbalance (ΔP) and minimum inclusion of primary response from governor. The obtained inertia trend result shows a small percentage declination of inertia over the decade. By examining the result alongside a generation mix graph, insights are gained into the dynamic interplay between shifting energy landscape and system inertia.

Dulal, Saurav↗
DOE OSTI2021

Efficient Topology Design Algorithms for Power Grid Stability

The dynamic response of power grids to small disturbances influences their overall stability. This letter examines the effect of network topology on the linearized time-invariant dynamics of electric power systems. The proposed framework utilizes H 2 -norm based stability metrics to study the optimal placement of lines on existing networks as well as the topology design of new networks. The design task is first posed as an NP-hard mixed-integer nonlinear program (MINLP) that is exactly reformulated as a mixed-integer linear program (MILP) using McCormick linearization. To improve computation time, graph-theoretic properties are exploited to derive valid inequalities (cuts) and tighten bounds on the continuous optimization variables. Moreover, a cutting plane generation procedure is put forth that is able to interject the MILP solver and augment additional constraints to the problem on-the-fly. Finally, the efficacy of our approach in designing optimal grid topologies is demonstrated through numerical tests on the IEEE 39-bus network.

24 POWER TRANSMISSION AND DISTRIBUTION↗