Associative version of the Ramalingam incremental algorithm for the dynamic single-source reachability problem

The paper provides a parallel implementation of the Ramalingam sequential algorithm for dynamically processing a graph with a single source after inserting a new arc. For this purpose, a model of associative (content-addressable) processors of the SIMD type with vertical data processing is used. The study of associative data processing began in the 60s. But studying the associative processing has never taken off, because only a limited amount of memory could be placed on a single die. However, progress in the computer industry and semiconductor technology in recent years has made the associative processing attractive again. Such an architecture best suits for solving problems of non-numeric data processing. In particular, this includes relational algebra, graph theory, seismic data processing. The main advantages of this architecture include data parallelism at the basic level, the use of twodimensional tables as a data structure, and a massively parallel search by content. To model of vertical processing systems the STAR-machine is used. The work of STAR-machine is given by the language STAR. This language contains a group of elementary operations for processing of bit columns, as well as a library of standard procedures for efficient processing of matrix data. Every associative algorithm is represented as a procedure written in the language STAR. Since common associative architecture does not exist yet, there is a problem of the efficient implementing the STAR-machine on real appropriate SIMD architecture. Therefore, the STAR machine was efficiently implemented on graphics accelerators. The Ramalingam algorithm receives as input the graph G, the set of reachable vertices from the source s, the dynamic spanning tree T, and the arc (u, v) inserted to the graph. After performing the Ramalingam algorithm the tree T is updated to the spanning tree on the updated set of reachable vertices. At the beginning, the Ramalingam sequential algorithm adds a new arc (u, v) to graph G. If the vertex u is reachable in the graph G and the vertex v is unreachable, then the arc (u, v) is added to the tree T and the vertex v becomes reachable. After that, all arcs outdoing from vertex v are added to the set Work Sets of processed arcs. Then each arc from this set is updated by analogy with the described method. To implement the Ramalingam algorithm on the STAR-machine, a special data structure is built, that allows one to access data by content. With a parallel implementation of this algorithm, the set of WorkSets was represented as a bit column. At each current iteration, the unreachable vertices entering the processing vertex are included into the Workset. These vertices become reachable, and the corresponding arcs are simultaneously added to the tree T. Note that in the sequential algorithm, the set WorkSet stores a set of processed arcs. While in the associative version, the slice WorkSet stores only unreachable vertices entering the processing vertex. The correctness of this associative version was proved. Using the implementation of the STAR-machine on the GPU, this algorithm was tested on the NVIDIA GEFORCE 920m on graphs with various numbers of reachable vertices (total number of vertices up to 5000, number of arcs up to 90,000). Test results show that the associative dynamic algorithm runs up to ten times faster than the static associative algorithm. Moreover, it performs significantly less iterations than the sequential dynamic algorithm.

Keywords

Authors

References