ExaGraph: Combinatorial Methods for Enabling Exascale Applications.
Abstract not provided.
Halappanavar, Mahantesh↗
Engineering topics
Halappanavar, Mahantesh
Publications and source records attributed to Halappanavar, Mahantesh.
Mapping Arbitrarily Sparse Two-body Interactions on One-dimensional Quantum Circuits
We consider an assignment problem arising in Fermionic-swap based mapping of the one-body and two-body interaction terms in simulating time evolution of a sparse second-quantized electronic structure Hamiltonian on a quantum computer. Relative efficiency of different swap networks depends on the relative costs of performing a swap layer and computing a Hamiltonian interaction term. Under the assumption that the interaction term cost dominates the computation, we develop an iterative algorithm that uses hypergraph optimal linear arrangement (HOLA) and partial distance-2 coloring to exploit arbitrary sparsity in the Hamiltonian for efficient computation using swap networks. Using a set of 122 problems from computational chemistry, we demonstrate performance improvements up to 100% relative to the state-of-the-art approaches for one-body terms and up to 86% utilization for two-body terms relative to a theoretical peak utilization. To the best of our knowledge, this is the first study to exploit arbitrary sparsity in orbital interactions for efficient computation on one-dimensional qubit connectivity layouts. The proposed algorithms form the basis for extension to map general k-body interactions that arise in other domains onto generalized qubit connectivity layouts.
quantum computing, Combinatorial Optimization, hyp↗
Identification of Critical Airports from the Perspective of Delay and Disruption Propagation in Air Travel Networks
It is well-known that delays and disruptions that originate at certain airports end up spreading spread on the network to other airports, sometimes straining a large fraction of the system. Hence data-driven modeling of this phenomenon is important from the standpoint of planning and strategy. In this work, utilizing the publicly available data from the Federal Aviation Administration (FAA), we employ the well-known influence maximization paradigm, to mine for the top airports in the US airport network, from the perspective of delay spread. In the process, we develop a diffusion simulator and implement a greedy algorithm to aid our task. We then explore the temporal trends by considering one winter month and one summer month in our analysis. Finally, we characterize the clusters in the US airport network and investigate the patterns of delay spread when airports in each of the clusters are affected.
Visweswara Sathanur, Arun↗
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↗
Scaling and Quality of Modularity Optimization Methods for Graph Clustering
Real-world graphs exhibit structures known as “communities” or “clusters” consisting of a group of vertices with relatively high connectivity between them, as compared to the rest of the vertices in the network. Graph clustering or community detection is a fundamental graph operation used to analyze real-world graphs occurring in the areas of computational biology, cybersecurity, electrical grids, etc. Similar to other graph algorithms, owing to irregular memory accesses and inherently sequential nature, current algorithms for community detection are challenging to parallelize. However, in order to analyze large networks, it is important to develop scalable parallel implementations of graph clustering that are capable of exploiting the architectural features of modern supercomputers. In response to the 2019 Streaming Graph Challenge, we present quality and performance analysis of our distributed- memory community detection using Vite, which is our distributed memory implementation of the popular Louvain method, on the ALCF Theta supercomputer. Clustering methods such as Louvain that rely on modularity maximization are known to suffer from the resolution limit problem, preventing identification of clusters of certain sizes. Hence, we also include quality analysis of our shared-memory implementation of the Fast-tracking Resistance method, in comparison with Louvain on the challenge datasets. Furthermore, we introduce an edge-balanced graph distribution for our distributed memory implementation, that significantly reduces communication, offering up to 80% improvement in the overall execution time. In addition to performance/quality analysis, we also include details on the power/energy consumption, and memory traffic of the distributed-memory clustering implementation using real-world graphs with over a billion edges.
Ghosh, Sayan↗
Fast and Scalable Implementations of Influence Maximization Algorithms
The Influence Maximization problem has been extensively studied in the past decade because of its practical applications in finding the key influencers in social networks. Due to the hardness of the underlying problem, existing algorithms have tried to trade off practical efficiency with approximation guarantees. However, even such approximate solutions take several hours of compute time on modest sized real world inputs. On the other hand, there is a lack of effective parallel and distributed algorithms to solve this problem. In this paper, we present efficient parallel algorithms for multithreaded and distributed systems to solve the influence maximization with approximation guarantee. Our algorithms extend state-of-the-art sequential approach based on computing reverse reachability sets. We present a detailed experimental evaluation, and analyze their performance and their sensitivity to input parameters, using real world inputs. Our experimental results demonstrate significant speedup on parallel architectures. We further show a speedup of up to 586X relative to the state-of-the-art sequential baseline using 1024 nodes of a supercomputer at far greater accuracy and twice the seed set size. To the best of our knowledge, this is the first effort in parallelizing the influence maximization operation at scale.
Minutoli, Marco↗
Exa-Graph/vite
MPI+OpenMP implementation of Louvain method for Graph Community Detection, with a number of parallel heuristics/approximate computing techniques Also called "CuVite"
Ghosh, Sayan↗
Exploring MPI Communication Models for Graph Applications Using Graph Matching as a Case Study
Traditional implementations of parallel graph operations on distributed memory platforms are written using Message Passing Interface (MPI) point to point communication primitives such as Send-Recv (blocking and nonblocking). Apart from this classical model, the MPI community has over the years added other communication models; however, their suitability for handling the irregular traffic workloads typical of graph operations remain comparatively less explored. Our aim in this paper is to study these relatively underutilized communication models of MPI for graph applications. More specifically, we evaluate MPI’s one-sided programming, or Remote Memory Access (RMA), and nearest neighborhood collectives using a process graph topology. There are features in these newer models that are intended to better map to irregular communication patterns, as exemplified in graph algorithms. As a concrete application for our case study, we use distributed memory implementations of a weighted graph matching algorithm to investigate performances of MPI-3 RMA and neighborhood collective operations compared to nonblocking Send- Recv. A matching in a graph is a subset of edges such that no two matched edges are incident on the same vertex. A maximum weight matching is a matching of maximum weight computed as the sum of the weights of matched edges. Algorithms for optimal matching have quadratic complexity and are difficult to parallelize. More importantly, execution of graph matching is dominated by high volume of irregular memory accesses, making it an ideal candidate for studying the effects of various MPI communication models on graph applications at scale. Our neighborhood collectives and RMA implementations yields up to 6× speedup over traditional optimized nonblocking Send-Recv implementations, on thousands of cores of the NERSC Cori supercomputer. We believe the lessons learned from this case study can be adopted to benefit a wider range of graph application codes.
Ghosh, Sayan↗