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

       

Блочные алгоритмы Фокса и Кэннона


При блочном представлении данных параллельная вычислительная схема матричного умножения в наиболее простом виде может быть построена, если топология вычислительной сети имеет вид прямоугольной решетки (если реальная топология сети имеет иной вид, представление сети в виде решетки можно обеспечить на логическом уровне). Основные положения параллельных методов для блочно представленных матриц состоят в следующем:

  1. каждый из процессоров решетки отвечает за вычисление одного блока матрицы C;
  2. в ходе вычислений на каждом из процессоров располагается по одному блоку исходных матриц A и В;
  3. при выполнении итераций алгоритмов блоки матрицы А последовательно сдвигаются вдоль строк процессорной решетки, а блоки матрицы B — вдоль столбцов решетки;
  4. в результате вычислений на каждом из процессоров получается блок матрицы С, при этом общее количество итераций алгоритма равно (где р – число процессоров).

В лекции 7 приводится полное описание параллельных методов Фокса и Кэннона для умножения блочно-представленных матриц.

Задания и упражнения

  • В активном окне вычислительного эксперимента системы ПараЛаб установите топологию Решетка. Выберите число процессоров, равное девяти. Сделайте текущей задачей этого окна задачу матричного умножения.
  • Выберите метод Фокса умножения матриц и проведите вычислительный эксперимент.
  • Выберите алгоритм Кэннона матричного умножения и выполните вычислительный эксперимент. Пронаблюдайте различные маршруты передачи данных при выполнении алгоритмов. Сравните временные характеристики алгоритмов.
  • Измените число процессоров в топологии Решетка на шестнадцать. Последовательно выполните вычислительные эксперименты с использованием метода Фокса и метода Кэннона. Сравните временные характеристики этих экспериментов.



Содержание раздела