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

Авторы: Долгов Борис (624), Галуза Дмитрий (624)

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

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

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

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

Так как алгоритм использует предположение о том, что близкие по координатам вершины будут связаны, а удалённые по координатам вершины будут не связаны, он не подходит для разбивания произвольных графов, а лучше всего подходит для разбития координатных сеток.

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

Пусть задан [math]G = (V, E)[/math] – неориентированный граф, где [math]V[/math] -- множество вершин, [math]E[/math] -- множество рёбер. Каждой вершине соответствует целочисленный координатный вектор [math]c_i[/math], вес [math]v_i[/math]. Кроме того, задано желаемое количество доменов [math]p[/math]. Требуется разбить множество [math]V[/math] на p непересекающихся подмножеств (доменов) [math]S_1, \ldots, S_p[/math], при этом должны быть выполнены следующие требования: Домены не пересекаются: [math]S_i \cap S_j = \emptyset[/math] Каждая вершина находится в домене: [math] \cup _i S_i = V[/math] Распределение вершин по доменам примерно равномерное: [math]|S_i| \approx |V| / p[/math] Минимизирован вес разрезанных рёбер: [math]\sum_{i \neq j} \sum_{v_1 \in S_i} \sum_{v2_ \in S_j} e_{i, j} \rightarrow min[/math] Один шаг алгоритма принимает соотношение для разбиения выглядит следующим образом:

• Выполняется поиск координатной оси, имеющей максимальную протяженность. Под протяженностью понимается разность между максимальным и минимальным значением по выбранной координатной оси серди всех вершин. Сам же поиск максимума и минимума по каждой координатной оси осуществляется одним линейным проходом по вершинам. Для выбора среди разностей – производится еще один линейный проход, уже по координатным осям.
• Вершины сортируются по выбранной координатной оси. Считаем, что одна вершина “меньше” другой, если значение выбранной на предыдущем шаге координаты меньше соответствующего значения другой вершины.
• Полученные на предыдущем пункте отсортированные вершины разбиваются на два домена, согласно заданному соотношению.
• Шаг запускается рекурсивно для полученных доменов.

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

Вычислительным ядром алгоритма является один шаг алгоритма. Основной вклад в вычислительную сложность вносит сортировка вершин, которая при использовании оптимального алгоритма выполняемая со сложностью [math]O(n log_2{n})[/math]. Поиск максимально протяжённой координатной оси выполняется за линейное время, а разбиение вершин на два домена – за константное.

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

Алгоритм декомпозиции на каждом шаге может использовать любой из параллельных алгоритмов сортировки.

При использовании алгоритма сортировки со сложностью [math]S(N)[/math], сложность алгоритма составит [math]p * (S(N) + N)[/math]

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

# Шаг алгоритма
Bisect(graf, n, subgraf1, n1, subgraf2, n2) {
  dim = argmax(i, max(j, graf[j][i]) - min(j, graf[j][i]));
  sort(graf, dim);
  subgraf1 = graf[0..n1];
  subgraf2 = graf[n1+1..n-1];
}
# Схема рекурсивной бисекции
RecursiveBisect(graf, n, k) {
  k1 = (k1+1)/2;
  k2 = k-k1;
  n1=n*k1/k;
  n2=n-n1;
  Bisect(graf, n, subgraf1, n1, subgraf2, n2);
  If (k1>1) RecursiveBisect(subgraf1, n1, k1);
  If (k2>1) RecursiveBisect(subgraf2, n2, k2);
}

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

Как было описано ранее, для разбиения графа размером n на p кластеров потребуется p рекурсивных шагов. Таким образом, при использовании оптимальной стратегии разбиения, время работы можно выразить рекуррентным соотношением [math]T(N) = O(N*log_2(N)) + 2 * T(N/2)[/math]. Согласно основной теореме о рекуррентных соотношениях ссылка , [math]T(N) = O(N*log_2(N)*log_2(N))[/math] в худшем случае (при N = P). При меньшем количестве кластеров, глубина рекурсии будет ограничена [math]log_2(P)[/math], следовательно, время работы алгоритма составит [math]O(log_2(p) * N * log_2(N))[/math]

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

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

При этом на каждом шаге выполняются действия, описанные в п 1.2.

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

Так как алгоритм работает с координатной сеткой – он обладает координатным параллелизмом. Ярусно-параллельная форма алгоритма имеет высоту в [math]log_2 k[/math] уровней, где k – требуемое значение конечных доменов. Соответственно ширина яруса i будет равна [math]2^i[/math]. Так как ширина i-го яруса равна [math]2^i[/math], а общее количество вершин примем за n – то в кажом домене на i-м ярусе будет по [math]n / 2^i[/math] вершин. Если на каждом шаге использовать оптимальную параллельную сортировку, сложность которой равна [math](n/p+p)*log_2 (n/p)[/math] (где n - количество сортируемых элементов, p - количество процессоров), то получаем итоговую сложность алгоритма как сумму всех ярусов, на которых параллельно запускается оптимальная сортировка. А именно: [math]\sum_{i=0}^{log_2 k} (n / p + p) / 2^i * log_2 ((n / p + p) / 2^i) =O((n/p + p) * log_2 (n/p + p) * log_2 k)[/math]

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

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

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

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

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

Детерминированность данного алгоритма может быть достигнута, если использовать устойчивый алгоритм сортировки.

Так как процессы обрабатывают примерно равное количество вершин, полученный алгоритм является сбалансированным по числу операций на каждом процессе.