Search NASA⌕ Search

SEARCH · Search NASA

Results for “high performance graph algorithms”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 37 records · Page 2
All sourcesNASA NTRSDOE OSTI
DOE OSTI2019

Distributed Direction-Optimizing Label Propagation for Community Detection

Designing a scalable algorithm for community detec-tion is challenging due to the tradeoff between the performance and the quality of the result. We propose a new distributed algorithm for community detection —Direction-Optimizing Label Propagation Algorithm, based on a novel Label Propagation Algorithm in community detection. The algorithm is inspired by the direction optimization technique for graph traversal algorithms and relies on the use of frontiers and alternates between label push and label pull operations. This organization creates ?exibility and affords opportunities for balancing the performance and the quality of the solution. We implement our algorithm in distributed memory with an active-message based asynchronous many-task runtime, AM++. We experiment with two seeding strategies for initial seeding stage, namely, random seeding and degree seeding. With the Graph Challenge datasets, our distributed implementation, in conjunction with the runtime support, achieves very good performance and reasonable quality of solution.

Liu, Xu↗
DOE OSTI2019

Extreme Scale De Novo Metagenome Assembly

Metagenome assembly is the process of transforming a set of short, overlapping, and potentially erroneous DNA segments from environmental samples into the accurate representation of the underlying microbiomes's genomes. State-of-the-art tools require big shared memory machines and cannot handle contemporary metagenome datasets that exceed Terabytes in size. In this paper, we introduce the MetaHipMer pipeline, a high-quality and high-performance metagenome assembler that employs an iterative de Bruijn graph approach. MetaHipMer leverages a specialized scaffolding algorithm that produces long scaffolds and accommodates the idiosyncrasies of metagenomes. MetaHipMer is end-to-end parallelized using the Unified Parallel C language and therefore can run seamlessly on shared and distributed-memory systems. Experimental results show that MetaHipMer matches or outperforms the state-of-the-art tools in terms of accuracy. Ultimately, MetaHipMer scales efficiently to large concurrencies and is able to assemble previously intractable grand challenge metagenomes. We demonstrate the unprecedented capability of MetaHipMer by computing the first full assembly of the Twitchell Wetlands dataset, consisting of 7.5 billion reads - size 2.6 TBytes.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1990

Strategies for concurrent processing of complex algorithms in data driven architectures

The performance modeling and enhancement for periodic execution of large-grain, decision-free algorithms in data flow architectures is examined. Applications include real-time implementation of control and signal processing algorithms where performance is required to be highly predictable. The mapping of algorithms onto the specified class of data flow architectures is realized by a marked graph model called ATAMM (Algorithm To Architecture Mapping Model). Performance measures and bounds are established. Algorithm transformation techniques are identified for performance enhancement and reduction of resource (computing element) requirements. A systematic design procedure is described for generating operating conditions for predictable performance both with and without resource constraints. An ATAMM simulator is used to test and validate the performance prediction by the design procedure. Experiments on a three resource testbed provide verification of the ATAMM model and the design procedure.

Stoughton, John W.↗
NASA NTRS1990

Strategies for concurrent processing of complex algorithms in data driven architectures

Performance modeling and performance enhancement for periodic execution of large-grain, decision-free algorithms in data flow architectures are discussed. Applications include real-time implementation of control and signal processing algorithms where performance is required to be highly predictable. The mapping of algorithms onto the specified class of data flow architectures is realized by a marked graph model called algorithm to architecture mapping model (ATAMM). Performance measures and bounds are established. Algorithm transformation techniques are identified for performance enhancement and reduction of resource (computing element) requirements. A systematic design procedure is described for generating operating conditions for predictable performance both with and without resource constraints. An ATAMM simulator is used to test and validate the performance prediction by the design procedure. Experiments on a three resource testbed provide verification of the ATAMM model and the design procedure.

Som, Sukhamoy↗
DOE OSTI2011

Distributed-memory Parallel Algorithms for Matching and Coloring

Graph matching and coloring constitute two fundamental classes of combinatorial problems having numerous established as well as emerging applications in computational science and engineering, high-performance computing, and informatics. We provide a snapshot of an on-going work on the design and implementation of new highly-scalable distributed-memory parallel algorithms for two prototypical problems from these classes, edge-weighted matching and distance-1 vertex coloring. Graph algorithms in general have low concurrency and poor data locality, making it challenging to achieve scalability on massively parallel machines. We overcome this challenge by employing a variety of techniques, including approximation, speculation and iteration, optimized communication, and randomization, in concert. We present preliminary results on weak and strong scalability studies conducted on an IBM Blue Gene/P machine employing up to tens of thousands of processors. The results show that the algorithms hold strong potential for computing at petascale.

Combinatorial scientific computing↗
DOE OSTI2012

Highly Asynchronous VisitOr Queue Graph Toolkit

HAVOQGT is a C++ framework that can be used to create highly parallel graph traversal algorithms. The framework stores the graph and algorithmic data structures on external memory that is typically mapped to high performance locally attached NAND FLASH arrays. The framework supports a vertex-centered visitor programming model. The frameworkd has been used to implement breadth first search, connected components, and single source shortest path.

Pearce, R.↗
DOE OSTI2012

Highly Asynchronous VisitOr Queue Graph Toolkit

HAVOQGT is a C++ framework that can be used to create highly parallel graph traversal algorithms. The framework stores the graph and algorithmic data structures on external memory that is typically mapped to high performance locally attached NAND FLASH arrays. The framework supports a vertex-centered visitor programming model. The frameworkd has been used to implement breadth first search, connected components, and single source shortest path.

Pearce, R.↗
DOE OSTI2022

Metall: A persistent memory allocator for data-centric analytics

Data analytics applications transform raw input data into analytics-specific data structures before performing analytics. Unfortunately, such data ingestion steps are often more expensive than analytics. In addition, various types of NVRAM devices are already used in many HPC systems today. Such devices will be useful for storing and reusing data structures beyond a single process life cycle. We developed Metall, a persistent memory allocator built on top of the memory-mapped file mechanism. Metall enables applications to transparently allocate custom C++ data structures into various types of persistent memories. Metall incorporates a concise and high-performance memory management algorithm inspired by Supermalloc and the rich C++ interface developed by Boost.Interprocess library. On a dynamic graph construction workload, Metall achieved up to 11.7x and 48.3x performance improvements over Boost.Interprocess and memkind (PMEM kind), respectively. We also demonstrate Metall’s high adaptability by integrating Metall into a graph processing framework, GraphBLAS Template Library. Here this study’s outcomes indicate that Metall will be a strong tool for accelerating future large-scale data analytics by allowing applications to leverage persistent memory efficiently.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2018

Neural Networks and Graph Algorithms with Next-Generation Processors

The use of graphical processors for distributed computation revolutionized the field of high performance scientific computing. As the Moore's Law era of computing draws to a close, the development of non-Von Neumann systems: neuromorphic processing units, and quantum annealers; again are redefining new territory for computational methods. While these technologies are still in their nascent stages, we discuss their potential to advance computing in two domains: machine learning, and solving constraint satisfaction problems. Each of these processors utilize fundamentally different theoretical models of computation. This raises questions about how to best use them in the design and implementation of applications. While many processors are being developed with a specific domain target, the ubiquity of spin-glass models and neural networks provides an avenue for multi-functional applications. This provides hints at the future infrastructure needed to integrate many next-generation processing units into conventional high-performance computing systems.

Hamilton, Kathleen↗
DOE OSTI2020

A supernodal all-pairs shortest path algorithm

We show how to exploit graph sparsity in the Floyd-Warshall algorithm for the all-pairs shortest path (Apsp) problem. Floyd-Warshall is an attractive choice for Apsp on high-performing systems due to its structural similarity to solving dense linear systems and matrix multiplication. However, if sparsity of the input graph is not properly exploited, Floyd-Warshall will perform unnecessary asymptotic work and thus may not be a suitable choice for many input graphs. To overcome this limitation, the key idea in our approach is to use the known algebraic relationship between Floyd-Warshall and Gaussian elimination, and import several algorithmic techniques from sparse Cholesky factorization, namely, fill-in reducing ordering, symbolic analysis, supernodal traversal, and elimination tree parallelism. When combined, these techniques reduce computation, improve locality and enhance parallelism. We implement these ideas in an efficient shared memory parallel prototype that is orders of magnitude faster than an efficient multi-threaded baseline Floyd-Warshall that does not exploit sparsity. Our experiments suggest that the Floyd-Warshall algorithm can compete with Dijkstra's algorithm (the algorithmic core of Johnson's algorithm) for several classes sparse graphs.

Sao, Piyush↗
DOE OSTI2018

Runtime Scheduling Policies for Distributed Graph Algorithms

In this paper we explore scheduling and runtime system support for unordered distributed graph computations that rely on optimistic (speculative) execution. Performance of such algorithms is impacted by two competing trends: the higher degree of parallelism enabled by optimistic execution in turn requires substantial runtime support. To address the potentially high overhead and scheduling complexity introduced by the runtime, we investigate customizable scheduling policies that augment the scheduler of the underlying runtime to adapt it to a specific graph application. We present several implementations of Distributed Control (DC), a data-driven unordered approach with work prioritization and demonstrate that customizable scheduling policies result in the most efficient implementation, outperforming the well-known -stepping Single-Source Shortest Paths (SSSP) and Jones-Plassmann vertex-coloring algorithms. We apply two scheduling techniques, flow control and adaptive frequency of network progress, which allow application-level control over the balance of domain work and the runtime work. Experimental results show the benefit of such application-aware scheduling for irregular distributed graph algorithms.

Firoz, Jesun S.↗
NASA NTRSDate not supplied

Improvements on Low-Density Parity-Check (LDPC) Codes and High-Performance Neuromorphic Engineering for Communication Systems

Belief propagation (BP) on LDPC codes is an iterative decoding algorithm that performs information transfer on the Tanner graph, which represents the code. In each iteration, the algorithm exchanges information (LLR) between variable nodes and check nodes through the edges of the graph. LLR values represent the probability that a given bit in a transmitted codeword equals 0 or 1, given a received word. In the hardware part, recent advancements in intelligent technologies, such as artificial intelligence, big data analytics, autonomous vehicles, and speech/image recognition, have heightened the demand for faster calculations and reduced energy consumption.

Danilo Barrionuevo↗
DOE OSTI2020

Compiler and Runtime Approaches to Enable Large-Scale Irregular Programs. Final report, July 2013 - July 2019

While regular algorithms, characterized by operations on dense matrices and arrays, have long been the mainstay of scientific, high-performance computing, irregular algorithms, which feature unpredictable accesses to pointer-based data structures, are becoming increasingly common in high performance computing, arising in graph analysis, data mining and visualization, among other domains. Unfortunately, the defining characteristics of irregular applications, their dynamic, unpredictable, data-dependent access patterns and data layouts, make achieving high performance on large scale systems difficult. Scaling applications to peta- and exa-scale requires carefully controlling communication and data movement and placement, an inherently difficult task when access patterns and data layouts are unpredictable! Most irregular applications that attain high performance must be painstakingly hand-written and hand-tuned, with few common principles or paradigms uniting various implementations and easing future development. Despite the increasing importance of irregular applications, there is little programmer knowledge, and even less compiler ability, devoted to optimizing them. This project aims to solve these problems. By allowing programmers to write irregular applications in high level forms, with at most a few annotations highlighting key structural properties, programmers can focus on developing their algorithms and methods. The compiler and run-time system can take on the tedious task of optimizing the application for execution at large scales, and can automatically provide efficient implementations. This will provide portability and ease maintenance for existing irregular applications, but, more importantly, open up whole new domains of computational science to large-scale, high-performance simulation codes.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Direction-optimizing Label Propagation Framework for Structure Detection in Graphs: Design, Implementation, and Experimental Analysis

Label Propagation is not only a well-known machine learning algorithm for classification but also an effective method for discovering communities and connected components in networks. We propose a new Direction-optimizing Label Propagation Algorithm (DOLPA) framework that enhances the performance of the standard Label Propagation Algorithm (LPA), increases its scalability, and extends its versatility and application scope. As a central feature, the DOLPA framework relies on the use of frontiers and alternates between label push and label pull operations to attain high performance. It is formulated in such a way that the same basic algorithm can be used for finding communities or connected components in graphs by only changing the objective function used. Additionally, DOLPA has parameters for tuning the processing order of vertices in a graph to reduce the number of edges visited and improve the quality of solution obtained. We present the design and implementation of the enhanced algorithm as well as our shared-memory parallelization of it using OpenMP. We also present an extensive experimental evaluation of our implementations using the LFR benchmark and real-world networks drawn from various domains. Compared with an implementation of LPA for community detection available in a widely used network analysis software, we achieve at most five times the F-Score while maintaining similar runtime for graphs with overlapping communities. We also compare DOLPA against an implementation of the Louvain method for community detection using the same LFR-graphs and show that DOLPA achieves about three times the F-Score at just 10% of the runtime. For connected component decomposition, our algorithm achieves orders of magnitude speedups over the basic LP-based algorithm on large-diameter graphs, up to 13.2× speedup over the Shiloach-Vishkin algorithm, and up to 1.6× speedup over Afforest on an Intel Xeon processor using 40 threads.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2017

A Work-Efficient Parallel Sparse Matrix-Sparse Vector Multiplication Algorithm

We design and develop a work-efficient multithreaded algorithm for sparse matrix-sparse vector multiplication (SpMSpV) where the matrix, the input vector, and the output vector are all sparse. SpMSpV is an important primitive in the emerging GraphBLAS standard and is the workhorse of many graph algorithms including breadth-first search, bipartite graph matching, and maximal independent set. As thread counts increase, existing multithreaded SpMSpV algorithms can spend more time accessing the sparse matrix data structure than doing arithmetic. Our shared-memory parallel SpMSpV algorithm is work efficient in the sense that its total work is proportional to the number of arithmetic operations required. The key insight is to avoid each thread individually scan the list of matrix columns. Our algorithm is simple to implement and operates on existing column-based sparse matrix formats. It performs well on diverse matrices and vectors with heterogeneous sparsity patterns. A high-performance implementation of the algorithm attains up to 15x speedup on a 24-core Intel Ivy Bridge processor and up to 49x speedup on a 64-core Intel KNL manycore processor. In contrast to implementations of existing algorithms, the performance of our algorithm is sustained on a variety of different input types include matrices representing scale-free and high-diameter graphs.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2011

Large-Scale Continuous Subgraph Queries on Streams

Graph pattern matching involves finding exact or approximate matches for a query subgraph in a larger graph. It has been studied extensively and has strong applications in domains such as computer vision, computational biology, social networks, security and finance. The problem of exact graph pattern matching is often described in terms of subgraph isomorphism which is NP-complete. The exponential growth in streaming data from online social networks, news and video streams and the continual need for situational awareness motivates a solution for finding patterns in streaming updates. This is also the prime driver for the real-time analytics market. Development of incremental algorithms for graph pattern matching on streaming inputs to a continually evolving graph is a nascent area of research. Some of the challenges associated with this problem are the same as found in continuous query (CQ) evaluation on streaming databases. This paper reviews some of the representative work from the exhaustively researched field of CQ systems and identifies important semantics, constraints and architectural features that are also appropriate for HPC systems performing real-time graph analytics. For each of these features we present a brief discussion of the challenge encountered in the database realm, the approach to the solution and state their relevance in a high-performance, streaming graph processing framework.

99 GENERAL AND MISCELLANEOUS↗
DOE OSTI2024

Matrix-Free High-Performance Saddle-Point Solvers for High-Order Problems in \(\boldsymbol{H}(\operatorname{\textbf{div}})\)

Here, this work describes the development of matrix-free GPU-accelerated solvers for high-order finite element problems in H(div). The solvers are applicable to grad-div and Darcy problems in saddle-point formulation, and have applications in radiation diffusion and porous media flow problems, among others. Using the interpolation–histopolation basis, efficient matrix-free preconditioners can be constructed for the (1, 1)-block and Schur complement of the block system. With these approximations, block-preconditioned MINRES converges in a number of iterations that is independent of the mesh size and polynomial degree. The approximate Schur complement takes the form of an M-matrix graph Laplacian and therefore can be well-preconditioned by highly scalable algebraic multigrid methods. High-performance GPU-accelerated algorithms for all components of the solution algorithm are developed, discussed, and benchmarked. Numerical results are presented on a number of challenging test cases, including the “crooked pipe” grad-div problem, the SPE10 reservoir modeling benchmark problem, and a nonlinear radiation diffusion test case.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Scalable Knowledge Graph Analytics at 136 Petaflop/s

We are motivated by newly proposed methods for data mining large-scale corpora of scholarly publications, such as the full biomedical literature, which may consist of tens of millions of papers spanning decades of research. In this setting, analysts seek to discover how concepts relate to one another. They construct graph representations from annotated text databases and then formulate the relationship-mining problem as one of computing all-pairs shortest paths (APSP), which becomes a significant bottleneck. In this context, we present a new high-performance algorithm and implementation of the Floyd-Warshall algorithm for distributed-memory parallel computers accelerated by GPUs, which we call DSNAPSHOT (Distributed Accelerated Semiring All-Pairs Shortest Path). For our largest experiments, we ran DSNAPSHOT on a connected input graph with millions of vertices using 4, 096nodes (24,576GPUs) of the Oak Ridge National Laboratory's Summit supercomputer system. We find DSNAPSHOT achieves a sustained performance of 136×1015 floating-point operations per second (136petaflop/s) at a parallel efficiency of 90% under weak scaling and, in absolute speed, 70% of the best possible performance given our computation (in the single-precision tropical semiring or “min-plus” algebra). Looking forward, we believe this novel capability will enable the mining of scholarly knowledge corpora when embedded and integrated into artificial intelligence-driven natural language processing workflows at scale.

Kannan, Ramakrishnan {ramki}↗