Последовательно-параллельный метод нахождения всех частных выражений для ассоциативных операций
Содержание
- 1 Описание свойств и структуры алгоритма
- 1.1 Словесное описание алгоритма
- 1.2 Математическое описание
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Описание схемы реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Описание ресурса параллелизма алгоритма
- 1.9 Описание входных и выходных данных
- 1.10 Свойства алгоритма
- 2 Программная реализация
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Описание локальности данных и вычислений
- 2.3 Возможные способы и особенности реализации параллельного алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
1 Описание свойств и структуры алгоритма
1.1 Словесное описание алгоритма
1.1.1 Решаемая задача
Пусть у нас на входе есть некоторый массив данных, записанный в вектор [math]\vec{x}[/math] размерности [math]n[/math]. При этом нам на выходе нужно выдать все результаты вычислений частных результатов последовательного выполнения некоторой ассоциативной операции [math]\circ[/math], то есть для всех [math]i[/math] от [math]1[/math] до [math]n[/math] вычислить выражения типа
- [math]x_1 \circ x_2 \circ \cdots \circ x_{i - 1} \circ x_i[/math]
Подобная задача возникает во многих случаях: при нахождении частных максимумов, сумм, произведений, при решении двухдиагональных (в т. ч. блочных) систем линейных алгебраических уравнений, при выполнении схемы Горнера и т. п. В каждом конкретном случае у решения задачи последовательно-параллельным методом будут свои особенности, описанные в соответствующем разделе. Здесь же мы опишем алгоритм общего вида. Операцию [math]\circ[/math] будем называть «суммирование».
1.1.2 Алгоритм
При использовании последовательно-параллельного метода массив разбивается на [math]p[/math] кусков (каждый кусок — на своём «процессоре»), в каждом из которых сначала частные выражения вычисляются обычным последовательным способом, после чего, используя ассоциативность операции, производится «сборка» полных частных выражений.
1.2 Математическое описание
Исходные данные: одномерный массив [math]n[/math] чисел.
Вычисляемые данные: [math]n[/math] частных выражений, получаемых каждое из некоторого числа начальных элементов массива.
Формулы метода: число [math]n[/math] разлагается в выражение типа [math]n = (p - 1) k + q[/math], где [math]p[/math] — количество процессоров, [math]k = \lceil \frac{n}{p} \rceil[/math], [math]q = n - k (p - 1)[/math].
После этого на [math]i[/math]-м процессоре ([math]i \lt p[/math]) последовательно вычисляется «сумма» (частное выражение для данной ассоциативной операции) элементов массива, начиная с [math](i - 1) k + 1[/math]-го, до [math]i k[/math]-го.
- [math]S_i = \bigcirc_{j = 1}^k x_{k (i - 1) + j}[/math]
На [math]p[/math]-м процессоре последовательно вычисляется сумма элементов массива, начиная с [math](p - 1) k + 1[/math]-го до [math](p - 1) k + q[/math]-го.
- [math]S_i = \bigcirc_{j = 1}^q x_{k (p - 1) + j}[/math]
По окончании этого процесса процессоры обмениваются данными и на одном из них получившиеся полные выражения для всех процессоров «суммируются» последовательно друг с другом
- [math]\bigcirc_{i = 1}^p S_i[/math]
а к частным выражениям каждого из процессоров добавляются полные суммы всех предыдущих выражений.
Удобно сразу рассмотреть граф алгоритма, до пункта «Информационный граф», поскольку графическое представление довольно наглядно даёт математику алгоритма. Здесь [math]'''n = 20'''[/math]. В первом горизонтальном столбце идут вычисления готовых частных результатов для [math]i[/math] от 1 до 5 (для 1 он уже готов и равен [math]x_1[/math]). Во втором — промежуточные частные результаты, где используются элементы от 6-го до 10-го (6-й берётся готовым), в третьем (пока считаем только столбцы, которые используют входные данные) — от 11-го до 15-го (11-й берётся готовым), в четвёртом — от 16-го до 20-го (16-й — готовый). После вычисления в указанных столбцах вычисляются операции в оставшихся столбцах: в первом вычисляются окончательные частные результаты с 6-го по 10-й, во втором — с 11-го по 15-й, в третьем — с 16-го по 20-й.
1.3 Вычислительное ядро алгоритма
Вычислительное ядро последовательно-параллельного метода можно составить из множественных (всего [math]p[/math]) вычислений «обобщённых сумм» элементов массива:
- [math]S_i = \bigcirc_{j = 1}^k x_{k (i - 1) + j}[/math]
и ещё [math]n - k[/math] вычислений частных результатов.
1.4 Макроструктура алгоритма
Как уже записано в описании ядра алгоритма, основную часть метода составляют множественные (всего [math]p[/math]) вычисления «обобщённых сумм»
- [math]S_i = \bigcirc_{j = 1}^k x_{k (i - 1) + j}[/math]
а также [math]n - k[/math] вычислений частных результатов.
1.5 Описание схемы реализации последовательного алгоритма
Формулы метода описаны выше. Последовательность исполнения суммирования может быть разная — как по возрастанию, так и по убыванию индексов. Обычно, однако, этот алгоритм в его последовательном виде не применяют, поскольку в нём присутствует [math]n - k - p[/math] избыточных по сравнению с последовательным методом операций.
1.6 Последовательная сложность алгоритма
Для вычисления полной «суммы» массива, состоящего из [math]n[/math] элементов, при любых разложениях [math]n[/math] суть алгоритма сводится к простому переставлению скобок в формуле «суммирования», и количество операций неизменно и равно [math]n - 1[/math]. Кроме этого, [math]n - k - p[/math] операций выполняется избыточно. Поэтому алгоритм должен быть отнесён к алгоритмам линейной сложности по количеству последовательных операций.
1.7 Информационный граф
Граф алгоритма в виде рисунка изображён выше.
1.8 Описание ресурса параллелизма алгоритма
Для «суммирования» массива порядка n последовательно-параллельным методом в параллельном варианте требуется последовательно выполнить следующие ярусы:
- [math]k - 1[/math] ярусов «суммирования» по частям массива ([math]p[/math] ветвей),
- [math]p - 1[/math] ярусов «суммирования» ([math]k[/math] ветвей).
Таким образом, в параллельном варианте критический путь алгоритма (и соответствующая ему высота ЯПФ) будет зависеть от произведённого разбиения массива на части. В оптимальном случае ([math]p = k = \sqrt{n}[/math]) высота ЯПФ будет равна [math]2 \sqrt{n} - 2[/math].
При классификации по высоте ЯПФ, таким образом, последовательно-параллельный метод относится к алгоритмам со сложностью корень квадратный. При классификации по ширине ЯПФ его сложность будет такой же — корень квадратный.
1.9 Описание входных и выходных данных
Входные данные: массив [math]\vec{x}[/math] (элементы [math]x_i[/math]).
Дополнительные ограничения: отсутствуют.
Объём входных данных: [math]n[/math].
Выходные данные: [math]n[/math] частных «сумм» элементов массива.
Объём выходных данных: [math]n[/math].
1.10 Свойства алгоритма
Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является корнем квадратным (отношение линейной к корню квадратному). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего 1 (входных и выходных данных столько же, сколько операций). При этом алгоритм не вполне полностью детерминирован, суммирование может быть проведено в разном порядке. Использование другого порядка выполнения ассоциативных операций может дать, с учётом особенностей входных данных, уменьшение влияния ошибок округления на результат. Дуги информационного графа частично локальны (в случае нелокальности имеют место пучки рассылочных дуг).
2 Программная реализация
В простейшем (без перестановок суммирования) варианте на Фортране можно записать так:
DO I = 1, P
SUM (K*(I-1)+1) = X(K*(I-1)+1)
IF (I.LQ.P) THEN
DO J = 2,K
SUM(K*(I-1)+J)=SUM(K*(I-1)+J-1)+X(K*(I-1)+J)
END DO
ELSE
DO J = 2,Q
SUM(K*(I-1)+J)=SUM(K*(I-1)+J-1)+X(K*(I-1)+J)
END DO
END IF
END DO
DO I = 2,P
IF (I.LQ.P) THEN
DO J = 1,K
SUM(K*(I-1)+J)=SUM(K*(I-1)+J)+SUM(K*(I-1))
END DO
ELSE
DO J = 1,Q
SUM(K*(I-1)+J)=SUM(K*(I-1)+J)+SUM(K*(I-1))
END DO
END IF
END DO
Можно записать и аналогичные схемы, где суммирование будет проводиться в обратном порядке. Подчеркнём, что граф алгоритма обеих схем - один и тот же!
2.1 Особенности реализации последовательного алгоритма
2.2 Описание локальности данных и вычислений
2.2.1 Описание локальности алгоритма
2.2.2 Описание локальности реализации алгоритма
2.2.2.1 Описание структуры обращений в память и качественная оценка локальности
2.2.2.2 Количественная оценка локальности
2.2.2.3 Анализ на основе теста Apex-Map
2.3 Возможные способы и особенности реализации параллельного алгоритма
2.4 Масштабируемость алгоритма и его реализации
2.4.1 Описание масштабируемости алгоритма
2.4.2 Описание масштабируемости реализации алгоритма
2.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
В чистом виде алгоритм последовательно-параллельного метода встречается редко, чаще ему предпочитают схему сдваивания. В последовательном варианте из-за избыточности вычислений его вообще почти не применяют.