Associative parallel algorithm for dynamic update of shortest paths tree after inserting an arc | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2019. № 46. DOI: 10.17223/20710410/46/5

The paper proposes an associative parallel algorithm for dynamic update of the shortest paths tree after inserting an arc into a directed weighted graph. First we shortly recall the STAR-machine that simulates the functioning of associative parallel processors. The associative parallel algorithm is given as a procedure InsertArcSPT, correctness of which is proved. Now we give a short description of the associative incremental algorithm. Let the arc (i, j ) be added to the graph G. Then we check whether the shortest distance from the root to the vertex j decreases if the shortest path to the vertex j includes the arc (i, j ). If this is true, then the vertex j becomes affected and the new shortest distance to this vertex is written in the matrix of the shortest distances. Then we replace the previous arc in the tree with the arc (i, j ). After that, we calculate the distance to those vertexes v for which there is an arc (j, v ). Then the all vertexes the distances to which decrease become affected. After that, the new distances are written in the corresponding rows of the shortest distance matrix. Moreover the corresponding arcs are included in the shortest paths tree. We have shown that the time complexity of this procedure is O(hk), while the time complexity of a static associative version of Dijkstra algorithm is O(hn). Here h is the number of bits for coding the maximum of the shortest paths length, n is the number of all graph vertexes and k is the number of affected vertexes for which the new distances are computed. This procedure was tested on the NVIDIA GEFORCE 920M using the implementation of STAR-machine on the GPU. Performance was evaluated on R-MAT graphs which simulate real graphs from social networks and the Internet. Graphs were generated by the GraphHPC-1.0 package with the following parameters: the number of vertexes is defined by a power of two (from 11 to 13), the average degree of vertexes connectivity is 32. We use two modes: zero weighting arcs are added (pessimistic mode) and arcs with random weight are added (realistic mode). In the experiments, we take into account as the runtime of the procedure and the number of affected vertexes. For each test, ≈ 10% n runs were performed. After that, the runs were distributed by the number of affected vertexes. The shortest paths and distances do not change in most runs (more than 50 % in the case of the pessimistic mode and more than 88 % in the case of the realistic mode). In 99 % cases, the number of affected vertexes does not exceed 5 in the first mode and 2 in the second mode. Note that the associative algorithm traverses the graph along the vertexes (outgoing arcs are processed in parallel). While in the sequential version, the graph is traversed along arcs, and the number of arcs that need to be checked can go up to 2000 and 100 accordingly. Also we note that in average the dynamic version runs about 500 times faster in the pessimistic mode and about 1000 times faster in the realistic mode than the static parallel version of Dijkstra's algorithm.