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

                                                       - 87 -


  Теперь в двух внутренних циклах доступен квадрат из m × m элементов мат-
риц a и b, который полностью помещается в кэш. Преобразование разделения на
блоки является комбинацией разделения на полосы и перестановки циклов.
  Преобразование перекос циклов используется с целью выделения скрытой па-
раллельности в основном вдоль волновых фронтов (в этом случае обновления
величин в массивах распространяется подобно волне). Типичный пример – ре-
шение дифуравнений в частных производных методом Гаусса-Зейделя при 5-
точечном шаблоне на равномерной квадратной сетке размером n × n [3]:




Рисунок 23 — Зависимости по данным в методе итераций Гаусса-Зейделя: a) – исход-
      ное пространство итераций, б) – пространство итераций после сдвига цикла.

  for [i=1 to n]
   for [j=1 to n]
    a[i, j] = 0.25 × (a[i-1, j]) + a[i, j-1] + a[i+1, j] + a[i, j+1]);

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

  for [i=1 to n]
   for [j=i+1 to i+n] // прибавить i к имеющимся границам                          (9)
    a[i, j-i] = 0.25 × (a[i-1, j-i]) + a[i, j-1-i] + a[i+1, j-i] + a[i, j+1-i]);

  Перекос цикла позволил выявить параллельность, ибо после преобразований
зависимостей в каждом столбце области итераций больше нет, однако зависи-
мости остались во внешнем цикле.
  Из фрагмента (9) видно, что границы внутреннего цикла зависят от значений
индекса внешнего. Однако границы исходных циклов независимы, поэтому вы-