README
Provided is the code for BFS, PR, SSSP, SpMV and WCC using different data layouts and compute variations.
This code was designed to evaluate existing techniques. Therefore, some files are reused from existing systems. More specifically: transpose_ligra, parallel_ligra, radixSort_ligra, utils_ligra from Ligra. Bitmap from Gemini .
The driver of the program is random.c. Pre-processing code is located in init_all.c. Files starting with algorithm names implement different variations of the same algorithm, used to evaluate programming techniques.
To compile the code you need compiler support for Cilk Plus. The code is then compiled simply by running make .
The input file is a binary edge array of the for [src][dst]. If the edges have weights, the –w flag needs to be added on running the program and the WEIGHTED constant changed to 1 in random.h . If the algorithm requires weights and the input file does not have them, random weights are generated by setting CREATE_FLAG to 1 in random.h.
To run the code you need to call the corresponding algorithm binary with a number of required options:
./algorithm_binary –n #_of_vertices –m load_mode –f path_to_graph [optional parameters].
When not running the NUMA-aware version, it is recommended to use numactl --interlave=all before the command line to improve performance.
To change the number of threads running, it is necessary to edit the constants ALGO_NB_THREADS and CONCURRENCY_THREADS in random.h.
The graph can be represented as:
- An edge array
- Adjacency lists
- 2D grid
The way these data layouts are created can be varied: Using a radix sort, a dynamic allocation and reallocation on load or count sort. The implementation of all of these options is in init_all.c. The data layout can be selected by setting the load_mode flag.
If the algorithm needs to be run an undirected graph, pass the –u flag when running the algorithm. If the graph is already undirected and the algorithm requires creating incoming adjacency lists, passing –s 1 will disable this.
The additional pre-processing step needed to place data in a NUMA-Aware manner is implemented in the actual files that run the algorithms with NUMA-Awareness: pr_numa and bfs_numa. The expected data layout is an adjacency list.
Most files contain the currently pushed data layouts for the algorithm except BFS and PR over a grid which are stored in separate files (bfsgrid, prgrid).