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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 9: Строка 9:
 
=== Информационный граф ===
 
=== Информационный граф ===
 
=== Ресурс параллелизма алгоритма ===
 
=== Ресурс параллелизма алгоритма ===
 +
При разбиении графа на <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>.
 +
 +
Использование параллельного алгоритма рекурсивной координатной бисекции целесообразно при разбиении на большое число подграфов.
 +
 +
Наибольшее ускорение достигается при разбиении на число подграфов, являющееся степенью двойки.
 +
 +
Наибольшее ускорение достигается при использовании числа процессоров, являющегося степенью двойки.
 +
 
=== Входные и выходные данные алгоритма ===
 
=== Входные и выходные данные алгоритма ===
 
=== Свойства алгоритма ===
 
=== Свойства алгоритма ===

Версия 19:52, 15 октября 2016

Содержание

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

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

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

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

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

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

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

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

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 Входные и выходные данные алгоритма

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

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

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.4.1 Масштабируемость алгоритма

2.4.2 Масштабируемость реализации алгоритма

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

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

GridSpiderPar [1]

Zoltan2 [2]

3 Литература