|
|
| (не показана 1 промежуточная версия этого же участника) |
| Строка 1: |
Строка 1: |
|
| |
|
| = Свойства и структура алгоритмов =
| |
| == Общее описание алгоритма ==
| |
| Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.<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 />
| |