Участник:ZhenyaNikishkina/Перемножение разреженных матриц - История изменений

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

2023-12-05T08:05:48Z

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

← Предыдущая версия		Версия от 08:05, 5 декабря 2023
Строка 175:		Строка 175:

	=== Информационный граф ===		=== Информационный граф ===
	На рис. 2 изображен информационный граф алгоритма перемножения разреженных матриц. Этапы выполнения метода помечены цифрами:		На рис. 2 изображен информационный граф алгоритма перемножения разреженных матриц. Этапы выполнения метода помечены цифрами:

	1 - инициализация результата;		1 - инициализация результата;

Строка 182:		Строка 183:
	3 - объединение полученных результатов.		3 - объединение полученных результатов.

	На этапе 2 параллельно для каждой строки считается ~~последовательно~~ скалярное произведение ~~с каждым столбцом~~.		На этапе 2 параллельно для каждой строки считается скалярное произведение. При этом в каждом потоке доступ к столбцам второй матрицы осуществляется последовательно.
	[[file:zhenya_skipod.png\|thumb\|center\|800px\|Рисунок 2. Информационный граф операции произведения разреженных матриц.]]		[[file:zhenya_skipod.png\|thumb\|center\|800px\|Рисунок 2. Информационный граф операции произведения разреженных матриц.]]

ZhenyaNikishkina: /* Масштабируемость алгоритма и его реализации */

2023-12-04T22:35:37Z

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

← Предыдущая версия		Версия от 22:35, 4 декабря 2023
Строка 230:		Строка 230:
	Проведём исследование масштабируемости параллельной реализации умножения разреженных матриц. Исследование проводилось на [https://parallel.ru/cluster/lomonosov2.html cуперкомпьютере "Ломоносов-2"]<ref>Суперкомпьютерный комплекс МГУ, включая суперкомпьютер "ЛОМОНОСОВ-2"</ref>.		Проведём исследование масштабируемости параллельной реализации умножения разреженных матриц. Исследование проводилось на [https://parallel.ru/cluster/lomonosov2.html cуперкомпьютере "Ломоносов-2"]<ref>Суперкомпьютерный комплекс МГУ, включая суперкомпьютер "ЛОМОНОСОВ-2"</ref>.

	Результаты экспериментов представлены на рис. 2 (для <code>int</code>) и рис. 3 (для <code>float</code>). Приведенные данные демонстрируют явное ускорение при выполнении процедуры в многопоточном режиме в отличие от однопоточного, причем с увеличением числа потоков эта разница увеличивается. Чтобы изучить это поведение более подробно, процедура была запущена на квадратных матрицах различного размера: <math>128 \times 128</math>, <math>512 \times 512</math>, <math>1024 \times 1024</math>, <math>4096 \times 4096</math>. Для каждой из матриц наблюдается следующее: при увеличении числа потоков время выполнения операции сокращается. Также можно заметить, что время выполнения операции для матриц с элементами типа <code>int</code> и <code>float</code> практически не отличается.		Результаты экспериментов представлены на рис. 3 (для <code>int</code>) и рис. 4 (для <code>float</code>). Приведенные данные демонстрируют явное ускорение при выполнении процедуры в многопоточном режиме в отличие от однопоточного, причем с увеличением числа потоков эта разница увеличивается. Чтобы изучить это поведение более подробно, процедура была запущена на квадратных матрицах различного размера: <math>128 \times 128</math>, <math>512 \times 512</math>, <math>1024 \times 1024</math>, <math>4096 \times 4096</math>. Для каждой из матриц наблюдается следующее: при увеличении числа потоков время выполнения операции сокращается. Также можно заметить, что время выполнения операции для матриц с элементами типа <code>int</code> и <code>float</code> практически не отличается.

	<gallery class="center" mode="slideshow" style="float:center">		<gallery class="center" mode="slideshow" style="float:center">
	file:zhenya_int.svg\|thumb\|center\|1800px\|Рисунок 2. Параллельная реализация умножения разреженных матриц с элементами типа int.		file:zhenya_int.svg\|thumb\|center\|1800px\|Рисунок 3. Параллельная реализация умножения разреженных матриц с элементами типа int.
	file:zhenya_float.svg\|thumb\|center\|1800px\|Рисунок 3. Параллельная реализация умножения разреженных матриц с элементами типа float.		file:zhenya_float.svg\|thumb\|center\|1800px\|Рисунок 4. Параллельная реализация умножения разреженных матриц с элементами типа float.
	</gallery>		</gallery>

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

2023-12-04T22:31:52Z

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

← Предыдущая версия		Версия от 22:31, 4 декабря 2023
Строка 176:		Строка 176:
	=== Информационный граф ===		=== Информационный граф ===
	На рис. 2 изображен информационный граф алгоритма перемножения разреженных матриц. Этапы выполнения метода помечены цифрами:		На рис. 2 изображен информационный граф алгоритма перемножения разреженных матриц. Этапы выполнения метода помечены цифрами:
	1 - инициализация ~~результатфа~~;		1 - инициализация результата;
	2 - параллельное вычисление скалярного произведения;
			2 - параллельное вычисление скалярного произведения;

	3 - объединение полученных результатов.		3 - объединение полученных результатов.

	На этапе 2 параллельно для каждой строки считается последовательно скалярное произведение с каждым столбцом.		На этапе 2 параллельно для каждой строки считается последовательно скалярное произведение с каждым столбцом.
	[[file:zhenya_skipod.png\|thumb\|center\|800px\|Рисунок 2. Информационный граф операции произведения разреженных матриц.]]		[[file:zhenya_skipod.png\|thumb\|center\|800px\|Рисунок 2. Информационный граф операции произведения разреженных матриц.]]

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

2023-12-04T22:31:27Z

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

← Предыдущая версия		Версия от 22:31, 4 декабря 2023
Строка 175:		Строка 175:

	=== Информационный граф ===		=== Информационный граф ===
			На рис. 2 изображен информационный граф алгоритма перемножения разреженных матриц. Этапы выполнения метода помечены цифрами:
	[[file:zhenya_skipod.png\|thumb\|center\|~~1200px~~\|Рисунок 2. Информационный граф операции произведения разреженных матриц.]]		1 - инициализация результатфа;
			2 - параллельное вычисление скалярного произведения;
			3 - объединение полученных результатов.
			На этапе 2 параллельно для каждой строки считается последовательно скалярное произведение с каждым столбцом.
			[[file:zhenya_skipod.png\|thumb\|center\|800px\|Рисунок 2. Информационный граф операции произведения разреженных матриц.]]

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

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

2023-12-04T22:19:08Z

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

← Предыдущая версия		Версия от 22:19, 4 декабря 2023
Строка 175:		Строка 175:

	=== Информационный граф ===		=== Информационный граф ===
	Информационный граф представляет шаги, описанные в виде последовательности операций в [[#Схема реализации последовательного алгоритма\|схеме реализации последовательного алгоритма]] с точками принятия решения и параллельной обработкой, указанными для цикла на шаге 4. Описанный граф изображен на рис. 1. Граф отображает параллельную версию операции произведения разреженных матриц, где каждая строка показывает ядро алгоритма (произведение строки на столбец).

	[[file:~~Zhenya_skipod~~.~~svg~~\|thumb\|center\|1200px\|Рисунок 1. ~~Граф алгоритма~~ операции произведения разреженных матриц.]]		[[file:zhenya_skipod.png\|thumb\|center\|1200px\|Рисунок 2. Информационный граф операции произведения разреженных матриц.]]

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

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

2023-12-04T22:17:25Z

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

← Предыдущая версия		Версия от 22:17, 4 декабря 2023
Строка 177:		Строка 177:
	Информационный граф представляет шаги, описанные в виде последовательности операций в [[#Схема реализации последовательного алгоритма\|схеме реализации последовательного алгоритма]] с точками принятия решения и параллельной обработкой, указанными для цикла на шаге 4. Описанный граф изображен на рис. 1. Граф отображает параллельную версию операции произведения разреженных матриц, где каждая строка показывает ядро алгоритма (произведение строки на столбец).		Информационный граф представляет шаги, описанные в виде последовательности операций в [[#Схема реализации последовательного алгоритма\|схеме реализации последовательного алгоритма]] с точками принятия решения и параллельной обработкой, указанными для цикла на шаге 4. Описанный граф изображен на рис. 1. Граф отображает параллельную версию операции произведения разреженных матриц, где каждая строка показывает ядро алгоритма (произведение строки на столбец).

	[[file:~~zhenya_skipod~~.svg\|thumb\|center\|1200px\|Рисунок 1. Граф алгоритма операции произведения разреженных матриц.]]		[[file:Zhenya_skipod.svg\|thumb\|center\|1200px\|Рисунок 1. Граф алгоритма операции произведения разреженных матриц.]]

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

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

2023-12-04T22:15:13Z

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

← Предыдущая версия		Версия от 22:15, 4 декабря 2023
Строка 177:		Строка 177:
	Информационный граф представляет шаги, описанные в виде последовательности операций в [[#Схема реализации последовательного алгоритма\|схеме реализации последовательного алгоритма]] с точками принятия решения и параллельной обработкой, указанными для цикла на шаге 4. Описанный граф изображен на рис. 1. Граф отображает параллельную версию операции произведения разреженных матриц, где каждая строка показывает ядро алгоритма (произведение строки на столбец).		Информационный граф представляет шаги, описанные в виде последовательности операций в [[#Схема реализации последовательного алгоритма\|схеме реализации последовательного алгоритма]] с точками принятия решения и параллельной обработкой, указанными для цикла на шаге 4. Описанный граф изображен на рис. 1. Граф отображает параллельную версию операции произведения разреженных матриц, где каждая строка показывает ядро алгоритма (произведение строки на столбец).

	[[file:zhenya_skipod.svg\|thumb\|~~right~~\|~~400px~~\|Рисунок 1. Граф алгоритма операции произведения разреженных матриц.]]		[[file:zhenya_skipod.svg\|thumb\|center\|1200px\|Рисунок 1. Граф алгоритма операции произведения разреженных матриц.]]

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

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

2023-12-04T22:13:17Z

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

← Предыдущая версия		Версия от 22:13, 4 декабря 2023
Строка 177:		Строка 177:
	Информационный граф представляет шаги, описанные в виде последовательности операций в [[#Схема реализации последовательного алгоритма\|схеме реализации последовательного алгоритма]] с точками принятия решения и параллельной обработкой, указанными для цикла на шаге 4. Описанный граф изображен на рис. 1. Граф отображает параллельную версию операции произведения разреженных матриц, где каждая строка показывает ядро алгоритма (произведение строки на столбец).		Информационный граф представляет шаги, описанные в виде последовательности операций в [[#Схема реализации последовательного алгоритма\|схеме реализации последовательного алгоритма]] с точками принятия решения и параллельной обработкой, указанными для цикла на шаге 4. Описанный граф изображен на рис. 1. Граф отображает параллельную версию операции произведения разреженных матриц, где каждая строка показывает ядро алгоритма (произведение строки на столбец).

	[[file:~~zhenya_diagram~~.svg\|thumb\|right\|400px\|Рисунок 1. Граф алгоритма операции произведения разреженных матриц.]]		[[file:zhenya_skipod.svg\|thumb\|right\|400px\|Рисунок 1. Граф алгоритма операции произведения разреженных матриц.]]

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

ZhenyaNikishkina: /* Схема реализации последовательного алгоритма */

2023-12-04T22:11:57Z

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

ZhenyaNikishkina: /* Схема реализации последовательного алгоритма */

2023-12-04T22:10:16Z

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

← Предыдущая версия		Версия от 22:10, 4 декабря 2023
Строка 165:		Строка 165:
	# Скопировать ненулевые элементы из <code>result_local</code> в <code>result.elements</code> и освободить память, выделенную для <code>result_local</code>.		# Скопировать ненулевые элементы из <code>result_local</code> в <code>result.elements</code> и освободить память, выделенную для <code>result_local</code>.
	# Вернуть результирующую матрицу в формате COO, содержащую произведение двух входных матриц.		# Вернуть результирующую матрицу в формате COO, содержащую произведение двух входных матриц.

			Граф представляет шаги, описанные в виде последовательности операций с точками принятия решения и параллельной обработкой, указанными для цикла на шаге 4. Описанный граф изображен на рис. 1.

			[[file:zhenya_diagram.svg\|thumb\|right\|400px\|Рисунок 1. Граф алгоритма операции произведения разреженных матриц.]]

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

← Предыдущая версия		Версия от 22:11, 4 декабря 2023
Строка 146:		Строка 146:

	=== Схема реализации последовательного алгоритма ===		=== Схема реализации последовательного алгоритма ===

			[[file:zhenya_diagram.svg\|thumb\|right\|400px\|Рисунок 1. Граф алгоритма операции произведения разреженных матриц.]]

	Для матричного умножения интуитивно понятно, что представление, которое может обеспечить легкий доступ к элементам каждой строки матрицы <math>A</math> и элементам каждого столбца матрицы <math>B</math>, является идеальным способом реализации данной процедуры. Форматы '''CSR''' и '''CSC''' естественным образом индексируют элементы в виде строк и столбцов соответственно, и при использовании в сочетании друг с другом удовлетворяют данное требование.		Для матричного умножения интуитивно понятно, что представление, которое может обеспечить легкий доступ к элементам каждой строки матрицы <math>A</math> и элементам каждого столбца матрицы <math>B</math>, является идеальным способом реализации данной процедуры. Форматы '''CSR''' и '''CSC''' естественным образом индексируют элементы в виде строк и столбцов соответственно, и при использовании в сочетании друг с другом удовлетворяют данное требование.
Строка 151:		Строка 153:

	# Инициализировать <code>totalcount</code> равным 0.		# Инициализировать <code>totalcount</code> равным 0.
	# Выделить память для массива <code>result_local</code> с размером, равным числу строк <~~сode~~>matrix.rows</code>.		# Выделить память для массива <code>result_local</code> с размером, равным числу строк <code>matrix.rows</code>.
	# Инициализировать массив <code>result_local</code> нулевым количеством просмотренных элементов в каждой строке и выделить память для массивов его элементов.		# Инициализировать массив <code>result_local</code> нулевым количеством просмотренных элементов в каждой строке и выделить память для массивов его элементов.
	# Ввести распараллеленный цикл (с помощью OpenMP) по строкам первой матрицы.		# Ввести распараллеленный цикл (с помощью OpenMP) по строкам первой матрицы.
	# Для каждой строки <code>i</code> вычислить количество ненулевых элементов в строке из первой матрицы, которая представлена в формате CSR.		# Для каждой строки <code>i</code> вычислить количество ненулевых элементов в строке из первой матрицы, которая представлена в формате CSR.
	# Для каждого столбца <code>j</code> в второй матрицы, представленной в формате CSC, выполнить следующие действия:		# Для каждого столбца <code>j</code> второй матрицы, представленной в формате CSC, выполнить следующие действия:
	## Инициализировать <code>dp</code> (скалярное произведение) равным 0.		## Инициализировать <code>dp</code> (скалярное произведение) равным 0.
	## Установить <code>m1pos</code> в качестве начального индекса строки <~~сode~~>i</code>, а <code>m1seen</code> - в 0.		## Установить <code>m1pos</code> в качестве начального индекса строки <code>i</code>, а <code>m1seen</code> - в 0.
	## Вычислить количество ненулевых элементов в столбце <code>j</code> (<code>m2count</code>) и установить для <code>m2pos</code> начальный индекс столбца <code>j</code>, а для <code>m2seen</code> - 0.		## Вычислить количество ненулевых элементов в столбце <code>j</code> (<code>m2count</code>) и установить для <code>m2pos</code> начальный индекс столбца <code>j</code>, а для <code>m2seen</code> - 0.
	## Выполнить итерацию по ненулевым элементам строки <code>i</code> и столбца <code>j</code>, умножая совпадающие элементы и суммируя их в <code>dp</code>.		## Выполнить итерацию по ненулевым элементам строки <code>i</code> и столбца <code>j</code>, умножая совпадающие элементы и суммируя их в <code>dp</code>.
Строка 167:		Строка 169:

	Граф представляет шаги, описанные в виде последовательности операций с точками принятия решения и параллельной обработкой, указанными для цикла на шаге 4. Описанный граф изображен на рис. 1.		Граф представляет шаги, описанные в виде последовательности операций с точками принятия решения и параллельной обработкой, указанными для цикла на шаге 4. Описанный граф изображен на рис. 1.

	~~[[file:zhenya_diagram.svg\|thumb\|right\|400px\|Рисунок 1. Граф алгоритма операции произведения разреженных матриц.]]~~

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