Distributed Graph Analytics: Programming, Languages, and Their Compilation

✍ Scribed by Unnikrishnan Cheramangalath, Rupesh Nasre, Y. N. Srikant

• Publisher: Springer
• Year: 2020
• Tongue: English
• Leaves: 213
• Category: Library

✦ Synopsis

This book brings together two important trends: graph algorithms and high-performance computing. Efficient and scalable execution of graph processing applications in data or network analysis requires innovations at multiple levels: algorithms, associated data structures, their implementation and tuning to a particular hardware. Further, programming languages and the associated compilers play a crucial role when it comes to automating efficient code generation for various architectures. This book discusses the essentials of all these aspects.

The book is divided into three parts: programming, languages, and their compilation. The first part examines the manual parallelization of graph algorithms, revealing various parallelization patterns encountered, especially when dealing with graphs. The second part uses these patterns to provide language constructs that allow a graph algorithm to be specified. Programmers can work with these language constructs without worrying about their implementation, which is the focus of the third part. Implementation is handled by a compiler, which can specialize code generation for a backend device. The book also includes suggestive results on different platforms, which illustrate and justify the theory and practice covered. Together, the three parts provide the essential ingredients for creating a high-performance graph application. The book ends with a section on future directions, which offers several pointers to promising topics for future research.

This book is intended for new researchers as well as graduate and advanced undergraduate students. Most of the chapters can be read independently by those familiar with the basics of parallel programming and graph algorithms. However, to make the material more accessible, the book includes a brief background on elementary graph algorithms, parallel computing and GPUs. Moreover it presents a case study using Falcon, a domain-specific language for graph algorithms, to illustrate the concepts.

✦ Table of Contents

Preface
Contents
1 Introduction to Graph Analytics
1.1 What Is Graph Analytics?
1.2 Graph Preliminaries
1.3 Graph Storage Formats
1.3.1 Adjacency Matrix
1.3.2 Compressed Sparse Row
1.3.3 Incidence Matrix
1.3.4 Other Formats
1.4 Graph Partitioning Strategies
1.5 Heterogeneous Distributed Systems
1.6 Programming Libraries and APIs
1.6.1 OpenMP
1.6.2 CUDA
1.6.3 OpenCL
1.6.4 Thrust
1.6.5 MPI
1.7 Graph Analytics in Real-World Applications
1.8 Graph Analytics Challenges
1.8.1 Classification of Graphs
1.8.2 Irregular Computation
1.8.3 Heterogeneous Hardware
1.8.4 Distributed Execution
1.8.5 Atomic Operations and Synchronization
1.8.6 Challenges in Programming
1.9 Programming Abstractions for Graph Analytics
1.9.1 Frameworks
1.9.1.1 Bulk Synchronous Parallel (BSP) Model
1.9.1.2 Asynchronous Execution Model
1.9.1.3 Gather-Apply-Scatter (GAS) Model
1.9.2 Domain Specific Languages
2 Graph Algorithms and Applications
2.1 Introduction
2.2 Fundamental Graph Algorithms
2.2.1 Breadth-First Search (BFS)
2.2.2 Depth-First Search
2.2.3 Single Source Shortest Path (SSSP)
2.2.4 All Pairs Shortest Path Computation (APSP)
2.2.5 Strongly Connected Components (SCC)
2.2.6 Weakly Connected Components (WCC)
2.2.7 Minimum Spanning Tree (MST)
2.2.8 Maximal Independent Set (MIS) Computation
2.3 Other Algorithms
2.3.1 Pagerank Algorithm
2.3.2 Triangle Counting
2.3.3 Graph Coloring
2.3.4 K-Core
2.3.5 Betweenness Centrality (BC)
2.4 Applications of Graph Analytics in Different Domains
2.4.1 Graph Mining
2.4.1.1 Graph Mining in Bioinformatics
2.4.2 Graph Databases (NoSQL)
2.4.3 Text Graphs in Natural Language Processing
3 Efficient Parallel Implementation of Graph Algorithms
3.1 Introduction
3.2 Issues in Programming Parallel Graph Algorithms
3.2.1 Parallelism
3.2.2 Atomicity
3.2.3 An Example
3.2.4 Graph Topology and Classification
3.2.5 Push vs. Pull Computation
3.2.6 Topology Driven vs. Data Driven
3.2.6.1 A Simple Topology-Driven Breadth-First Search Algorithm
3.2.6.2 A Simple Data-Driven Breadth-First Search Computation
3.3 Different Ways of Solving a Problem
3.3.1 Vertex-Based SSSP Computation
3.3.2 Worklist-Based SSSP Computation
3.3.3 Edge-Based SSSP Computation
3.3.4 -Stepping SSSP
3.4 A Note on Efficient Parallel Implementations of Graph Algorithms
3.5 Some Important Parallel Graph Algorithms
3.5.1 Parallel Computation of Maximal Independent Sets
3.5.2 Parallel Computation of Strongly Connected Components
3.5.3 Parallel Computation of Connected Components
3.5.4 Parallel Computation of Betweenness Centrality (BC)
3.5.5 Parallel Union-Find and Applications
3.5.5.1 Concurrent Disjoint Set Union and Find Algorithms
3.5.5.2 Finding Connected Components in Parallel Using Union-Find
3.5.5.3 Parallel MST Computation with Boruvka's Algorithm
3.6 Graph Analytics on Distributed Systems
3.6.1 Distributed System with CPUs
3.6.2 Distributed System with CPUs and GPUs
3.6.3 Multi-GPU Machine
4 Graph Analytics Frameworks
4.1 Introduction
4.2 Frameworks—Merits and Demerits
4.3 Models for Graph Analytics
4.3.1 Bulk Synchronous Parallel (BSP)
4.3.1.1 Pregel
4.3.1.2 GPS
4.3.1.3 Pregelix
4.3.1.4 Ligra
4.3.1.5 Apache Giraph and Apache Hama
4.3.1.6 Totem
4.3.2 Map-Reduce
4.3.3 Asynchronous Execution
4.3.4 External Memory Frameworks
4.3.5 Gather-Apply-Scatter Model
4.3.6 Inspector-Executor
4.3.7 Advance-Filter-Compute
4.4 Frameworks for Single Machines
4.4.1 Multi-Core CPU
4.4.2 Single GPU
4.4.2.1 IrGL
4.4.2.2 Lonestar-GPU
4.4.2.3 MapGraph
4.4.2.4 Other Frameworks
4.4.3 Multi GPU
4.4.3.1 Medusa
4.4.3.2 Lux
4.5 Frameworks for Distributed Systems
4.5.1 Distributed System with CPU
4.5.2 Distributed System with CPU and GPU
5 GPU Architecture and Programming Challenges
5.1 Introduction
5.2 Graphics Processing Unit (GPU)
5.2.1 GPU Architecture
5.2.2 Multi-GPU Machine
5.2.3 Distributed GPU Systems
5.3 General Purpose Computing on GPU (GPGPU)
5.3.1 CUDA Programming
5.3.2 GPU Thread Scheduling
5.3.3 Warp Based Execution
5.3.4 Memory Hierarchy
5.4 Graph Analytics on GPU
5.4.1 Topology Driven Algorithms
5.4.2 Other Elementary Graph Algorithms
6 Dynamic Graph Algorithms
6.1 Introduction
6.2 Dynamic Algorithms for Elementary Graph Problems
6.3 Dynamic Shortest Path Computation
6.3.1 Incremental Dynamic SDSP Computation
6.3.1.1 Example for Incremental SDSP Computation
6.3.2 Decremental Dynamic SDSP Computation
6.3.2.1 Example for Decremental SDSP Computation
6.4 Computational Geometry Algorithms
6.4.1 Delaunay Triangulation (DT)
6.4.2 Delaunay Mesh Refinement (DMR)
6.4.3 Parallel Delaunay Mesh Refinement (DMR)
6.5 Challenges in Implementing Dynamic Algorithms
6.5.1 Dynamic Memory Management
6.5.2 Parallel Computation
7 Falcon: A Domain Specific Language for Graph Analytics
7.1 Introduction
7.2 Overview
7.2.1 SSSP Program in Falcon
7.3 Falcon Data Types
7.4 Falcon API
7.5 Constructs for Parallel Execution and Synchronization
7.5.1 section and parallel sections Statements
7.6 Code Generation—Single Machine
7.6.1 Compilation of Data Types
7.6.2 Extra Property Memory Allocation
7.6.3 Compilation of foreach Statement
7.6.4 Data Transfer Between CPU and GPU
7.6.5 Compiling single Statement
7.6.6 Compiling Parallel Sections
7.6.7 Handling Reduction Operations
7.7 Falcon for Distributed Systems
7.7.1 Storage of Subgraphs in Falcon
7.7.2 Initialization Code
7.7.3 Allocation and Synchronization of Global Variables
7.7.4 Distributed Communication and Synchronization
7.7.5 Code Generation for Set and Collection Data Types
7.7.6 Code Generation for Parallel and Synchronization Statements
7.7.6.1 single Statement
7.7.7 foreach Statement
8 Experiments, Evaluation and Future Directions
8.1 Introduction
8.2 Single Machine Experiments
8.2.1 Random and R-MAT Graphs
8.2.2 Road Network Graphs
8.2.3 Connected Components and MST
8.2.4 Summary
8.3 Distributed Systems
8.3.1 Multi-GPU
8.3.2 GPU Cluster
8.3.3 CPU Cluster
8.3.4 CPU + CPU Cluster
8.3.5 Results
8.4 Future Directions in Distributed Graph Analytics
8.4.1 Custom Graph Processing
8.4.2 Adaptive Graph Partitioning and Processing
8.4.3 Hardware for Graph Processing
8.4.4 Handling Dynamic Updates
8.4.5 Performance Modeling
8.4.6 Learning to Aid Graph Processing
References
Index