Теория и практика параллельных вычислений
Краткий обзор лекции
В данной лекции рассмотрены три параллельных метода для выполнения операции матричного умножения. Первый алгоритм основан на ленточном разделении матриц между процессорами. В лекции приведены два различных варианта этого алгоритма. Первый вариант алгоритма основан на различном разделении перемножаемых матриц – первая матрица (матрица A) разбивается на горизонтальные полосы, а вторая матрица (матрица B) делится на вертикальные полосы. Второй вариант ленточного алгоритма использует разбиение обеих матриц на горизонтальные полосы.
Далее в лекции рассматриваются широко известные алгоритмы Фокса и Кэннона, основанные на блочном разделении матриц. При использовании одинаковой схемы разбиения матриц данные алгоритмы отличаются характером выполняемых операций передачи данных. Для алгоритма Фокса в ходе вычислений осуществляется рассылка и циклический сдвиг блоков матриц, в алгоритме Кэннона выполняется только операция циклического сдвига.
Различие в способах разбиения данных приводит к разным топологиям коммуникационной сети, при которых выполнение параллельных алгоритмов является наиболее эффективным. Так, алгоритмы, основанные на ленточном разделении данных, ориентированы на топологию сети в виде гиперкуба или полного графа. Для реализации алгоритмов, основанных на блочном разделении данных, необходимо наличие топологии решетки.
На рис. 7.12 на общем графике представлены показатели ускорения, полученные в результате выполнения вычислительных экспериментов для всех рассмотренных алгоритмов. Выполненные расчеты показывают, что при большем количестве процессоров более эффективными становятся блочные алгоритмы умножения матриц.
Рис. 7.12. Ускорение трех параллельных алгоритмов при умножении матриц с использованием четырех процессоров
