Параллельные вычисления на динамически меняющемся графе

Рассматривается задача параллельного вычисления значения функции от мультимножества значений, записанных в вершинах ориентированного сильно-связного графа. Вычисление выполняется автоматами, находящимися в вершинах графа. Автомат имеет локальную информацию о графе: он «знает» только о дугах, выходящих из вершины, в которой он находится, но «не знает», куда (в какие вершины) эти дуги ведут. Автоматы обмениваются сообщениями, передаваемыми по дугам графа, которые играют роль каналов передачи сообщений. Вычисление инициируется сообщением, приходящим извне в автомат выделенной начальной вершины графа. Этот же автомат в конце работы посылает вовне вычисленное значение функции. Для решения этой задачи предлагаются два алгоритма. Первый алгоритм выполняет исследование графа, целью которого является разметка графа с помощью изменения состояний автоматов в вершинах. Такая разметка используется вторым алгоритмом, который и производит вычисление значения той или иной функции. Это вычисление основано на алгоритме пульсации: сначала от автомата начальной вершины по всему графу распространяются сообщения-вопросы , которые должны достигнуть каждой вершины, а затем от каждой вершины «в обратную сторону» к начальной вершине двигаются сообщения-ответы . Алгоритм пульсации, по сути, вычисляет агрегатные функции, для которых значение функции от объединения мультимножеств вычисляется по значениям функции от этих мультимножеств. Однако показано, что любая функция F(x) имеет агрегатное расширение, то есть может быть вычислена как H(G(x)) , где G агрегатная функция. Заметим, что разметка графа не зависит от той функции, которая будет вычисляться. Это означает, что разметка графа выполняется один раз, после чего может многократно использоваться для вычисления различных функций. Поскольку автоматы в вершинах графа работают параллельно, как разметка графа, так и вычисление функции выполняются параллельно. Это первая особенность работы. Вторая особенность - вычисления выполняются на динамически меняющемся графе: его дуги могут исчезать, появляться или менять свои конечные вершины. На изменения графа налагаются такие минимальные ограничения, которые позволяют решать эту задачу за ограниченное время. Приводится оценка времени работы обоих предлагаемых алгоритмов.

ориентированные графы, исследование графа, взаимодействующие автоматы, параллельная работа, агрегатные функции, динамически меняющиеся графы, ориентированные графы, исследование графа, взаимодействующие автоматы, параллельная работа, агрегатные функции, динамически меняющиеся графы

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

2. И. Бурдонов, А. Косачев. Мониторинг динамически меняющегося графа. Труды Института системного программирования РАН Том 27. Выпуск 1. 2015 г. Стр. 69-96. ISSN 2220-6426 (Online), ISSN 2079-8156 (Print). DOI: 10.15514/ISPRAS-2015-27(1)-5

3. Steven S. Skiena. The Algorithm Design Manual. Springer-Verlag, New York, 1997.

4. И.Б. Бурдонов, А.С. Косачев, В.В. Кулямин. Неизбыточные алгоритмы обхода ориентированных графов. Детерминированный случай. Программирование, 2003 г., №5, с. 59-69.

5. И.Б. Бурдонов, А.С. Косачев, В.В. Кулямин. Неизбыточные алгоритмы обхода ориентированных графов. Недетерминированный случай. Программирование, 2004 г., №1, с. 2-17.

6. M.O. Rabin. Maze Threading Automata. An unpublished lecture presented at MIT and UC. Berkeley, 1967.

7. И.Б. Бурдонов. Обход неизвестного ориентированного графа конечным роботом. Программирование, 2004 г., № 4, с. 11-34.

8. И.Б. Бурдонов. Проблема отката по дереву при обходе неизвестного ориентированного графа конечным роботом. Программирование, 2004 г., № 6, с. 6-29.

9. Бурдонов И.Б., Косачев А.С. Обход неизвестного графа коллективом автоматов. Труды ИСП РАН. Том 26-2, 2014 г., стр. 43-86.

10. Бурдонов И.Б., Косачев А.С., Кулямин В.В. Исследование графа набором автоматов. Программирование, 2015, №6, (в печати).

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