Search NASA⌕ Search

SEARCH · Search NASA

Results for “graph 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 181 records · Page 10

A Performance-Portable MultiGPU Implementation of 3D Euler Equations using ProtoX and IRIS

Computational scientists often face challenges when developing and optimizing code for high-performance computing (HPC), especially when trying to leverage GPUs. Given the heterogeneity of the nodes that comprise many modern HPC facilities, considerable demand exists for performance portable solutions for the core computational kernels used in many scientific computing libraries. In this work, we demonstrate a fourth-order finite volume method–based implementation of the Euler equations, which are an integral part of computational fluid dynamics. Our performance-portable multiGPU implementation for Euler equations uses ProtoX to generate kernels and IRIS for portability. ProtoX is a domain-specific language that uses a structured-grid partial differential equation library called Proto as its front end and the SPIRAL code generation system as its back end to generate optimized kernels for different architectures. Optimized kernels generated by ProtoX are orchestrated through the IRIS intelligent runtime system to provide portability. Two levels of optimizations within the IRIS runtime— directed acyclic graph fusion and task fusion—are explored to efficiently utilize computing resources in a multiGPU environment. Performance improvement through these optimizations is showcased by comparing the base ProtoX-IRIS implementation on AMD GPUs (Frontier node) and on NVIDIA GPUs (NVIDIA DGX-1).

Mankad, Het↗

Decomposition Algorithms for Solving NP-hard Problems on a Quantum Annealer

NP-hard problems such as the maximum clique or minimum vertex cover problems, two of Karp’s 21 NP-hard problems, have several applications in computational chemistry, biochemistry and computer network security. Adiabatic quantum annealers can search for the optimum value of such NP-hard optimization problems, given the problem can be embedded on their hardware. However, this is often not possible due to certain limitations of the hardware connectivity structure of the annealer. This paper studies a general framework for a decomposition algorithm for NP-hard graph problems aiming to identify an optimal set of vertices. Our generic algorithm allows us to recursively divide an instance until the generated subproblems can be embedded on the quantum annealer hardware and subsequently solved. Furthermore, the framework is applied to the maximum clique and minimum vertex cover problems, and we propose several pruning and reduction techniques to speed up the recursive decomposition. The performance of both algorithms is assessed in a detailed simulation study.

97 MATHEMATICS AND COMPUTING↗

Designing networks: A mixed-integer linear optimization approach

Designing networks with specified collective properties is useful in a variety of application areas, enabling the study of how given properties affect the behavior of network models, the downscaling of empirical networks to workable sizes, and the analysis of network temporal evolution. Despite the importance of the task, there currently exists a gap in our ability to systematically generate networks that adhere to theoretical guarantees for the given property specifications. In this work, we propose the use of Mixed-Integer Linear Optimization modeling and solution methodologies to address this Network Generation Problem. We present useful modeling techniques and apply them to mathematically express and constrain a broad class of network properties in the context of an optimization formulation. We derive complete formulations for the generation of networks that attain specified levels of connectivity, spread, assortativity and robustness, and we illustrate these via a number of computational case studies.

97 MATHEMATICS AND COMPUTING↗

C-SAW: a framework for graph sampling and random walk on GPUs

Many applications require to learn, mine, analyze and visualize large-scale graphs. These graphs are often too large to be addressed efficiently using conventional graph processing technologies. Fortunately, recent research efforts find out graph sampling and random walk, which significantly reduce the size of original graphs, can benefit the tasks of learning, mining, analyzing and visualizing large graphs by capturing the desirable graph properties. This paper introduces C-SAW, the first framework that accelerates Sampling and Random Walk framework on GPUs. Particularly, C-SAW makes three contributions: First, our framework provides a generic API which allows users to implement a wide range of sampling and random walk algorithms with ease. Second, offloading this framework on GPU, we introduce warp-centric parallel selection, and two novel optimizations for collision migration. Third, towards supporting graphs that exceed the GPU memory capacity, we introduce efficient data transfer optimizations for out-of-memory and multi-GPU sampling, such as workload-aware scheduling and batched multi-instance sampling. Taken together, our framework constantly outperforms the state of the art projects in addition to the capability of supporting a wide range of sampling and random walk algorithms.

97 MATHEMATICS AND COMPUTING↗

Scaling whole-chip QAOA for higher-order ising spin glass models on heavy-hex graphs

Abstract We show that the quantum approximate optimization algorithm (QAOA) for higher-order, random coefficient, heavy-hex compatible spin glass Ising models has strong parameter concentration across problem sizes from 16 up to 127 qubits for p = 1 up to p = 5, which allows for computationally efficient parameter transfer of QAOA angles. Matrix product state (MPS) simulation is used to compute noise-free QAOA performance. Hardware-compatible short-depth QAOA circuits are executed on ensembles of 100 higher-order Ising models on noisy IBM quantum superconducting processors with 16, 27, and 127 qubits using QAOA angles learned from a single 16-qubit instance using the JuliQAOA tool. We show that the best quantum processors find lower energy solutions up to p = 2 or p = 3, and find mean energies that are about a factor of two off from the noise-free distribution. We show that p = 1 QAOA energy landscapes remain very similar as the problem size increases using NISQ hardware gridsearches with up to a 414 qubit processor.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Scalable All-pairs Shortest Paths for Huge Graphs on Multi-GPU Clusters

We present an optimized Floyd-Warshall (Floyd-Warshall) algorithm that computes the All-pairs shortest path (APSP) for GPU accelerated clusters. The Floyd-Warshall algorithm due to its structural similarities to matrix-multiplication is well suited for highly parallel GPU architectures. To achieve high parallel efficiency, we address two key algorithmic challenges: reducing high communication overhead and addressing limited GPU memory. To reduce high communication costs, we redesign the parallel (a) to expose more parallelism, (b) aggressively overlap communication and computation with pipelined and asynchronous scheduling of operations, and (c) tailored MPI-collective. To cope with limited GPU memory, we employ an offload model, where the data resides on the host and is transferred to GPU on-demand. The proposed optimizations are supported with detailed performance models for tuning. Our optimized parallel Floyd-Warshall implementation is up to 5x faster than a strong baseline and achieves 8.1 PetaFLOPS/sec on 256~nodes of the Summit supercomputer at Oak Ridge National Laboratory. This performance represents 70% of the theoretical peak and 80% parallel efficiency. The offload algorithm can handle 2.5x larger graphs with a 20% increase in overall running time.

Sao, Piyush↗

A Parallel Computing Framework for Finding the Supported Solutions to a Biobjective Network Optimization Problem

Abstract Solving multi‐objective combinatorial optimization problems can quickly become computationally challenging when applied to large networks generated from big data. Present‐day first‐rate Mixed Integer Programming (MIP) solvers have parallelism built‐in to take advantage of multicore architectures; but specialized network optimization algorithms that can often solve graph problems more efficiently than a general MIP solver are typically programmed serially. Thus, these network algorithm implementations do not take full advantage of modern multicore computer capabilities. Many parallel computing languages include a fork/join framework into their concurrency packages that allow for simple conversion of recursive serial algorithms to operate in parallel without having to use complicated low‐level message‐passing interfaces. Fork/join is particularly well suited to divide and conquer algorithms such as Non‐Inferior Set Estimation (NISE) method for computing the supported Pareto front of a multi‐objective optimization problem. This work develops a simple general parallel NISE (pNISE) implementation using the Java 7 concurrency tools, and then offers results from a specific implementation of solving a bi‐objective shortest path problem. The results indicate that this method is capable of sizeable speed‐ups on both small‐scale personal computers as well as large‐scale shared memory supercomputers. Finally, other network problems suitable to this method are discussed, including multi‐objective variants of the minimum spanning tree problem, transportation problem, assignment problem, maximum flow problem, and the minimum‐cost flow problem. Copyright © 2015 John Wiley & Sons, Ltd.

Medrano, Fernando Antonio↗

Review of Graph Databases for Big Data Dynamic Entity Scoring

Modeling data as a graph enables users to quickly analyze networked phenomenon, such as social network-based marketing data (e.g., linking entities in social media based on their friends and their "likes", their friend-of-a-friend's "likes", etc.) and scientific data, such as in biology to assess a gene's proximity in a graph to particular disease phenotype. Numerous purpose-built graph databases (DBs) called “NoSQL” or “Not Only SQL” DBs are emerging to support this type of graph analysis. These DBs differ from traditional relational DBs in that they are optimized to improve storage and query performance across large, complex graphs. This document reviews the state of the art in graph DBs and identifies potential DBs that show promise for dynamic entity-scoring algorithms. Dynamic entity scoring is a new area of research that allows analysis of data within graphs using undirected methods to weigh the edges of the graph based on the proximity or ambient influence of near-by nodes. The EntityScore (eScore) methodology developed at Lawrence Livermore National Laboratory (LLNL) is one application of these emerging graph-analysis algorithms to help analysts identify and prioritize entities, based on complex, analyst-defined weighting criteria. Our review examines a wide range of different, well-known graph DBs in use since at least 2010 and identifies unique advantages and disadvantages that may impact eScore-specific requirements. Specifically, we review data structures employed, query features employed, load times, query calculation times, memory usage and several other important attributes reported in the literature. We limited our considerations for eScore to Blueprints-compliant graph DBs (https://github.com/tinkerpop/blueprints/) because they provide a standard, java application programming interface (API) based on the property graph model.

42 ENGINEERING↗

Accelerating computational fluid dynamics simulation of post-combustion carbon capture modeling with MeshGraphNets

Packed columns are commonly used in post-combustion processes to capture CO 2 emissions by providing enhanced contact area between a CO 2 -laden gas and CO 2 -absorbing solvent. To study and optimize solvent-based post-combustion carbon capture systems (CCSs), computational fluid dynamics (CFD) can be used to model the liquid–gas countercurrent flow hydrodynamics in these columns and derive key determinants of CO 2 -capture efficiency. However, the large design space of these systems hinders the application of CFD for design optimization due to its high computational cost. In contrast, data-driven modeling approaches can produce fast surrogates to study large-scale physics problems. We build our surrogates using MeshGraphNets (MGN), a graph neural network framework that efficiently learns and produces mesh-based simulations. We apply MGN to a random packed column modeled with over 160K graph nodes and a design space consisting of three key input parameters: solvent surface tension, inlet velocity, and contact angle. Our models can adapt to a wide range of these parameters and accurately predict the complex interactions within the system at rates over 1700 times faster than CFD, affirming its practicality in downstream design optimization tasks. This underscores the robustness and versatility of MGN in modeling complex fluid dynamics for large-scale CCS analyses.

97 MATHEMATICS AND COMPUTING↗

Evaluating conducting network based transparent electrodes from geometrical considerations

Conducting nanowire networks have been developed as viable alternative to existing indium tin oxide based transparent electrode (TE). The nature of electrical conduction and process optimization for electrodes have gained much from the theoretical models based on percolation transport using Monte Carlo approach and applying Kirchhoff's law on individual junctions and loops. While most of the literature work pertaining to theoretical analysis is focussed on networks obtained from conducting rods (mostly considering only junction resistance), hardly any attention has been paid to those made using template based methods, wherein the structure of network is neither similar to network obtained from conducting rods nor similar to well periodic geometry. Here, we have attempted an analytical treatment based on geometrical arguments and applied image analysis on practical networks to gain deeper insight into conducting networked structure particularly in relation to sheet resistance and transmittance. Many literature examples reporting networks with straight or curvilinear wires with distributions in wire width and length have been analysed by treating the networks as two dimensional graphs and evaluating the sheet resistance based on wire density and wire width. The sheet resistance values from our analysis compare well with the experimental values. Our analysis on various examples has revealed that low sheet resistance is achieved with high wire density and compactness with straight rather than curvilinear wires and with narrower wire width distribution. Similarly, higher transmittance for given sheet resistance is possible with narrower wire width but of higher thickness, minimal curvilinearity, and maximum connectivity. For the purpose of evaluating active fraction of the network, the algorithm was made to distinguish and quantify current carrying backbone regions as against regions containing only dangling or isolated wires. The treatment can be helpful in predicting the properties of a network simply from image analysis and will be helpful in improvisation and comparison of various TEs and better understanding of electrical percolation.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

3D_MolGNN_RL

3D-MolGNNRL, couples reinforcement learning (RL) to a deep generative model based on 3D-Scaffold to generate target candidates specific to a protein pocket building up atom by atom from the core scaffold. 3D-MolGNNRL provides an efficient way to optimize key features within a protein pocket using a parallel graph neural network model. The agent learns to build molecules in 3D space while optimizing the binding affinity, potency, and synthetic accessibility of the candidates generated for the SARS-CoV-2 Main protease

Kumar, Neeraj↗

Towards Enhancing Coding Productivity for GPU Programming Using Static Graphs

The main contribution of this work is to increase the coding productivity of GPU programming by using the concept of Static Graphs. GPU capabilities have been increasing significantly in terms of performance and memory capacity. However, there are still some problems in terms of scalability and limitations to the amount of work that a GPU can perform at a time. To minimize the overhead associated with the launch of GPU kernels, as well as to maximize the use of GPU capacity, we have combined the new CUDA Graph API with the CUDA programming model (including CUDA math libraries) and the OpenACC programming model. We use as test cases two different, well-known and widely used problems in HPC and AI: the Conjugate Gradient method and the Particle Swarm Optimization. In the first test case (Conjugate Gradient) we focus on the integration of Static Graphs with CUDA. In this case, we are able to significantly outperform the NVIDIA reference code, reaching an acceleration of up to 11x thanks to a better implementation, which can benefit from the new CUDA Graph capabilities. In the second test case (Particle Swarm Optimization), we complement the OpenACC functionality with the use of CUDA Graph, achieving again accelerations of up to one order of magnitude, with average speedups ranging from 2x to 4x, and performance very close to a reference and optimized CUDA code. Our main target is to achieve a higher coding productivity model for GPU programming by using Static Graphs, which provides, in a very transparent way, a better exploitation of the GPU capacity. The combination of using Static Graphs with two of the current most important GPU programming models (CUDA and OpenACC) is able to reduce considerably the execution time w.r.t. the use of CUDA and OpenACC only, achieving accelerations of up to more than one order of magnitude. Finally, we propose an interface to incorporate the concept of Static Graphs into the OpenACC Specifications.

58 GEOSCIENCES↗

Multi-qubit entanglement and algorithms on a neutral-atom quantum computer

Gate model quantum computers promise to solve currently intractable computational problems if they can be operated at scale with long coherence times and high fidelity logic. Neutral atom hyperfine qubits provide inherent scalability due to their identical characteristics, long coherence times, and ability to be trapped in dense multi-dimensional arrays. Combined with the strong entangling interactions provided by Rydberg states, all the necessary characteristics for quantum computation are available. Here we demonstrate several quantum algorithms on a programmable gate model neutral atom quantum computer in an architecture based on individual addressing of single atoms with tightly focused optical beams scanned across a two-dimensional array of qubits. Preparation of entangled Greenberger-Horne-Zeilinger (GHZ) states with up to 6 qubits, quantum phase estimation for a chemistry problem, and the Quantum Approximate Optimization Algorithm (QAOA) for the MaxCut graph problem are demonstrated. These results highlight the emergent capability of neutral atom qubit arrays for universal, programmable quantum computation, as well as preparation of non-classical states of use for quantum enhanced sensing.

97 MATHEMATICS AND COMPUTING↗

MapsTorch : automatic differentiation for X-ray fluorescence data analysis

X-ray fluorescence (XRF) is a popular spectroscopy technique for elemental analysis. Spectrum fitting and parameter tuning are at the core of XRF analysis and are conventionally manually intensive, especially for synchrotron experiments involving large amounts of diverse samples. This work introduces the automatic differentiation (AD) technique to XRF and an open-source package called MapsTorch. By transforming an analytical model of the XRF spectrum into a differentiable computation graph with AD, MapsTorch enables robust optimization of parameters and elemental intensities. We evaluate MapsTorch by conducting computational experiments on a large number of historical synchrotron XRF datasets and compare its performance with the currently practiced fitting tool NLopt. The results show that MapsTorch consistently achieves high-quality fits and often leads to better fitting quality than NLopt, particularly in tasks such as initial spectrum fitting and elemental intensity refinement. The robust performance of MapsTorch paves the way for developing automated and high-throughput XRF data analysis workflows to handle the increasing data volumes expected from next-generation synchrotron facilities.

X-ray fluorescence↗

Structure- and Physics-Preserving Reductions of Power Grid Models

The large size of multiscale, distribution and transmission, power grids hinders fast systemwide estimation and real-time control and optimization of operations. This paper studies graph reduction methods of power grids that are favorable for fast simulations and follow-up applications. While the classical Kron reduction has been successful in reduced order modeling of power grids with traditional, hierarchical design, the selection of reference nodes for the reduced model in a multiscale, distribution and transmission, network becomes ambiguous. In this work we extend the use of the iterative Kron reduction by utilizing the electric grid's graph topology for the selection of reference nodes, consistent with the design features of multiscale networks. Additionally, we propose further reductions by aggregation of coherent subnetworks of triangular meshes, based on the graph topology and network characteristics, in order to preserve currents and build another power-flow equivalent network. Our reductions are achieved through the use of iterative aggregation of subgraphs that include general tree structures, lines, and triangles. Important features of our reduction algorithms include that (i) the reductions are either equivalent to the Kron reduction or otherwise produce a power-flow equivalent network; (ii) due to the mentioned power-flow equivalence, the reduced network can model the dynamic of the swing equations for a lossless, inductive, steady state network; (iii) the algorithms efficiently utilize hash tables to store the sequential reduction steps. The third feature allows for easy reintroduction of detailed models into the reduced, conceptual network and makes the final reduced order model backward compatible with a sequence of intermediate, partially reduced networks with varying resolution---the ordered sequence of iterative reductions corresponds to a sequence of reduced order models. The performance of our graph reduction algorithms and features of the reduced grids are discussed on a real-word transmission and distribution grid. We produce visualizations of the reduced models through open source libraries and release our reduction algorithms with example code and toy data.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Enhancing scalability of a matrix-free eigensolver for studying many-body localization

We propose several techniques to enhance the parallel scalability of a matrix-free eigensolver designed for studying many-body localization (MBL) of quantum spin chain models with nearest-neighbor interactions and on-site disorder. This type of problem is computationally challenging because the dimension of the associated Hamiltonian matrix grows exponentially with respect to the number of spins L, and we need to average over different realizations of the random disorder to obtain relevant statistical behavior. For each disorder realization, we need to compute eigenvalues from different regions of the spectrum and their corresponding eigenvectors. In previous work, the interior eigenstates for a single eigenvalue problem are computed via the shift-and-invert Lanczos algorithm. Due to the extremely high memory footprint of the LU factorizations, this technique is not well suited for large L’s. For example, we need thousands of compute nodes on modern high performance computing infrastructures to go beyond L = 24. The matrix-free approach does not suffer from this memory bottleneck, however, its scalability is limited by a computation and communication load imbalance. To reduce this imbalance and to significantly enhance the scalability of the matrix-free eigensolver, we reorder the matrix and leverage the consistent space runtime, CSPACER. We also show its efficiency in managing irregular communication patterns at scale compared to optimized MPI non-blocking two-sided and one-sided RMA implementation variants. This effort enables us to study MBL for spin chains with a larger number of spins. The efficiency and effectiveness of the proposed algorithm is demonstrated by computing eigenstates on a massively parallel many-core high performance computer.

METIS↗

Summer Proceedings 2019

The Computer Science Research Institute (CSRI) brings university faculty and students to Sandia for focused collaborative research on Department of Energy (DOE) computer and computational science problems. The institute provides an opportunity for university researchers to learn about problems in computer and computational science at DOE laboratories. Participants conduct leading-edge research, interact with scientists and engineers at the laboratories, and help transfer results of their research to programs at the labs. Some specific CSRI research interest areas are: scalable solvers, optimization, adaptivity and mesh refinement, graph-based, discrete, and combinatorial algorithms, uncertainty estimation, mesh generation, dynamic load-balancing, virus and other malicious-code defense, visualization, scalable cluster computers and heterogeneous computers, data-intensive computing, environments for scalable computing, parallel input/output, advanced architectures, and theoretical computer science. The CSRI Summer Program includes the organization of a weekly seminar series and the publication of this summer proceedings.

97 MATHEMATICS AND COMPUTING↗

CSRI Summer Proceedings 2020

The Computer Science Research Institute (CSRI) brings university faculty and students to Sandia for focused collaborative research on Department of Energy (DOE) computer and computational science problems. The institute provides an opportunity for university researchers to learn about problems in computer and computational science at DOE laboratories. Participants conduct leading-edge research, interact with scientists and engineers at the laboratories, and help transfer results of their research to programs at the labs. Some specific CSRI research interest areas are: scalable solvers, optimization, adaptivity and mesh refinement, graph-based, discrete, and combinatorial algorithms, uncertainty estimation, mesh generation, dynamic load-balancing, virus and other malicious-code defense, visualization, scalable cluster computers, data-intensive computing, environments for scalable computing, parallel input/output, advanced architectures, and theoretical computer science. The CSRI Summer Program is organized by CSRI and typically includes the organization of a weekly seminar series and the publication of a summer proceedings. In 2020, the CSRI summer program was executed completely virtually; all student interns worked from home, due to the COVID-19 pandemic.

97 MATHEMATICS AND COMPUTING↗