Dot product

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

1.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

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

1.2 Описание локальности данных и вычислений

1.2.1 Описание локальности реализации алгоритма

1.2.1.1 Описание структуры обращений в память и качественная оценка локальности

Рисунок 1. Скалярное произведение векторов. Общий профиль обращений в память

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

Можно увидеть, что фрагменты 2 и 3 идентичны и являются просто последовательным перебором всех элементов массивов. Такой профиль характеризуется высокой пространственной локальностью и очень низкой временной локальностью, поскольку отсутствуют повторные обращения к элементам.

Рассмотрим подробнее фрагмент 1, показанный на рис. 2. Из общего профиля на рис. 1 это заметить сложно, однако при подобном приближении сразу становится понятно, что данный фрагмент состоит из двух одинаковых последовательных переборов всех элементов массива. В данном случае временная локальность становится немного лучше, поскольку появляется повторное обращение к каждому элементу.

Рисунок 2. Фрагмент 1 (профиль обращений к первому массиву)

1.2.1.2 Количественная оценка локальности

Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен здесь (функция KernelScalarSeqpar). Условия запуска описаны здесь.

Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.

На рисунке 3 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что, благодаря высокой пространственной локальности, производительность данной программы достаточно высока и находится на уровне теста CG из набора тестов NPB.

Рисунок 3. Сравнение значений оценки daps

Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.

На рисунке 4 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Можно увидеть, что, согласно данной оценке, профиль по уровню локальности подобен, например, тесту Triad или Sum из набора тестов STREAM. Это выглядит закономерным, поскольку в данных тестах также происходит перебор элементов массивов.

Рисунок 4. Сравнение значений оценки cvg

1.4 Масштабируемость алгоритма и его реализации

Рисунок 1. Параллельная реализация Скалярного произведения векторов Максимальная производительность.

Рисунок 2. Параллельная реализация Скалярного произведения векторов Максимальная эффективность.

Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:

• число процессоров [4 : 1024]
• размер вектора [134217728 : 2013265920]

Эффективность выполнения реализации алгоритма

• Минимальная эффективность 9,54 %
• Максимальная эффективность 24,52%

Оценка масштабируемости

• По числу процессов: 0.00414 – при увеличении числа процессов эффективность увеличивается на рассмотренной области изменений параметров запуска, однако, в целом увеличение не интенсивное. Увеличение эффективности на рассмотренной области работы параллельной программы объясняется тем, что при увеличении числа процессоров декомпозиция данных в какой-то момент приводит к тому, что данные лучше укладываются в КЭШ-память. Это подтверждает проявление этого явления, но со смещением по числу процессов, и при увеличении вычислительной сложности задачи.
• По размеру задачи: -0.01385 – при увеличении размера задачи эффективность в целом уменьшается по рассматриваемой области. Это объясняется тем, что при малом размере задачи данные хорошо укладываются в КЭШ память, что приводит к высокой эффективности работы приложения при малом размере задачи. При увеличении размера эффективность уменьшается при выходе за границы КЭШ-памяти.
• По двум направлениям: -0.000169 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, однако интенсивность уменьшения эффективности небольшая. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров составляет почти 15 % говорит о том, что на поверхности присутствуют области с очень интенсивным изменением эффективности, но очень малые по площади. На остальной поверхности изменения эффективности незначительны и находятся на приблизительно одном и том же уровне.

Исследованная параллельная реализация на языке C

1.7 Существующие реализации алгоритма

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