Теория и практика параллельных вычислений
Ленточный алгоритм
При ленточной схеме разделения данных исходные матрицы разбиваются на горизонтальные (для матрицы A) и вертикальные (для матрицы B) полосы. Получаемые полосы распределяются по процессорам, при этом на каждом из имеющегося набора процессоров располагается только по одной полосе матриц A и B. Перемножение полос (а данная операция может быть выполнена процессорами параллельно) приводит к получению части блоков результирующей матрицы C. Для вычисления оставшихся блоков матрицы C сочетания полос матриц A и B на процессорах должны быть изменены. В наиболее простом виде это может быть обеспечено, например, при кольцевой топологии вычислительной сети (при числе процессоров, равном количеству полос) – в этом случае необходимое для матричного умножения изменение положения данных может быть реализовано циклическим сдвигом полос матрицы B по кольцу. После многократного выполнения описанных действий (количество необходимых повторений является равным числу процессоров) на каждом процессоре получается набор блоков, образующий горизонтальную полосу матрицы C.
Рассмотренная схема вычислений позволяет определить параллельный алгоритм матричного умножения при ленточной схеме разделения данных как итерационную процедуру, на каждом шаге которой происходит параллельное выполнение операции перемножения полос и последующего циклического сдвига полос одной из матриц по кольцу. Подробное описание ленточного алгоритма приводится в лекции 7.
Задания и упражнения
- Создайте в системе ПараЛаб новое окно вычислительного эксперимента. Для этого окна выберите задачу матричного умножения (щелкните левой кнопкой мыши на строке Матричное умножение пункта меню Задача).
- Откройте диалоговое окно выбора метода и убедитесь в том, что выбран метод ленточного умножения матриц.
- Проведите несколько вычислительных экспериментов. Изучите зависимость времени выполнения алгоритма от объема исходных данных и от количества процессоров.
