Скалярное произведение векторов, вещественная версия, последовательный вариант: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
м (формулы, разметка, иллюстрации)
Строка 35: Строка 35:
 
Опишем граф алгоритма в виде рисунков. На верхнем рисунке граф варианта без «холостого» суммирования. На нижнем рисунке граф варианта с более простым кодом. Приведён граф вычисления скалярного произведения последовательным способом при <math>n = 6</math>.
 
Опишем граф алгоритма в виде рисунков. На верхнем рисунке граф варианта без «холостого» суммирования. На нижнем рисунке граф варианта с более простым кодом. Приведён граф вычисления скалярного произведения последовательным способом при <math>n = 6</math>.
  
{| align="left"
+
[[file:serial_dot_product_graph_without_dummy_summation.png|center|thumb|800px]]
    |- valign="top"
+
[[file:serial_dot_product_graph_with_dummy_summation.png|center|thumb|800px]]
    | [[File:serial_dot_product_graph_without_dummy_summation.png|600px|thumb|left]]
 
    |-
 
    | [[File:serial_dot_product_graph_with_dummy_summation.png|600px|thumb|left]]
 
|}
 
  
 
=== Описание ресурса параллелизма алгоритма ===
 
=== Описание ресурса параллелизма алгоритма ===
Строка 52: Строка 48:
 
Дополнительные ограничения: отсутствуют.
 
Дополнительные ограничения: отсутствуют.
  
Объём входных данных: <math>2 n \frac{n (n - 1)}{2}</math>.  
+
Объём входных данных: <nowiki/><math>2 n</math>.  
  
 
Выходные данные: сумма попарных произведений элементов массивов.
 
Выходные данные: сумма попарных произведений элементов массивов.

Версия 20:39, 15 июня 2014

Содержание

1 Описание свойств и структуры алгоритма

1.1 Словесное описание алгоритма

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

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

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

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

Формулы метода: для векторов [math]\vec{a}[/math] и [math]\vec{b}[/math] размерности [math]n[/math] вычисляется сумма [math]\sum_{i = 1}^n a_i b_i[/math].

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

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

Вычислительное ядро скалярного произведения в последовательном варианте можно представить либо (с предварительной инициализацией «накопителя» нулём) в качестве набора [math]n[/math] «двойных» операций (попарное умножение соответствующих элементов массивов и добавление результата к уже накопленной части скалярного произведения), либо в качестве одного попарного умножения первых элеменов массива и набора [math]n-1[/math] «двойных» операций (попарное умножение соответствующих элементов массивов и добавление результата к уже накопленной части скалярного произведения). Последняя версия более экономна по операциям с вещественной арифметикой, однако широко используется и первая, с одним «холостым» вычислением суммы числа и нуля. Это связано с более простой записью кода у первой версии. Интересно, что, несмотря на разные графы, эти версии дают одинаковые результаты с точностью до бита, поэтому выбор одной из них никак не влияет на ошибки округления.

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

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

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

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

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

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

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

Опишем граф алгоритма в виде рисунков. На верхнем рисунке граф варианта без «холостого» суммирования. На нижнем рисунке граф варианта с более простым кодом. Приведён граф вычисления скалярного произведения последовательным способом при [math]n = 6[/math].

Serial dot product graph without dummy summation.png
Serial dot product graph with dummy summation.png

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

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

1.9 Описание входных и выходных данных

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

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

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

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

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

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

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

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

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

В простейшем (входные данные — вектора) варианте на Фортране можно записать так:

	SCP = A(1)*B(1)
	DO I = 2, N
		SCP = SCP + A(I)*B(I)
	END DO

В варианте с «холостым» сложением запись такая:

	SCP = 0.
	DO I = 1, N
		SCP = SCP + A(I)*B(I)
	END DO

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 Существующие реализации алгоритма

Помимо выписанных выше простейших реализаций, существуют более сложные коды, реализующие тот же алгоритм. Это объясняется тем, что порой чисто программистскими приёмами оптимизируют работу с регистрами, с кэшем и т. п. В частности, даже в Линпаке есть разные реализации кода — из BLAS или другие варианты. Большинство их сводится к сведению одинарного цикла длиной n к двойному циклу либо к одинарному с меньшим числом итераций, но более длинной операцией в теле цикла. Между тем, разбиения циклов на группы для вычислений частных сумм в скалярном произведении могут быть полезны и для лучшего использования кэша на отдельных узлах, когда самих скалярных произведений вычисляется сразу много и распараллеливание программы состоит в их распределении между узлами.