Теория и практика параллельных вычислений



         

Выделение информационных зависимостей


Итак, за основу параллельных вычислений для матричного умножения при блочном разделении данных принят подход, при котором базовые подзадачи отвечают за вычисления отдельных блоков матрицы 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).




Содержание  Назад  Вперед