Участник:Kisel dv/DNS алгоритм умножения матриц - История изменений

Kisel dv: /* Информационный граф */

2017-11-16T22:42:00Z

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

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

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


			[[File:InfographDNS.png\|thumb\|center\|500px\|]]

			Серым на графе помечен этап, в котором происходит считывание матриц <math>A</math> и <math>B</math> и их запись в "смежные грани куба".

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

			Зеленым обозначен этап суммирования и вывода результата - матрицы <math>C</math>.

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

Kisel dv: /* Масштабируемость алгоритма */

2017-11-16T20:04:13Z

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

← Предыдущая версия		Версия от 20:04, 16 ноября 2017
Строка 90:		Строка 90:
	Рассматривались квадратные матрицы размерностью <math>N</math>, где <math>500\leqslant N \leqslant 2000</math>, а число процессов изменялось от <math>2</math> до <math>128</math>. Для примера посмотрим как изменялось время выполнения программы в зависимости от числа процессов (здесь берутся матрицы размера <math>N = 2000</math>)		Рассматривались квадратные матрицы размерностью <math>N</math>, где <math>500\leqslant N \leqslant 2000</math>, а число процессов изменялось от <math>2</math> до <math>128</math>. Для примера посмотрим как изменялось время выполнения программы в зависимости от числа процессов (здесь берутся матрицы размера <math>N = 2000</math>)

	Размер блоков, на которые разбивается матрица, выбирается по оптимальному принципу: целая часть от <math>\frac{N}{q^{\frac{1}{3}}}</math>.		Размер блоков, на которые разбивается матрица, выбирается по оптимальному принципу: целая часть от <math>\frac{N}{q^{\frac{1}{3}}}</math>, где <math>N, q</math>, соответственно, размер матрицы и количество процессов.

	{\| class="wikitable"		{\| class="wikitable"

Kisel dv: /* Масштабируемость алгоритма */

2017-11-16T20:03:23Z

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

← Предыдущая версия		Версия от 20:03, 16 ноября 2017
Строка 90:		Строка 90:
	Рассматривались квадратные матрицы размерностью <math>N</math>, где <math>500\leqslant N \leqslant 2000</math>, а число процессов изменялось от <math>2</math> до <math>128</math>. Для примера посмотрим как изменялось время выполнения программы в зависимости от числа процессов (здесь берутся матрицы размера <math>N = 2000</math>)		Рассматривались квадратные матрицы размерностью <math>N</math>, где <math>500\leqslant N \leqslant 2000</math>, а число процессов изменялось от <math>2</math> до <math>128</math>. Для примера посмотрим как изменялось время выполнения программы в зависимости от числа процессов (здесь берутся матрицы размера <math>N = 2000</math>)

	Размер блоков, на которые разбивается матрица, выбирается по оптимальному принципу: <math>~~\left[~~\frac{N}{q^{\frac{1}{3}}~~\right]~~}</math>.		Размер блоков, на которые разбивается матрица, выбирается по оптимальному принципу: целая часть от <math>\frac{N}{q^{\frac{1}{3}}}</math>.

	{\| class="wikitable"		{\| class="wikitable"

Kisel dv: /* Масштабируемость алгоритма */

2017-11-16T20:02:16Z

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

← Предыдущая версия		Версия от 20:02, 16 ноября 2017
Строка 90:		Строка 90:
	Рассматривались квадратные матрицы размерностью <math>N</math>, где <math>500\leqslant N \leqslant 2000</math>, а число процессов изменялось от <math>2</math> до <math>128</math>. Для примера посмотрим как изменялось время выполнения программы в зависимости от числа процессов (здесь берутся матрицы размера <math>N = 2000</math>)		Рассматривались квадратные матрицы размерностью <math>N</math>, где <math>500\leqslant N \leqslant 2000</math>, а число процессов изменялось от <math>2</math> до <math>128</math>. Для примера посмотрим как изменялось время выполнения программы в зависимости от числа процессов (здесь берутся матрицы размера <math>N = 2000</math>)

	Размер блоков, на которые разбивается матрица, выбирается по оптимальному принципу: <math>[\frac{N}{q^{\frac{1}{3}}]}</math>.		Размер блоков, на которые разбивается матрица, выбирается по оптимальному принципу: <math>\left[\frac{N}{q^{\frac{1}{3}}\right]}</math>.

	{\| class="wikitable"		{\| class="wikitable"

Kisel dv: /* Масштабируемость алгоритма */

2017-11-16T20:01:57Z

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

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

	Рассматривались квадратные матрицы размерностью <math>N</math>, где <math>500\leqslant N \leqslant 2000</math>, а число процессов изменялось от <math>2</math> до <math>128</math>. Для примера посмотрим как изменялось время выполнения программы в зависимости от числа процессов (здесь берутся матрицы размера <math>N = 2000</math>)		Рассматривались квадратные матрицы размерностью <math>N</math>, где <math>500\leqslant N \leqslant 2000</math>, а число процессов изменялось от <math>2</math> до <math>128</math>. Для примера посмотрим как изменялось время выполнения программы в зависимости от числа процессов (здесь берутся матрицы размера <math>N = 2000</math>)

			Размер блоков, на которые разбивается матрица, выбирается по оптимальному принципу: <math>[\frac{N}{q^{\frac{1}{3}}]}</math>.

	{\| class="wikitable"		{\| class="wikitable"
Строка 112:		Строка 114:
	\|4		\|4
	\|162.214		\|162.214
	\|-
	\|2
	~~\|495.675~~
	\|-		\|-
	\|}		\|}

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

	Проиллюстрируем данные графиком:		Проиллюстрируем данные графиком:

Kisel dv: /* Ресурс параллелизма алгоритма */

2017-11-16T19:49:45Z

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

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

	<math> \cdot </math>  После того, как каждый процесс завершил умножение, результаты процессов <math> [i, j, 0], [i, j, 1], ..., [i, j, m-1] </math>  суммируются в <math> C_{ij} </math> . Суммирование всех <math> C_{ij} </math>  может выполняться одновременно за <math> log(m) </math>  шагов. <ref>http://parallelcomp.uw.hu/ch08lev1sec2.html</ref>		<math> \cdot </math>  После того, как каждый процесс завершил умножение, результаты процессов <math> [i, j, 0], [i, j, 1], ..., [i, j, m-1] </math>  суммируются в <math> C_{ij} </math> . Суммирование всех <math> C_{ij} </math>  может выполняться одновременно за <math> log(m) </math>  шагов. <ref>http://parallelcomp.uw.hu/ch08lev1sec2.html</ref>


			[[File:DNS1.PNG\|thumb\|center\|500px\|]]

			[[File:DNS2.PNG\|thumb\|center\|500px\|]]

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

Kisel dv: /* Информационный граф */

2017-11-16T19:49:25Z

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

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

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

	~~На представленных ниже рисунках изображена иллюстрация работы алгоритма.~~

	~~[[File:DNS1.PNG\|thumb\|center\|500px\|]]~~

	~~[[File:DNS2.PNG\|thumb\|center\|500px\|]]~~

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

Kisel dv: /* Масштабируемость алгоритма */

2017-11-16T19:10:21Z

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

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

	[[File: DNS_graph1.jpg\|thumb\|center\|500px\|]]		[[File: DNS_graph1.jpg\|thumb\|center\|500px\|]]

			3d-график:

			[[File: DNS_graph3.jpg\|thumb\|center\|500px\|]]

	Очевидно, что система хорошо масштабируема.		Очевидно, что система хорошо масштабируема.

Kisel dv: /* Информационный граф */

2017-11-16T18:06:11Z

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

← Предыдущая версия		Версия от 18:06, 16 ноября 2017
Строка 52:		Строка 52:
	На представленных ниже рисунках изображена иллюстрация работы алгоритма.		На представленных ниже рисунках изображена иллюстрация работы алгоритма.

	[[File:DNS1.PNG\|thumb\|center\|~~1000px~~\|]]		[[File:DNS1.PNG\|thumb\|center\|500px\|]]

	[[File:DNS2.PNG\|thumb\|center\|~~1000px~~\|]]		[[File:DNS2.PNG\|thumb\|center\|500px\|]]

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

Kisel dv: /* Информационный граф */

2017-11-16T17:46:35Z

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

← Предыдущая версия		Версия от 17:46, 16 ноября 2017
Строка 52:		Строка 52:
	На представленных ниже рисунках изображена иллюстрация работы алгоритма.		На представленных ниже рисунках изображена иллюстрация работы алгоритма.

	[[File:DNS1.PNG]]		[[File:DNS1.PNG\|thumb\|center\|1000px\|]]

	[[File:DNS2.PNG]]		[[File:DNS2.PNG\|thumb\|center\|1000px\|]]

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