Постановка задачи

Целью данной работы является разработка программы, вычисляющей произведение квадратных матриц больших размерностей. Используя несколько потоков обработки данных, требуется разработать алгоритм, позволяющий достаточно ускорить этот процесс. За основу берется блочный алгоритм умножения матриц Фокса. Требуется провести сравнение работы алгоритма при использовании одного и двух потоков обработки данных.

Описание алгоритма и метод решения

Алгоритм Фокса

Итак, за основу параллельных вычислений для матричного умножения при блочном разделении данных принят подход, при котором базовые подзадачи отвечают за вычисления отдельных блоков матрицы C и при этом в подзадачах на каждой итерации расчетов располагается только по одному блоку исходных матриц A и B. Для нумерации подзадач будем использовать индексы размещаемых в подзадачах блоков матрицы C, т.е. подзадача (i,j) отвечает за вычисление блока C_ij – тем самым, набор подзадач образует квадратную решетку, соответствующую структуре блочного представления матрицы C.

Возможный способ организации вычислений при таких условиях состоит в применении широко известного алгоритма Фокса (Fox). .

В соответствии с алгоритмом Фокса в ходе вычислений на каждой базовой подзадаче (i,j) располагается четыре матричных блока:

• блок C_ij матрицы C, вычисляемый подзадачей;
• блок A_ij матрицы A, размещаемый в подзадаче перед началом вычислений;
• блоки A'_ij, B'_ij матриц A и B, получаемые подзадачей в ходе выполнения вычислений.

Выполнение параллельного метода включает:

• этап инициализации, на котором каждой подзадаче (i,j) передаются блоки A_ij, B_ij и обнуляются блоки C_ij на всех подзадачах;
• этап вычислений, в рамках которого на каждой итерации l, 0<=l< q, осуществляются следующие операции:

• для каждой строки i, 0<=i< q, блок A_ij подзадачи (i,j) пересылается на все подзадачи той же строки i решетки; индекс j, определяющий положение подзадачи в строке, вычисляется в соответствии с выражением j = ( i + l ) mod q
  где mod есть операция получения остатка от целочисленного деления;
• полученные в результаты пересылок блоки A'_ij, B'_ij каждой подзадачи (i, j) перемножаются и прибавляются к блоку C_ij
• блоки >B'_ij каждой подзадачи (i,j) пересылаются подзадачам, являющимся соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).


Для пояснения этих правил параллельного метода на рис. 7.6 приведено состояние блоков в каждой подзадаче в ходе выполнения итераций этапа вычислений (для решетки подзадач 2x2 ).

Оценка эффективности

Определим вычислительную сложность данного алгоритма Фокса. Построение оценок будет происходить при условии выполнения всех ранее выдвинутых предположений: все матрицы являются квадратными размера nxn, количество блоков по горизонтали и вертикали являются одинаковым и равным q (т.е. размер всех блоков равен kxk, k=n/q ), процессоры образуют квадратную решетку и их количество равно p=q².

Как уже отмечалось, алгоритм Фокса требует для своего выполнения q итераций, в ходе которых каждый процессор перемножает свои текущие блоки матриц А и В и прибавляет результаты умножения к текущему значению блока матрицы C.

Примем за T_s - время работы последовательного алгоритма, за T_p - время работы параллельного алгоритма, за S - ускорение, за E - эффективность, за p – количество процессоров.

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

S_p = n³ / ( n³ / p) = p
E_p = n³ / [ p * ( n³ / p) ] = 1