Difference between revisions of "Dot product"

From Algowiki
Jump to navigation Jump to search
[unchecked revision][unchecked revision]
(Created page with "== Программная реализация == === Особенности реализации последовательного алгоритма === В простей...")
 
Line 1: Line 1:
−
== Программная реализация ==
+
Основные авторы описания: [[Участник:Frolov|А.В.Фролов]], [[Участник:VadimVV|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений|раздел 2.2]]), [[Участник:Teplov|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации|2.4]])
  
−
=== Особенности реализации последовательного алгоритма ===
+
== Описание свойств и структуры алгоритма ==
  
−
В простейшем (без перестановок суммирования) варианте на Фортране можно записать так:
+
=== Общее описание алгоритма ===
  
−
<source lang="fortran">
+
'''Скалярное произведение векторов''' используется в качестве одной из базовых операций в широком круге методов. При этом используется как в версии скалярного произведения собственно <math>n</math>-мерных векторов (одномерных массивов размера <math>n</math>), так и в версии скалярного произведения строк, столбцов и других линейных подмножеств массивов большей размерности. Последняя отличается от первой тем, что соответствующая подпрограмма получает, кроме стартовых адресов векторов, также и параметры смещения следующих элементов относительно предыдущих (в первой версии эти смещения равны 1). Разные формулы существуют для скалярных произведений в вещественной арифметике и для комплексных векторов. Здесь мы рассматриваем только вещественную арифметику и последовательно-параллельную реализацию.
−
DO  I = 1, P
 
−
S (I) = A(K*(I-1)+1)*B(K*(I-1)+1)
 
−
IF (I.LQ.P) THEN
 
−
DO J = 2,K
 
−
S(I)=S(I)+A(K*(I-1)+J)*B(K*(I-1)+J)
 
−
            END DO
 
−
ELSE
 
−
DO J = 2,Q
 
−
S(I)=S(I)+A(K*(I-1)+J)*B(K*(I-1)+J)
 
−
            END DO
 
−
END IF
 
−
END DO
 
−
SCP = S(1)
 
−
DO I = 2, P
 
−
SCP = SCP + S(I)
 
−
END DO
 
−
</source>
 
  
−
Можно записать и аналогичные схемы, где суммирование будет проводиться в обратном порядке.  Подчеркнём, что граф алгоритма обеих схем — [[#Информационный граф|один и тот же]]! Тело первого цикла целиком может быть заменено вызовом функции скалярного произведения, если она реализована в последовательном варианте.
+
=== Математическое описание ===
  
−
=== Описание локальности данных и вычислений ===
+
Исходные данные: два одномерных массива n чисел.
−
==== Описание локальности реализации алгоритма ====
 
−
===== Описание структуры обращений в память и качественная оценка локальности =====
 
  
−
[[file:Seqpar dot 1.PNG|thumb|center|700px|Рисунок 1. Скалярное произведение векторов. Общий профиль обращений в память]]
+
Вычисляемые данные: сумма попарных произведений элементов массива.
  
−
На рис. 1 представлен профиль обращений в память для вычисления скалярного произведения векторов, вещественная версия. Данный профиль состоит из обращений к трем массивам, фрагменты для отдельных массивов выделены на рис. 1 зеленым цветом. Поскольку мы рассматриваем последовательную реализацию последовательно-параллельного метода суммирования, строение профиля практически никак не зависит от выбранного количества ветвей – будет меняться только число задействованных элементов во фрагменте 1.
+
Формулы метода:
 +
число <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 < p</math>) последовательно вычисляется «частичное» скалярное произведение подмассивов, начиная с <math>(i - 1) k + 1</math>-го номера элемента, до <math>ik</math>-го номера.
  
−
Можно увидеть, что фрагменты 2 и 3 идентичны и являются просто последовательным перебором всех элементов массивов. Такой профиль характеризуется высокой пространственной локальностью и очень низкой временной локальностью, поскольку отсутствуют повторные обращения к элементам.
+
:<math>S_i = \sum_{j = 1}^k a_{k (i - 1) + j} b_{k (i - 1) + j}</math>
  
−
Рассмотрим подробнее фрагмент 1, показанный на рис. 2. Из общего профиля на рис. 1 это заметить сложно, однако при подобном приближении сразу становится понятно, что данный фрагмент состоит из двух одинаковых последовательных переборов всех элементов массива. В данном случае временная локальность становится немного лучше, поскольку появляется повторное обращение к каждому элементу.
+
На <math>p</math>-м процессоре последовательно вычисляется «частичное» скалярное произведение подмассивов, начиная с <math>(p - 1) k + 1</math>-го номера элемента до <math>(p - 1) k + q</math>-го номера.
  
−
[[file:Seqpar_dot_2.jpg|thumb|center|400px|Рисунок 2. Фрагмент 1 (профиль обращений к первому массиву)]]
+
:<math>S_p = \sum_{j = 1}^q a_{k (p - 1) + j} b_{k (p - 1) + j}</math>
  
 +
По окончании этого процесса процессоры обмениваются данными и на одном из них (либо на всех одновременно, если результат нужен далее на всех процессорах) получившиеся суммы суммируются последовательно друг с другом.
  
−
===== Количественная оценка локальности =====
+
:<math>\sum_{i = 1}^p S_i</math>
  
−
Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [http://git.algowiki-project.org/Voevodin/locality/blob/master/benchmarks/vectors_seqpar/vectors_seqpar.h здесь] (функция KernelScalarSeqpar). Условия запуска описаны [http://git.algowiki-project.org/Voevodin/locality/blob/master/README.md здесь].
+
При этом в последовательно-параллельном варианте при вычислений сумм из формул используется последовательный порядок суммирования (обычно от меньших индексов к большим).  
  
−
Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.
+
=== Вычислительное ядро алгоритма ===
  
−
На рисунке 3 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что, благодаря высокой пространственной локальности, производительность данной программы достаточно высока и находится на уровне теста CG из набора тестов NPB.  
+
Вычислительное ядро скалярного произведения в последовательно-параллельном варианте можно представить как <math>p</math> вычислений «частных» скалярных произведений c последующим последовательным суммированием получившихся <math>p</math> чисел.
  
−
[[file:Seqpar_dot_daps_ru.PNG|thumb|center|700px|Рисунок 3. Сравнение значений оценки daps]]
+
=== Макроструктура алгоритма ===
  
−
Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.  
+
Как уже записано в описании ядра алгоритма, основную часть вычисления скалярного произведения составляют параллельное вычисление скалярных произведений меньшей размерности последовательным методом и последовательное вычисление суммы получившихся «частных» скалярных произведений подмассивов.
  
−
На рисунке 4 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Можно увидеть, что, согласно данной оценке, профиль по уровню локальности подобен, например, тесту Triad или Sum из набора тестов STREAM. Это выглядит закономерным, поскольку в данных тестах также происходит перебор элементов массивов.
+
=== Описание схемы реализации последовательного алгоритма ===
  
−
[[file:Seqpar_dot_cvg.PNG|thumb|center|700px|Рисунок 4. Сравнение значений оценки cvg]]
+
Формулы метода описаны выше. Последовательность исполнения суммирования может быть разная — как по возрастанию, так и по убыванию индексов. Обычно без особых причин порядок не меняют, используя естественный (возрастание индексов).
  
−
=== Возможные способы и особенности реализации параллельного алгоритма ===
+
=== Последовательная сложность алгоритма ===
−
=== Масштабируемость алгоритма и его реализации ===
 
  
−
[[file:Масштабируемость_скалярного_произведения_векторов_производительность.png|thumb|center|700px|Рисунок 1. Параллельная реализация Скалярного произведения векторов Максимальная производительность. ]]
+
Для вычисления скалярного произведения массивов, состоящих из <math>n</math> элементов, при любых разложениях количество операций умножения неизменно и равно <math>n</math>, а количество операций сложения равно <math>n - 1</math>. Поэтому алгоритм должен быть отнесён к алгоритмам ''линейной'' сложности по количеству последовательных операций.
−
[[file:Масштабируемость_скальярного_произведения_векторов_Максимальная_эффективность.png|thumb|center|700px|Рисунок 2. Параллельная реализация Скалярного произведения векторов Максимальная эффективность. ]]
 
−
Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:
 
−
* число процессоров [4 : 1024]
 
−
* размер вектора [134217728 : 2013265920]
 
−
Эффективность выполнения реализации алгоритма
 
−
* Минимальная эффективность 9,54 %
 
−
* Максимальная эффективность 24,52%
 
−
Оценка масштабируемости
 
−
* По числу процессов: 0.00414 – при увеличении числа процессов эффективность увеличивается на рассмотренной области изменений параметров запуска, однако, в целом увеличение не интенсивное. Увеличение эффективности на рассмотренной области работы параллельной программы объясняется тем, что при увеличении числа процессоров декомпозиция данных в какой-то момент приводит к тому, что данные лучше укладываются в КЭШ-память. Это подтверждает проявление этого явления, но со смещением по числу процессов, и при увеличении вычислительной сложности задачи.
 
−
* По размеру задачи: -0.01385 – при увеличении размера задачи эффективность в целом уменьшается по рассматриваемой области. Это объясняется тем, что при малом размере задачи данные хорошо укладываются в КЭШ память, что приводит к высокой эффективности работы приложения при малом размере задачи. При увеличении размера эффективность уменьшается при выходе за границы КЭШ-памяти.
 
−
* По двум направлениям: -0.000169 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, однако интенсивность уменьшения эффективности небольшая. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров составляет почти 15 % говорит о том, что на поверхности присутствуют области с очень интенсивным изменением эффективности, но очень малые по площади. На остальной поверхности изменения эффективности незначительны и находятся на приблизительно одном и том же уровне.
 
  
−
[http://git.algowiki-project.org/Teplov/Scalability/blob/master/vectormult/vectormult.c Исследованная параллельная реализация на языке C]
+
=== Информационный граф ===
−
==== Описание масштабируемости алгоритма ====
 
−
==== Описание масштабируемости реализации алгоритма ====
 
  
−
=== Динамические характеристики и эффективность реализации алгоритма ===
+
Опишем граф алгоритма в виде рисунка. Однако следует отметить, что в большинстве случаев программисты не экономят на одном вызове операции сложения, а инициализируют начальное значение переменной нулём. В этом случае граф становится таким, как на втором рисунке (n=24).
−
=== Выводы для классов архитектур ===
 
−
=== Существующие реализации алгоритма ===
 
  
−
Помимо [[#Особенности реализации последовательного алгоритма|выписанной выше простейшей реализации]], существуют более сложные коды, реализующие тот же алгоритм. Следует обратить внимание на то, что ряд реализаций (в том же BLAS) использует разложение <math>n</math> на небольшое и большое числа. При этом внутренние циклы не используются, поскольку суммирование небольшого числа произведений проводится «вручную›, увеличением тела первого цикла. Часть реализаций последовательно-параллельного метода вычисления скалярного произведения не оформлена в виде отдельных подпрограмм, а раскидана по тексту программы алгоритма, использующего скалярное произведение, но фактически представляет именно такую реализацию. Примером этого могут быть блочные реализации различных разложений (Холецкого, Гаусса и др.).
+
{| align="left"
 +
    |- valign="top"
 +
    | [[file:series-parallel dot product graph.png|thumb|750px|Последовательно-параллельное вычисление скалярного произведения с экономией операций сложения]]
 +
    | [[file:Series-parallel dot product graph straight.png|thumb|790px|Последовательно-параллельное вычисление скалярного произведения без экономии операций сложения]]
 +
|}
  
 +
=== Описание ресурса параллелизма алгоритма ===
 +
 +
Для вычисления скалярного произведения массивов порядка <math>n</math> последовательно-параллельным методом в параллельном варианте требуется последовательно выполнить следующие ярусы:
 +
* 1 ярус вычисления произведений,
 +
* <math>k - 1</math> ярусов суммирования по частям массивов (<math>p</math> ветвей),
 +
* <math>p - 1</math> ярусов суммирования (одна последовательная ветвь).
 +
 +
Таким образом, в параллельном варианте критический путь алгоритма  (и соответствующая ему высота ЯПФ) будет зависеть от произведённого разбиения массива на части. В оптимальном случае (<math>p = \sqrt{n}</math>) высота ЯПФ будет равна <math> 2 \sqrt{n} - 1</math>. При классификации по высоте ЯПФ, таким образом, последовательно-параллельный метод относится к алгоритмам ''со сложностью «корень квадратный»''. При классификации по ширине ЯПФ его сложность также будет ''«корень квадратный»''.
 +
 +
=== Описание входных и выходных данных ===
 +
 +
Входные данные: массивы <math>a</math> (элементы <math>a_i</math>), <math>b</math> (элементы <math>b_i</math>).
 +
 +
Дополнительные ограничения: отсутствуют.
 +
 +
Объём входных данных: <nowiki/><math>2 n</math>.
 +
 +
Выходные данные: сумма попарных произведений элементов массивов.
 +
 +
Объём выходных данных: один скаляр.
 +
 +
=== Свойства алгоритма ===
 +
 +
Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''корнем квадратным'' (отношение линейной к корню квадратному). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего ''1 (входных и выходных данных почти столько же, сколько операций; если точнее - даже больше на 2)''. При этом алгоритм полностью детерминирован при заданном разложении <math>n</math>. Дуги информационного графа локальны. Для уменьшения ошибок округления режимом накопления в ряде алгоритмов, использующих скалярное произведение одинарной точности, оно вычисляется с двойной точностью. Впрочем, у последовательно-параллельного способа вычисления скалярного произведения и без режима накопления влияние ошибок округления «в среднем» меньше в <math>\sqrt{n}</math> раз.
  
 
[[Category:Started articles]]
 
[[Category:Started articles]]
  
 
[[Ru:Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант]]
 
[[Ru:Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант]]

Revision as of 09:38, 6 July 2015

Основные авторы описания: А.В.Фролов, Вад.В.Воеводин (раздел 2.2), А.М.Теплов (раздел 2.4)

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

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

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

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

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

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

Формулы метода: число [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]ik[/math]-го номера.

[math]S_i = \sum_{j = 1}^k a_{k (i - 1) + j} b_{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 a_{k (p - 1) + j} b_{k (p - 1) + j}[/math]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Retrieved from "https://algowiki-project.org/algowiki/en/index.php?title=Dot_product&oldid=272"