Жадная раскраска графов на параллельных системах с распределенной памятью

Евгений Власов, Введение Умение раскрашивать графы – это очень хорошо. Например для задачи распараллеливания. Задача раскраски: поделить все вершины графа на классы, в каждом из которых вершины попарно не связаны (минимально возможное число таких классов называется хроматическим числом графа). Задача нахождения хроматического числа NP- трудна. Но огорчаться не стоит – для наших целей ее не обязательно решать точно. Нам хочется параллельный алгоритм для решения

Евгений Власов, Цели Хотим получить семейство алгоритмов (framework) и выбрать из них наилучший. Масштабируемость: время работы уменьшается с числом процессоров Количество цветов, выдаваемое алгоритмами семейства, должно быть близко к идеалу

Евгений Власов, Основные черты алгоритмов Делим все вершины графа между процессорами. Каждый процессор на очередном шаге красит S своих вершин. S >0. Каждый шаг алгоритма – покраска + этап обнаружения конфликтов (обмен информацией с другими процессорами и проверка коллизий). На этапе обнаружения конфликтов процессор проверяет только недавно покрашенные вершины. Алгоритм завершается при отсутствии конфликтов.

Евгений Власов, Оси вариации Параметр S. Закраска вершин разными процессорами на одном шаге – синхронно или асинхронно. Выбор очередных вершин для покраски. Выбор цвета для покраски той или иной вершины. Общение процессоров – один алгоритм для всех или индивидуальная настройка.

Евгений Власов, Немного истории Алгоритм Luby Алгоритм Йохансона Его улучшение данное Финоччи Алгоритм Gebremedhin'а-Manne Недостатки этих алгоритмов

Евгений Власов, Общий framework

Евгений Власов, Вариации : выбор цвета Выбираем цвет из некоторого множества FF (First Fit) – берем цвет с наименьшим подходящим номером. Если ни один не подходит – добавляем цвет, расширяя множество. SFF (Staggered First Fit) – опираясь на заранее подобранное K, i-й процессор выбирает номер цвета из отрезка [i*K / P],...., K. Если нужного цвета там нет, то пытаемся взять из другого отрезка – с меньшими номерами. Не повезло и на этот раз – добавляем новый цвет.

Евгений Власов, Вариации : порядок покраски Внутренние вершины до граничных. Внутренние вершины после граничных И те и другие параллельно.

Евгений Власов, Вариации : стратегии обхода У нас полная свобода относительно этого =)

Евгений Власов, Вариации : синхронизация Можем поставить барьер, у которого процессоры, закончившие покраску, ждут товарищей. Меньше сообщений, больше время простоя Без барьера. Простоев нет, сообщений - туча.

Евгений Власов, Вариации : коммуникация Каждый передает информацию только тем, кому она и впрямь нужна Каждый попросту транслирует информацию.

Евгений Власов, Использованные алгоритмы Последовательный алгоритм покраски граничных вершин Алгоритм секвенциального разрешения конфликтов Модифицированный алгоритм Джонса-Плазмана

Евгений Власов, Алгоритм покраски граничных вершин Параллельной обработке подвергаем только внутренние вершины. Граф, индуцированный граничными вершинами кидаем на специальный процессор, который считает и красит все последовательно

Евгений Власов, Разрешение конфликтов (SCR) Это вариант SPCFramework с одним раундом Конфликты, обнаруженные в этом раунде разрешаются на одном процессоре последовательно. Граф, индуцированный граничными конфликтными вершинами, кладется на отдельный процессор и раскрашивается последовательно.

Евгений Власов, Алгоритм Джонса-Плазмана Применяется только для граничных вершин. Внутренние раскрашиваются тривиально в конце алгоритма. У i-го процессора – свой список D(i) доминирующих вершин (большее значение рандомной функции). i-й процессор отсылает новости только тем, кто владеет вершинами, соседними с D(i). Если после окраски вершины V какой-либо ее бесцветный сосед W вдруг стал доминировать над своими бесцветными соседями, то заносим его в список. Продолжаем пока все вершины не покрасятся Утверждение. Раундов здесь не меньше чем в SPCFramework

Евгений Власов, Эксперименты и выбор лучшего алгоритма Каждая буква – выбор варианта в соответствующей вариации FIAC FISC FBAC FUAC FIAC

Евгений Власов, Эксперименты и выбор лучшего алгоритма Для естественных графов лучшими оказались FIAC и FBAC, для синтетических - FIAB и FBAB. SPCFramework показал отличные результаты в плане масштабируемости – сокращение времени практически линейно от числа процессоров, в отличие от алгоритма Джонса-Плазмана SFF, как и ожидалось дает меньше конфликтов, чем FF, но и цветов получается больше FIAC и FIAB практически неотличимы на естественных графах, а вот на синтетических лучше FIAB

Евгений Власов, Литература A Framework for Scalable Greedy Coloring on Doruk Bozda˘g, Assefaw H. Gebremedhin, Fredrik Manne, Erik G. Boman, Umit Catalyurek