Distributed Graph Analytics: Programming, Languages, and Their Compilation

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