Умножение плотной матрицы на вектор - История изменений

Frolov в 15:36, 7 ноября 2017

2017-11-07T15:36:50Z

← Предыдущая версия		Версия от 15:36, 7 ноября 2017
Строка 15:		Строка 15:
	</math>		</math>

	~~Классическое~~ [[Умножение плотной неособенной матрицы на вектор (последовательный вещественный вариант)]] - классический вариант алгоритма, решающего данную задачу.		[[Умножение плотной неособенной матрицы на вектор (последовательный вещественный вариант)]] - классический вариант алгоритма, решающего данную задачу.

	= Литература =		= Литература =

Frolov в 15:34, 7 ноября 2017

2017-11-07T15:34:51Z

← Предыдущая версия		Версия от 15:34, 7 ноября 2017
Строка 16:		Строка 16:

	Классическое [[Умножение плотной неособенной матрицы на вектор (последовательный вещественный вариант)]] - классический вариант алгоритма, решающего данную задачу.		Классическое [[Умножение плотной неособенной матрицы на вектор (последовательный вещественный вариант)]] - классический вариант алгоритма, решающего данную задачу.

			= Литература =

Frolov в 15:34, 7 ноября 2017

2017-11-07T15:34:29Z

← Предыдущая версия		Версия от 15:34, 7 ноября 2017
Строка 1:		Строка 1:
	~~#перенаправление~~ [[Умножение плотной неособенной матрицы на вектор (последовательный вещественный вариант)]]		{{level-p}}

			'''Умножение матрицы на вектор''' - одна из базовых задач в алгоритмах линейной алгебры, широко применяется в большом количестве разных методов.
			Здесь мы рассмотрим умножение <math>y = Ax</math> плотной неособенной матрицы на вектор<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref>, то есть тот вариант, где никак не может использоваться специальный вид матрицы или вектора.

			Исходные данные: плотная матрица <math>A</math> (элементы <math>a_{ij}</math>), умножаемый на неё вектор <math>x</math> (элементы <math>x_{i}</math>).

			Вычисляемые данные: вектор решения <math>y</math> (элементы <math>y_{i}</math>).

			Формулы:
			:<math>
			\begin{align}
			y_{i} = \sum_{j = 1}^{n} a_{ij} x_{j}, \quad i \in [1, m].
			\end{align}
			</math>

			Классическое [[Умножение плотной неособенной матрицы на вектор (последовательный вещественный вариант)]] - классический вариант алгоритма, решающего данную задачу.

Frolov: перенос (слияние страниц)

2014-10-08T16:31:18Z

перенос (слияние страниц)

← Предыдущая версия		Версия от 16:31, 8 октября 2014
Строка 1:		Строка 1:
	~~== Описание свойств и структуры алгоритма ==~~		#перенаправление [[Умножение плотной неособенной матрицы на вектор (последовательный вещественный вариант)]]
	~~=== Общее описание алгоритма ===~~
	~~=== Математическое описание ===~~
	~~=== Вычислительное ядро алгоритма ===~~
	~~=== Макроструктура алгоритма ===~~
	~~=== Описание схемы реализации последовательного алгоритма ===~~
	~~=== Последовательная сложность алгоритма ===~~
	~~=== Информационный граф ===~~
	~~=== Описание ресурса параллелизма алгоритма ===~~
	~~=== Описание входных и выходных данных ===~~
	~~=== Свойства алгоритма ===~~
	~~== Программная реализация ==~~
	~~=== Особенности реализации последовательного алгоритма ===~~
	~~=== Описание локальности данных и вычислений ===~~
	~~==== Описание локальности алгоритма ====~~
	~~==== Описание локальности реализации алгоритма ====~~
	~~===== Описание структуры обращений в память и качественная оценка локальности =====~~

	[[~~file:mv mult 1.PNG\|thumb\|center\|700px\|Рисунок 12.1.~~ Умножение плотной матрицы на вектор~~. Общий профиль обращений в память]]~~

	На рисунке 12.1 представлен профиль обращений в память для реализации умножения плотной матрицы на вектор. В данном алгоритме задействовано три массива. Выделенный зеленым фрагмент 1 образован обращениями к результирующему вектору; фрагмент 2 – обращениями к исходному вектору; остальные обращения (фрагмент 3) выполняются к матрице, на которую умножается исходный вектор.

	~~Если посмотреть на исходный код, становится понятным, что каждый фрагмент устроен очень просто:~~
	~~<source lang="C">~~
	~~for~~(~~int i = 0; i < size; i++)~~
	~~for(int j = 0; j < size; j++)~~
	~~vec_out[i] += matrix[i][j] * vec_in[j];~~
	~~</source>~~

	Видно, что фрагмент 1 (обращения к массиву vec_out) состоит из последовательного перебора всех элементов вектора, только к каждому элементу происходит подряд size обращений. Во фрагменте 2 (массив vec_in) выполняется обычный последовательный перебор, который затем повторяется size раз. Фрагмент 3 также представляет собой последовательный перебор всех элементов матрицы, который выполняется только один раз.

	Самой высокой локальностью обладает фрагмент 1 из-за повторяющихся подряд обращений к одним и тем же элементам. Однако фрагмент 2 также обладает высокой как пространственной, так и временной локальностью, поскольку число повторных проходов достаточно велико. Фрагмент 3, как и остальные, характеризуется высокой пространственной локальностью (из-за последовательного перебора)~~, однако очень низкой временной локальностью – повторные обращения в нем просто отсутствуют.~~

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

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

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

	~~[[file:mv mult daps ru.PNG\|thumb\|center\|700px\|Рисунок 12.2. Сравнение значений оценки daps~~]]

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

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

	~~[[file:mv mult cvg.PNG\|thumb\|center\|700px\|Рисунок 12.3. Сравнение значений оценки cvg]]~~

	~~=== Возможные способы и особенности реализации параллельного алгоритма ===~~
	~~=== Масштабируемость алгоритма и его реализации ===~~
	~~==== Описание масштабируемости алгоритма ====~~
	~~==== Описание масштабируемости реализации алгоритма ====~~
	[[file:Масштабируемость перемножения матрицы и вектора производительность.png\|thumb\|center\|700px\|Рисунок 1. Параллельная реализация произведения матрицы на вектор Максимальная производительность. ]]
	[[file:Масштабируемость перемножения матрицы и вектора эффективность.png\|thumb\|center\|700px\|Рисунок 2. Параллельная реализация произведения матрицы на вектор Максимальная эффективность. ]]
	~~Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:~~
	* число процессоров [4 : 256]
	* размерность матрицы [1024 : 51200]
	~~Эффективность выполнения реализации алгоритма~~
	* Минимальная эффективность 0,02%
	* Максимальная эффективность 9,55%
	~~Оценка масштабируемости~~
	* По числу процессов: -0.01517 – при увеличении числа процессов эффективность убывает достаточно интенсивно на всей рассмотренной области изменений параметров запуска. Уменьшение эффективности на рассмотренной области работы параллельной программы звязано с увеличением числа пересылок с ростом числа процессов и как следствие ростом накладных расходов на организацию вычислений. Основной вклад в значение эффективности вносит область с малым числом процессов и малой задачей, там эффективность достигает максимума в 9,5%. Далее эффективность очень резко падает до уровня около 1% Присутствует область, на которой при увеличении числа процессов эффективность возрастает, но при дальнейшем росте продолжает снижаться. Это скорее всего объясняется декомпозицей данных, при которой наступает момент, когда размер матрицы позволяет блокам укладываться в КЭШ-память. Так же это подтверждает проявление этого явления, но со смещением по числу процессов, и при увеличении вычислительной сложности задачи.
	* По размеру задачи: -0.0014 – при увеличении размера задачи эффективность в целом уменьшается по рассматриваемой области, хотя и менее интенсивно, чем при увеличении числа процессов. Снижение эффективности объясняется тем, что при росте вычислительной сложности существенно возрастают объемы передаваемых данных. При увеличении размера данных наступает момент резкого снижения эффективности с значений около 1% к долям процента и минимуму. С увеличением числа процессоров такой переход появляется на большем объеме данных. Это свидетельствует о том, что присутствует момент, когда данных слишком много и эффективность работы с ними становится значительно ниже, но чем больше имеется процессов, там позже наступает такой момент декомпозиции. Присутствует область возрастания эффективности, на всех рассмотренных размерах матрицы. Это объясняется тем, что при малом размере задачи данные хорошо укладываются в КЭШ память, что приводит к высокой эффективности работы приложения при малом размере задачи. При дальнейшем увеличении размера эффективность уменьшается при выходе за границы КЭШ-памяти.
	* По двум направлениям: -0.0001546 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, интенсивность уменьшения эффективности не очень высока. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров составляет около 9% говорит о том, что уменьшение эффективности по всей области довольно равномерное, но интенсивно лишь в не очень больших участках по площади. На остальной области значений параметров изменения эффективности не столь значительны и находятся на приблизительно одном и том же уровне.

	~~=== Динамические характеристики и эффективность реализации алгоритма ===~~
	~~=== Выводы для классов архитектур ===~~
	~~=== Существующие реализации алгоритма ===~~

Teplov: /* Описание масштабируемости реализации алгоритма */

2014-10-06T13:57:33Z