ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ ~
УДК 681.3.06
ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ НА ГРАФЕ
© 2015 г. И.Б. Бурдонов, A.C. Косачев, В.В. Кулямин
Институт системного программирования РАН 109004 Москва, ул. А. Солженицына, 25 E-mail: igor@ispras.ru, kos@ispras.ru, kuliamin@ispras.ru, Поступила в редакцию 07.09.2014
Рассматривается задача параллельного вычисления значения функции от мультимножества значений, записанных в вершинах ориентированного графа. Вычисление выполняется автоматами, находящимися в вершинах графа и обменивающихся между собой сообщениями, передаваемыми по дугам графа (в направлении их ориентации). Предполагается, что ёмкость дуги, то есть число одновременно передаваемых по ней сообщений, ограничена. Вычисление инициируется сообщением, приходящим извне в автомат выделенной начальной вершины графа. Этот же автомат в конце работы посылает вовне вычисленное значение функции. Для решения этой задачи предлагаются два алгоритма. Первый алгоритм выполняет исследование графа, основанное на его обходе. Его цель - разметить граф с помощью изменения состояний автоматов в вершинах. Строятся прямой и обратный остовы графа. Прямой остов ориентирован от корня, которым является начальная вершина графа. Обратный остов ориентирован к тому же корню. Кроме того, в каждой вершине устанавливается значение счётчика входящих дуг обратного остова. Такая разметка используется вторым алгоритмом, который и производит вычисление значения той или иной функции. Это вычисление основано на алгоритме пульсации: сначала от автомата начальной вершины по всему графу распространяются сообщения-вопросы, которые должны достигнуть каждой вершины, а затем от каждой вершины "в обратную сторону" к начальной вершине двигаются сообщения-ответы. Алгоритм пульсации, по сути, вычисляет агрегатные функции, для которых значение функции от объединения мультимножеств вычисляется по значениям функции от этих мультимножеств. Однако показано, что любая функция f (x) имеет агрегатное расширение, то есть может быть вычислена как h(f'(x)), где f' — агрегатная функция. Заметим, что разметка графа не зависит от той функции, которая будет вычисляться. Это означает, что разметка графа выполняется один раз, после чего может многократно использоваться для вычисления различных функций.
1. ВВЕДЕНИЕ
Исследование ориентированных графов является корневой задачей во многих приложениях. Достаточно указать исследование сетей связи, в том числе сети интернета и GRID, и тестирование программных и аппаратных систем, моделируемых графами переходов. Исследование графа, как правило, базируется на его обходе, а это уже старая классическая задача обхода лабиринта. Эта задача нетривиальна, если граф ориентирован, то есть в лабиринте "улицы с односторонним движением".
Обход ориентированного графа требует време-
ни порядка иш^е п - число вершин графа, а т - число дуг. Такое время обхода достигается многими хорошо известными алгоритмами: обход в глубину, обход в ширину, "жадный" алгоритм и др. [1, 2, 3].
В 1976 г. М.О. Рабин поставил задачу обхода ориентированного графа конечным автоматом [4]. Автомат на графе аналогичен машине Тьюринга: ячейке ленты соответствует вершина графа, а движение влево или вправо по ленте заменяется переходом по одной из дуг, выходящих из текущей вершины графа. На сегодняшний день наиболее быстрый алгоритм предложен
в [5], он имеет оценку пт + п21од1одп. При повторном обходе, когда автомат может использовать пометки, оставленные им же после первого обхода, оценка уменьшается до пт + п21(п), где 1(п) - число логарифмирований, при котором достигается соотношение 1 < 1од(1од ... (п)...) < 2 [6]. Отличие от нижней оценки пт объясняется тем, что автомату бывает нужно "вернуться" в начало только что пройденной дуги.
За последние годы размер реально используемых систем и сетей и, следовательно, размер исследуемых графов непрерывно растёт. Проблемы возникают тогда, когда исследование графа одним автоматом (компьютером) либо требует недопустимо большого времени, либо граф не помещается в памяти одного компьютера, либо и то, и другое. Поэтому возникает задача параллельного и распределённого исследования графов. Эта задача формализуется как задача исследования графа коллективом автоматов.
В [7] и [8] предложены алгоритмы работы такого коллектива автоматов. При этом предполагается, что автоматы не могут ничего писать в вершины графа или читать из них, но могут обмениваться между собой сообщениями с помощью сети связи, ортогональной графу, а также генерировать новые автоматы. Наилучшая полученная оценка т + пВ, где В - диаметр графа, т.е. длина максимального пути (маршрута без самопересечений) в графе.
В данной работе мы рассматриваем классическую задачу исследования графа автоматами, обмен информацией между которыми происходит только через память вершин графа. Это эквивалентно исследованию графа с помощью сообщений, которыми обмениваются между собой автоматы, неподвижно "сидящие" в вершинах графа, а дуги графа играют роль каналов передачи сообщений. Автомат, находящийся в вершине, посылает сообщение по одной из дуг, выходящих из этой вершины, и через какое-то время такое сообщение принимается автоматом в конце дуги. Оценка времени работы алгоритма зависит от числа сообщений, которые могут одновременно передаваться по дуге. Такое число мы будем называть ёмкостью дуги и обозначать к.
Как алгоритмы исследования графа, так и оценка времени их работы, существенно зависят от того, имеют ли автоматы в вершинах графа
какую-то информацию о графе, или каждый автомат находится в начальном состоянии и "ничего не знает" о графе. В данной работе мы предлагаем два алгоритма. Первый алгоритм выполняет первичный обход графа с помощью пересылаемых сообщений, когда в начальный момент времени все автоматы находятся в начальном состоянии. После завершения обхода автоматы оказываются в таких конечных состояниях, которые позволяют выполнять параллельное вычисление требуемой функции с помощью второго алгоритма. Обход графа выполняется за время порядка п/к + В, а вычисление функции - за время порядка В.
Второй алгоритм - это алгоритм пульсации, основанный на том, что сначала от автомата выделенной начальной вершины по всему графу распространяются сообщения-вопросы, которые должны достигнуть каждой вершины. А затем от каждой вершины "в обратную сторону" к начальной вершине двигаются сообщения-ответы. С помощью алгоритма пульсации можно параллельно вычислять любую функцию от мультимножества значений, записанных в памяти автоматов по всем вершинам графа (мы будем говорить "записанных в вершинах"). Вот лишь несколько примеров таких функций:
1. Максимум чисел, записанных в вершинах графа.
2. В более общем виде вместо максимума можно использовать любую коммутативную и ассоциативную операцию над числами: минимум, сложение, произведение и т.д.
3. Частные случаи: число вершин в графе, ес-
1
дуг в графе, если в каждой вершине записать число выходящих дуг.
4. Дизъюнкция логических значений, записанных в вершинах графа.
5. В более общем виде вместо дизъюнкции можно использовать любую коммутативную и ассоциативную операцию над логическими значениями: конъюнкцию, эквивалентность и т.д.
6. В ещё более общем виде вместо чисел или логических значений можно использовать
любые значения и любые коммутативные и ассоциативные операции над ними.
7. Среднее арифметическое, среднее геометрическое или среднее квадратичное от чисел, записанных в вершинах графа.
2. ОПИСАНИЕ АЛГОРИТМА ОБХОДА
Там, где это не приведёт к коллизиям, мы для краткости будем говорить "вершина", имея в виду "автомат вершины" или "память автомата вершины". Посылая сообщение, автомат в вершине должен указывать дугу, выходящую из вершины, по которой сообщение посылается. Мы будем считать, что дуги, выходящие из вершины, перенумерованы, начиная с 1, и автомат указывает номер дуги.
т,
п,
рута без самопересечений) равна Б, число дуг, выходящих из вершины, не превышает во, а число дуг, входящих в вершину, не превышает $1. Очевидно, т < пво. Мы предлагаем алгоритм обхода графа со следующими характеристиками:
• память автомата вер шины 0(пБ1одв о),
• размер сообщения 0(Б1одво),
• ёмкость дуги к,
• время работы алгоритма 0(п/к + Б).
Замечание 2.1: Очевидно, что посылка по дуге одновременно к1 < к сообщений размером г бит эквивалентна посылке по дуге одного сообщения размером к'г бит, или, в общем случае, посылке к1 сообщений размером к2г, где к1к2 = к. Тем самым оценка времени работы алгоритма при раз-
гк ний совпадает с оценкой времени работы алго-
к1 г
дуги к2 сообщений, где к^2 = к. Поэтому наш алгоритм после тривиальной модификации имеет следующие характеристики:
• память автомата вер шины 0(пБ1одв о),
• размер сообщения 0(к201одво),
• к1 ,
• время работы алгор итма 0(п/к1к2 + Б).
Для оценки времени работы алгоритма мы будем предполагать, что временем срабатывания автомата в вершине можно пренебречь, а время передачи сообщения по дуге ограничено свер-1
Одни сообщения посылаются из вершины сразу по всем выходящим дугам, другие - только по части выходящих дуг, а третьи - только по одной выходящей дуге. Тем не менее для простоты мы будем считать, что сообщение ожидает в вершине освобождения сразу всех выходящих дуг. Таким образом, для автомата вершины не нужен сигнал об освобождении данной выходящей дуги, а достаточно общего сигнала об освобождении всех выходящих дуг. Также будем считать, что автомат в общем случае посылает по дуге
к
кости дуги.
В процессе работы алгоритма строятся остовы графа: прямой остов, ориентированный от корня, и обратный остов, ориентированный к корню. Дуги, выходящие из вершины: прямые дуги - дуги прямого остова, хорды, - остальные выходящие дуги, обратная дуга - дуга обратного остова (может быть как прямой дугой, так и хордой). Прямой путь - путь из прямых дуг от корня. Обратный путь - путь из обратных дуг до корня. Вектором маршрута будем называть список номеров дуг маршрута в графе. В алгоритме будут использоваться только вектора путей длины не более Б и контуров (циклов, в которых вершина н
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.