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

UptoLike

ВУЗ: 

МИРЭА | Москва

Составители: 

Рубрика: 

- 86 -
Преобразование развертки и сжатия равноценны разделению на полосы
внешнего цикла, перемещению разделенного цикла на место внутреннего и его
развертки (цикл максимальной вложенности использует индекс
i1
):
for [i=1 to n by 2] // половина всех итераций (только нечетные i)
for [j=1 to n]
for [k=1 to n]
for [i1=1 to i+1] // полоса из двух итераций
c[i1, j] = c[i1, j] + a[i1, k] + b[k, j];
После развертки внутреннего цикла (т.е. замены
i1
двумя значениями –
i
и
i+1
)
получается программа, равноценная полученной преобразованием развертки и
сжатия (8).
При разделении на блоки распределение данных в памяти компактируется и,
следовательно, повышается эффективность кэширования на МВС с общей памя-
тью или размещение данных в распределенной памяти. В качестве примера рас-
сматривается фрагмент транспонирования матрицы:
for [i=1 to n]
for [j=1 to n]
b[i, j] = a[j, i];
При условии хранения в памяти массивов по строкам (характерно для C/C++)
д
о
ступ к элементам матрицы
b
осуществляется с шагом 1 (каждый элемент
b
размещается рядом с предыдущим вычисленным элементом
b
в соответствии с
внутренним циклом по
j
). Однако доступ к элементам матрицы
a
осуществляется
с шагом
n
(длина всей строки). Т.о. при ссылках на
a
кэш используется неэф-
фективно (в кэш загружается излишне много значений элементов
a
, из которых
реально нужна всего
1/n
).
Разбиение матрицы на блоки делит область итераций на прямоугольники
(квадраты в частном случае), размер данных в которых не превышают размера
кэша. При желании полностью поместить в кэш
m
×
m
(само собой,
m<n
) чисел
(значений матриц
a
или
b
) следует изменить алгоритм транспонирования таким
образом:
for [i=1 to n by m] // для каждой m-й строки
for [j=1 to n by m] // и m-ного столбца…
for [i1=i to min(i+m-1, n)] // блок размером m строк
for [j1=j to min(j+m-1, n)] // блок размером m столбцов
b[i1, j1] = a[j1, i1];
                                          - 86 -



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

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

  После развертки внутреннего цикла (т.е. замены i1 двумя значениями – i и i+1)
получается программа, равноценная полученной преобразованием развертки и
сжатия (8).
  При разделении на блоки распределение данных в памяти компактируется и,
следовательно, повышается эффективность кэширования на МВС с общей памя-
тью или размещение данных в распределенной памяти. В качестве примера рас-
сматривается фрагмент транспонирования матрицы:

  for [i=1 to n]
   for [j=1 to n]
    b[i, j] = a[j, i];

   При условии хранения в памяти массивов по строкам (характерно для C/C++)
доступ к элементам матрицы b осуществляется с шагом 1 (каждый элемент b
размещается рядом с предыдущим вычисленным элементом b в соответствии с
внутренним циклом по j). Однако доступ к элементам матрицы a осуществляется
с шагом n (длина всей строки). Т.о. при ссылках на a кэш используется неэф-
фективно (в кэш загружается излишне много значений элементов a, из которых
реально нужна всего 1/n).
   Разбиение матрицы на блоки делит область итераций на прямоугольники
(квадраты в частном случае), размер данных в которых не превышают размера
кэша. При желании полностью поместить в кэш m × m (само собой, m

Страницы