STAR Project - Investigation of associative parallel algorithms of updating trees

The project is devoted to design a group of associative parallel algorithms for solving optimization graph problems. Our model of computation (the STAR-machine) simulates the run of associative (content addressable) parallel systems with vertical processing and single--bit processing elements. Such an architecture performs data parallelism at the base level, provides massively parallel search by contents, and allows one using two-dimensional tables as basic data structures.

Dynamic graph algorithms are designed to handle graph changes. They maintain some property of a changing graph more efficiently than recomputation of the entire graph with a static algorithm after every change.

For undirected graphs, we are planning to work out a group of new associative parallel algorithms for dynamic update of a minimum spanning tree (MST). This group includes reconstructing a new MST from the current MST after insertion of an edge or a vertex and all its incident edges in a given graph or after deletion of an edge or a vertex and its incident edges from a graph.

For directed graphs, we are planning to design a group of associative parallel algorithms for dynamic update of a tree of the shortest paths after performing the above-mentioned changes in a graph.

Moreover, we are planning to build an associative version of Dijkstra's algorithm that determines for every vertex of a directed graph the shortest path along with the distance from the source vertex.

We hope to obtain efficient and elegant associative parallel algorithms due to the use of natural and simple data structures, execution of parallel search by contents, and the use of new constructions for updating tree paths. The corresponding procedures will be implemented on the STAR-machine.

This progect was supported by the Russian Foundation for Basic Research under Grant 03--01--00399.

Participants

Head of project: Anna Nepomiaschaya
Developer: Borets T. V.