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