Лекции по параллельным вычислениям. Гергель В.П - 136 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

136
Размещение всех требуемых данных в каждой подзадаче неизбежно приве-
дет к дублированию и к значительному росту объема требуемой памяти. По-
этому целесообразно вычисления организовать таким образом, чтобы в каждый
текущий момент времени подзадачи содержали лишь необходимые для реали-
зации текущего этапа данные. При этом для доступа к остальным данным пона-
добится передача данных между процессорами. Ниже рассматривается два воз-
можных способа организации такой вычислительной схемы (алгоритм Фокса)
[3].
В рассматриваемой (первой) вычислительной схеме в каждой подзадаче на
каждой итерации расчетов располагается только по одному блоку исходных
матриц A и B. Для нумерации подзадач используются индексы размещаемых в
подзадачах блоков матрицы C, т.е. подзадача (i,j) отвечает за вычисление блока
C
i,j
– тем самым набор подзадач образует квадратную решетку, соответствую-
щую структуре блочного представления матрицы C.
С учетом принятых обозначений в ходе вычислений каждой подзадаче (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, определяющий положение подза-
дачи в строке, вычисляется в соответствии с выражением

Страницы