Участник:Юлия Жосан/Разбиение вершин графа на равные по мощности блоки методом рекурсивной координатной бисекции

Метод рекурсивной координатной бисекции
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ O(nlog_{2}nlog_{2}p) }[/math]
Объём входных данных	[math]\displaystyle{ |G|+p }[/math]
Объём выходных данных	[math]\displaystyle{ p*|S| }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]\displaystyle{ O(log_2 k) }[/math]

Автор: Юлия Жосан

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

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

---

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

• минимизация максимального веса исходящих из домена ребер
• равномерное распределение по доменам суммарного веса узлов/ребер

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

Основные этапы работы алгоритма:

1. Выбор направления, вдоль которого будут упорядочиваться вершины домена
2. Упорядочивание вершин вдоль выбранного в п.1 направления
3. Вычисление номера m первой вершины второго домена
4. Формирование двух новых доменов, первый из которых включает вершины от первой до m-1 входящего домена, а второй включает вершины с m до последней вершины входящего домена
5. Запуск алгоритма для полученных в п.4 доменов

Выделяют следующие достоинства данного алгоритма:

• высокая скорость работы
• низкий уровень дисбаланса распределения вершин между доменами
• экономичность по памяти

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

---

Пусть на вход алгоритму подаются следующие данные:

• неориентированный граф [math]\displaystyle{ G=(V, E) }[/math], где [math]\displaystyle{ V }[/math] - множество вершин, [math]\displaystyle{ E }[/math] - множество ребер
• Требуемое число доменов [math]\displaystyle{ p }[/math]

На выходе алгоритма требуется получить множество доменов [math]\displaystyle{ \{S_{p}\} }[/math].Это множество [math]\displaystyle{ p }[/math] непересекающихся подмножеств [math]\displaystyle{ \{V_{i}\} }[/math]:
[math]\displaystyle{ V=\bigcup\limits_{i=1}^{p} V_{i} }[/math], [math]\displaystyle{ V_{i}\cap V_{j}=\emptyset }[/math] для [math]\displaystyle{ i\not=j }[/math] при котором минимизируются следующие функционалы:

• суммарный вес вершин в домене: [math]\displaystyle{ \vert S_{p}\vert=\sum\limits_{i=1}^{p} \vert v_{i} \vert\rightarrow min }[/math]
• суммарный вес разрезанных ребер:[math]\displaystyle{ \sum\limits_{ij} \vert e_{ij} \vert\rightarrow min , v_{i}\in S_{l}, v_{j}\in S_{r}, S_{l}\cap S_{r}=\emptyset }[/math]

Опишем подробнее схему работу рекурсивного алгоритма:

1. Выбор оси, вдоль которой будет осуществляться сортировка. Для этого вычисляется величина [math]\displaystyle{ l_{k}=max\left( v_{i}^{k}\right)-min\left(v_{i}^{k}\right) , v_{i}^{k}\in V , k }[/math] - координатная ось, и выбирается ее максимальное значение.
2. Сортировка множества вершин [math]\displaystyle{ V }[/math] по выбранной в п.1 координате по возрастанию номеров коодинат вершин
3. Вычисляется номер вершины, по которой пойдет разбиение множества: [math]\displaystyle{ m=(iend-istart+1)*\frac{\frac{p+1}{2}}{p} }[/math], где [math]\displaystyle{ iend, istart }[/math] - номер первой вершины в множестве и номер последней вершины в множестве соответственно
4. Множество вершин делится на две части: [math]\displaystyle{ V_{l}=|v_{l}|, l=istart..m ,V_{r}=|v_{r}|, r=m+1..iend }[/math]
5. Алгоритм запускается для [math]\displaystyle{ V_{l} }[/math] и [math]\displaystyle{ V_{r} }[/math]
6. Алгоритм останавливается на итерации, для которой [math]\displaystyle{ |V_{l}|=1 , |V_{r}|=1 }[/math]

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

---

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

• сортировка массива координат вершин [math]\displaystyle{ V }[/math] (могут применяться различные виды сортировок)
• вычисление величины [math]\displaystyle{ l_{k} }[/math] - координатной оси
• вычисление величины [math]\displaystyle{ m }[/math] - точки раздела множества

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

---

Основной составляющей метода является повторяющиеся сортировки множества координат вершин [math]\displaystyle{ V }[/math] на каждом рекурсивном шаге. Всего таких шагов [math]\displaystyle{ p-1 }[/math].

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

---

Представим последовательную реализацию метода рекурсивной координатной бисекции с помощью псевдокода:
[math]\displaystyle{ BisectCoordRec\{V, iend, istart , p\} }[/math]
{
Шаг 1: [math]\displaystyle{ l_{k}=argmax{max\left( v_{i}^{k}\right)-min\left(v_{i}^{k}\right)} }[/math] - //определение оси для сортировки
Шаг 2: [math]\displaystyle{ Sort(V, iend, istart ,l_{k}) }[/math]- //сортировка вершин по выбранной координате
Шаг 3: [math]\displaystyle{ m=(iend-istart+1)*\frac{\frac{p+1}{2}}{p} }[/math] - //поиск точки для разделения множества вершин
Шаг 4: [math]\displaystyle{ Bisect\left(V,(iend-istart) , V_{l}, \frac{p+1}{2}, V_{r}, \frac{\frac{(iend-istart)*(p+1)}{2}}{p}\right) }[/math]- //разделение массива вершин на два
Шаг 5: [math]\displaystyle{ if |V_{l}|\gt 1 : BisectCoordRec\{V_{l},\frac{(iend-istart)*\frac{p+1}{2}}{p} , \frac{p+1}{2}, p\} }[/math]
Шаг 6: [math]\displaystyle{ if |V_{r}|\gt 1 : BisectCoordRec\{V_{r}, (iend-istart) - \frac{(iend-istart)*\frac{p+1}{2}}{p} , p - \frac{p+1}{2}, p\} }[/math]
}

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

---

Пусть в графе [math]\displaystyle{ G }[/math] содержится [math]\displaystyle{ |V|=n }[/math] вершин.

• Для определения координат [math]\displaystyle{ iend, istart }[/math] требуется [math]\displaystyle{ O(n) }[/math] попарных сравнений
• Для сортировки массива вершин по координате требуется [math]\displaystyle{ O(nlog_{2}n) }[/math] попарных сравнений

Так как всего осуществляется [math]\displaystyle{ p-1 }[/math] шагов рекурсии, глубина ее составляет [math]\displaystyle{ -log_{2}p+1 }[/math] Значит можно определить сложность алгоритма следующим образом: [math]\displaystyle{ O(nlog_{2}nlog_{2}p) }[/math]

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

---

Рисунок 1. Информационный граф.

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

---

Структура параллельного алгоритма:

1. Подготовительный этап:
   • определение числа и объема требуемых доменов по процессорам
     • Пусть имеется граф с n вершинами, он распределяется по k доменам. Тогда глубина рекурсии - [math]\displaystyle{ log_{2}k }[/math], что равняется числу ярусов.
2. Разделение доменов по процессорам:
   • вызов рекурсивной покоординатной бисекции по процессорам:
     • сортировка вершин графа (на i-м ярусе выполняется [math]\displaystyle{ 2^i }[/math] операций)
     • разделение на два подграфа для разделения по доменам
3. Параллельные вызовы алгоритма для каждого процессора
   • вызов локальной координатной бисекции по доменам

Пусть сложность сортировки равна [math]\displaystyle{ O(n\log_2{n}) }[/math].
Тогда сложность алгоритма можно представить в следующем виде: [math]\displaystyle{ O(\sum\limits_{i=0}^{log_2{k}}\frac{n}{2^i}\log_2{\frac{n}{2^i}})= O(\sum\limits_{i=0}^{log_2{k}}(n\frac{(log_2{n}-i)}{2^i}))= O(n(\sum\limits_{i=0}^{log_2{k}}(\frac{log_2{n}}{2^i})-\sum\limits_{i=0}^{log_2{k}}(\frac{i}{2^i})))= O(n\log_2{n})-O(n)=O(n\log_2{n}) }[/math].

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

---

Вход алгоритма:

• неориентированный граф [math]\displaystyle{ G=(V, E) }[/math], где [math]\displaystyle{ V }[/math] - множество вершин, [math]\displaystyle{ E }[/math] - множество ребер
• Требуемое число доменов [math]\displaystyle{ p }[/math]

Выход алгоритма:

• [math]\displaystyle{ p }[/math] доменов [math]\displaystyle{ \{S_{p}\} }[/math], задающих декомпозицию графа

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

---

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

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

---

Существующие реализации алгоритма

---

Параллельные реализации:

• ParMETIS
• JOSTLE
• PT-SCOTCH
• ZOLTAN

Последовательные реализации:

• METIS
• JOSTLE
• SCOTCH
• CHACO
• PARTY

Литература

---

[1] Якобовский М.В. Введение в параллельные методы решения задач: Учебное пособие / Предисл.: В. А. Садовничий. – М.: Издательство Московского университета, 2012. – 328 с., илл. – (Серия «Суперкомпьютерное образование»), ISBN 978-5-211-06382-2 URL: http://lira.imamod.ru/ITTPMOPS/
[2] Головченко Е.Н. Декомпозиция расчетных сеток для решения задач механики сплошных сред на высокопроиводительных вычислительных системах. Дисс ... канд. ф.-м.наук. Институт прикладной математики им. М. В. Келдыша РАН, г. Москва URL: http://keldysh.ru/council/3/D00202403/golovchenko_diss.pdf