-stepping is an algorithm for solving single source shortest path problem. It is very e cient on a large class of graphs, providing nearly linear time complexity in sequential implementation, and can be parallelized. However, this algorithm requires some tuning and has unpredictable performance behaviour on systems with di erent parallel architectures. In this paper we describe details of implementation of this algorithm on CPU and GPU. Performing numerous tests we studied scalability of algorithms on CPU and GPU and compared performance for di erent parameter. We show that performance results for CPU and GPU varies for di erent delta. Also, we noticed that GPU performance are stable for some di erent delta values. Our result shows how to choose for achieving best performance for tested graphs.
SSSP has a lot of e cient solutions. Most of the algorithms are derived either from Dijkstra's algorithm or from
Bellman-Ford algorithm. General Dijkstra's algorithm implementation can achieve O(n log n + m) time
complexity and Bellman-Ford algorithm runs in O(nm) time. Some PRAM algorithms process vertices subsequently
in Dijkstra's order, preforming edge relaxation in parallel [
-stepping algorithm exposes both Dijkstra's and Bellman-Ford algorithms ideas. Let d be a maximum vertex
degree in graph and L = maxv2V dist(v). It is provable [
The basic algorithm pseudocode is represented in Algorithm 1 [
B[ dist[w] ] B[ dist[w] ] n fwg
B[ x ] [ fwg
x
Initially distance to the source vertex is 0 and distance to any other vertex is +1. This algorithm requires maintaining structure of vertices called bucket. Considering B as array of buckets, each bucket B[i] stores set fv 2 V : v is queued and dist(v) 2 [i ; (i + 1) )g as one-dimensional array. With cyclic reusing of buckets jBj can be set to maxe2E d!(e)= e + 1.
On each iteration algorithm nds rst nonempty bucket B[i] and processes it in inner loop. It is looking for all light edges (e 2 E : !(e) ), that are outgoing from vertices in bucket B[i]. Then all vertices are removed from that bucket, but collected in set R for further processing. After that, relaxation of previously found light edges is performed. It is important, that some vertices may be reinserted in this bucket after relaxation due to improvement of their current distance. When current bucket B[i] remains empty after inner loop, all weights for vertices fv : dist(v) 2 [i ; (i + 1) )g have been nally computed. Then all heavy edges (e 2 E : !(e) > ), outgoing from every vertex that was removed from processed bucket and gathered in R, are relaxed. All process above is repeated until all buckets are empty. 3
The main interest of this study is a parallel implementation of algorithm. There are a few e cient ways of providing parallel version of -stepping algorithm. Although CPU and GPU implementations will di er in some way, they expose same ideas.
It has to be mentioned that in this paper was considered not an optimal parallel version of algorithm, yet very simple one, that is easy to analyze and implement.
Parallelization strategy is clearly straightforward: some set of vertices assigned for processing by one thread. All threads run in parallel. Hence, procedures like searching for all light or heavy edges outgoing from set of vertices (lines 9, 13) also performs in parallel.
Maintaining buckets structure, algorithm has to be able to concurrently determine whether each vertex belongs to any bucket, and return the index of bucket, that vertex belongs to, if it does. It can be implemented using two arrays. First one stores an index of bucket for each vertex in it, or -1 if vertex does not belong to any bucket. Second array stores size of each bucket.
Also, described strategy allows to relax found edges (lines 12, 14) in parallel. 3.1
CPU implementation has restriction in number of threads running in parallel. So for that case all vertices are evenly distributed into chunks so that each thread has to process its own chunk. For instance, if p threads are available, all vertices are put into p chunks of size n=p. In this study this division is done automatically using OpenMP pragmas for lines 9{11, 12, 13, 14.
On every iteration of inner loop (lines 8{12) each thread for each vertex in its chunk subsequently checks if vertex belongs to current bucket and moves it to set R if it does, adding relaxation requests for light edges of this vertex. Then it moves to the next vertex. In next parallel OpenMP block each thread relaxes light edges requests for each vertex in its chunk that occurs in request.
When bucket remains empty, two OpenMP blocks of code process set R, creating relaxation requests for heavy edges, outgoing from vertices in that set, and performing that relaxation. 3.2
For GPU implementation CUDA technology was used. Parallelization strategy is to assign to each CUDA thread a vertex from graph.
This speci c implementation uses four di erent CUDA kernels for lines 9-11, 12, 13, 14. Each of them is being called with number of threads equal to number of vertices in graph, performing parallel processing, described above, for each vertex. However, edge relaxation is performed subsequently for each vertex.
Thus, on every iteration of inner loop each thread in rst CUDA kernel checks if its vertex belongs to current bucket. If vertex belongs, thread creates corresponding relaxation-request for light edges and moves vertex to set R. In next CUDA kernel each thread performs subsequent relaxation of previously created requests.
Finally, third kernel creates requests for heavy edges for all vertex in set R, and last kernel relaxes that requests. 4 4.1
For performing benchmarks R-MAT graphs [
Let us denote that graph has scale n if it has 2n vertices. In performed benchmarks R-MAT graphs with scale 17 to 23 and average vertex degree 32 were used. Weights of edges are double precision oating point numbers uniformly distributed in range [0; 1].
Graphs were packed in CSR (compressed sparse row) data structure for achieving better memory e ciency while keeping constant time access to any vertex's adjacency list. 4.2
All test were performed on single node of cluster of Institute of Mathematics and Computer Science in Ural Federal University with following con guration:
CPU: Intel Xeon E5-2620 v2 @ 2.10 GHz, 12 cores, 32 GB of RAM,
GPU: Nvidia Tesla K20Xm, 2688 CUDA Cores @ 732 MHz, 6 GB of memory.
All benchmarks code was written in C99. CPU versions were parallelized via OpenMP standard, GPU versions were written in CUDA 7.0. Compilers used: gcc 4.8.5, nvcc 7.0.27. 4.3
It is reasonable to rstly compare performance of most popular algorithms: Dijkstra's and Bellman-Ford with performance of -stepping algorithm.
These tests were performed on CPU. We separately compared sequential implementations of all three algorithms and parallel implementations of Bellman-Ford and -stepping algorithms along with sequential Dijkstra's algorithm. Figure 1 shows resulting performance of algorithms in millions of traversed edges per second (MTEPS). For that comparison parameter was 0.04125.
-stepping outperforms other algorithms in both sequential version and parallel one. This result corresponds asymptotic of these algorithms. Moreover, -stepping does not degrade on larger graphs as Bellman-Ford algorithm does due to some cache e ciency. On each iteration Bellman-Ford algorithm has to relax all edges, so it has to do a lot of memory operations. -stepping algorithm allows processor to keep some buckets in cache so it can access vertices in them and their outgoing edges very fast, keeping high performance. 4.4
-stepping performance on CPU and GPU Performance results are based on 128 launches of algorithm for every graph and then taking a mean MTEPS value. Source vertex was randomly chosen each time. Also, for the sake of clarity of dependency on parameter time of moving data to and from GPU was not included in total time of nding problem solution. That means that results in real-life case might be signi cantly lower. However, trend will be the same. (a) Sequential implementations (b) Parallel implementations (a) CPU performance
(b) GPU performance
CPU results seem to t theoretical research in [
GPU performance results need more analysis to nd out its cause. Firstly, it is clear that on relatively small graphs (scale 18), device can not achieve enough occupancy performing parallel processing of small number of vertices and edges, and therefore providing bad performance. On larger graph there are enough vertices to fully utilize device, which yields best performance, comparing to even bigger graphs, on which algorithm degrades due to graph scaling.
Quite topical question is analysis of dependency on parameter. Seems like any 0:5 provides good performance for no reason, because algorithm behaves di erently on = 1 and = 0:5.
The point is that with relatively low (0.5 in that case) algorithm behaves in optimal way, but average vertex
degree in graph is quite small, so all parallel work is done for not large enough set of vertices simultaneously
to achieve good occupancy on the device. Small vertex degree provides poor scaling. With higher parameter
algorithm treats more edges as light (and with 1 all of them). That means that -stepping algorithm behaves
more like Bellman-Ford algorithm, providing good parallelization level, but doing a lot of work. However, with
small mean vertex degree and relatively high it is possible to get higher level of device occupancy while doing
parallel work, providing better performance. By researching graphs with higher vertex degree parameter can
be chosen closer to theoretical best one [
It is reasonable to choose = mn [8]. For R-MAT, however, equation 1=d = mn takes place. Taking = 1=32 in our case results to worse performance than = 0:1 and especially = 0:5.
-stepping algorithm performance depends on parameter because con guring this parameter may solve
trade o between a lot of phase number and too much work on each phase [
This study presents results of one approach of -stepping parallelization and comparison of performance with di erent parameters. We show that optimal parameter for R-MAT graphs with mean vertex degree 32 is between 0.04 and 0.05 for CPU. Optimal parameter for GPU implementation on same graphs is 0.5 and may become smaller using graphs with higher vertex degree.
This result is quite case-speci c due to some restrictions, yet is interesting to analyse and extrapolate on other similar cases.
Further research may be focused on determining best performance algorithm setup on di erent systems.
-stepping: a parallelizable shortest path algortihm. Journal of Algorithms,