Уровень алгоритма

Последовательно-параллельный метод суммирования: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][досмотренная версия]
 
(не показано 38 промежуточных версий 10 участников)
Строка 1: Строка 1:
== Описание свойств и структуры алгоритма ==
+
{{level-a}}
  
=== Словесное описание алгоритма ===
+
Основные авторы описания: [[Участник:Frolov|А.В.Фролов]].
  
'''Последовательно-параллельный метод''' используется в качестве блочной реализации вычисления длинных последовательностей ассоциативных операций (например, массового суммирования). Получил распространение благодаря следующим особенностям: а) реализует приём получения двойных циклов из одинарных; б) в последовательной архитектуре компьютеров позволял для ряда операций уменьшать влияние округления на результат. Здесь будем описывать его версию для суммирования чисел.
+
== Свойства и структура алгоритма ==
  
=== Математическое описание ===
+
=== Общее описание алгоритма ===
 +
 
 +
'''Последовательно-параллельный метод''' используется в качестве эрзаца блочной реализации вычисления длинных последовательностей ассоциативных операций (например, массового суммирования). Получил распространение благодаря следующим особенностям: а) реализует приём получения двойных циклов из одинарных; б) в последовательной архитектуре компьютеров позволял для ряда операций уменьшать влияние округления на результат. Здесь будем описывать его версию для суммирования чисел.
 +
 
 +
=== Математическое описание алгоритма ===
  
 
Исходные данные: одномерный массив <math>N</math> чисел.
 
Исходные данные: одномерный массив <math>N</math> чисел.
Строка 36: Строка 40:
 
:<math>\sum_{i = 1}^p S_i</math>
 
:<math>\sum_{i = 1}^p S_i</math>
  
=== Описание схемы реализации последовательного алгоритма ===
+
=== Схема реализации последовательного алгоритма ===
  
 
Формулы метода описаны выше. Последовательность исполнения суммирования может быть разная — как по возрастанию, так и по убыванию индексов. Обычно без особых причин порядок не меняют, используя естественный (возрастание индексов).
 
Формулы метода описаны выше. Последовательность исполнения суммирования может быть разная — как по возрастанию, так и по убыванию индексов. Обычно без особых причин порядок не меняют, используя естественный (возрастание индексов).
Строка 46: Строка 50:
 
=== Информационный граф ===
 
=== Информационный граф ===
  
Опишем граф алгоритма в виде рисунка. В данном случае выполнено суммирование 30 элементов массива.
+
На рис.1 изображён граф алгоритма. В данном случае выполнено суммирование 24 элементов массива.
 +
 
 +
[[file:series-parallel summation graph.png|center|thumb|600px|Рисунок 1. Последовательно-параллельный метод суммирования массива]]
  
[[file:series-parallel summation graph.png|center|thumb|600px]]
+
<center>
 +
{{#widget:Algoviewer
 +
|url=seq_par/Algo_view_seq_par4.html
 +
|width=1300
 +
|height=800
 +
|border=1
 +
}}
 +
<br/>
 +
Интерактивное изображение графа алгоритма без входных и выходных данных для случая суммирования 20 элементов массива
 +
</center>
  
 
=== Описание ресурса параллелизма алгоритма ===
 
=== Описание ресурса параллелизма алгоритма ===
Строка 60: Строка 75:
 
При классификации по высоте ЯПФ, таким образом, последовательно-параллельный метод относится к алгоритмам со сложностью ''корень квадратный''. При классификации по ширине ЯПФ его сложность будет такой же — ''корень квадратный''.
 
При классификации по высоте ЯПФ, таким образом, последовательно-параллельный метод относится к алгоритмам со сложностью ''корень квадратный''. При классификации по ширине ЯПФ его сложность будет такой же — ''корень квадратный''.
  
=== Описание входных и выходных данных ===
+
=== Входные и выходные данные алгоритма ===
  
 
Входные данные: массив <math>\vec{x}</math> (элементы <math>x_i</math>).
 
Входные данные: массив <math>\vec{x}</math> (элементы <math>x_i</math>).
Строка 76: Строка 91:
 
Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''корнем квадратным'' (отношение линейной к корню квадратному). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего ''1 (входных и выходных данных столько же, сколько операций)''. При этом алгоритм не вполне полностью детерминирован, суммирование может быть проведено в разном порядке. Использование другого порядка выполнения ассоциативных операций может дать, с учётом особенностей входных данных, уменьшение влияния ошибок округления на результат. Дуги информационного графа локальны.
 
Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''корнем квадратным'' (отношение линейной к корню квадратному). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего ''1 (входных и выходных данных столько же, сколько операций)''. При этом алгоритм не вполне полностью детерминирован, суммирование может быть проведено в разном порядке. Использование другого порядка выполнения ассоциативных операций может дать, с учётом особенностей входных данных, уменьшение влияния ошибок округления на результат. Дуги информационного графа локальны.
  
== Программная реализация ==
+
== Программная реализация алгоритма ==
  
 
=== Особенности реализации последовательного алгоритма ===
 
=== Особенности реализации последовательного алгоритма ===
Строка 102: Строка 117:
 
Можно записать и аналогичные схемы, где суммирование будет проводиться в обратном порядке. Подчеркнём, что граф алгоритма обеих схем — [[#Информационный граф|один и тот же]]!
 
Можно записать и аналогичные схемы, где суммирование будет проводиться в обратном порядке. Подчеркнём, что граф алгоритма обеих схем — [[#Информационный граф|один и тот же]]!
  
=== Описание локальности данных и вычислений ===
+
=== Возможные способы и особенности параллельной реализации алгоритма ===
==== Описание локальности алгоритма ====
 
==== Описание локальности реализации алгоритма ====
 
===== Описание структуры обращений в память и качественная оценка локальности =====
 
  
[[file:Seqpar sum 1.PNG|thumb|center|700px|Рисунок 12.1. Суммирование элементов массива. Общий профиль обращений в память]]
+
В чистом виде алгоритм последовательно-параллельного метода для суммирования массива встречается редко, в основном встречаются его модификации, например для случаев вычисления скалярного произведения (вместо элементов массива будут фигурировать произведения элементов двух массивов), равномерной нормы (вместо элементов массива — их модули) и т. п. В случае вычисления скалярного произведения в одном из частных случаев подобный приём применён в библиотеке BLAS (там одна из размерностей равна 5), но, видимо, не для распараллеливания, а для оптимизации работы с регистрами процессора. Между тем, разбиения массивов на группы для вычислений частных сумм могут быть полезны и для лучшего использования кэша на отдельных узлах.
  
На рис. 12.1 представлен профиль обращений в память для суммирования элементов массива. Данный профиль состоит из обращений к двум массивам, фрагменты для отдельных массивов выделены на рис. 12.1 зеленым цветом. Поскольку мы рассматриваем последовательную реализацию последовательно-параллельного метода суммирования, строение профиля практически никак не зависит от выбранного количества ветвей – будет меняться только число задействованных элементов во фрагменте 1.
+
=== Результаты прогонов ===
 
+
=== Выводы для классов архитектур ===
Фрагмент 2 устроен очень просто и представляет собой последовательный перебор всех элементов массива. Фрагмент 1 состоит из двух одинаковых переборов элементов массива, что хорошо видно из рис. 12.2, где данный фрагмент рассмотрен отдельно.
 
 
 
[[file:Seqpar sum 2.jpg|thumb|center|400px|Рисунок 12.2. Фрагмент 1 (профиль обращений к первому массиву)]]
 
 
 
Данные фрагмент характеризуются высокой пространственной локальностью и низкой временной, поскольку практически отсутствуют повторные обращения.
 
 
 
===== Количественная оценка локальности =====
 
 
 
Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.
 
 
 
На рисунке 12.3 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что значение данной оценки достаточно высоко и близко к последовательно-параллельному скалярному произведению двух векторов, что является закономерным вследствие однотипности структуры выполняемых операций.
 
 
 
[[file:Seqpar sum daps ru.PNG|thumb|center|700px|Рисунок 12.3. Сравнение значений оценки daps]]
 
 
 
Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.
 
 
 
На рисунке 12.4 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Можно увидеть, что, согласно данной оценке, локальность профиля достаточно высока, что коррелирует со значением оценки daps.
 
  
[[file:Seqpar sum cvg.PNG|thumb|center|700px|Рисунок 12.4. Сравнение значений оценки cvg]]
+
== Литература ==
  
=== Возможные способы и особенности реализации параллельного алгоритма ===
+
<references />
=== Масштабируемость алгоритма и его реализации ===
 
==== Описание масштабируемости алгоритма ====
 
==== Описание масштабируемости реализации алгоритма ====
 
[[file:Масштабируемость производительность ссумирования элементов массива.png|thumb|center|700px|Рисунок 1. Параллельная реализация Сумирования элементов массива Максимальная производительность. ]]
 
[[file:Масштабируемость суммирования элементов массива Эффективность.png|thumb|center|700px|Рисунок 2. Параллельная реализация сумирования элементов массива Максимальная эффективность. ]]
 
Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:
 
* число процессоров [2 : 256]
 
* размер вектора [80000000:320000000]
 
Эффективность выполнения реализации алгоритма
 
* Минимальная эффективность 0,00004%
 
* Максимальная эффективность 0,0037%
 
Оценка масштабируемости
 
* По числу процессов: -3.059e-06 – при увеличении числа процессов эффективность уменьшается на рассмотренной области изменений параметров запуска, однако, в целом уменьшение не интенсивное. Это объясняется тем, что при увеличении числа процессов доля сильно возрастают накладные расходы на организацию схемы сдваивания сумирования, однако так, как общая эффективность составляет доли процента интенсивность сильная только при переходе от работы процессов в рамках одного физического узла к использованию коммуникационной сети. В остальной области рассмотренных значений параметров запуска эффективность близка к 0 в силу того, что на каждый процесс приходится черезвычайно малая доля вычислений. Больше полезного времени уходит на организацию работы процессов.
 
* По размеру задачи: 6.426e-09 – при увеличении размера задачи эффективность в целом очень незначительно увеличивается по рассматриваемой области. Это объясняется общим увеличением вычислительной сложности задачи в связи с увеличением размерности. Однако вычислительная сложность алгоритма <math>(N-1)</math>не позволяет существенно увеличить долю времени затрачиваемую на вычисления.
 
* По двум направлениям: -8.047e-08 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, однако интенсивность уменьшения эффективности небольшая. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров несущественная говорит о том, что на поверхности присутствуют области с очень интенсивным изменением эффективности на участке 2-16 процессов, но очень малые по площади. На остальной поверхности изменения эффективности незначительны и находятся на приблизительно одном и том же уровне.
 
  
=== Динамические характеристики и эффективность реализации алгоритма ===
+
[[Категория:Законченные статьи]]
=== Выводы для классов архитектур ===
+
[[Категория:Последовательно-параллельная группировка операций]]
=== Существующие реализации алгоритма ===
+
[[Категория:Векторные операции]]
  
В чистом виде алгоритм последовательно-параллельного метода для суммирования массива встречается редко, в основном встречаются его модификации, например для случаев вычисления скалярного произведения (вместо элементов массива будут фигурировать произведения элементов двух массивов), равномерной нормы (вместо элементов массива — их модули) и т. п. В случае вычисления скалярного произведения в одном из частных случаев подобный приём применён в библиотеке BLAS (там одна из размерностей равна 5), но, видимо, не для распараллеливания, а для оптимизации работы с регистрами процессора. Между тем, разбиения массивов на группы для вычислений частных сумм могут быть полезны и для лучшего использования кэша на отдельных узлах.
+
[[En:The serial-parallel summation method]]

Текущая версия на 15:10, 8 июля 2022


Основные авторы описания: А.В.Фролов.

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

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

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

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

Исходные данные: одномерный массив [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 = \sum_{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_p = \sum_{j = 1}^q x_{k (p - 1) + j}[/math]

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

[math]\sum_{i = 1}^p S_i[/math]

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

Вычислительное ядро последовательно-параллельного метода суммирования можно составить из множественных (всего [math]p[/math]) вычислений сумм элементов массива:

[math]S_i = \sum_{j = 1}^k x_{k (i - 1) + j}[/math]

и ещё одного вычисления суммы элементов частичных сумм

[math]\sum_{i = 1}^p S_i[/math]

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

Как уже записано в описании ядра алгоритма, основную часть метода составляют множественные (всего [math]p + 1[/math]) вычисления сумм

[math]S_i = \sum_{j = 1}^k x_{k (i - 1) + j}[/math]
[math]\sum_{i = 1}^p S_i[/math]

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

Формулы метода описаны выше. Последовательность исполнения суммирования может быть разная — как по возрастанию, так и по убыванию индексов. Обычно без особых причин порядок не меняют, используя естественный (возрастание индексов).

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

Для вычисления суммы массива, состоящего из [math]N[/math] элементов, при любых разложениях [math]N[/math] суть алгоритма сводится к простому переставлению скобок в формуле суммирования, и количество операций неизменно и равно [math]N - 1[/math]. Поэтому алгоритм должен быть отнесён к алгоритмам линейной сложности по количеству последовательных операций.

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

На рис.1 изображён граф алгоритма. В данном случае выполнено суммирование 24 элементов массива.

Рисунок 1. Последовательно-параллельный метод суммирования массива


Интерактивное изображение графа алгоритма без входных и выходных данных для случая суммирования 20 элементов массива

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

Для суммирования массива порядка [math]n[/math] последовательно-параллельным методом в параллельном варианте требуется последовательно выполнить следующие ярусы:

  • [math]k - 1[/math] ярусов суммирования по частям массива ([math]p[/math] ветвей),
  • [math]p - 1[/math] ярусов суммирования (одна последовательная ветвь).

Таким образом, в параллельном варианте критический путь алгоритма (и соответствующая ему высота ЯПФ) будет зависеть от произведённого разбиения массива на части. В оптимальном случае ([math]p = \sqrt{n}[/math]) высота ЯПФ будет равна [math]2 \sqrt{n} - 2[/math].

При классификации по высоте ЯПФ, таким образом, последовательно-параллельный метод относится к алгоритмам со сложностью корень квадратный. При классификации по ширине ЯПФ его сложность будет такой же — корень квадратный.

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

Входные данные: массив [math]\vec{x}[/math] (элементы [math]x_i[/math]).

Дополнительные ограничения: отсутствуют.

Объём входных данных: [math]N[/math].

Выходные данные: сумма элементов массива.

Объём выходных данных: один скаляр.

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

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

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

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

В простейшем (без перестановок суммирования) варианте на Фортране можно записать так:

	DO  I = 1, P
		S (I) = X(K*(I-1)+1)
		IF (I.LQ.P) THEN
			DO J = 2,K
				S(I)=S(I)+X(K*(I-1)+J)
		             END DO
		ELSE
			DO J = 2,Q
				S(I)=S(I)+X(K*(I-1)+J)
		             END DO
		END IF
	END DO
	SUM = S(1)
	DO I = 2, P
		SUM = SUM + S(I)
	END DO

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

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

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

2.3 Результаты прогонов

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

3 Литература