I recently went to ISC16 for their Student Cluster Competition, and one of the challenges was to create our “own implementation of Graph500 to run on a cluster.”

If you don’t know about the Student Cluster Competition, they are cluster competitions where student teams work with vendors to create a cluster and optimize high performance scientific applications to be run under 3000 watts of power on real datasets.

Graph500 is a rating of supercomputer systems focused on data intensive loads. There are two main kernels.

The first kernel constructs an undirected graph. The second kernel performs breadth-first search of the graph. Both kernels are timed.

There are a bunch of other nitty-gritty requirements outlined in their full specifications page.

The Graph500 reference code and implementations only contain sequential, OpenMP, XMT, and MPI versions.

The original developers have provided CPU implementations, but where’s the CUDA version? No one wants to put their awesome versions of Graph500 open source!

 

Existing Open Source CUDA Graph500

While searching to find Graph500 on CUDA, we found only one open source version provided by the Suzumura Laboratory.

The Suzumura Laboratory has done a great contribution to the open source community on Graph500 with their papers, “Parallel Distributed Breadth First Search on GPU” and “Highly Scalable Graph Search for the Graph500 Benchmark” written by Koji Ueno and Toyotaro Suzumura.

Their version was created on June 2012.

First thing that we wanted our Graph500 to be was open source.

The HPC Advisory Council states that “Other implementations of Graph500 exist and likely to improve performance, however not freely obtainable.”

graph500-implementations

 

Our version of Graph500 on CUDA with MPI

We made a much simpler model for Graph500 that you may want to check for understanding the Graph500 specifications easier. We created ours on June 2016.

https://github.com/buhpc/isc16-graph500

We’ll be updating this post to explain how we created our version of Graph500 on a later day, but we hope that our source code will help you run Graph500 on your cluster with NVIDIA GPUs or create a version yourselves!

 

Testing our version of Graph500

We will test our version of Graph500 on a single NVIDIA Jetson TX1. Below are the NVIDIA Jetson TX1 specifications:

nvidia-jetson-tx1-specifications

The prequisite for running our version of Graph500 is having CUDA. Our NVIDIA Jetson TX1 already had CUDA and OpenMPI installed when we set up Ubuntu 14.04. To check if you have CUDA setup, run:

nvcc --version
nvcc: NVIDIA (R) Cuda compiler driver
Copyright (c) 2005-2015 NVIDIA Corporation
Built on Thu_May__5_22:52:38_CDT_2016
Cuda compilation tools, release 7.0, V7.0.74

To check if you have MPI setup, run:

mpirun --version
mpirun (Open MPI) 1.6.5

Report bugs to http://www.open-mpi.org/community/help/

If you don’t have CUDA or MPI, you will need to Google how to do it for your respective operating system. Now, we have to install git to download our source code.

sudo apt-get install git -y

After you install git, you can git clone our repository.

git clone https://github.com/buhpc/isc16-graph500
cd isc16-graph500/

Make any changes to the Makefile to fit your location of CUDA.

vim Makefile

I have to make a small change to the LDFLAGS value. lib should be lib64 for me.

Original:

CC=mpicxx
FLAGS=-std=c++11
INCLUDE= -Iinclude -I/usr/local/cuda/include
LDFLAGS=-L/usr/local/cuda/lib
LIB=-lcudart
EXE=main
NVCC=nvcc
Q=@

New:

CC=mpicxx
FLAGS=-std=c++11
INCLUDE= -Iinclude -I/usr/local/cuda/include
LDFLAGS=-L/usr/local/cuda/lib64
LIB=-lcudart
EXE=main
NVCC=nvcc
Q=@
make
CXX src/constructGraph.cpp
CXX src/graph.cpp
CXX src/edgeList.cpp
CXX src/init.cpp
CXX src/breadthFirstSearch.cpp
CXX src/main.cpp
CXX src/generateKey.cpp
CXX src/validation.cpp
NVCC src/buildAdjMatrix.cu
NVCC src/bfsStep.cu
CXX main

The Graph500 binary created is called main.

[USAGE] ./main <config.ini> <scale> <edgefactor>

N
the total number of vertices, 2^SCALE.

M
the number of edges. M = edgefactor * N.

We will use main with mpirun and keep track of runtime with the time command. You may supply a hostfile. Check run.sh for a sample command to run the program.

In this example, we’ll use a SCALE of 6 and edgefactor of 1 for a result of 64 vertices and 64 edges. But first, how many cores we can use?

grep -c ^processor /proc/cpuinfo
4

Now, we will run Graph500 on a single node with a very small graph.

time mpirun -n 4 ./main config.ini 6 1
Constructing graph...
Done.

Running 64 BFSs...
Got 24291.5 TEPS
Got 29580.9 TEPS
Got 60708.3 TEPS
Got 35433.1 TEPS
Got 62827.2 TEPS
Got 36697.2 TEPS
Got 54054.1 TEPS
Got 51428.6 TEPS
Got 53892.2 TEPS
Got 38461.5 TEPS
Got 53491.8 TEPS
Got 54298.6 TEPS
Got 42452.8 TEPS
Got 41142.9 TEPS
Got 54628.2 TEPS
Got 32727.3 TEPS
Got 54711.2 TEPS
Got 35928.1 TEPS
Got 62827.2 TEPS
Got 39955.6 TEPS
Got 63492.1 TEPS
Got 36108.3 TEPS
Got 58919.8 TEPS
Got 70588.2 TEPS
Got 42007 TEPS
Got 34515.8 TEPS
Got 54380.7 TEPS
Got 36659.9 TEPS
Got 58631.9 TEPS
Got 63492.1 TEPS
Got 53973 TEPS
Got 53491.8 TEPS
Got 69632.5 TEPS
Got 41237.1 TEPS
Got 60200.7 TEPS
Got 36363.6 TEPS
Got 62283.7 TEPS
Got 42402.8 TEPS
Got 48913 TEPS
Got 40000 TEPS
Got 69632.5 TEPS
Got 42755.3 TEPS
Got 61120.5 TEPS
Got 40678 TEPS
Got 48192.8 TEPS
Got 37228.5 TEPS
Got 55900.6 TEPS
Got 46272.5 TEPS
Got 3831.42 TEPS
Got 41618.5 TEPS
Got 60301.5 TEPS
Got 40540.5 TEPS
Got 70312.5 TEPS
Got 42553.2 TEPS
Got 48979.6 TEPS
Got 49792.5 TEPS
Got 53175.8 TEPS
Got 53254.4 TEPS
Got 63380.3 TEPS
Got 2178.65 TEPS
Got 59308.1 TEPS
Done.

real 0m0.752s
user 0m1.000s
sys 0m0.680s

We measure TEPS, traversed edges per second. Let m be the number of input edge tuples within the component traversed by the search, counting any multiple edges and self-loops. Let timeK2(n) be the measured execution time for kernel 2.

TEPS(n) = m / timeK2(n)

Let us know if you have any questions. Feel free to fork our repository and improve our Graph500 code! Our output may not be exactly the same as the official Graph500 implementation, but it does fit the specifications as far as we know.