Параллельные вычисления автоматами на прямом и обратном остовах графа

Аннотация

В статье представлен алгоритм параллельного вычисления произвольной функции от мультимножества значений, находящихся в вершинах графа. Вычисления выполняются автоматами, размещенными в вершинах графа и обменивающихся сообщениями по дугам графа. В основе алгоритма лежит использование информации о структуре графа, извлеченной в результате параллельного исследования графа и представляющей собой прямой и обратный остовы графа. Для хранения этой информации требуется конечное число бит в каждой вершине графа. Вычисление значения той или иной функции основано на алгоритме пульсации: сначала от автомата начальной вершины по всему графу распространяются сообщения-вопросы, которые должны достигнуть каждой вершины, а затем от каждой вершины «в обратную сторону» к начальной вершине двигаются сообщения-ответы. Алгоритм пульсации, по сути, вычисляет агрегатные функции, для которых значение функции от объединения мультимножеств вычисляется по значениям функции от этих мультимножеств. Показано, что любая функция f(x) имеет агрегатное расширение, то есть может быть вычислена как h(f`(x)), где f` агрегатная функция.