Теория и практика параллельных вычислений
Выделение информационных зависимостей
Для вычисления одной строки матрицы С необходимо, чтобы в каждой подзадаче содержалась строка матрицы А и был обеспечен доступ ко всем столбцам матрицы B. Возможные способы организации параллельных вычислений состоят в следующем.
1. Первый алгоритм. Алгоритм представляет собой итерационную процедуру, количество итераций которой совпадает с числом подзадач. На каждой итерации алгоритма каждая подзадача содержит по одной строке матрицы А и одному столбцу матрицы В. При выполнении итерации проводится скалярное умножение содержащихся в подзадачах строк и столбцов, что приводит к получению соответствующих элементов результирующей матрицы С. По завершении вычислений в конце каждой итерации столбцы матрицы В должны быть переданы между подзадачами с тем, чтобы в каждой подзадаче оказались новые столбцы матрицы В и могли быть вычислены новые элементы матрицы C. При этом данная передача столбцов между подзадачами должна быть организована таким образом, чтобы после завершения итераций алгоритма в каждой подзадаче последовательно оказались все столбцы матрицы В.
Возможная простая схема организации необходимой последовательности передач столбцов матрицы В между подзадачами состоит в представлении топологии информационных связей подзадач в виде кольцевой структуры. В этом случае на каждой итерации подзадача i, 0i<n, будет передавать свой столбец матрицы В подзадаче с номером i+1 (в соответствии с кольцевой структурой подзадача n-1 передает свои данные подзадаче с номером 0) – см. рис. 7.2. После выполнения всех итераций алгоритма необходимое условие будет обеспечено – в каждой подзадаче поочередно окажутся все столбцы матрицы В.
На рис. 7.2 представлены итерации алгоритма матричного умножения для случая, когда матрицы состоят из четырех строк и четырех столбцов (n=4). В начале вычислений в каждой подзадаче i, 0i<n, располагаются i-я строка матрицы A и i-й столбец матрицы B. В результате их перемножения подзадача получает элемент cii
результирующей матрицы С. Далее подзадачи осуществляют обмен столбцами, в ходе которого каждая подзадача передает свой столбец матрицы B следующей подзадаче в соответствии с кольцевой структурой информационных взаимодействий.
Итак, за основу параллельных вычислений для матричного умножения при блочном разделении данных принят подход, при котором базовые подзадачи отвечают за вычисления отдельных блоков матрицы C и при этом в подзадачах на каждой итерации расчетов располагается только по одному блоку исходных матриц A и B. Для нумерации подзадач будем использовать индексы размещаемых в подзадачах блоков матрицы C, т.е. подзадача (i,j) отвечает за вычисление блока Cij – тем самым, набор подзадач образует квадратную решетку, соответствующую структуре блочного представления матрицы C.
Возможный способ организации вычислений при таких условиях состоит в применении широко известного алгоритма Фокса (Fox) — см., например, [[34], [51]].
В соответствии с алгоритмом Фокса в ходе вычислений на каждой базовой подзадаче (i,j) располагается четыре матричных блока:
- блок Cij матрицы C, вычисляемый подзадачей;
- блок Aij матрицы A, размещаемый в подзадаче перед началом вычислений;
- блоки A'ij , B'ij матриц A и B, получаемые подзадачей в ходе выполнения вычислений.
Выполнение параллельного метода включает:
- этап инициализации, на котором каждой подзадаче (i,j) передаются блоки Aij, Bij и обнуляются блоки Cij на всех подзадачах;
- этап вычислений, в рамках которого на каждой итерации l, 0l<q, осуществляются следующие операции:
- для каждой строки i, 0i<q, блок Aij подзадачи (i,j) пересылается на все подзадачи той же строки i решетки; индекс j, определяющий положение подзадачи в строке, вычисляется в соответствии с выражением
где mod есть операция получения остатка от целочисленного деления;
- полученные в результаты пересылок блоки A'ij, B'ij каждой подзадачи (i,j) перемножаются и прибавляются к блоку Cij
- блоки B'ij каждой подзадачи (i,j) пересылаются подзадачам, являющимся соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).
Рис. 7.6. Состояние блоков в каждой подзадаче в ходе выполнения итераций алгоритма Фокса
Для пояснения этих правил параллельного метода на рис. 7.6
приведено состояние блоков в каждой подзадаче в ходе выполнения итераций этапа вычислений (для решетки подзадач 2?2).
Отличие алгоритма Кэннона от метода Фокса состоит в изменении схемы начального распределения блоков перемножаемых матриц между подзадачами вычислительной системы. Начальное расположение блоков в алгоритме Кэннона подбирается таким образом, чтобы блоки в подзадачах могли бы быть перемножены без каких-либо дополнительных передач данных. При этом подобное распределение блоков может быть организовано таким образом, что перемещение блоков между подзадачами в ходе вычислений может осуществляться с использованием более простых коммуникационных операций.
С учетом высказанных замечаний этап инициализации алгоритма Кэннона включает выполнение следующих операций передач данных:
- в каждую подзадачу (i,j) передаются блоки Aij, Bij;
- для каждой строки i решетки подзадач блоки матрицы A сдвигаются на (i-1) позиций влево;
- для каждого столбца j решетки подзадач блоки матрицы B сдвигаются на (j-1) позиций вверх.
Выполняемые при перераспределении матричных блоков процедуры передачи данных являются примером операции циклического сдвига – см. лекцию 3. Для пояснения используемого способа начального распределения данных на рис. 7.9 показан пример расположения блоков для решетки подзадач 3і3.
увеличить изображение
Рис. 7.9. Перераспределение блоков исходных матриц между процессорами при выполнении алгоритма Кэннона
В результате такого начального распределения в каждой базовой подзадаче будут располагаться блоки, которые могут быть перемножены без дополнительных операций передачи данных. Кроме того, получение всех последующих блоков для подзадач может быть обеспечено при помощи простых коммуникационных действий — после выполнения операции блочного умножения каждый блок матрицы A должен быть передан предшествующей подзадаче влево по строкам решетки подзадач, а каждый блок матрицы В – предшествующей подзадаче вверх по столбцам решетки. Как можно показать, последовательность таких циклических сдвигов и умножение получаемых блоков исходных матриц A и B приведет к получению в базовых подзадачах соответствующих блоков результирующей матрицы C.
