Труды Института системного программирования РАН (Oct 2018)
Parallel Calculations on Dynamic Graph
Abstract
The problem of parallel computation of the value of a function of multiset of values recorded at the vertices of a directed strongly connected graph is considered. Computation is performed by automata that are located at the graph vertices. The automaton has local information on the graph: it "knows" only about arcs outgoing from the vertex it resides in, but it "does not know" where (to which vertices) those arcs go. The automata exchange messages with each other that are transmitted along the graph arcs that play role of message transfer channels. Computation is initiated by a message coming from outside to the automaton located at the initial vertex of the graph. At the end of work, this automaton sends outside the calculated function value. Two algorithms are proposed to solve this problem. The first algorithm carries out an analysis of the graph. Its purpose is to mark the graph by a change of the states of the automata at the vertices. Such marking is used by the second algorithm, which calculates the function value. This calculation is based on a pulsation algorithm: first, request messages are distributed from the automaton of the initial vertex over the graph, which should reach each vertex, and then response messages are sent from each vertex back to the initial vertex. In fact, the pulsation algorithm calculates aggregate functions for which the value of a function of a union of multisets is calculated by the values of the function of these multisets. However, it is shown that any function F(x) has an aggregate extension; that is, an aggregate function can be calculated as H(G(x)), where G is an aggregate function. Note that the marking of a graph does not depend on a function that will be calculated. This means that the marking of a graph is carried out once; after that, it can be reused for calculating various functions. Since the automata located in different vertices of the graph work in parallel, both graph marking and function calculation are performed in parallel. It is the first feature of this work. The second feature is that calculations are performed on a dynamically changing graph: its arcs can disappear, reappear or change their target vertices. The constraints put on the graph changes are as minimal as it allows solving this problem in limited time. Estimate of working time is given for both algorithms.
Keywords
