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



         

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


Отличие алгоритма Кэннона от метода Фокса состоит в изменении схемы начального распределения блоков перемножаемых матриц между подзадачами вычислительной системы. Начальное расположение блоков в алгоритме Кэннона подбирается таким образом, чтобы блоки в подзадачах могли бы быть перемножены без каких-либо дополнительных передач данных. При этом подобное распределение блоков может быть организовано таким образом, что перемещение блоков между подзадачами в ходе вычислений может осуществляться с использованием более простых коммуникационных операций.

С учетом высказанных замечаний этап инициализации алгоритма Кэннона включает выполнение следующих операций передач данных:

  • в каждую подзадачу (i,j) передаются блоки Aij, Bij;
  • для каждой строки i решетки подзадач блоки матрицы A сдвигаются на (i-1) позиций влево;
  • для каждого столбца j решетки подзадач блоки матрицы B сдвигаются на (j-1) позиций вверх.

Выполняемые при перераспределении матричных блоков процедуры передачи данных являются примером операции циклического сдвига – см. лекцию 3. Для пояснения используемого способа начального распределения данных на рис. 7.9 показан пример расположения блоков для решетки подзадач 3і3.


увеличить изображение
Рис. 7.9.  Перераспределение блоков исходных матриц между процессорами при выполнении алгоритма Кэннона

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




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