Parallel calculations by automata on direct and back spanning trees of a graph.

Parallel calculations by automata on direct and back spanning trees of a graph.

Авторы

Burdonov, A. Kossachev, V. Kuliamin.

Аннотация

The paper presents a parallel computation algorithm of an arbitrary function value on a multiset of values distributed on directed graph vertices. The computation is performed by message passing executed by automata distributed on the graph vertices. The key idea of the algorithm is to use a structural information on the graph that can be extracted by its parallel exploration and encoded into structures of direct and back spanning trees of the graph, which require only finite number of bits in each graph vertex, and to represent the function calculated as a composition of so called aggregate function and another one. Aggregate functions are characterized by possibility to calculate their value on a union of multisets by aggregating their values on separate multisets, that makes them easy for parallel computation.

Ключевые слова

parallel computation; directed graphs; group of automata; graph spanning tree.

Издание

French-Russian Seminar on Software Verification, Testing, and Quality Estimation, Paris, France, November 24-25, 2014.

Научная группа

Технологии программирования

Все публикации за 2014 год

Все публикации