RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Труды ИСП РАН:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Труды ИСП РАН, 2015, том 27, выпуск 2, страницы 189–220 (Mi tisp130)  

Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)

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

Игорь Бурдонов, Александр Косачев

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

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

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

DOI: https://doi.org/10.15514/ISPRAS-2015-27(2)-12

Полный текст: PDF файл (433 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья

Образец цитирования: Игорь Бурдонов, Александр Косачев, “Параллельные вычисления на динамически меняющемся графе”, Труды ИСП РАН, 27:2 (2015), 189–220

Цитирование в формате AMSBIB
\RBibitem{BurKos15}
\by Игорь~Бурдонов, Александр~Косачев
\paper Параллельные вычисления на динамически меняющемся графе
\jour Труды ИСП РАН
\yr 2015
\vol 27
\issue 2
\pages 189--220
\mathnet{http://mi.mathnet.ru/tisp130}
\crossref{https://doi.org/10.15514/ISPRAS-2015-27(2)-12}
\elib{http://elibrary.ru/item.asp?id=23827854}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/tisp130
  • http://mi.mathnet.ru/rus/tisp/v27/i2/p189

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. И. Б. Бурдонов, А. С. Косачев, “Общий подход к решению задач на графах коллективом автоматов”, Труды ИСП РАН, 29:2 (2017), 27–76  mathnet  crossref  elib
    2. I. B. Burdonov, A. S. Kossatchev, V. V. Kuliamin, A. N. Tomilin, V. Z. Shnitman, “Asynchronous distributed algorithms for static and dynamic directed rooted graphs”, Труды ИСП РАН, 30:1 (2018), 69–88  mathnet  crossref  elib
  • Труды института системного программирования РАН
    Просмотров:
    Эта страница:81
    Полный текст:25
    Литература:16
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020