Параллельные вычисления на графе.
Параллельные вычисления на графе.
Авторы
Аннотация
Рассматривается задача параллельного вычисления значения функции от мультимножества значений, записанных в вершинах ориентированного сильно-связного графа. Вычисление выполняется автоматами, находящимися в вершинах графа и обменивающихся между собой сообщениями, передаваемыми по дугам графа (в направлении их ориентации). Предполагается, что ёмкость дуги, то есть число одновременно передаваемых по ней сообщений, ограничена. Вычисление инициируется сообщением, приходящим извне в автомат выделенной начальной вершины графа. Этот же автомат в конце работы посылает вовне вычисленное значение функции. Для решения этой задачи предлагаются два алгоритма. Первый алгоритм выполняет исследование графа, основанное на его обходе. Его цель – разметить граф с помощью изменения состояний автоматов в вершинах. Строятся прямой и обратный остовы графа. Прямой остов ориентирован от корня, которым является начальная вершина графа. Обратный остов ориентирован к тому же корню. Кроме того, в каждой вершине устанавливается значение счётчика входящих дуг обратного остова. Такая разметка используется вторым алгоритмом, который и производит вычисление значения той или иной функции. Это вычисление основано на алгоритме пульсации: сначала от автомата начальной вершины по всему графу распространяются сообщения-вопросы, которые должны достигнуть каждой вершины, а затем от каждой вершины «в обратную сторону» к начальной вершине двигаются сообщения-ответы. Алгоритм пульсации, по сути, вычисляет агрегатные функции, для которых значение функции от объединения мультимножеств вычисляется по значениям функции от этих мультимножеств. Однако показано, что любая функция f(x) имеет агрегатное расширение, то есть может быть вычислена как h(f`(x)), где f` агрегатная функция. Заметим, что разметка графа не зависит от той функции, которая будет вычисляться. Это означает, что разметка графа выполняется один раз, после чего может многократно использоваться для вычисления различных функций.
Полный текст статьи в формате pdfКлючевые слова
Издание
Программирование, 41(1):3-17, 2015.
Научная группа
Все публикации за 2015 год
Все публикации