|
|
| (не показано 9 промежуточных версий этого же участника) |
| Строка 1: |
Строка 1: |
| | | | |
| − | = Свойства и структура алгоритмов =
| |
| − | == Общее описание алгоритма ==
| |
| − | Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти.
| |
| − |
| |
| − |
| |
| − | == Математическое описание алгоритма ==
| |
| − | Исходные данные: квадратная матрица <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>
| |
| − |
| |
| − | == Макроструктура алгоритма ==
| |
| − |
| |
| − | Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
| |
| − | :<math>
| |
| − | \begin{align}
| |
| − | \sum_{k = 1}^{n} a_{ik} b_{kj}
| |
| − | \end{align}
| |
| − | </math>
| |
| − |
| |
| − |
| |
| − | == Схема реализации последовательного алгоритма ==
| |
| − |
| |
| − | Вначале производится рассылка в процесс с координатами (i, j) блоков Aij, Bij исходных матриц.
| |
| − | Кроме того, выполняется обнуление матрицы Cij, предназначенной для хранения соответствующего блока
| |
| − | результирующего произведения AB.
| |
| − | Затем запускается цикл по m (m = 0, …, q), в ходе которого выполняются три действия:
| |
| − | * для каждой строки i (i = 0, …, q) блок Aij одного из процессов пересылается во все процессы этой
| |
| − | же строки; при этом индекс j пересылаемого блока определяется по формуле j = (i + m) mod q;
| |
| − | * полученный в результате подобной пересылки блок матрицы A и содержащийся в процессе (i, j)
| |
| − | блок матрицы B перемножаются, и результат прибавляется к матрице Сij;
| |
| − | * для каждого столбца j (j = 0, …, q) выполняется циклическая пересылка блоков матрицы B, содержащихся в каждом процессе (i, j) этого столбца, в направлении убывания номеров строк.
| |
| − |
| |
| − | После завершения цикла в каждом процессе будет содержаться матрица Cij, равная соответствующему блоку произведения AB. Останется переслать эти блоки главному процессу.
| |
| − |
| |
| − |
| |
| − | == Последовательная сложность алгоритма ==
| |
| − |
| |
| − | == Информационный граф ==
| |
| − |
| |
| − | == Ресурс параллелизма алгоритма ==
| |
| − |
| |
| − | == Входные и выходные данные алгоритма ==
| |
| − |
| |
| − | = Программная реализация алгоритма =
| |
| − |
| |
| − | = Литература =
| |
| − | <references />
| |
| − | 1. Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016
| |
| − |
| |
| − | 2. Гергель В. П. Теория и практика параллельных вычислений: учебное пособие, ИНТУИТ, 2007
| |
