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

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

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 Существующие реализации алгоритма

GridSpiderPar [1]

Zoltan2 [2]