Алгоритм Фокса умножения матриц: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 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>).

Версия 20:31, 9 октября 2017

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

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

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

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

Исходные данные: квадратная матрица [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]


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

Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы [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]

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

Как уже записано в описании ядра алгоритма, основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы [math]A[/math] на блоки матрицы [math]B[/math]. Перемножать блоки будем стандартным методом, используя определение произведения матриц:

[math] \begin{align} \sum_{k = 1}^{n} a_{ik} b_{kj} \end{align} [/math]


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

Разобьем исходные матрицы на блоки [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].

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

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

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

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

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

3 Литература

1. Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016

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