OpenGraph is an open source graph processing framework, designed as a modular benchmarking suite for graph processing algorithms. It provides an end to end evaluation infrastructure which includes the preprocessing stage (forming the graph structure) and the graph algorithm. The OpenMP part of OpenGraph has been developed on Ubuntu 20.04.1, with PowerPC/Intel architecture taken into account. OpenGraph is coded using C giving the researcher full flexibility with modifying data structures and other algorithmic optimizations.
- Presentations that explains end-to-end graph processing (implementation is inspired from these sources)
- Preprocessing two steps (third one is optional) :
- [Sorting the edge-list], using count-sort or radix-sort.
- [Building the graph structure]. CSR, Gird, Adjacency-Linked-List, and Adjacency-Array-List.
- Ref: Xiaowei Zhu, Wentao Han and Wenguang Chen. GridGraph: Large-Scale Graph Processing on a Single Machine Using 2-Level Hierarchical Partitioning. Proceedings of the 2015 USENIX Annual Technical Conference, pages 375-386.
- Ref: Malicevic, Jasmina, Baptiste Lepers, and Willy Zwaenepoel. "Everything you always wanted to know about multicore graph processing but were afraid to ask." 2017 USENIX Annual Technical Conference. Proceedings of the 2015 USENIX Annual Technical Conference, pages 375-386.
- [Relabeling the graph], this step achieves better cache locality (better performance) with preprocessing overhead.
- Ref: J. Arai, H. Shiokawa, T. Yamamuro, M. Onizuka, and S. Iwamura. Rabbit Order: Just-in-time Parallel Reordering for Fast Graph Analysis. IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2016.
- Ref:P. Faldu and J. Diamond and B. Grot, "A Closer Look at Lightweight Graph Reordering," in Proceedings of the International Symposium on Workload Characterization (IISWC), November 2019.
- Graph Algorithm step depends on the direction of the data (Push/Pull):
- [BFS example], although it doesn't show direction optimized. But we discusses the Push and Pull approach separately.
- [Ref]: Scott Beamer, Krste Asanović, David Patterson. The GAP Benchmark Suite. arXiv:1508.03619 [cs.DC], 2015.
- [Page-Rank (PR) example]: Discussing PR cache behavior.
- Ref: J. Arai, H. Shiokawa, T. Yamamuro, M. Onizuka, and S. Iwamura. Rabbit Order: Just-in-time Parallel Reordering for Fast Graph Analysis. IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2016.
- [BFS example], although it doesn't show direction optimized. But we discusses the Push and Pull approach separately.
- Preprocessing two steps (third one is optional) :
- Judy Arrays
open@graph:~$ sudo apt-get install libjudy-dev
- OpenMP is already a feature of the compiler, so this step is not necessary.
open@graph:~$ sudo apt-get install libomp-dev
- Clone OpenGraph.
open@graph:~$ git clone https://github.com/atmughrabi/OpenGraph.git
- From the home directory go to the OpenGraph directory:
open@graph:~$ cd OpenGraph/
- Make the source code
open@graph:~OpenGraph$ make
- The default compilation is
openmp
mode:
open@graph:~OpenGraph$ make
- From the root directory you can modify the Makefile with the (parameters) you need for OpenMP:
open@graph:~OpenGraph$ make run
- OR
open@graph:~OpenGraph$ make run-openmp
- You can pass parameters modifying
Makefile
parameters (easiest way) - cross reference with (parameters) to pass the correct values.
PARAMETER | FUNCTION |
---|---|
ARGS | arguments passed to open-graph |
PARAMETER | FUNCTION |
---|---|
Graph Files Directory | |
FILE_BIN | graph edge-list location |
FILE_LABEL | graph edge-list reorder list |
PARAMETER | FUNCTION |
---|---|
Graph Structures PreProcessing | |
SORT_TYPE | graph edge-list sort (count/radix) |
DATA_STRUCTURES | CSR,GRID,LinkedList,ArrayList |
REORDER_LAYER1 | Reorder graph for cache optimization |
PARAMETER | FUNCTION |
---|---|
Algorithms General | |
ALGORITHMS | BFS, PR, DFS, etc |
PULL_PUSH | Direction push,pull,hybrid |
PARAMETER | FUNCTION |
---|---|
Algorithms Specific | |
ROOT | source node for BFS, etc |
TOLERANCE | PR tolerance for convergence |
NUM_ITERATIONS | PR iterations or convergence |
DELTA | SSSP delta step |
PARAMETER | FUNCTION |
---|---|
General Performance | |
NUM_THREADS_PRE | number of threads for the preprocess step (graph sorting, generation) |
NUM_THREADS_ALGO | number of threads for the algorithm step (BFS,PR, etc) |
NUM_THREADS_KER | (Optional) number of threads for the algorithm kernel (BFS,PR, etc) |
NUM_TRIALS | number of trials for the same algorithms |
- If you open the Makefile you will see the convention for graph directories :
BENCHMARKS_DIR/GRAPH_NAME/graph.wbin
. .bin
stands to unweighted edge list,.wbin
stands for wighted,In binary format
. (This is only a convention you don't have to use it)- The reason behind converting the edge-list from text to binary, it is simply takes less space on the drive for large graphs, and easier to use with the
mmap
function.
Source | Dest | Weight (Optional) |
---|---|---|
30 | 3 | 1 |
3 | 4 | 1 |
- Example:
- INPUT: (unweighted textual edge-list)
- ../BENCHMARKS_DIR/GRAPH_NAME/graph
30 3
3 4
25 5
25 7
6 3
4 2
6 12
6 8
6 11
8 22
9 27
- convert to binary format and add random weights, for this example all the weights are
1
. --graph-file-format
is the type of graph you are reading,--convert-format
is the type of format you are converting to.- NOTE: you can read the file from text format without the convert step. By adding
--graph-file-format 0
to the argument list. The default is1
assuming it is binary. please check--help
for better explanation. --stats
is a flag that enables conversion. It used also for collecting stats about the graph (but this feature is on hold for now).- (unweighted graph)
open@graph:~OpenGraph/00_graph_bench$ make convert
- OR (weighted graph)
open@graph:~OpenGraph/00_graph_bench$ make convert-w
- OR (weighted graph)
open@graph:~OpenGraph/00_graph_bench$ ./bin/open-graph-openmp --generate-weights --stats --graph-file-format=0 --convert-format=1 --graph-file=../BENCHMARKS_DIR/GRAPH_NAME/graph
Makefile
parameters
PARAMETER | FUNCTION |
---|---|
File Formats | |
FILE_FORMAT | the type of graph read |
CONVERT_FORMAT | the type of graph converted |
- OUTPUT: (weighted binary edge-list)
- ../BENCHMARKS_DIR/GRAPH_NAME/graph.wbin
1e00 0000 0300 0000 0100 0000 0300 0000
0400 0000 0100 0000 1900 0000 0500 0000
0100 0000 1900 0000 0700 0000 0100 0000
0600 0000 0300 0000 0100 0000 0400 0000
0200 0000 0100 0000 0600 0000 0c00 0000
0100 0000 0600 0000 0800 0000 0100 0000
0600 0000 0b00 0000 0100 0000 0800 0000
1600 0000 0100 0000 0900 0000 1b00 0000
0100 0000
OpenGraph can handle multiple representations of the graph structure in memory, each has their own theoretical benefits and shortcomings.
Usage: open-graph-openmp [OPTION...]
-f <graph file> -d [data structure] -a [algorithm] -r [root] -n
[num threads] [-h -c -s -w]
OpenGraph is an open source graph processing framework, it is designed to be a
benchmarking suite for various graph processing algorithms using pure C.
-a, --algorithm=[DEFAULT:[0]-BFS]
[0]-BFS,
[1]-Page-rank,
[2]-SSSP-DeltaStepping,
[3]-SSSP-BellmanFord,
[4]-DFS,
[5]-SPMV,
[6]-Connected-Components,
[7]-Betweenness-Centrality,
[8]-Triangle Counting,
[9-BUGGY]-IncrementalAggregation.
-b, --delta=[DEFAULT:1]
SSSP Delta value [Default:1].
-c, --convert-format=[DEFAULT:[1]-binary-edgeList]
[serialize flag must be on --serialize to write]
Serialize graph text format (edge list format) to
binary graph file on load example:-f <graph file>
-c this is specifically useful if you have Graph
CSR/Grid structure and want to save in a binary
file format to skip the preprocessing step for
future runs.
[0]-text-edgeList,
[1]-binary-edgeList,
[2]-graphCSR-binary.
-C, --cache-size=<LLC>
LLC cache size for MASK vertex reodering
-d, --data-structure=[DEFAULT:[0]-CSR]
[0]-CSR,
[1]-Grid,
[2]-Adj LinkedList,
[3]-Adj ArrayList
[4-5] same order bitmap frontiers.
-e, --tolerance=[EPSILON:0.0001]
Tolerance value of for page rank
[default:0.0001].
-f, --graph-file=<FILE>
Edge list represents the graph binary format to
run the algorithm textual format change
graph-file-format.
-F, --labels-file=<FILE>
Read and reorder vertex labels from a text file,
Specify the file name for the new graph reorder,
generated from Gorder, Rabbit-order, etc.
-g, --bin-size=[SIZE:512]
You bin vertices's histogram according to this
parameter, if you have a large graph you want to
illustrate.
-i, --num-iterations=[DEFAULT:20]
Number of iterations for page rank to converge
[default:20] SSSP-BellmanFord [default:V-1].
-j, --verbosity=[DEFAULT:[0:no stats output]
For now it controls the output of .perf file and
PageRank .stats (needs --stats enabled)
filesPageRank .stat [1:top-k results] [2:top-k
results and top-k ranked vertices listed.
-k, --remove-duplicate
Removers duplicate edges and self loops from the
graph.
-K, --Kernel-num-threads=[DEFAULT:algo-num-threads]
Number of threads for graph processing kernel
(critical-path) (graph algorithm)
-l, --light-reorder-l1=[DEFAULT:[0]-no-reordering]
Relabels the graph for better cache performance
(first layer).
[0]-no-reordering,
[1]-out-degree,
[2]-in-degree,
[3]-(in+out)-degree,
[4]-DBG-out,
[5]-DBG-in,
[6]-HUBSort-out,
[7]-HUBSort-in,
[8]-HUBCluster-out,
[9]-HUBCluster-in,
[10]-(random)-degree,
[11]-LoadFromFile (used for Rabbit order).
-L, --light-reorder-l2=[DEFAULT:[0]-no-reordering]
Relabels the graph for better cache performance
(second layer).
[0]-no-reordering,
[1]-out-degree,
[2]-in-degree,
[3]-(in+out)-degree,
[4]-DBG-out,
[5]-DBG-in,
[6]-HUBSort-out,
[7]-HUBSort-in,
[8]-HUBCluster-out,
[9]-HUBCluster-in,
[10]-(random)-degree,
[11]-LoadFromFile (used for Rabbit order).
-O, --light-reorder-l3=[DEFAULT:[0]-no-reordering]
Relabels the graph for better cache performance
(third layer).
[0]-no-reordering,
[1]-out-degree,
[2]-in-degree,
[3]-(in+out)-degree,
[4]-DBG-out,
[5]-DBG-in,
[6]-HUBSort-out,
[7]-HUBSort-in,
[8]-HUBCluster-out,
[9]-HUBCluster-in,
[10]-(random)-degree,
[11]-LoadFromFile (used for Rabbit order).
-M, --mask-mode=[DEFAULT:[0:disabled]]
Encodes [0:disabled] the last two bits of
[1:out-degree]-Edgelist-labels
[2:in-degree]-Edgelist-labels or
[3:out-degree]-vertex-property-data
[4:in-degree]-vertex-property-data with hot/cold
hints [11:HOT]|[10:WARM]|[01:LUKEWARM]|[00:COLD]
to specialize caching. The algorithm needs to
support value unmask to work.
-n, --pre-num-threads=[DEFAULT:MAX]
Number of threads for preprocessing (graph
structure) step
-N, --algo-num-threads=[DEFAULT:MAX]
Number of threads for graph processing (graph
algorithm)
-o, --sort=[DEFAULT:[0]-radix-src]
[0]-radix-src,
[1]-radix-src-dest,
[2]-count-src,
[3]-count-src-dst.
-p, --direction=[DEFAULT:[0]-PULL]
[0]-PULL,
[1]-PUSH,
[2]-HYBRID.
NOTE: Please consult the function switch table for each
algorithm.
-r, --root=[DEFAULT:0]
BFS, DFS, SSSP root
-s, --symmetrize
Symmetric graph, create a set of incoming edges.
-S, --stats
Write algorithm stats to file. same directory as
the graph.PageRank: Dumps top-k ranks matching
using QPR similarity metrics.
-t, --num-trials=[DEFAULT:[1 Trial]]
Number of trials for whole run (graph algorithm
run) [default:1].
-w, --generate-weights
Load or Generate weights. Check ->graphConfig.h
#define WEIGHTED 1 beforehand then recompile using
this option.
-x, --serialize
Enable file conversion/serialization use with
--convert-format.
-z, --graph-file-format=[DEFAULT:[1]-binary-edgeList]
Specify file format to be read, is it textual edge
list, or a binary file edge list. This is
specifically useful if you have Graph CSR/Grid
structure already saved in a binary file format to
skip the preprocessing step.
[0]-text edgeList,
[1]-binary edgeList,
[2]-graphCSR binary.
-?, --help Give this help list
--usage Give a short usage message
-V, --version Print program version
-
00_graph_bench
include
- Major function headersgraphalgorithms
- supported Graph algorithmsopenmp
- OpenMP integrationBFS.h
- Breadth First SearchDFS.h
- Depth First SearchSSSP.h
- Single Source Shortest PathbellmanFord.h
- Single Source Shortest Path using Bellman FordincrementalAgreggation.h
- Incremental Aggregation for clusteringpageRank.h
- Page Rank AlgorithmSPMV.h
- Sparse Matrix Vector Multiplication
preprocessing
- preprocessing graph structurecountsort.h
- sort edge list using count sortradixsort.h
- sort edge list using radix sortreorder.h
- cluster reorder the graph for better cache localitysortRun.h
- chose which sorting algorithm to use
structures
- structures that hold the graph in memorygraphAdjArrayList.h
- graph using adjacency list array with arraysgraphAdjLinkeList.h
- graph using adjacency list array with linked listsgraphCSR.h
- graph using compressed sparse matrixgraphGrid.h
- graph using Grid
src
- Major function Source filesgraphalgorithms
- supported Graph algorithmsopenmp
- OpenMP integrationBFS.c
- Breadth First SearchDFS.c
- Depth First SearchSSSP.c
- Single Source Shortest PathbellmanFord.c
- Single Source Shortest Path using Bellman FordincrementalAgreggation.c
- Incremental Aggregation for clusteringpageRank.c
- Page Rank AlgorithmSPMV.c
- Sparse Matrix Vector Multiplication
preprocessing
- preprocessing graph structurecountsort.c
- sort edge list using count sortradixsort.c
- sort edge list using radix sortreorder.c
- cluster reorder the graph for better cache localitysortRun.c
- chose which sorting algorithm to use
structures
- structures that hold the graph in memorygraphAdjArrayList.c
- graph using adjacency list array with arraysgraphAdjLinkeList.c
- graph using adjacency list array with linked listsgraphCSR.c
- graph using compressed sparse matrixgraphGrid.c
- graph using Grid
-
Makefile
- Global makefile
- Finish preprocessing sort
- Radix sort
- Count sort
- Bitonic sort
- Finish preprocessing Graph Data-structures
- CSR (Compressed Sparse Row)
- Grid
- Adjacency Linked List
- Adjacency Array List
- Add Light weight reordering
- Finish graph algorithms suite OpenMP
- BFS (Breadth First Search)
- PR (Page-Rank)
- DFS (Depth First Search)
- IA (Incremental Aggregation) BUGGY*
- SSSP (BellmanFord)
- SSSP (Delta Stepping)
- SPMV (Sparse Matrix Vector Multiplication)
- CC (Connected Components)
- TC (Triangle Counting)
- BC (Betweenness Centrality)
- Support testing
Report bugs to: