Social Network Analysis Algorithms on GPU

A command-line GPU-accelerated application for computing the most important centrality metrics of sparse graphs that represent social networks.

Currently, only undirected and unweighted graphs are supported. For unconnected graphs only the largest connected component is extracted and analyzed. Self-loops are disallowed by default, but they can be enabled. Duplicated edges are not expected and won’t be removed.

Installation

Prerequisites

These are the dependencies needed to build the project:

• A compiler for C and C++ must be installed;

• CUDA Toolkit must be installed;

• CMake 3.9+;

• The Snap library is used for benchmarking GPU algorithms with an optimized parallel CPU implementation of the Betweenness Centrality algorithm. A script for downloading, building and installing it under lib/ is available in the script/ directory.

• The Boost Graph Library is used for generating random graphs.

⚠️	During the development of the project only GCC 10.3.0 and CUDA Toolkit 11.2 on Ubuntu 18.04 has been tested.

Compilation

First clone this repo and enter it:

git clone https://github.com/Da3dalu2/SocNetAlgsOnGPU.git
cd SocNetAlgsOnGPU

To build this project (not test, nor the SNAP algorithm for benchmarking) with GNU Make:

cd src
make

To build this project with CMake:

mkdir build-release && cd build-release
cmake .. -DCMAKE_BUILD_TYPE=Release

Optionally the symbol -DCMAKE_CUDA_ARCHITECTURES=x can be specified to compile for a specific architecture.

⚠️	Only GPUs with at least compute capability 6.x are supported because atomics with double precision have been used.

If the project is built with cmake, binary source file are available in build/src directory. Binary test files are available in build/test directory. All tests can be run by typing ctest in the build/test directory.

ℹ️	There are two build types available, Release and Debug. Release builds with optimization flags enabled (-O3) and Debug uses both debug symbols (-g) and -Wall -Werror -Wpedantic.

Generating Datasets

All dataset-related code is under the dataset subdirectory. Only Matrix-market coordinate-formatted graph format is supported.

A program for generating random graphs is given, dataset/graph_gen. Instructions for compiling it are given in the file.

To download them just type make in the dataset subdirectory. To only download one specific dataset step into its subdirectory and type make there.

Included libraries

There are three libraries included in the project:

• mmio for parsing Matrix Market files;

• the doctest header file for writing unit tests of C++ code;

• zf_log C library for logging.

Usage

 ./sna_bc [-i|--input file] [-t|--technique] [-b|--dump-scores file]
          [-s|--dump-stats file] [-v|--verbose] [-c|--check]
          [-wsl|--wself-loops] [-d|--device] [-q|--quiet]
          [-u|--usage] ][-h|--help]

Some examples:

• Compute centrality metrics (Betweeness Centrality, Closeness Centrality and Degree) of the collaboration network ca-GrQc using the Vertex Parallel technique for computing the BC.

 ./sna_bc -i ../../dataset/ca-GrQc/ca-GrQc.mtx -t 1

• Compute centrality metrics of a random Small World graph using the Edge Parallel technique for computing the BC, allowing self-loops and dumping the computed scores in a .csv file called scores. Then run a serial CPU algorithm and check if the result of the CPU and GPU algorithms are the same.

 ./sna_bc -i ../../dataset/synthetic/rnd-sw.mtx -t 2 -p -b "scores" -c

• Compute centrality metrics of a graph representing the power grid of the USA using the Work Efficient technique, appending statistics like runtime and MTEPS to a .csv file called stats. In addition, show output from the logger and use a (Nvidia) GPU with device id equal to 1.

 ./sna_bc -i ../../dataset/USpowerGrid/USpowerGrid.mtx -t 3 -s "stats" -v -d 1

Hardware

The GPU used during the development of this project is a Quadro P620 with four Streaming Multiprocessors, a base clock of 2505 Mhz, two GB of GDDR5 memory and compute capability of 6.1 (Pascal architecture).

Performance Analysis

• Speedup, among different techniques for the GPU’s algorithms and between GPU and CPU.

• Runtime, measured in ms. For the GPU’s algorithms this includes memory transfer times and computation time.

For GPU’s algorithms only:

• Throughput, in terms of MTEPS (Million Traversed Edges Per Second).