Параллельные вычисления. Баканов В.М. - 93 стр.

                                          - 93 -


   Фрагмент (9) повторяется циклически, чтобы вычисляемые прямоугольные
блоки заполнили матрицу [C] целиком. Хотя для вычисления каждого блока
матрицы [C] в самом деле необходимы указанные на рис.25 горизонтальная
лента [A] и вертикальная лента [B], оне (ленты) будут пересылаться еще мно-
го раз при вычислении других прямоугольных блоков результирующей мат-
рицы [C]. Одна из модификаций алгоритма лежит буквально ‘на поверхно-
сти’ – при заданной вертикальной ленте [B] возможно вычислить не только
прямоугольный блок сij , i ∈ [i 1...i 1], i ∈ [j 1... j 2] , но и всю вертикальную ленту
сij , i ∈ [ 1...i max ], i ∈ [j 1... j 2] элементов матрицы [C] (выделено пунктиром на
рис.25); для этого достаточно пересылать процессорам только новые гори-
зонтальные ленты матрицы [A] при неизменной вертикальной ленте [B].
  Анализ избыточности пересылок привел к модификации методов умно-
жения матриц – блочным алгоритмам Фокса (Geoffrey Fox) и Кэннона, в слу-
чае применения которых процессам пересылаются для обработки не ленты, а
прямоугольные блоки перемножаемых матриц (эти алгоритмы требуют до-
полнительных обменов данными между процессорами, вычисляющим итого-
вую матрицу). Наличие интенсивных обменов между процессами характерно
и для методов волновой обработки данных (wavefront or hyperplane methods).
  Подобным же целям (конечная решаемая задача – реализация возможно
более крупноблочного параллелизма) служит метод распределения данных с
теневыми гранями (окружение основного обрабатываемого блока буферной
зоной шириной 1 элемент данных, куда принимаются при обменах копии
значений от соседних процессоров), [5].

  Контрольные вопросы

1. Что такое граф алгоритма? Почему ГА является ориентированным? Чем
   определяется принадлежность вершин ГА к множеству входных и выход-
   ных? Что такое ярусно-параллельная форма алгоритма?
2. Каким образом матрица смежности представляет граф алгоритма?
3. Что такое операторы-преобразователи и операторы-распознаватели? В ка-
   ких моделях графового представления алгоритмов они используются?
4. В чем заключается потенциал параллелизма в циклах? Какие методы ана-
   лиза пространства итераций используются для выявления параллелизма?
   Что такое циклы ParDO?
5. Каким образом выявляется параллелизм системами автоматического рас-
   параллеливания? Какие эквивалентные преобразования обычно выполня-
   ются этими системами? Что такое редукция высоты дерева и на основе ка-
   ких свойств арифметики она реализуется?
6. Что такое сбалансированность загрузки процессоров при распараллелива-
   нии? Каково условие сбалансированности?