Участник:Lizord/Алгоритм Джонса Плассмана: различия между версиями

Текущая версия от 10:30, 29 ноября 2025

Основные авторы описания: Демаков М. А.

Алгоритм Джонса-Плассмана
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ O(\|V\| + \|E\|) }[/math]
Объём входных данных	[math]\displaystyle{ 8\|E\| }[/math]
Объём выходных данных	[math]\displaystyle{ \|V\| }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]\displaystyle{ O(\frac{log(V)}{log log(V)}) }[/math] ^[1]
Ширина ярусно-параллельной формы	[math]\displaystyle{ O(log(V)) }[/math] ^[1]

Свойства и структура алгоритмов

Общее описание алгоритма

Алгоритм Джонса-Плассмана - параллельная версия жадного алгоритма для раскраски графа, предложен американскими исследователями Марком Джонсом и Паулем Плассманом в 1991 году. Алгоритм основан на выделении из графа максимального независимого подмножества вершин и параллельной его раскраске. Способ выделения такого подмножества вершин был предложен Луби, он заключается в назначении вершинам уникальных меток, и последующего выбора ранее не выбранных вершин с максимальной меткой среди своих соседей. ^[2]

Математическое описание алгоритма

Исходные данные: граф [math]\displaystyle{ G = G(V, E) }[/math], где [math]\displaystyle{ V }[/math] - множество вершин, а [math]\displaystyle{ E }[/math] - множество ребёр.
Вычисляемые данные: вектор цветов [math]\displaystyle{ c = \{c_i\} }[/math] размерности [math]\displaystyle{ |V| }[/math]

Для раскраски графа, необходимо проделать следующие шаги:

Обозначим множество нераскрашенных вершин как [math]\displaystyle{ V' = V }[/math].
На каждой итерации будем выделять максимальное независимое подмножество вершин [math]\displaystyle{ I \subset V' }[/math], которое раскрашивается параллельно.
1. Для каждой вершины [math]\displaystyle{ v_i \in V' }[/math] назначается уникальная случайная метка [math]\displaystyle{ p(v_i) }[/math]
2. [math]\displaystyle{ v_i \in I \Leftrightarrow p(v_i) \gt p(w), \forall w \in adj(v_i) }[/math]
После этого полагаем [math]\displaystyle{ V' = V'\;\backslash\;I }[/math]. Алгоритм работает, пока [math]\displaystyle{ V' \neq \emptyset }[/math].

Для раскраски вершины [math]\displaystyle{ v_i \in I }[/math] необходимо назначить ей цвет [math]\displaystyle{ c_i }[/math] такой, что [math]\displaystyle{ c_i \notin N_c(v_i) }[/math], где [math]\displaystyle{ N_c(v_i) }[/math] - цвета вершин, соседних для [math]\displaystyle{ v_i }[/math]. Это можно сделать последовательным перебором, это займёт в худшем случае Δ итераций (Δ - наибольшая из степеней графа).

Функции приоритета

Существуют различные способы определять функцию приоритета [math]\displaystyle{ p(v_i) }[/math], которая используется для выбора независимых вершин для раскраски. Помимо классического варианта с назначением случайных меток, вершины могут также выбираться следующими способами:

First Fit: вершины рассматриваются в некотором заранее выбранном порядке. Например, в порядке появления в графе.
Saturation-Degree-Ordering: выбирается вершина с максимальной насыщенной степенью, то есть с максимальным числом различно раскрашенных смежных вершин.
Incidence-Degree-Ordering: выбирается вершина с максимальным числом раскрашенных смежных вершин.
Largest-Degree-First: вершины раскрашиваются в порядке уменьшения степеней
Smallest-Degree-Last: из графа удаляются все вершины с минимальной степенью, затем рекурсивно раскрашивается оставшийся граф. Удаленные вершины раскрашиваются в последнюю очередь.
и др.

Вычислительное ядро алгоритма

Вычислительным ядром алгоритма является выделение из множества нераскрашенных вершин графа максимального независимого подмножества, которое впоследствии раскрашивается параллельно.

Макроструктура алгоритма

Псевдокод алгоритма:

Входные данные:
  граф с вершинами V, рёбрами E.
Выходные данные: цветовые метки с(v) для каждой вершины v ∈ V

color := []
w := []
for each v ∈ V:
     color[v] := 0
     w[v] := PRIORITY(v)

while v с color[v] == 0:
     S := ∅
     for each v с color[v] == 0 in parallel:
         isMax := true
         for each u ∈ N(v):
             if color[u] == 0 и ( w[u] > w[v] или (w[u] == w[v] и u.id > v.id) ):
                 isMax := false
                 break
         if isMax:
             S.append(v)

     for each v ∈ S in parallel:
         used := { color[u] : u ∈ N(v) и color[u] ≠ 0 }
         c := 1
         while c ∈ used:
             c := c + 1
         color[v] := c

Схема реализации последовательного алгоритма

Последовательной версией алгоритма Джонса-Плассмана является обычная жадная раскраска графа. Описание её алгоритма можно получить, убрав параллельные секции из описания алгоритма Джонса-Плассмана (т.е исполняя их последовательно).

Последовательная сложность алгоритма

Для каждой вершины v алгоритм проделывает следующие шаги:

Просматривает её соседей.
Собирает цвета уже окрашенных соседей.
Выбирает минимальный свободный цвет.
Присваивает его v.

Инициализация начальных структур (расстановка приоритетов и цветов) требует один проход на [math]\displaystyle{ |V| }[/math] итераций, что даёт сложность [math]\displaystyle{ O(|V|) }[/math]. Для выбора доступного цвета необходимо просмотреть всех соседей вершины, что требует в сумме для всех вершин [math]\displaystyle{ \sum\limits_{v \in V} {deg(v)} = 2|E| }[/math] итераций, что даёт вклад [math]\displaystyle{ O(|E|) }[/math]. Выбор минимального свободного цвета требует, в простейшем случае, также [math]\displaystyle{ \sum\limits_{v \in V} {O(deg(v))} = O(|E|) }[/math] итераций, однако при эффективной реализации это можно делать за O(1) (например, при хранении доступных цветов в битовой карте).

Итого получаем суммарную сложность [math]\displaystyle{ O(|V| + |E|) }[/math]

Информационный граф

Далее представлен информационный граф одной итерации алгоритма. После её завершения, вершины, которые не были раскрашены прогоняются ещё раз - алгоритм работает, пока все вершины не будут раскрашены.

Обозначения: Синие круги - набор нераскрашенных вершин, белые блоки вокруг них означают наборы соседей (в общем случае они могут пересекаться, но это не влияет на ход работы). Зеленые круги - операции выбора вершины с наибольшим приоритетом, желтые круги - операции выбора цвета, оранжевые круги - операции, непосредственно, раскраски

Ресурс параллелизма алгоритма

Как видно из информационного графа, параллелизм достигается за счёт выделения из множества вершин независимых подмножеств, между которыми нет ребёр. Очевидно, что вершинам из таких подмножеств можно назначить цвет независимо, т.е параллельно.

Входные и выходные данные алгоритма

Входные данные: Граф [math]\displaystyle{ G = G(V, E) }[/math]
Объём входных данных: [math]\displaystyle{ 8|E| }[/math] если граф представлен списком связности, либо [math]\displaystyle{ |V|^2 }[/math], если матрицей смежности

Выходные данные: Вектор [math]\displaystyle{ c = \{c_i\} }[/math], содержащий итоговые цвета вершин.
Объём выходных данных: [math]\displaystyle{ |V| }[/math]

Свойства алгоритма

Жадные алгоритмы дают раскраски хорошего качества с точки зрения количества цветов (получаемые раскраски имеют не более, чем Δ + 1 цвет), однако эти раскраски не будут являться сбалансированными (количество цветов в цветовых классах будет распределено неравномерно)

Программная реализация алгоритма

Особенности реализации последовательного алгоритма

Для вычисления доступного вершине цвета имеет смысл использовать битмап, где каждый установленный бит означает доступный цвет. На большинстве вычислительных архитектур получить первый установленный бит в числе можно одной аппаратной инструкцией.

Эту же оптимизацию можно перенести и на ядра для параллельной реализации.

Возможные способы и особенности параллельной реализации алгоритма

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

Результаты прогонов

Из результатов прогонов видно, что несмотря на ожидаемый рост потенциальной производительности (скорости вычислений без учёта затрат на коммуникацию) с увеличением количества процессов, реальная производительность показывает прямо противоположную картину, с незначительным ростом производительности лишь на большом количестве процессов.

Тесты проводились на синтетических графах с 8 миллионами вершинами и количеством ребёр равным 40, 60, 80, 100, 120, 140 и 160 миллионам.

Производительность в данном случае измеряется в GTEPS - миллиардах обработанных ребёр в секунду. Это классическая метрика производительности для задач на графах.

Выводы для классов архитектур

Несмотря на хорошую масштабируемость в рамках одного устройства (без необходимости обмениваться данными с другими процессами), алгоритм обладает слабой масштабируемостью на кластере ввиду роста расходов на коммуникацию между независимыми потоками (после каждой итерации каждый из потоков должен синхронизировать своё состояние с остальными). Для раскраски графов на распределенных системах следует использовать специализированные алгоритмы, основанные на разбиении графа ^[3].

Литература

↑ ^1,0 ^1,1 Maciej Besta, Armon Carigiet et. al. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality. // ACM/IEEE Supercomputing Conference, 2020
↑ M.T.Jones, P.E.Plassmann. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, vol. 14, no. 3, pp. 654–669, 1993
↑ Ian Bogle and George M. Slota, Parallel Graph Coloring Algorithms for Distributed GPU Environments

[compl-1] 1,0 ^1,1 Maciej Besta, Armon Carigiet et. al. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality. // ACM/IEEE Supercomputing Conference, 2020

[jp-2] M.T.Jones, P.E.Plassmann. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, vol. 14, no. 3, pp. 654–669, 1993

[3] Ian Bogle and George M. Slota, Parallel Graph Coloring Algorithms for Distributed GPU Environments

[1]

[2]

[3]

@@ Строка 1: / Строка 1: @@
-{{in use|[[Участник:Lizord|Lizord]] ([[Обсуждение участника:Lizord|обсуждение]])}}
+Основные авторы описания: [[Участник:Lizord|Демаков М. А.]]
-Автор: [[Участник:Lizord|Демаков М. А.]]
 {{algorithm
 | name              = Алгоритм Джонса-Плассмана
-| serial_complexity = <math>O(V + E)</math>
+| serial_complexity = <math>O(|V| + |E|)</math>
-| pf_height         = <math>O(\frac{log(V)}{log log(V)})</math>
+| pf_height         = <math>O(\frac{log(V)}{log log(V)})</math> <ref name="compl">Maciej Besta, Armon Carigiet et. al. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality. // ACM/IEEE Supercomputing Conference, 2020</ref>
-| pf_width          = <math>O(log(V))</math>
+| pf_width          = <math>O(log(V))</math> <ref name="compl"></ref>
-| input_data        = <math>V + E</math>
+| input_data        = <math>8|E|</math>
-| output_data       = <math>V</math>
+| output_data       = <math>|V|</math>
 }}
 == Свойства и структура алгоритмов ==
 === Общее описание алгоритма ===
-=== Математическое описание алгоритма ===
+'''Алгоритм Джонса-Плассмана''' - параллельная версия жадного алгоритма для раскраски графа, предложен американскими исследователями Марком Джонсом и Паулем Плассманом в 1991 году. Алгоритм основан на выделении из графа максимального независимого подмножества вершин и параллельной его раскраске. Способ выделения такого подмножества вершин был предложен Луби, он заключается в назначении вершинам уникальных меток, и последующего выбора ранее не выбранных вершин с максимальной меткой среди своих соседей. <ref name="jp">M.T.Jones, P.E.Plassmann. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, vol. 14, no. 3, pp. 654–669, 1993</ref>
-=== Вычислительное ядро алгоритма ===
-=== Макроструктура алгоритма ===
+=== Математическое описание алгоритма ===
-=== Схема реализации последовательного алгоритма ===
+Исходные данные: граф <math>G = G(V, E)</math>, где <math>V</math> - множество вершин, а <math>E</math> - множество ребёр.<br>
-=== Последовательная сложность алгоритма ===
+Вычисляемые данные: вектор цветов <math>c = \{c_i\}</math> размерности <math>|V|</math>
-=== Информационный граф ===
-=== Ресурс параллелизма алгоритма ===
+Для раскраски графа, необходимо проделать следующие шаги:
+# Обозначим множество нераскрашенных вершин как <math>V' = V</math>.<br>
+# На каждой итерации будем выделять максимальное независимое подмножество вершин <math>I \subset V'</math>, которое раскрашивается параллельно.
+## Для каждой вершины <math>v_i \in V'</math> назначается уникальная случайная метка <math>p(v_i)</math>
+## <math>v_i \in I \Leftrightarrow p(v_i) > p(w), \forall w \in adj(v_i) </math>
+# После этого полагаем <math>V' = V'\;\backslash\;I</math>. Алгоритм работает, пока <math>V' \neq \emptyset</math>.
+Для раскраски вершины <math>v_i \in I</math> необходимо назначить ей цвет <math>c_i</math> такой, что <math>c_i \notin N_c(v_i)</math>, где <math>N_c(v_i)</math> - цвета вершин, соседних для <math>v_i</math>. Это можно сделать последовательным перебором, это займёт в худшем случае Δ итераций (Δ - наибольшая из степеней графа).<br>
+==== Функции приоритета ====
+Существуют различные способы определять функцию приоритета <math>p(v_i)</math>, которая используется для выбора независимых вершин для раскраски. Помимо классического варианта с назначением случайных меток, вершины могут также выбираться следующими способами:
+* First Fit: вершины рассматриваются в некотором заранее выбранном порядке. Например, в порядке появления в графе.
+* Saturation-Degree-Ordering: выбирается вершина с максимальной насыщенной степенью, то есть с максимальным числом различно раскрашенных смежных вершин.
+* Incidence-Degree-Ordering: выбирается вершина с максимальным числом раскрашенных смежных вершин.
+* Largest-Degree-First: вершины раскрашиваются в порядке уменьшения степеней
+* Smallest-Degree-Last: из графа удаляются все вершины с минимальной степенью, затем рекурсивно раскрашивается оставшийся граф. Удаленные вершины раскрашиваются в последнюю очередь.
+* и др.
+=== Вычислительное ядро алгоритма ===
+Вычислительным ядром алгоритма является выделение из множества нераскрашенных вершин графа максимального независимого подмножества, которое впоследствии раскрашивается параллельно.
+=== Макроструктура алгоритма ===
+Псевдокод алгоритма:
+<source>
+Входные данные:
+  граф с вершинами V, рёбрами E.
+Выходные данные: цветовые метки с(v) для каждой вершины v ∈ V
+color := []
+w := []
+for each v ∈ V:
+     color[v] := 0
+     w[v] := PRIORITY(v)
+while v с color[v] == 0:
+     S := ∅
+     for each v с color[v] == 0 in parallel:
+         isMax := true
+         for each u ∈ N(v):
+             if color[u] == 0 и ( w[u] > w[v] или (w[u] == w[v] и u.id > v.id) ):
+                 isMax := false
+                 break
+         if isMax:
+             S.append(v)
+     for each v ∈ S in parallel:
+         used := { color[u] : u ∈ N(v) и color[u] ≠ 0 }
+         c := 1
+         while c ∈ used:
+             c := c + 1
+         color[v] := c
+</source>
+=== Схема реализации последовательного алгоритма ===
+Последовательной версией алгоритма Джонса-Плассмана является обычная жадная раскраска графа. Описание её алгоритма можно получить, убрав параллельные секции из описания алгоритма Джонса-Плассмана (т.е исполняя их последовательно).
+=== Последовательная сложность алгоритма ===
+Для каждой вершины v алгоритм проделывает следующие шаги:
+# Просматривает её соседей.
+# Собирает цвета уже окрашенных соседей.
+# Выбирает минимальный свободный цвет.
+# Присваивает его v.
+Инициализация начальных структур (расстановка приоритетов и цветов) требует один проход на <math>|V|</math> итераций, что даёт сложность <math>O(|V|)</math>.
+Для выбора доступного цвета необходимо просмотреть всех соседей вершины, что требует в сумме для всех вершин <math>\sum\limits_{v \in V} {deg(v)} = 2|E|</math> итераций, что даёт вклад <math>O(|E|)</math>.
+Выбор минимального свободного цвета требует, в простейшем случае, также <math>\sum\limits_{v \in V} {O(deg(v))} = O(|E|)</math> итераций, однако при эффективной реализации это можно делать за O(1) (например, при хранении доступных цветов в битовой карте).
+Итого получаем суммарную сложность <math>O(|V| + |E|)</math>
+=== Информационный граф ===
+Далее представлен информационный граф  '''одной итерации''' алгоритма. После её завершения, вершины, которые не были раскрашены прогоняются ещё раз - алгоритм работает, пока все вершины не будут раскрашены.
+[[Файл:Информационный граф итерации алгоритма Джонса Плассмана.png|center|thumb|500px|Рисунок 1. Информационный граф одной итерации алгоритма Джонса-Плассмана]]
+Обозначения:
+Синие круги - набор нераскрашенных вершин, белые блоки вокруг них означают наборы соседей (в общем случае они могут пересекаться, но это не влияет на ход работы). Зеленые круги - операции выбора вершины с наибольшим приоритетом, желтые круги - операции выбора цвета, оранжевые круги - операции, непосредственно, раскраски
+=== Ресурс параллелизма алгоритма ===
+Как видно из информационного графа, параллелизм достигается за счёт выделения из множества вершин независимых подмножеств, между которыми нет ребёр. Очевидно, что вершинам из таких подмножеств можно назначить цвет независимо, т.е параллельно.
 === Входные и выходные данные алгоритма ===
+'''Входные данные''': Граф <math>G = G(V, E)</math><br>
+'''Объём входных данных''': <math>8|E|</math> если граф представлен списком связности, либо <math>|V|^2</math>, если матрицей смежности<br>
+'''Выходные данные''': Вектор <math>c = \{c_i\}</math>, содержащий итоговые цвета вершин.<br>
+'''Объём выходных данных''': <math>|V|</math>
 === Свойства алгоритма ===
+Жадные алгоритмы дают раскраски хорошего качества с точки зрения количества цветов (получаемые раскраски имеют не более, чем Δ + 1 цвет), однако эти раскраски не будут являться сбалансированными (количество цветов в цветовых классах будет распределено неравномерно)
 == Программная реализация алгоритма ==
 === Особенности реализации последовательного алгоритма ===
+Для вычисления доступного вершине цвета имеет смысл использовать битмап, где каждый установленный бит означает доступный цвет. На большинстве вычислительных архитектур получить первый установленный бит в числе можно одной аппаратной инструкцией.
+Эту же оптимизацию можно перенести и на ядра для параллельной реализации.
 === Возможные способы и особенности параллельной реализации алгоритма ===
+Стандартные способы хранения графов обычно обладают плохой локальностью, которую можно улучшить, если изначально сортировать вершины, размещая их рядом с соседними.
 === Результаты прогонов ===
+[[Файл:Результаты прогона алгоритма Джонса-Плассмана.png|center|800px|Рисунок 2. Результаты прогона алгоритма Джонса-Плассмана]]
+Из результатов прогонов видно, что несмотря на ожидаемый рост потенциальной производительности (скорости вычислений без учёта затрат на коммуникацию) с увеличением количества процессов, реальная производительность показывает прямо противоположную картину, с незначительным ростом производительности лишь на большом количестве процессов.
+Тесты проводились на синтетических графах с 8 миллионами вершинами и количеством ребёр равным 40, 60, 80, 100, 120, 140 и 160 миллионам.
+Производительность в данном случае измеряется в GTEPS - миллиардах обработанных ребёр в секунду. Это классическая метрика производительности для задач на графах.
 === Выводы для классов архитектур ===
+Несмотря на хорошую масштабируемость в рамках одного устройства (без необходимости обмениваться данными с другими процессами), алгоритм обладает слабой масштабируемостью на кластере ввиду роста расходов на коммуникацию между независимыми потоками (после каждой итерации каждый из потоков должен синхронизировать своё состояние с остальными). Для раскраски графов на распределенных системах следует использовать специализированные алгоритмы, основанные на разбиении графа <ref>Ian Bogle and George M. Slota, Parallel Graph Coloring Algorithms for Distributed GPU Environments</ref>.
 == Литература ==
-# M.T.Jones, P.E.Plassmann. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, vol. 14, no. 3, pp. 654–669, 1993
+<references />
-# Maciej Besta, Armon Carigiet et. al. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality. // ACM/IEEE Supercomputing Conference, 2020

Участник:Lizord/Алгоритм Джонса Плассмана: различия между версиями

Текущая версия от 10:30, 29 ноября 2025

Содержание

Свойства и структура алгоритмов

Общее описание алгоритма

Математическое описание алгоритма

Функции приоритета

Вычислительное ядро алгоритма

Макроструктура алгоритма

Схема реализации последовательного алгоритма

Последовательная сложность алгоритма

Информационный граф

Ресурс параллелизма алгоритма

Входные и выходные данные алгоритма

Свойства алгоритма

Программная реализация алгоритма

Особенности реализации последовательного алгоритма

Возможные способы и особенности параллельной реализации алгоритма

Результаты прогонов

Выводы для классов архитектур

Литература

Навигация

Участник:Lizord/Алгоритм Джонса Плассмана: различия между версиями

Текущая версия от 10:30, 29 ноября 2025

Свойства и структура алгоритмов

Общее описание алгоритма

Математическое описание алгоритма

Функции приоритета

Вычислительное ядро алгоритма

Макроструктура алгоритма

Схема реализации последовательного алгоритма

Последовательная сложность алгоритма

Информационный граф

Ресурс параллелизма алгоритма

Входные и выходные данные алгоритма

Свойства алгоритма

Программная реализация алгоритма

Особенности реализации последовательного алгоритма

Возможные способы и особенности параллельной реализации алгоритма

Результаты прогонов

Выводы для классов архитектур

Литература

Навигация

Поиск