Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “fast optimization”

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 505 records · Page 28

NSFnets (Navier-Stokes flow nets): Physics-informed neural networks for the incompressible Navier-Stokes equations

In the last 50 years there has been a tremendous progress in solving numerically the Navier-Stokes equations using finite differences, finite elements, spectral, and even meshless methods. Yet, in many real cases, we still cannot incorporate seamlessly (multi-fidelity) data into existing algorithms, and for industrial-complexity applications the mesh generation is time consuming and still an art. Moreover, solving ill-posed problems (e.g., lacking boundary conditions) or inverse problems is often prohibitively expensive and requires different formulations and new computer codes. Here, we employ physics-informed neural networks (PINNs), encoding the governing equations directly into the deep neural network via automatic differentiation, to overcome some of the aforementioned limitations for simulating incompressible laminar and turbulent flows. We develop the Navier-Stokes flow nets (NSFnets) by considering two different mathematical formulations of the Navier-Stokes equations: the velocity-pressure (VP) formulation and the vorticity-velocity (VV) formulation. Since this is a new approach, we first select some standard benchmark problems to assess the accuracy, convergence rate, computational cost and flexibility of NSFnets; analytical solutions and direct numerical simulation (DNS) databases provide proper initial and boundary conditions for the NSFnet simulations. The spatial and temporal coordinates are the inputs of the NSFnets, while the instantaneous velocity and pressure fields are the outputs for the VP-NSFnet, and the instantaneous velocity and vorticity fields are the outputs for the VV-NSFnet. This is unsupervised learning and, hence, no labeled data are required beyond boundary and initial conditions and the fluid properties. The residuals of the VP or VV governing equations, together with the initial and boundary conditions, are embedded into the loss function of the NSFnets. No data is provided for the pressure to the VP-NSFnet, which is a hidden state and is obtained via the incompressibility constraint without extra computational cost. Unlike the traditional numerical methods, NSFnets inherit the properties of neural networks (NNs), hence the total error is composed of the approximation, the optimization, and the generalization errors. Here, we empirically attempt to quantify these errors by varying the sampling (“residual”) points, the iterative solvers, and the size of the NN architecture. For the laminar flow solutions, we show that both the VP and the VV formulations are comparable in accuracy but their best performance corresponds to different NN architectures. The initial convergence rate is fast but the error eventually saturates to a plateau due to the dominance of the optimization error. For the turbulent channel flow, we show that NSFnets can sustain turbulence at , but due to expensive training we only consider part of the channel domain and enforce velocity boundary conditions on the subdomain boundaries provided by the DNS data base. We also perform a systematic study on the weights used in the loss function for balancing the data and physics components, and investigate a new way of computing the weights dynamically to accelerate training and enhance accuracy. In the last part, we demonstrate how NSFnets should be used in practice, namely for ill-posed problems with incomplete or noisy boundary conditions as well as for inverse problems. We obtain reasonably accurate solutions for such cases as well without the need to change the NSFnets and at the same computational cost as in the forward well-posed problems. As a result, we also present a simple example of transfer learning that will aid in accelerating the training of NSFnets for different parameter settings.

97 MATHEMATICS AND COMPUTING↗

Deep reinforcement learning assisted co-optimization of Volt-VAR grid service in distribution networks

With the increasing penetration of distributed energy resources in distribution networks, Volt-VAR control and optimization (VVC/VVO) have become very important to ensure an acceptable quality of service to all customers. System operators can rely on slow-responding utility devices, including capacitor banks and on-load tap changing transformers, along with fast-responding battery and photovoltaic (PV) inverters for the VVC/VVO implementation. Because of variations in response time of these two classes of devices, and different control actions (discrete versus continuous), coordinated and optimal scheduling and operation have become of utmost importance. Here, this paper develops a look-ahead deep reinforcement learning (DRL)-based multi-objective VVO technique to improve the voltage profile of active distribution networks, decrease network and inverter power loss, and save the operational cost of the grid. It proposes a deep deterministic policy gradient (DDPG)-based approach to schedule the optimal reactive and/or active power set-points of fast-responding inverters, and a deep Q-network (DQN)-based DRL agent to schedule the discrete decisions variables of slow-responding assets. The reactive power output of PV and battery smart inverters are scheduled at 30-minute intervals and the capacitors’ commitment status is scheduled with several hour intervals. The proposed framework is validated on the modified IEEE 34-bus and 123-bus test cases with embedded PV and PV-plus-storage. To validate the efficacy of the proposed VVO, it is compared with several scenarios, including the base case without VVO, localized droop control of DERs, DDPG-only, and twin delayed DDPG (TD3) agent-based DRL techniques. The results justify the superior performance of the proposed method to improve the voltage profile, reduce network power loss, and minimize the look-ahead grid operational cost while minimizing the undesirable power losses in inverters as a result of power factor adjustments.

24 POWER TRANSMISSION AND DISTRIBUTION↗

LaSDI: Parametric Latent Space Dynamics Identification

Enabling fast and accurate physical simulations with data has become an important area of computational physics to aid in inverse problems, design-optimization, uncertainty quantification, and other various decision-making applications. This paper presents a data-driven framework for parametric latent space dynamics identification procedure that enables fast and accurate simulations. The parametric model is achieved by building a set of local latent space model and designing an interaction among them. An individual local latent space dynamics model achieves accurate solution in a trust region. By letting the set of trust region to cover the whole parameter space, our model shows an increase in accuracy with an increase in training data. Herein we introduce two different types of interaction mechanisms, i.e., point-wise and region-based approach. Both linear and nonlinear data compression techniques are used. We illustrate the framework of Latent Space Dynamics Identification (LaSDI) enable a fast and accurate solution process on various partial differential equations, i.e., Burgers’ equations, radial advection problem, and nonlinear heat conduction problem, achieving 0 (100)x speed-up and 0 (1)% relative error with respect to the corresponding full order models.

97 MATHEMATICS AND COMPUTING↗

Parallel-vector computation for linear structural analysis and non-linear unconstrained optimization problems

Several parallel-vector computational improvements to the unconstrained optimization procedure are described which speed up the structural analysis-synthesis process. A fast parallel-vector Choleski-based equation solver, pvsolve, is incorporated into the well-known SAP-4 general-purpose finite-element code. The new code, denoted PV-SAP, is tested for static structural analysis. Initial results on a four processor CRAY 2 show that using pvsolve reduces the equation solution time by a factor of 14-16 over the original SAP-4 code. In addition, parallel-vector procedures for the Golden Block Search technique and the BFGS method are developed and tested for nonlinear unconstrained optimization. A parallel version of an iterative solver and the pvsolve direct solver are incorporated into the BFGS method. Preliminary results on nonlinear unconstrained optimization test problems, using pvsolve in the analysis, show excellent parallel-vector performance indicating that these parallel-vector algorithms can be used in a new generation of finite-element based structural design/analysis-synthesis codes.

Nguyen, D. T.↗

Latent Space Simulation for Carbon Capture Design Optimization

The CO2 capture efficiency in solvent-based carbon capture systems (CCSs) critically depends on the gas-solvent interfacial area (IA), making maximization of IA a foundational challenge in CCS design. While the IA associated with a particular CCS design can be estimated via a computational fluid dynamics (CFD) simulation, using CFD to derive the IAs associated with numerous CCS designs is prohibitively costly. However, previous works such as Deep Fluids (Kim et al., 2019) show that large simulation speed-ups and low error are achievable by replacing CFD simulators with neural-network (NN) surrogates that mimic the CFD simulation process. This raises the possibility for a fast, accurate replacement for a CFD simulator, and thus computationally feasible IA-based CCS-design optimization. As such, here, we explore whether an existing NN-surrogate approach (and variants we develop) can successfully be applied to our complex carbon-capture CFD simulations, with the ultimate goal of obtaining a fast and accurate simulator for our CCS-design application. Our experiments build on the Deep Fluids approach and find that resulting surrogates can produce large speed ups (4000x) while maintaining IA relative errors as low as 4% on unseen CCS configurations (interpolating between configurations seen during training). Thus, despite less faithfulness to the underlying physics of the problem, NN surrogates may be a promising tool for our CCS design optimization problem. Notably, though, the Deep Fluids approach has limitations for our application (such as model non-transferability to CCS-packing changes), which we discuss. We conclude with potential directions for future work that may, like innovations we introduced here (e.g., transformer-based dynamics prediction), improve performance on our complicated dataset of CCS CFD simulations.

AI Surrogate Simulation, Carbon Capture, design op↗

Applications Performance Under MPL and MPI on NAS IBM SP2

On July 5, 1994, an IBM Scalable POWER parallel System (IBM SP2) with 64 nodes, was installed at the Numerical Aerodynamic Simulation (NAS) Facility Each node of NAS IBM SP2 is a "wide node" consisting of a RISC 6000/590 workstation module with a clock of 66.5 MHz which can perform four floating point operations per clock with a peak performance of 266 Mflop/s. By the end of 1994, 64 nodes of IBM SP2 will be upgraded to 160 nodes with a peak performance of 42.5 Gflop/s. An overview of the IBM SP2 hardware is presented. The basic understanding of architectural details of RS 6000/590 will help application scientists the porting, optimizing, and tuning of codes from other machines such as the CRAY C90 and the Paragon to the NAS SP2. Optimization techniques such as quad-word loading, effective utilization of two floating point units, and data cache optimization of RS 6000/590 is illustrated, with examples giving performance gains at each optimization step. The conversion of codes using Intel's message passing library NX to codes using native Message Passing Library (MPL) and the Message Passing Interface (NMI) library available on the IBM SP2 is illustrated. In particular, we will present the performance of Fast Fourier Transform (FFT) kernel from NAS Parallel Benchmarks (NPB) under MPL and MPI. We have also optimized some of Fortran BLAS 2 and BLAS 3 routines, e.g., the optimized Fortran DAXPY runs at 175 Mflop/s and optimized Fortran DGEMM runs at 230 Mflop/s per node. The performance of the NPB (Class B) on the IBM SP2 is compared with the CRAY C90, Intel Paragon, TMC CM-5E, and the CRAY T3D.

Saini, Subhash↗

Generalized Linear Targeting For Cislunar Flight

An important element of Artemis and NASA’s campaign to explore the Moon is the autonomous onboard two-level targeter (TLT) used during all cislunar flight phases. The function of the TLT is to autonomously recompute the burn targets for the upcoming burn (or multiple burns) in response to navigation and vehicle dispersion providing a solution that meets all of the trajectory constraints. Although the TLT has been utilized previously as a ground-based planning tool, and flown onboard during the Artemis I mission, it’s complexity and iterative nature make is difficult to incorporate into and support rapid analyses such as robust optimal trajectory design applications where speed is essential. In this paper, a set of generalized linear targeting algorithms that mimics many of the properties of the TLT is derived. The generalized algorithms can handle single or multiple impulsive maneuvers, with multiple constraints at multiple fixed or variable times. A linear targeting algorithm for finite burn maneuvers is also derived. The generalized linear targeting algorithms are exceptionally fast and easy to implement in Monte Carlo analysis, linear covariance (LinCov) analysis, and robust optimal trajectory design. Several cislunar flight examples are provided.

Linear Covariance Analysis↗

Enabling fast charging of lithium-ion batteries through secondary-/dual- pore network: Part II - numerical model

To increase the market share of electric vehicles, it is desirable to reduce the battery charge times, which are significantly limited by poor electrolyte transport. A high rate charging is achievable by using expensive and low energy density cells with thin electrodes. For higher energy density cells, new electrolytes with improved conductivity and diffusivity and/or electrodes with advanced architecture are required to boost the electrolyte transport, leading to a more uniform utilization of active materials. In our previous work, an analytical model was developed to investigate the effect of secondary pore network (SPN) on electrolyte transport and the configuration of SPN was optimized by enforcing equal characteristic diffusion times in through-plane and in-plane directions. Here, to evaluate the effect of SPN on the fast-charging capability of lithium-ion batteries, a 2D physics-based electrochemical model is developed with SPN in either one or both electrodes. Additionally, the effect of SPN on cell energy density and lithium plating is investigated for cells with different loadings and electrode porosities. Combining SPN with elevated charging temperatures, the model predicts that the volumetric discharge energy density of a 3 mA h/cm2 cell can reach 270 Wh/L after a 6C constant-current charging.

25 ENERGY STORAGE↗

Opportunity Assessment for Sustainable Aviation Fuel Production from Woody Biomass via Ex Situ Catalytic Fast Pyrolysis and Refinery Hydroprocessing

Biofuels have become a promising solution to reduce emissions in hard-to-electrify transportation sectors, such as aviation. However, several biofuel conversion pathways will likely be needed to scale sustainable aviation fuel (SAF) production to meet lower carbon intensity goals when biomass feedstock availability constraints are considered. This study evaluates the future potential of the catalytic fast pyrolysis (CFP) pathway to contribute to U.S. SAF production goals as outlined in the U.S. Department of Energy’s (DOE) SAF Grand Challenge, understanding that the CFP pathway is still under development toward maturity and scaleup. National forestland resource data from the DOE’s 2023 Billion Ton Study are integrated with recent experimental results demonstrating end-to-end woody biomass conversion to SAF via CFP and hydroprocessing in a novel bioeconomy optimization framework. U.S. refinery hydroprocessing capacity is also considered with repurposing and coprocessing strategies. Results indicate that the CFP process can contribute up to 4.6 billion gallons of SAF annually by 2040, meeting 13% of the 2050 SAF Grand Challenge target while reducing the carbon intensity (CI) of the U.S. jet fuel pool by 16%. The study further explores optimal processing strategies, suggesting that colocating CFP operations with existing petroleum refineries and repurposing some U.S. hydrocracking capacity may offer significant cost advantages and enhance the commercial viability of the CFP pathway. These results underscore the CFP pathway’s potential to support the global aviation industry’s lower carbon intensity objectives while producing other renewable fuels and products.

09 BIOMASS FUELS↗

Optimal Operations Management of Mobility-on-Demand Systems

The emergence of the sharing economy in urban transportation networks has enabled new fast, convenient and accessible mobility services referred to as Mobilty-on-Demand systems (e.g., Uber, Lyft, DiDi). These platforms have flourished in the last decade around the globe and face many operational challenges in order to be competitive and provide good quality of service. A crucial step in the effective operation of these systems is to reduce customers' waiting time while properly selecting the optimal fleet size and pricing policy. In this paper, we jointly tackle three operational decisions: (i) fleet size, (ii) pricing, and (iii) rebalancing, in order to maximize the platform's profit or its customers' welfare. To accomplish this, we first devise an optimization framework which gives rise to a static policy. Then, we elaborate and propose dynamic policies that are more responsive to perturbations such as unexpected increases in demand. We test this framework in a simulation environment using three case studies and leveraging traffic flow and taxi data from Eastern Massachusetts, New York City, and Chicago. Our results show that solving the problem jointly could increase profits between 1% and up to 50%, depending on the benchmark. Moreover, we observe that the proposed fleet size yield utilization of the vehicles in the fleet is around 75% compared to private vehicle utilization of 5%.

Wollenstein-Betech, Salomón↗

How Does Escherichia coli Allocate Proteome?

Microorganisms are shown to actively partition their intracellular resources, such as pro- teins, for growth optimization. Recent experiments have begun to reveal molecular com- ponents unpinning the partition; however, it remains unclear quantitatively how individual parts orchestrate to yield precise resource allocation that is both robust and dynamic. Here we developed a coarse-grained mathematical framework that centers on guanosine pentaphosphate (ppGpp)-mediated regulation, and used it to systematically uncover the design principles of proteome allocation in Escherichia coli. Our results showed that cellular ability of resource partition lies in an ultrasensitive, negative feedback control- ling topology with the ultrasensitivity arising from zero-order amino acid kinetics and the negative feedback from ppGpp-controlled ribosome synthesis. In addition, together with the time-scale separation between slow ribosome kinetics and fast turnovers of ppGpp and amino acids, the network topology confers the organism an optimization mechanism which mimics sliding mode control, a nonlinear optimization strategy that is widely used in man-made systems. We further showed that such a controlling mechanism is robust against parameter variations and molecular fluctuations, and is also efficient for biomass production over time. Furthermore, this work elucidates the fundamental controlling mechanism of E. coli proteome allocation, thereby providing insights into quantitative microbial physiology as well as the design of synthetic gene networks.

59 BASIC BIOLOGICAL SCIENCES↗

Joint scheduling of energy, fast and primary frequency response reserves in integrated transmission–distribution networks

Inverter-based distributed energy resources (DERs) connected to distribution networks (DNs) can provide fast frequency support, but their reserve deliverability depends on feeder constraints and differs from synchronous primary frequency response (PFR). Existing transmission–distribution coordination studies usually treat reserve generically or neglect feeder-level feasibility, while frequency-security scheduling studies rarely represent distribution feeders explicitly. This paper develops a bi-level day-ahead scheduling framework for integrated transmission–distribution networks that jointly clears energy, transmission-side PFR, and distribution-side fast frequency response (FFR) under exogenous hourly inertia and largest-loss inputs from an external unit commitment (UC) schedule. The transmission problem is modeled with DC-optimal power flow (OPF) and closed-form second-order cone (SOC) frequency-security constraints, whereas each DN is represented by a reserve-aware branch-flow AC-OPF so that scheduled fast reserves remain deliverable during activation. The bi-level problem is reformulated through Karush–Kuhn–Tucker (KKT) conditions into a mixed-integer SOC program, and a penalty term is used to tighten the distribution-network relaxation. In the reduced test system, lower exogenous inertia increased the required primary response from 179.64 MW to 191.08 MW, distribution-side fast response reduced total frequency-response procurement by up to 4.9%, and neglecting distribution constraints overstated the combined distribution-side energy and reserve award by up to 18%. In the expanded study, the largest case was solved in 2.02 s with a 0.00% optimality gap. Time-domain simulations kept the frequency nadir above 59.0 Hz in all tested hours. These results demonstrate the value of fast-response modeling and distribution-feasible reserve delivery in coordinated market clearing.

Noh, Seung-Gil↗

NSTX-U theory, modeling and analysis results

Here, the mission of the low aspect ratio spherical tokamak NSTX-U is to advance the physics basis and technical solutions required for optimizing the configuration of next-step steady-state tokamak fusion devices. NSTX-U will ultimately operate at up to 2 MA of plasma current and 1 T toroidal field on axis for 5 s, and has available up to 15 MW of neutral beam injection power at different tangency radii and 6 MW of high harmonic fast wave heating. With these capabilities NSTX-U will develop the physics understanding and control tools to ramp-up and sustain high performance fully non-inductive plasmas with large bootstrap fraction and enhanced confinement enabled via the low aspect ratio, high beta configuration. With its unique capabilities, NSTX-U research also supports ITER and other critical fusion development needs. Super-Alfvénic ions in beam-heated NSTX-U plasmas access energetic particle (EP) parameter space that is relevant for both α-heated conventional and low aspect ratio burning plasmas. NSTX-U can also generate very large target heat fluxes to test conventional and innovative plasma exhaust and plasma facing component solutions. This paper summarizes recent analysis, theory and modelling progress to advance the tokamak physics basis in the areas of macrostability and 3D fields, EP stability and fast ion transport, thermal transport and pedestal structure, boundary and plasma material interaction, RF heating, scenario optimization and real-time control.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

Reinforcement Learning for In-Spill Optimization of the Mu2e Resonant Extraction: Compensating Non-Stationarity

We present design considerations and challenges for the fast machine learning component of a third-order resonant beam extraction regulation system being commissioned to deliver steady beam rates to the mu2e experiment at Fermilab. Dedicated quadrupoles drive the tune toward the 29/3 resonance each spill, extracting beam at kV multiwire septa. The overall Spill Regulation System consists of (1) a “slow” process using ~100-spill averages to adjust the base quad ramp infrequently, (2) a feedforward harmonic content compensator, and (3) the “fast” ML agent reacting during each ongoing spill with on-the-fly additive corrections to the sum of (1) and (2). We have demonstrated improved beam-rate steadying for a fast ML agent compared to a PID controller using a quasi-physical spill simulation, and demonstrated distillation of that simulation into a predictive surrogate model. Current work includes a data-and-training pipeline to generate data-aware surrogates with real-world dynamics, even as the dynamics shift unpredictably. The surrogates are to act as RL environments against which to train our fast ML control agents before deploying them on FPGA in the live system. Further current efforts focus on modeling and controlling beam loss around the storage ring, understanding additional available hardware inputs to the model, and the interplay of these with beam-steadying performance.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

A stochastic optimal feedforward and feedback control methodology for superagility

A new control design methodology is developed: Stochastic Optimal Feedforward and Feedback Technology (SOFFT). Traditional design techniques optimize a single cost function (which expresses the design objectives) to obtain both the feedforward and feedback control laws. This approach places conflicting demands on the control law such as fast tracking versus noise atttenuation/disturbance rejection. In the SOFFT approach, two cost functions are defined. The feedforward control law is designed to optimize one cost function, the feedback optimizes the other. By separating the design objectives and decoupling the feedforward and feedback design processes, both objectives can be achieved fully. A new measure of command tracking performance, Z-plots, is also developed. By analyzing these plots at off-nominal conditions, the sensitivity or robustness of the system in tracking commands can be predicted. Z-plots provide an important tool for designing robust control systems. The Variable-Gain SOFFT methodology was used to design a flight control system for the F/A-18 aircraft. It is shown that SOFFT can be used to expand the operating regime and provide greater performance (flying/handling qualities) throughout the extended flight regime. This work was performed under the NASA SBIR program. ICS plans to market the software developed as a new module in its commercial CACSD software package: ACET.

Halyo, Nesim↗

Coil optimization for quasi-helically symmetric stellarator configurations

Filament-based coil optimizations are performed for several quasi-helical stellarator configurations, beginning with the one from Landreman & Paul ( Phys. Rev. Lett. , vol. 128, 2022, 035001), demonstrating that precise quasi-helical symmetry can be achieved with realistic coils. Several constraints are placed on the shape and spacing of the coils, such as low curvature and sufficient plasma–coil distance for neutron shielding. The coils resulting from this optimization have a maximum curvature 0.8 times that of the coils of the Helically Symmetric eXperiment (HSX) and a mean squared curvature 0.4 times that of the HSX coils when scaled to the same plasma minor radius. When scaled up to reactor size and magnetic field strength, no fast particle losses were found in the free-boundary configuration when simulating 5000 alpha particles launched at $3.5\,\mathrm {MeV}$ on the flux surface with a normalized toroidal flux of $s=0.5$ . An analysis of the tolerance of the coils to manufacturing errors is performed using a Gaussian process model, and the coils are found to maintain low particle losses for smooth, large-scale errors up to amplitudes of approximately $0.15\,\mathrm {m}$ . Another coil optimization is performed for the Landreman–Paul configuration with the additional constraint that the coils are purely planar. Visual inspection of the Poincaré plot of the resulting magnetic field-lines reveal that the planar modular coils alone do a poor job of reproducing the target equilibrium. Additional non-planar coil optimizations are performed for the quasi-helical configuration with $5\,\%$ volume-averaged plasma beta from Landreman et al. ( Phys. Plasma , vol. 29, issue 8, 2022, 082501), and a similar configuration also optimized to satisfy the Mercier criterion. The finite beta configurations had larger fast-particle losses, with the free-boundary Mercier-optimized configuration performing the worst, losing approximately $5.5\,\%$ of alpha particles launched at $s=0.5$ .

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

Fast arithmetic in MacLISP

MacLISP provides a compiler which produces numerical code competitive in speed with some FORTRAN implementations and yet compatible with the rest of the MacLISP system. All numerical programs can be run under the MacLISP interpreter. Additional declarations to the compiler specify type information which allows the generation of optimized numerical code which generally does not require the garbage collection of temporary numerical results. Array accesses are almost as fast as in FORTRAN, and permit the use of dynamically allocated arrays of varying dimensions. The implementation decisions regarding user interface, data representations, and interfacing conventions are discussed which allow the generation of fast numerical LISP code.

Steele, G. L., Jr.↗

GraphTango: A Hybrid Representation Format for Efficient Streaming Graph Updates and Analysis

Abstract Streaming graph processing performs batched updates and analytics on a time-evolving graph. The underlying representation format of the graph largely determines the throughputs of these updates and analytics phases. Existing representation formats usually employ variations of hash tables or adjacency lists. However, a recent study showed that the adjacency-list-based approaches perform poorly on heavy-tailed graphs, and the hash table-based approaches suffer on short-tailed graphs. We propose GraphTango, a hybrid representation format that provides excellent update and analytics throughput regardless of the graph’s degree distribution. GraphTango dynamically switches among three different formats based on a vertex’s degree: (i) Low-degree vertices store the edges directly with the neighborhood metadata, confining accesses to a single cache line, (2) Medium-degree vertices use adjacency lists, and (3) High-degree vertices use hash tables as well as adjacency lists. In this case, the adjacency list provides fast traversal during the analytics phase, while the hash table provides constant-time lookups during the update phase. We further optimized the performance by designing an open-addressing-based hash table that fully utilizes every fetched cache line. In addition, we developed a thread-local lock-free memory pool that allows fast growing/shrinking of the adjacency lists and hash tables in a multi-threaded environment. We evaluated GraphTango with the help of the SAGA-Bench framework and compared it with four other representation formats: Stinger, Degree-aware Robin Hood Hashing, and two adjacency list-based formats with different workload balancing scheme. On average, GraphTango provides 4.5x higher insertion throughput, 3.2x higher deletion throughput, and 1.1x higher analytics throughput over the next best format. Furthermore, we integrated GraphTango with the state-of-the-art graph processing frameworks DZiG and RisGraph. Compared to the vanilla DZiG and vanilla RisGraph , [ GraphTango + DZiG ] and [ GraphTango + RisGraph ] reduces the average batch processing time by 2.3x and 1.5x, respectively.

Ahmed, Alif↗