Участник:Diana Pimenova/Алгоритм Фокса умножения матриц - История изменений

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

2017-11-26T15:58:01Z

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

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

	* Каждой подзадаче <math>(i,j)</math> передаются блоки <math>A_{ij}</math>, <math>B_{ij}</math> и обнуляются блоки <math>C_{ij}</math> на всех подзадачах.		* Каждой подзадаче <math>(i,j)</math> передаются блоки <math>A_{ij}</math>, <math>B_{ij}</math> и обнуляются блоки <math>C_{ij}</math> на всех подзадачах.
	* Для каждой строки <math>i</math> блок <math>A_{ij}</math> ~~подзадачи <math>(i,j)</math>~~ пересылается на все ~~подзадачи той~~ же строки ~~<math>i</math> решетки~~.		* Для каждой строки <math>i (i = 0, …, q)</math> блок <math>A_{ij}</math> одного из процессов пересылается во все процессы этой же строки.
	* ~~Полученные~~ в ~~результаты пересылок блоки~~ <math>A~~'_{ij}~~</math>, <math>~~B'_{ij}~~</math> ~~каждой подзадачи~~ <math>~~(i,j)~~</math> перемножаются и ~~прибавляются~~ к ~~блоку~~ <math>C_{ij}</math><math>~~: C_{ij}~~ = ~~C_{ij} + A'_{ij}B'_{ij}~~ </math>.		* Полученный в результате подобной пересылки блок матрицы <math>A</math> и содержащийся в процессе <math>(i, j)</math>
	* блоки <math>B~~'_{ij}~~</math> ~~каждой подзадачи~~ <math>(i,j)</math> ~~пересылаются подзадачам~~, ~~являющимися соседями сверху~~ в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).		блок матрицы <math>B</math> перемножаются, и результат прибавляется к матрице <math>С_{ij}</math>.
			* Для каждого столбца <math>j (j = 0, …, q)</math> выполняется циклическая пересылка блоков матрицы <math>B</math>, содер-
			жащихся в каждом процессе <math>(i, j)</math> этого столбца, в направлении убывания номеров строк.


	Число блоков определяется как округление снизу корня квадратного из числа доступных процессов.		Число блоков определяется как округление снизу корня квадратного из числа доступных процессов.

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

2017-11-26T15:51:44Z

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

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

	Число блоков определяется как округление снизу корня квадратного из числа доступных процессов.		Число блоков определяется как округление снизу корня квадратного из числа доступных процессов.
	[[File: ~~Foxgraph~~.~~png~~\|thumb\|center\|400px\|]]		[[File: fox.jpg\|thumb\|center\|400px\|]]

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

2017-11-16T20:08:36Z

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

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


	Синим цветом на информационном графе отмечен этап инициализации результирующей матрицы, то есть заполнение всех блоков нулями. Красным цветом обозначен этап, на котором происходит умножение подматриц, хранящихся в этом процессе, а также обмен подматрицами с другими процессами и прибавление произведения переданных подматриц на сохраненные.Желтым цветом обозначен уже вывод результата соответствующего блока.		Синим цветом на информационном графе отмечен этап инициализации результирующей матрицы, то есть заполнение всех блоков нулями. Красным цветом обозначен этап, на котором происходит умножение подматриц, хранящихся в этом процессе, а также обмен подматрицами с другими процессами и прибавление произведения переданных подматриц на сохраненные(на картинках в начале статьи более подробно нарисовано, какие блоки передаются).Желтым цветом обозначен уже вывод результата соответствующего блока.

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

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

2017-11-16T20:05:16Z

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

← Предыдущая версия		Версия от 20:05, 16 ноября 2017
Строка 74:		Строка 74:
	* блоки <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).		* блоки <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).

			Число блоков определяется как округление снизу корня квадратного из числа доступных процессов.
	[[File: Foxgraph.png\|thumb\|center\|400px\|]]		[[File: Foxgraph.png\|thumb\|center\|400px\|]]

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

2017-11-16T20:04:18Z

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

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

	[[File: Foxgraph.png\|thumb\|center\|400px\|]]		[[File: Foxgraph.png\|thumb\|center\|400px\|]]


			Синим цветом на информационном графе отмечен этап инициализации результирующей матрицы, то есть заполнение всех блоков нулями. Красным цветом обозначен этап, на котором происходит умножение подматриц, хранящихся в этом процессе, а также обмен подматрицами с другими процессами и прибавление произведения переданных подматриц на сохраненные.Желтым цветом обозначен уже вывод результата соответствующего блока.

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

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

2017-11-16T19:48:30Z

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

← Предыдущая версия		Версия от 19:48, 16 ноября 2017
Строка 74:		Строка 74:
	* блоки <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).		* блоки <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).

	[[File: Foxgraph.png\|thumb\|center\|~~600px~~\|]]		[[File: Foxgraph.png\|thumb\|center\|400px\|]]

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

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

2017-11-16T19:48:16Z

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

← Предыдущая версия		Версия от 19:48, 16 ноября 2017
Строка 73:		Строка 73:
	* Полученные в результаты пересылок блоки <math>A'_{ij}</math>, <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> перемножаются и прибавляются к блоку <math>C_{ij}</math><math>: C_{ij} = C_{ij} + A'_{ij}B'_{ij} </math>.		* Полученные в результаты пересылок блоки <math>A'_{ij}</math>, <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> перемножаются и прибавляются к блоку <math>C_{ij}</math><math>: C_{ij} = C_{ij} + A'_{ij}B'_{ij} </math>.
	* блоки <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).		* блоки <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).

			[[File: Foxgraph.png\|thumb\|center\|600px\|]]

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

Diana Pimenova: /* Общее описание алгоритма */

2017-11-16T19:46:57Z

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

← Предыдущая версия		Версия от 19:46, 16 ноября 2017
Строка 5:		Строка 5:
	== Общее описание алгоритма ==		== Общее описание алгоритма ==
	Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.<ref>Лекции по высокопроизводительным вычислительным системам СПбГПУ, 2016.</ref>		Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.<ref>Лекции по высокопроизводительным вычислительным системам СПбГПУ, 2016.</ref>


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

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

	== Математическое описание алгоритма ==		== Математическое описание алгоритма ==

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

2017-11-16T19:46:29Z

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

← Предыдущая версия		Версия от 19:46, 16 ноября 2017
Строка 68:		Строка 68:
	* Полученные в результаты пересылок блоки <math>A'_{ij}</math>, <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> перемножаются и прибавляются к блоку <math>C_{ij}</math><math>: C_{ij} = C_{ij} + A'_{ij}B'_{ij} </math>.		* Полученные в результаты пересылок блоки <math>A'_{ij}</math>, <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> перемножаются и прибавляются к блоку <math>C_{ij}</math><math>: C_{ij} = C_{ij} + A'_{ij}B'_{ij} </math>.
	* блоки <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).		* блоки <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).


	~~[[File:Fox1.png]]~~

	~~[[File:Fox2.png]]~~

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

Diana Pimenova: /* Характеристики программно-аппаратной среды */

2017-11-16T19:28:27Z

Характеристики программно-аппаратной среды

← Предыдущая версия		Версия от 19:28, 16 ноября 2017
Строка 169:		Строка 169:
	Все вычисления были произведены на суперкомпьютере "Ломоносов".		Все вычисления были произведены на суперкомпьютере "Ломоносов".

	Для компиляции был использован компилятор языка C++ GNU 4.4.6.		Для компиляции был использован компилятор языка C++ GNU 4.4.6. Использованная реализация MPI: Intel MPI 4.0.3. Опции компилятора: -lm.

	Вычисления производились в очереди test. Ограничений на лимит времени на узел наложено не было.		Вычисления производились в очереди test. Ограничений на лимит времени на узел наложено не было.


	== Динамические характеристики и эффективность реализации алгоритма ==		== Динамические характеристики и эффективность реализации алгоритма ==