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

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

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

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

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

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

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

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

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

    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, которой осуществляется разбиение вершин на два подграфа на каждом из этапов.

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 вершины из медианы распределяются по областям произвольным образом, что увеличивает число разрезанных ребер.

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