Участник:Fokina/Рекурсивная координатная бисекция

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

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

Метод рекурсивной координатной бисекции был предложен Бергером (M. Berger) и Бохари (S. Bokhari) в 1987 году для решения задачи статической баланисировки загрузки. В основе метода лежит идея равномерного разбиения точек в пространстве с помощью гиперплоскостей.

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

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

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

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

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

На каждом этапе рекурсивной координатной бисекции происходит следующее:

1. Определяются границы наименьшего параллелепипеда, охватывающего все вершины, которые делятся на данном этапе. Вычисляются максимумы по каждой из координат. Определяется координата [math]j[/math], вдоль которой параллелепипед имеет наибольшую протяженность.
2. Выполняется сортировка вершин по координате [math]j[/math].
3. Создается два новых поддомена. Первая половина вершин из отсортированного домена помещается в первый поддомен, все последующие -- в второй.

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

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

void
recursive_bisect(struct Vertex *graph, int n, int k) {
    int                             k1, k2;
    int                             n1, n2;
    struct Vertex *                 subgraph1;
    struct Vertex *                 subgraph2;

    k1 = (k + 1) / 2;
    k2 = k - k1;
    n1 = n * k1 / k;
    n2 = n - n1;

    bisect(graph, n, subgraph1, n1, subgraph2, n2);
    
    if (k1 > 1) recursive_bisect(subgraph1, n1, k1);
    if (k2 > 1) recursive_bisect(subgraph2, n2, k2);

    return;
}

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

void
coord_bisect(struct Vertex *graph, int n, struct Vertex *subgraph1, int n1, struct Vertex *subgraph2, int n2) {
    int                             axis;

    /* Calculate direction in which the initial graph is most elongated. */
    axis = calculate_max_distance(graph, n);

    /* Sort vertices along the selected axis. */
    sort(graph, n, axis);

    /* Create subgraphs. */
    subgraph1 = create_subgraph(graph, 0, n1);
    subgraph2 = create_subgraph(graph, n1, n);

    return;
}

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

В течение каждого этапа выполняются следующие действия:

1. Определение диаметра графа по каждой из координат -- [math]m*O(n)[/math], где [math]m[/math] -- размерность пространства, [math]n[/math] -- количество вершин. Поскольку величина [math]m[/math], как правило, очень мала, ей можно пренебречь, оставив в качестве оценки сложности данного действия [math]O(n)[/math].
2. Поиск максимального расстояния -- осуществляется за [math]O(m)[/math], также пренебрежимо мало.
3. Сортировка. Наиболее эффективным алгоритмом последовательной сортировки является комбинация сортировки слиянием и пирамидальной сортировки . Сложность как пирамидальной сортировки, так и сортировки слиянием оценивается как [math]O(nlog_2(n))[/math].
4. Разбиение домена на поддомены осуществляется за [math]O(1)[/math].

Исходя из этого, общая сложность каждой итерации оценивается сверху как [math]O(nlog_2(n))[/math], а их количество составляет [math](k - 1)[/math]. Таким образом, последовательная сложность метода -- [math]O((k-1) *n*log(n))[/math].

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

На рисунке 1 приведена общая схема работы метода. Входными данными является граф -- массив вершин, заданных в виде векторов координат. Выходными данными является множество массивов, элементами которых являются исходные вершины.

Рис. 1. Общая схема рекурсивной координатной бисекции

На рисунке 2 изображен информационный граф метода при распределении домена из 4 вершин, заданных в двумерном пространстве, на 2 поддомена. Входными данными являются вектора A1-A4, которые могут содержаться либо в исходном домене, либо в поддомене, полученном на предыдущей итерации. Выходные данные -- непересекающиеся множества векторов B1 и B2. В них содержатся вектора A1-A4. Вершины с меткой CD обозначают операцию вычисления диаметра домена (т.е. наибольшего расстояния между содержащимися в домене вершинами) по координатам [math]x[/math] и [math]y[/math] соответственно. Вершина MAX обозначает нахождение максимума, SORT -- сортировку, SPLIT -- разбиение домена на два поддомена равного размера.

Рис. 2. Информационный граф для одной итерации

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

При разбиении графа на [math]k[/math] подграфов глубина рекурсии составляет [math]\lceil log_2 k \rceil[/math], а на каждом [math]i[/math] шаге решается до [math]2^i[/math] подзадач. Поскольку подзадачи, возникающие на каждом шаге рекурсии, не имеют информационных зависимостей друг между другом, их решение можно распараллелить, получив таким образом некоторый прирост производительности. Исходя из того, что сложность этих подзадач примерно одинакова, можно считать, что их решение занимает примерно одинаковое время [math]t[/math] и не зависит от яруса, на котором решается конкретная подзадача. При разбиении графа на [math]k[/math] подграфов требуется решить [math]k-1[/math] подзадач. Время их последовательного выполнения составляет [math]T_1 = t*(k-1)[/math]. Пусть доступно бесконечное число одинаковых процессоров. При распараллеливании затраченное время сокращается до [math]T_\infty(k) = t * \lceil log_2 k \rceil[/math]. Таким образом, предельное ускорение от распараллеливания рекурсивной бисекции составляет [math]S(k) = \frac{T_1(k)}{T_\infty(k)} = \frac{k-1}{\lceil log_2 k \rceil}[/math].

Если количество доступных процессоров ограничено некоторым числом [math]p[/math], то имеет место следующее соотношение: [math]S(k, p) = \frac{p * \lfloor log_2 k \rfloor}{2*p - 2 + \lfloor log_2 k \rfloor - \lceil log_2 p \rceil}[/math].

Использование параллельного алгоритма рекурсивной координатной бисекции целесообразно при разбиении на большое число подграфов.

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

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

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

Метод рекурсивной координатной бисекции работает над графами, часто -- сеточными. Поскольку метод не учитывает связи между вершинами, входные данные удобно задавать в виде массива координат в [math]n[/math]-мерном прострастве, т.е. векторов размерности [math]n[/math]. Как правило, в прикладных задачах [math]n[/math] составляет 2 или 3, т.е. заданы координаты на плоскости или в объеме.

Входные данные алгоритма: Исходный граф [math]G[/math], натуральное число [math] k \in \N [/math] -- количество подграфов, на которое нужно осуществить разбиение.

Выходные данные алгоритма: Множество [math]G_1 .. G_k[/math] подграфов исходного графа [math]G[/math].

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

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

Наиболее широко в настоящее время применяется параллельный алгоритм рекурсивной координатной бисекции, реализованный в пакете ZOLTAN (Zoltan2) [1].

Метод рекурсивной координатной бисекции сеток реализован в пакете GridSpiderPar [2]. Использованный в нем алгоритм отличается от аналогичного алгоритма в пакете ZOLTAN тем, что в нем секущая плоскость (медиана) при необходимости разрезается по нескольким координатам. Это позволяет обрабатывать ситуации наличия на одной плоскости множества узлов с одинаковым значением координаты, что характерно для регулярных сеток. В пакете ZOLTAN вершины из медианы распределяются по областям произвольным образом, что увеличивает число разрезанных ребер.

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