Алгоритм Фокса умножения матриц - История изменений

Diana Pimenova: Полностью удалено содержимое страницы

2017-10-23T19:29:18Z

Полностью удалено содержимое страницы

← Предыдущая версия		Версия от 19:29, 23 октября 2017
Строка 1:		Строка 1:
	~~Автор: [[Участник:Diana Pimenova\|Д.В.Пименова]]~~

	~~= Свойства и структура алгоритмов =~~

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

	~~== Математическое описание алгоритма ==~~
	Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

	~~Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).~~

	При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
	~~:<math>~~
	~~\begin{align}~~
	~~C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].~~
	~~\end{align}~~
	~~</math>~~


	~~== Вычислительное ядро алгоритма ==~~
	Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
	~~:<math>~~
	~~\begin{align}~~
	~~\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].~~
	~~\end{align}~~
	~~</math>~~
	~~<ref>http://it.kgsu.ru/ParalAlg/palg046.html</ref>~~

	~~== Макроструктура алгоритма ==~~

	Как уже записано в [[#Вычислительное ядро алгоритма\|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
	~~:<math>~~
	~~\begin{align}~~
	~~\sum_{k = 1}^{n} a_{ik} b_{kj}~~
	~~\end{align}~~
	~~</math>~~


	~~== Схема реализации последовательного алгоритма ==~~
	~~Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.~~
	Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
	Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

	~~:<math>~~
	~~\begin{align}~~
	~~С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].~~
	~~\end{align}~~
	~~</math>~~

	После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.<ref>Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016.</ref>

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

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

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

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

	~~= Программная реализация алгоритма =~~

	~~= Литература =~~
	~~<references />~~

Diana Pimenova в 15:11, 23 октября 2017

2017-10-23T15:11:13Z

← Предыдущая версия		Версия от 15:11, 23 октября 2017
Строка 1:		Строка 1:
			Автор: [[Участник:Diana Pimenova\|Д.В.Пименова]]

	= Свойства и структура алгоритмов =		= Свойства и структура алгоритмов =

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

Diana Pimenova: /* Вычислительное ядро алгоритма */

2017-10-09T17:44:12Z

Вычислительное ядро алгоритма

← Предыдущая версия		Версия от 17:44, 9 октября 2017
Строка 24:		Строка 24:
	\end{align}		\end{align}
	</math>		</math>
			<ref>http://it.kgsu.ru/ParalAlg/palg046.html</ref>

	== Макроструктура алгоритма ==		== Макроструктура алгоритма ==

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

2017-10-09T17:43:06Z

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

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

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

Diana Pimenova: /* Литература */

2017-10-09T17:39:16Z

Литература

← Предыдущая версия		Версия от 17:39, 9 октября 2017
Строка 60:		Строка 60:
	= Литература =		= Литература =
	<references />		<references />
	~~1. Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016~~

	~~2. Гергель В. П. Теория и практика параллельных вычислений: учебное пособие, ИНТУИТ, 2007~~

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

2017-10-09T17:39:02Z

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

← Предыдущая версия		Версия от 17:39, 9 октября 2017
Строка 46:		Строка 46:
	</math>		</math>

	После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.		После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.<ref>Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016.</ref>

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

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

2017-10-09T17:32:54Z

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

← Предыдущая версия		Версия от 17:32, 9 октября 2017
Строка 2:		Строка 2:
	= Свойства и структура алгоритмов =		= Свойства и структура алгоритмов =
	== Общее описание алгоритма ==		== Общее описание алгоритма ==
	Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти.		Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.

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

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

2017-10-09T17:31:08Z

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

← Предыдущая версия		Версия от 17:31, 9 октября 2017
Строка 2:		Строка 2:
	= Свойства и структура алгоритмов =		= Свойства и структура алгоритмов =
	== Общее описание алгоритма ==		== Общее описание алгоритма ==
	Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти.		Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти.


	== Математическое описание алгоритма ==		== Математическое описание алгоритма ==
	Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).		Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

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

2017-10-09T17:16:32Z

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

← Предыдущая версия		Версия от 17:16, 9 октября 2017
Строка 43:		Строка 43:
	:<math>		:<math>
	\begin{align}		\begin{align}
	S_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].		С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
	\end{align}		\end{align}
	</math>		</math>

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

2017-10-09T17:13:42Z

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

@@ Строка 37: / Строка 37: @@
 == Схема реализации последовательного алгоритма ==
-Вначале производится рассылка в процесс с координатами (i, j) блоков Aij, Bij исходных матриц.
+После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.
 == Последовательная сложность алгоритма ==