Associative parallel algorithm for dynamic update of~shortest paths tree after inserting an arc

A. Sh. Nepomniaschaya ; T. V. Snytnikova

Prikladnaâ diskretnaâ matematika, no. 4 (2019), pp. 58-71.

Résumé

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, $ \approx 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.

Détail

Keywords: oriented weighted graph, adjacency matrix, affected vertex, vertical data processing, associative parallel processor.
Mots-clés : incremental algorithm

Bibliographie

[1] Fet Y. I., “Vertical processing systems: a survey”, IEEE Micro, 15:1 (1995), 65–75 | DOI

[2] Potter J. L., Associative Computing: a Programming Paradigm for Massively Parallel Computers, Perseus Publishing, Boston, 1991, 304 pp.

[3] Nepomniaschaya A. Sh., “Language STAR for associative and parallel computation with vertical data processing”, Parallel Computing Technologies, World Scientific, Singapore, 1991, 258–265

[4] Nepomniaschaya A. Sh., “Basic associative parallel algorithms for vertical processing systems”, Bulletin of the Novosibirsk Computing Center. Ser. Comp. Sci., 2009, no. 9, 63–77 | Zbl

[5] Foster C. C., Content Addressable Parallel Processors, John Wiley Sons, N.Y., 1976, 233 pp.

[6] Nepomniaschaya A. Sh., Dvoskina M. A., “A simple implementation of Dijkstra's shortest path algorithm on associative parallel processors”, Fundamenta Informaticae, 43, IOS Press, 2000, 227–243 | DOI | MR

[7] Nepomniaschaya A. S., “Solution of path problems using associative parallel processors”, Proc. ICPADS'97, IEEE Computer Society Press, Seoul, 1997, 610–617

[8] Nepomniaschaya A. S., “Comparison of performing the Prim–Dijkstra algorithm and the Kruskal algorithm by means of associative parallel processors”, Cybernetics and System Analysis, 2000, no. 2, 19–27

[9] Nepomniaschaya A. S., “Associative version of the Ramalingam algorithm for the dynamic update of the shortest paths subgraph after inserting a new edge”, Cybernetics and System Analysis, 2012, no. 3, 45–57

[10] Nepomniaschaya A. S., “Efficient parallel implementation of the Ramalingam decremental algorithm for updating the shortest paths subgraph”, Computing and Informatics, 32 (2013), 331–354 | MR | Zbl

[11] Nepomniaschaya A. S., “Associative version of the Ramalingam decremental algorithm for the dynamic all-pairs shortest-path problem”, Bulletin of the Novosibirsk Computing Center. Ser. Comp. Sci., 2016, no. 39, 37–50 | Zbl

[12] Nepomniaschaya A. S., “Associative version of the Ramalingam incremental algorithm for the dynamic all-pairs shortest-path problem”, Bulletin of the Novosibirsk Computing Center. Ser. Comp. Sci., 2016, no. 40, 75–86

[13] Nepomniaschaya A. S., “Associative parallel algorithm for dynamic update shortest paths tree”, Modeling and Analysis of Information Systems, 20:2 (2013), 5–22 (in Russian)

[14] Mirenkov N. N., “The Siberian approach for an open-system high-performance computing architecture”, Computing and Control Engineering J., 3:3 (1992), 137–142 | DOI

[15] Nepomniaschaya A. S., Vladyko M. A., “A comparison of associative computation models”, Programming and Computer Software, 1997, no. 6, 319–324 | Zbl

[16] Snytnikova T. V., Nepomniaschaya A. Sh., “Solution of graph problems by means of the STAR-machine being implemented on GPUs”, Prikladnaya Diskretnaya Matematika, 2016, no. 3(33), 98–115 (in Russian) | MR

[17] Snytnikova T. V., Snytnikov A. V., “Implementation of the STAR-machine on GPU”, Bulletin of the Novosibirsk Computing Center. Ser. Comp. Sci., 2016, no. 39, 51–60

[18] Snytnikova T. V., “Realizatsiya modeli assotsiativnyh vychisleniy na GPU: biblioteka bazovyh protsedur yazyka STAR [Implementation of an associative-computing model on GPU: a basic procedure library of the STAR language”, Numerical Methods and Programming. Advanced Computing, 19:1 (2018), 85–95 (in Russian)

[19] GraphHPC-1.0, , 2018 http://www.dislab.org/GraphHPC-2018/contest/GraphHPC-1.0.tgz