Участник:Obirvalger/Метод рекурсивной координатной бисекции

Авторы: Гордеев Михаил, Колмаков Евгений.

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

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

1.1.1 Задача декомпозиции графа

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

1.1.2 Критерии декомпозиции

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

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

1.1.3 Метод рекурсивной бисекции

Метод рекурсивной координатной бисекции является частным случаем более общего метода рекурсивной бисекции. В этом методе сетка последовательно за [math]k-1[/math] шаг делится на [math]k[/math] частей. На первом шаге сетка делится на две части, далее каждая из полученных ранее частей также делится на две части и т.п. Конкретные алгоритмы деления сетки на две части (бисекции) и определяют метод рекурсивной бисекции. Соотношение размеров частей зависит количества доменов и процедуры вычисления желаемого числа вершин в каждой из формируемых частей графа.

1.1.4 Метод рекурсивной координатной бисекции

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

Метод рекурсивной координатной бисекции основан на методе рекурсивной бисекции. Для разбиения сетки на две части используется следующая процедура:

• выбирается одна из координатных осей;
• множество вершин сортируется по этой координате;
• отсортированное множество разбивается на две части, то есть указывается индекс [math]i[/math] такой, что в первую часть попадают вершины с номерами меньшими либо равными [math]i[/math], а во вторую - оставшиеся вершины; геометрически это соответствует гиперплоскости, перпендикулярной выбранной оси, которая разбивает множество вершин сетки на две части, соотношение размеров которых зависит

1.1.5 Выбор координатной оси

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

• Протяжённость области вдоль данной оси: для каждой оси вычисляется разность между максимумом и минимумом координат вершин сетки по данной оси, и выбирается ось с наибольшим значением этой величины;
• Число разрезанных ребер при разбиении сетки вдоль данной оси: вершины упорядочиваются вдоль каждой из осей, и выбирается тот вариант, который приводит к наименьшему числу разрезанных ребер;

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

Исходные данные: граф [math]G = (V, E) [/math], вложенный в [math]\mathbb{R}^N[/math] (то есть каждая вершина этого графа - это точка в [math]N[/math] мерном пространстве), и число [math]k[/math] доменов, на которое нужно разбить граф. Под декомпозицией графа на [math]k[/math] доменов понимается разбиение множества вершин [math]V[/math] на [math]k[/math] подмножеств [math]V_1, \dots, V_k[/math] таких, что

[math]V = \bigcup_{i = 1}^k V_i[/math] и [math]V_i \cap V_j = \varnothing[/math] при [math]i \neq j[/math].

С каждым доменом можно связать порождённый им подграф [math]G(V_i) = (V_i, E_i)[/math], где [math]E_i \subseteq E[/math] - множество рёбер, оба конца которых принадлежат домену.

Задача заключается в нахождении декомпозиции [math]V_1, \dots, V_k[/math], доставляющей минимум некоторого функционала (см. соответствующий пункт), например, числа разрезанных рёбер [math]E_{\mbox{cut}} = |\{(u, v) \in E \mid u \in V_i, v \in V_j, i \neq j\}| = |E| - \sum_{i = 1}^k |E_i|[/math].

Дадим формальное описание алгоритма. Как уже упоминалось, метод основан на алгоритме рекурсивной бисекции, поэтому представляет собой рекурсивную процедуру, на вход которой поступает граф [math]G = (V, E) [/math] и число доменов [math]k[/math], на которое нужно разбить множество вершин данного графа. Внутри этой процедуры выполняется следующая последовательность действий:

• в зависимости от числа доменов вычисляется "желаемое" число доменов и вершин в каждой из частей разбиения;
• вызывается процедура координатной бисекции для получения разбиения графа на две части;
• для каждой из двух полученных частей рекурсивно вызывается описываемая процедура (если число доменов для этой части больше единицы).

Процедура координатной бисекции устроена следующим образом:

• выбирается координатная ось [math]m^* \in \{1, \dots, N\}[/math];
  • в случае максимизации протяженности: для каждой оси [math]m[/math] вычисляется величина [math]l_m = \max_{v \in V} v_m - \min_{v \in V} v_m[/math], и выбирается ось [math]m^* = \arg\max_{m \in \{1, \dots, N\}} l_m[/math];
  • в случае минимизации числа разрезанных ребер: вершины упорядочиваются вдоль каждой из осей, для каждой оси вычисляется величина [math]E^m_{\mbox{cut}}[/math], равная числу разрезанных ребер при разбиении вдоль данной оси, и выбирается ось [math]m^* = \arg\max_{m \in \{1, \dots, N\}} E^m_{\mbox{cut}}[/math];
• множество вершин сортируется по возрастанию координаты с номером [math]m^*[/math];
• отсортированный массив вершин делится на две (непрерывные) части в соответствии с желаемым числом вершин в каждой из частей;
  • как правило, выбирается индекс [math]i = \lfloor\frac{k+1}{2k}\rfloor \cdot |V|[/math], соответствующий примерно равному разделению текущего графа на части;
• первая часть состоит из вершин [math]v \in V[/math] с индексами [math]j \leqslant i[/math], вторая - с индексами [math]j \gt i[/math].

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

Вычислительное ядро алгоритма составляют сортировки массива вершин сетки по выбранной координате при каждом из [math]k - 1[/math] вызовов процедуры бисекции.

Также, в зависимости от критерия выбора координатной оси, требуются дополнительные вычисления:

• В случае максимизации протяженности при каждом вызове требуется вычисление величины [math]l_m[/math].
• В случае минимизации числа разрезанных ребер при каждом вызове требуется сортировка по каждой из координат (таким образом, при каждом разбиении осуществляется [math]N[/math] сортировок).

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

Как записано в описании ядра алгоритма, основную часть метода составляют множественные (всего [math]k-1[/math]) сортировки (функция sort).

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

Обозначим через [math]D_k(n)[/math] сложность алгоритма рекурсивной координатной бисекции для декомпозиции графа с [math]n[/math] вершинами на [math]k[/math] доменов.

Определим величину [math]D(n) = D_n(n)[/math]. Для [math]D(n)[/math] имеет место следующее рекуррентное равенство:

[math] \begin{array}{l} D(n) = S(n) + 2D(\frac{n}{2}) \\ D(1) = S(1) = 0. \\ \end{array} [/math], где [math]S(n)[/math] - это сложность алгоритма сортировки массива из [math]n[/math] элементов.

Пусть [math]S(n) = O(n\log_2{n})[/math] (например, для сортировки слиянием), тогда по теореме о рекуррентном неравенстве для произвольного положительного [math]\varepsilon[/math] имеет место оценка [math]D(n) \lesssim n^{1+\varepsilon}[/math].

Величину [math]D_k(n)[/math] можно явно посчитать по формуле [math]\sum\limits_{i=0}^{\lceil\log_2{k}\rceil}2^i S(\frac{n}{2^i})[/math]. Если использовать сортировку со сложностью [math]S(n) = O(n\log{n})[/math], то

[math]D_k(n) = [/math] [math]O(\sum\limits_{i=0}^{\lceil\log_2{k}\rceil}2^i \frac{n}{2^i} \log_2{\frac{n}{2^i}}) = [/math] [math]O(n\log_2(\prod\limits_{i=0}^{\lceil\log_2{k}\rceil}\frac{n}{2^i})) = [/math] [math]O(n\log_2{\frac{n^{\log_2{k}}}{2^\frac{\log_2{k}(\log_2{k}+1))}{2}}}) =[/math] [math] O(n(\log_2{n}\log_2{k} - \frac{\log^2_2{k}}{2})) = [/math] [math]O(n\log{n}\log{k})[/math].

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

Данный алгоритм обладает координатным параллелизмом. Для декомпозиции графа с [math]n[/math] вершинами на [math]k[/math] доменов методом рекурсивной координатной бисекции в параллельном варианте требуется последовательно выполнить [math]\lceil\log_2{k}\rceil[/math] ярусов. На [math]i[/math]-ом ярусе будет выполнятся [math]2^i[/math] операций сортировки. Рассмотрим два случая распараллеливания нашего алгоритма:

• Параллельное выполнение операций на каждом ярусе с использованием последовательного алгоритма сортировки со сложностью [math]O(n\log{n})[/math].

1. На первом шаге один процессор производит сортировку всех вершин, разделяет граф на два подграфа и передает однин из подрафов новому процессору.
2. На [math]i[/math]-ом шаге каждый из уже получивший свой граф процессор производит сортировку всех вершин, разделяет граф на два подграфа и передает однин из подрафов новому процессору.

Тогда сложность нашего алгоритма равна:

[math]D_k(n) = O(\sum\limits_{i=0}^{\lceil\log_2{k}\rceil}\frac{n}{2^i} \log_2{\frac{n}{2^i}}) = [/math] [math]n\sum\limits_{i=0}^{\lceil\log_2{k}\rceil}(\frac{\log_2{n}}{2^i} - \frac{i}{2^i}) = [/math] [math]O(n\log_2{n}) - O(n) = O(n\log{n})[/math].

• Параллельное выполнение операций на каждом ярусе с использованием параллельного алгоритма сортировки со сложностью [math]O(\log_2^2{n})[/math].

На каждом шаге производится параллельная сортировка вершин и разбиение графа на два подграфа. В этом случае [math]D_k(n) = \sum\limits_{i=0}^{\lceil\log_2{k}\rceil}log^2\frac{n}{2^i} = O(\log^2{n}\log^2{k})[/math].

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

Входные данные: граф [math]G = (V, E) [/math], вложенный в [math]\mathbb{R}^N[/math], и число [math]k[/math] частей (доменов), на которое нужно разбить граф. Таким образом, помимо матрицы смежности (или любого другого представления графа) для каждой вершины [math]v \in V[/math] задан набор её координат [math]v = (v_1, \dots, v_N) \in \mathbb{R}^N[/math], поэтому [math]V[/math] задаётся массивом [math]N[/math]-мерных векторов или матрицей размера [math]|V| \times N[/math].

Объём входных данных: [math]N|V| + |G|[/math], где [math]|G|[/math] - объём данных, представляющих граф [math]G[/math], который в общем случае зависит от выбранного представления.

Выходные данные: [math]k[/math] доменов графа [math]G[/math], задающих его декомпозицию.

Объём выходных данных: [math]|V|[/math] - для каждого домена достаточно хранить соответствующие вершинам из этого домена индексы строк в матрице, представляющей множество вершин.

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

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

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

Последовательная версия алгоритма реализована в пакетах Chaco, JOSTLE, METIS, SCOTCH.

Параллельная версия реализована в пакетах JOSTLE, ParMETIS, PT-SCOTCH.

Стоит отметить, что пакеты METIS и ParMETIS распространяются свободно.

3 Литература

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