Приложение 4
Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант
Свойства и структура алгоритма
Общее описание алгоритма
Скалярное произведение векторов используется в качестве одной из базовых операций в широком круге методов. При этом используется как в версии скалярного произведения собственно [math]\displaystyle{ n }[/math]-мерных векторов (одномерных массивов размера [math]\displaystyle{ n }[/math]), так и в версии скалярного произведения строк, столбцов и других линейных подмножеств массивов большей размерности. Последняя отличается от первой тем, что соответствующая подпрограмма получает, кроме стартовых адресов векторов, также и параметры смещения следующих элементов относительно предыдущих (в первой версии эти смещения равны 1). Разные формулы существуют для скалярных произведений в вещественной арифметике и для комплексных векторов. Здесь мы рассматриваем только вещественную арифметику и последовательно-параллельную реализацию.
Математическое описание алгоритма
Исходные данные: два одномерных массива n чисел.
Вычисляемые данные: сумма попарных произведений элементов массива.
Формулы метода: число [math]\displaystyle{ n }[/math] разлагается в выражение типа [math]\displaystyle{ n = (p - 1) k + q }[/math], где [math]\displaystyle{ p }[/math] — количество процессоров, [math]\displaystyle{ k = \lceil \frac{n}{p} \rceil }[/math], [math]\displaystyle{ q = n - k (p - 1) }[/math]. После этого на [math]\displaystyle{ i }[/math]-м процессоре ([math]\displaystyle{ i \lt p }[/math]) последовательно вычисляется «частичное» скалярное произведение подмассивов, начиная с [math]\displaystyle{ (i - 1) k + 1 }[/math]-го номера элемента, до [math]\displaystyle{ ik }[/math]-го номера.
- [math]\displaystyle{ S_i = \sum_{j = 1}^k a_{k (i - 1) + j} b_{k (i - 1) + j} }[/math]
На [math]\displaystyle{ p }[/math]-м процессоре последовательно вычисляется «частичное» скалярное произведение подмассивов, начиная с [math]\displaystyle{ (p - 1) k + 1 }[/math]-го номера элемента до [math]\displaystyle{ (p - 1) k + q }[/math]-го номера.
- [math]\displaystyle{ S_p = \sum_{j = 1}^q a_{k (p - 1) + j} b_{k (p - 1) + j} }[/math]
По окончании этого процесса процессоры обмениваются данными и на одном из них (либо на всех одновременно, если результат нужен далее на всех процессорах) получившиеся суммы суммируются последовательно друг с другом.
- [math]\displaystyle{ \sum_{i = 1}^p S_i }[/math]
При этом в последовательно-параллельном варианте при вычислений сумм из формул используется последовательный порядок суммирования (обычно от меньших индексов к большим).
Вычислительное ядро алгоритма
Вычислительное ядро скалярного произведения в последовательно-параллельном варианте можно представить как [math]\displaystyle{ p }[/math] вычислений «частных» скалярных произведений c последующим последовательным суммированием получившихся [math]\displaystyle{ p }[/math] чисел.
Макроструктура алгоритма
Как уже записано в описании ядра алгоритма, основную часть вычисления скалярного произведения составляют параллельное вычисление скалярных произведений меньшей размерности последовательным методом и последовательное вычисление суммы получившихся «частных» скалярных произведений подмассивов.
Схема реализации последовательного алгоритма
Формулы метода описаны выше. Последовательность исполнения суммирования может быть разная — как по возрастанию, так и по убыванию индексов. Обычно без особых причин порядок не меняют, используя естественный (возрастание индексов).
Последовательная сложность алгоритма
Для вычисления скалярного произведения массивов, состоящих из [math]\displaystyle{ n }[/math] элементов, при любых разложениях количество операций умножения неизменно и равно [math]\displaystyle{ n }[/math], а количество операций сложения равно [math]\displaystyle{ n - 1 }[/math]. Поэтому алгоритм должен быть отнесён к алгоритмам линейной сложности по количеству последовательных операций.
Информационный граф
На рис.1 изображён граф аогоритма. Однако следует отметить, что в большинстве случаев программисты не экономят на одном вызове операции сложения, а инициализируют начальное значение переменной нулём. В этом случае граф становится таким, как на рис.2 (n=24).
 |
 |
Ресурс параллелизма алгоритма
Для вычисления скалярного произведения массивов порядка [math]\displaystyle{ n }[/math] последовательно-параллельным методом в параллельном варианте требуется последовательно выполнить следующие ярусы:
- 1 ярус вычисления произведений,
- [math]\displaystyle{ k - 1 }[/math] ярусов суммирования по частям массивов ([math]\displaystyle{ p }[/math] ветвей),
- [math]\displaystyle{ p - 1 }[/math] ярусов суммирования (одна последовательная ветвь).
Таким образом, в параллельном варианте критический путь алгоритма (и соответствующая ему высота ЯПФ) будет зависеть от произведённого разбиения массива на части. В оптимальном случае ([math]\displaystyle{ p = \sqrt{n} }[/math]) высота ЯПФ будет равна [math]\displaystyle{ 2 \sqrt{n} - 1 }[/math]. При классификации по высоте ЯПФ, таким образом, последовательно-параллельный метод относится к алгоритмам со сложностью «корень квадратный». При классификации по ширине ЯПФ его сложность также будет «корень квадратный».
Входные и выходные данные алгоритма
Входные данные: массивы [math]\displaystyle{ a }[/math] (элементы [math]\displaystyle{ a_i }[/math]), [math]\displaystyle{ b }[/math] (элементы [math]\displaystyle{ b_i }[/math]).
Дополнительные ограничения: отсутствуют.
Объём входных данных: [math]\displaystyle{ 2 n }[/math].
Выходные данные: сумма попарных произведений элементов массивов.
Объём выходных данных: один скаляр.
Свойства алгоритма
Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является корнем квадратным (отношение линейной к корню квадратному). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего 1 (входных и выходных данных почти столько же, сколько операций; если точнее - даже больше на 2). При этом алгоритм полностью детерминирован при заданном разложении [math]\displaystyle{ n }[/math]. Дуги информационного графа локальны. Для уменьшения ошибок округления режимом накопления в ряде алгоритмов, использующих скалярное произведение одинарной точности, оно вычисляется с двойной точностью. Впрочем, у последовательно-параллельного способа вычисления скалярного произведения и без режима накопления влияние ошибок округления «в среднем» меньше в [math]\displaystyle{ \sqrt{n} }[/math] раз.