Участник: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.4 Макроструктура алгоритма

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

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

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

Введем [math]D(n) = D_k(n)[/math] при [math]k = 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{n})[/math], например для сортировки слиянием, тогда по теореме о рекуррентном неравенстве [math]D(n) \lesssim n^{1+\varepsilon}[/math].

Для [math]D(n)[/math] есть точное значение: [math]\sum\limits_{i=0}^{\log_2{n}}2^i S(\frac{n}{2^i})[/math].

[math]D_k(n) = \sum\limits_{i=0}^{\log_2{k}}2^i S(\frac{n}{2^i})[/math]. Если использовать сортировку со сложностью [math]S(n) = [/math] [math]O(n\log{n})[/math], то [math]D_k(n) = [/math] [math]O(\sum\limits_{i=0}^{\log_2{k}}2^i \frac{n}{2^i} \log{\frac{n}{2^i}}) = [/math] [math]O(n\log(\prod\limits_{i=0}^{\log_2{k}}\frac{n}{2^i})) = [/math] [math]O(n\log{\frac{n^{\log_2{k}}}{2^\frac{\log_2{k}(\log_2{k}+1))}{2}}}) =[/math] [math] O(n(\log{n}\log{k} - \frac{\log^2_2{k}}{2})) = [/math] [math]O(n\log{n}\log{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] - для каждого домена достаточно хранить соответствующие вершинам из этого домена индексы строк в матрице, представляющей множество вершин.