<p align="center"><img src="./02_slides/fig/logo.svg" width="200" ></p>

OpenGraphSim Benchmark Suite

Graph Processing Framework with SniperSIM/GEM5/OpenMP

Overview

OpenGraphSim builds on OpenGraph by integrating it with simulators like SNIPER/GEM5. It 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 OpenGraphSim has been developed on Ubuntu 20.04, with PowerPC/Intel architecture taken into account. OpenGraphSim 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) :
    1. [Sorting the edge-list], using count-sort or radix-sort.
    2. [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.
    3. [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):
    1. [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.
    2. [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.

<!-- ## Details --> <!-- ### OpenGraphSim Supported Algorithms -->

Installation and Dependencies

CPU Mode

<img src="./02_slides/fig/openmp_logo.png" height="45" align="right" >

OpenMP

1. Judy Arrays

open@graph:~$ sudo apt-get install libjudy-dev

2. OpenMP is already a feature of the compiler, so this step is not necessary.

open@graph:~$ sudo apt-get install libomp-dev

Setting up the source code

1. Clone OpenGraphSim.

open@graph:~$ git clone https://github.com/atmughrabi/OpenGraphSim.git

2. From the home directory go to the OpenGraphSim directory:

open@graph:~$ cd OpenGraphSim/

3. Make the source code

open@graph:~OpenGraphSim$ make

Simulation Mode

Simple Trace Cache simulator

No setup needed, cache simulator is included within the code. And highlighted in the code with: (Algorithms Supported)

#ifdef CACHE_HARNESS_META
  //Simple Cache structures
#endif

• OR

#ifdef CACHE_HARNESS
  //Simple Cache function calls
#endif

<img src="./02_slides/fig/sniper_logo.png" height="80" align="right" >

The Sniper Multi-Core Simulator

Sniper simulator is needed. And highlighted in the code with: (Algorithms Supported)

#ifdef SNIPER_HARNESS
  //Sniper ROI function call
#endif

1. Obtain The Sniper Multi-Core Simulator for their website, (SniperSim).
2. Follow the steps for setting up and patching sniper to function with the correct the compiler, and ROI support.
3. Copy the sniper simulator to OpenGraphSim/00_graph_bench

open@graph:~OpenGraphSim$ mkdir -p 00_graph_bench/sniper
open@graph:~OpenGraphSim$ cp ORIGINAL_SNIPERSIM_SOURCE 00_graph_bench/sniper

4. go to 00_graph_bench/sniper and build

open@graph:~OpenGraphSim$ cd 00_graph_bench/sniper
open@graph:~OpenGraphSim/00_graph_bench/sniper$ make

5. go to the root directory to OpenGraphSim now you can run sniper with OpenGraph benchmarks

open@graph:~OpenGraphSim/00_graph_bench/sniper$ cd ../..
open@graph:~OpenGraphSim$ make run-sniper

<img src="./02_slides/fig/gem5_logo.png" height="100" align="right" >

gem5 simulator

1. Coming soon

Running OpenGraphSim

CPU Mode

<img src="./02_slides/fig/openmp_logo.png" height="45" align="right" >

Initial compilation for the Graph framework with OpenMP

1. The default compilation is openmp mode:

open@graph:~OpenGraphSim$ make

2. From the root directory you can modify the Makefile with the (parameters) you need for OpenMP:

open@graph:~OpenGraphSim$ make run

• OR

open@graph:~OpenGraphSim$ 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 |

Simulation Mode

Simple trace-driven Cache

1. From the root directory you can modify the Makefile with the (parameters) you need for trace cache:

open@graph:~OpenGraphSim$ make clean; make run-cache

2. These arguments are not passed through the Args-list you need to modify from OpenGraphSim/00_graph_bench/include/cache/cache.h :

//OpenGraphSim/00_graph_bench/src/main/open-graph.c
#ifdef CACHE_HARNESS_META
    arguments->l1_size   = L1_SIZE;
    arguments->l1_assoc  = L1_ASSOC;
    arguments->blocksize = BLOCKSIZE;
    arguments->policey   = POLICY;
#endif

<img src="./02_slides/fig/sniper_logo.png" height="80" align="right" >

The Sniper Multi-Core Simulator

1. From the root directory you can modify the Makefile with the (parameters) you need for sniper:

open@graph:~OpenGraphSim$ make clean; make run-sniper

2. Simulation results are output to OpenGraphSim/00_graph_bench/sniper-results
3. To clean simulation stats

open@graph:~OpenGraphSim$ make clean-stats

• You can pass parameters modifying Makefile parameters (easiest way) - cross reference with (SniperSim) to pass the correct values.

| PARAMETER | FUNCTION | | :--- | :--- | | SNIPER_ARGS | arguments passed to sniper simulator |

<img src="./02_slides/fig/gem5_logo.png" height="100" align="right" >

gem5 Simulator

1. Coming soon

Graph structure Input (Edge list)

• 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