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

                                     - 84 -


же если указатели не разрешены (как в Fortran’e) и индексные выражения яв-
ляются линейными функциями, проблема является NP-трудной, т.е. эффек-
тивного алгоритма решения ее скорее всего не существует.
  Ниже рассматриваются несколько полезных преобразований для циклов:
локализация, расширение скаляра, распределение цикла, слияние циклов, раз-
вертка и сжатие, развертка цикла, разделение на полосы, разделение на
блоки, перекос цикла, которые помогают выявлять параллельность, устранять
зависимости и оптимизировать использование памяти:

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

   Распределение циклов используется для устранения зависимости в цикле (фак-
тически для выявления параллелизма). Если исходный цикл имеет вид (здесь и
далее используется нотация языка программирования, равноудаленная и от For-
tran’а и от C)

  for [i=1 to n] {
   a[i] = … ;
   … = … + a[i-1];
  }

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

  for [i=1 to n]
   a[i] = … ;