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

                                              - 85 -

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

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

  for [i=1 to n]
   for [j=1 to n]
    for [k=1 to n
     c[i, j] = c[i, j] + a[i, k] * b[k, j];

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

  for [i=1 to n by 2] // половина всех итераций (только нечетные i)
   for [j=1 to n]
    for [k=1 to n]                                                        (8)
    {
      c[i, j] = c[i, j] + a[i, k] + b[k, j];
      c[i+1, j] = c[i+1, j] + a[i, k] + b[k, j];
    }

  Здесь в каждом внешнем цикле вычисляются два скаляра c[i, j] и c[i+1, j], рас-
полагающиеся в смежных ячейках памяти (при условии, что матрицы в ОП хра-
нятся по столбцам – что характерно для Fortran’а и отнюдь не для C/C++). А
что мешает в каждом внешнем цикле вычислять не 2, а 3,4,5.. скаляров (конечно,
если n не делится нацело на это число, понадобится некоторое дополнение алго-
ритма)?
  В случае разделения на полосы цикл делится надвое, причем во внешнем цик-
ле перебираются полосы, а внутренний итерирует все элементы данной полосы.
Например, для умножения матриц единократное развертывание внешнего цикла
равноценно разделению полосы шириной 2 итерации (дополнительные итера-
ции производятся по индексу i1):

  for [i=1 to n by 2] // половина всех итераций (только нечетные i)
   for [i1=i to i+1] // полоса из двух итераций
    for [j=1 to n]
     for [k=1 to n]
      c[i1, j] = c[i1, j] + a[i1, k] + b[k, j];