Сборники трудов ИСП РАН


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

Игорь Бурдонов, Александр Косачев, Виктор Кулямин.

Аннотация

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

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

параллельные вычисления; ориентированный граф; коллектив автоматов; остов

Издание

Труды Института системного программирования РАН, том 26, вып. 6, 2014, стр. 63-66.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2014-26(6)-5

Полный текст статьи в формате pdf (на английском) Вернуться к содержанию тома