Приложение 4

1 Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант

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

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

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

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

Исходные данные: два одномерных массива n чисел.

Вычисляемые данные: сумма попарных произведений элементов массива.

Формулы метода: число $n$ разлагается в выражение типа $n = (p - 1) k + q$, где $p$ — количество процессоров, $k = \lceil \frac{n}{p} \rceil$, $q = n - k (p - 1)$. После этого на $i$-м процессоре ($i \lt p$) последовательно вычисляется «частичное» скалярное произведение подмассивов, начиная с $(i - 1) k + 1$-го номера элемента, до $ik$-го номера.

$S_i = \sum_{j = 1}^k a_{k (i - 1) + j} b_{k (i - 1) + j}$

На $p$-м процессоре последовательно вычисляется «частичное» скалярное произведение подмассивов, начиная с $(p - 1) k + 1$-го номера элемента до $(p - 1) k + q$-го номера.

$S_p = \sum_{j = 1}^q a_{k (p - 1) + j} b_{k (p - 1) + j}$

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

$\sum_{i = 1}^p S_i$

При этом в последовательно-параллельном варианте при вычислений сумм из формул используется последовательный порядок суммирования (обычно от меньших индексов к большим).

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

Вычислительное ядро скалярного произведения в последовательно-параллельном варианте можно представить как $p$ вычислений «частных» скалярных произведений c последующим последовательным суммированием получившихся $p$ чисел.

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

Как уже записано в описании ядра алгоритма, основную часть вычисления скалярного произведения составляют параллельное вычисление скалярных произведений меньшей размерности последовательным методом и последовательное вычисление суммы получившихся «частных» скалярных произведений подмассивов.

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

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

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

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

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

На рис.1 изображён граф аогоритма. Однако следует отметить, что в большинстве случаев программисты не экономят на одном вызове операции сложения, а инициализируют начальное значение переменной нулём. В этом случае граф становится таким, как на рис.2 (n=24).

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

Рисунок 2. Последовательно-параллельное вычисление скалярного произведения без экономии операций сложения

1.1.8 Ресурс параллелизма алгоритма

Для вычисления скалярного произведения массивов порядка $n$ последовательно-параллельным методом в параллельном варианте требуется последовательно выполнить следующие ярусы:

• 1 ярус вычисления произведений,
• $k - 1$ ярусов суммирования по частям массивов ($p$ ветвей),
• $p - 1$ ярусов суммирования (одна последовательная ветвь).

Таким образом, в параллельном варианте критический путь алгоритма (и соответствующая ему высота ЯПФ) будет зависеть от произведённого разбиения массива на части. В оптимальном случае ($p = \sqrt{n}$) высота ЯПФ будет равна $2 \sqrt{n} - 1$. При классификации по высоте ЯПФ, таким образом, последовательно-параллельный метод относится к алгоритмам со сложностью «корень квадратный». При классификации по ширине ЯПФ его сложность также будет «корень квадратный».

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

Входные данные: массивы $a$ (элементы $a_i$), $b$ (элементы $b_i$).

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

Объём входных данных: $2 n$.

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

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

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

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является корнем квадратным (отношение линейной к корню квадратному). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего 1 (входных и выходных данных почти столько же, сколько операций; если точнее - даже больше на 2). При этом алгоритм полностью детерминирован при заданном разложении $n$. Дуги информационного графа локальны. Для уменьшения ошибок округления режимом накопления в ряде алгоритмов, использующих скалярное произведение одинарной точности, оно вычисляется с двойной точностью. Впрочем, у последовательно-параллельного способа вычисления скалярного произведения и без режима накопления влияние ошибок округления «в среднем» меньше в $\sqrt{n}$ раз.