Preview

Труды Института системного программирования РАН

Расширенный поиск

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

https://doi.org/10.15514/ISPRAS-2014-26(6)-5

Полный текст:

Аннотация

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

Об авторах

Игорь Бурдонов
Институт Системного Программирования РАН
Россия


Александр Косачев
Институт Системного Программирования РАН
Россия


Виктор Кулямин
Институт Системного Программирования РАН
Россия


Список литературы

1. Б. Бурдонов, А.С. Косачев, В.В. Кулямин. "Параллельные вычисления на графе"// Программирование, 2015 г., № 1, с. 3-20.

2. Кушнеренко А.Г., Лебедев Г.В. "Программирование для математиков", Наука, Главная редакция физико-математической литературы, Москва, 1988.


Для цитирования:


Бурдонов И., Косачев А., Кулямин В. Параллельные вычисления автоматами на прямом и обратном остовах графа. Труды Института системного программирования РАН. 2014;26(6):63-66. https://doi.org/10.15514/ISPRAS-2014-26(6)-5

For citation:


Burdonov I., Kossachev A., Kuliamin V. Parallel calculations by automata on direct and back spanning trees of a graph. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2014;26(6):63-66. (In Russ.) https://doi.org/10.15514/ISPRAS-2014-26(6)-5

Просмотров: 31


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


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