Слияние циклов для локализации данных

В течение нескольких десятилетий наблюдается рост производительности процессоров (выполнение операций умножения) примерно на 30% в год, а рост пропускной способности памяти (скорость чтения/записи данных из оперативной памяти) растет только на 9% [1] . Таким образом, если ранее основное время работы вычислительных систем уходило на вычислительные операции, то сейчас – на доступ к данным.

Актуальность оптимизации параллельных вычислений подчеркивается тем, что параллельные программы часто показывают низкую эффективность [2] . Для многих приложений наблюдается, что при повышении уровня параллелизма с некоторого момента скорость выполнения программ даже замедляется. Проблема отставания реальной производительности программного обеспечения от пиковой производительности вычислительных систем отмечается как отечественными, так и зарубежными исследователями [3] , [4] .

Y-4.0

Наиболее типичная последовательность прохождения данных в компьютере с общей памятью, иерархией кэш-памяти и многоядерным процессором выглядит примерно следующим образом:

RAM → L 3 → L 2 → L 1 → R → ALU

Распараллеливание происходит после L 3 – у каждого процессорного ядра свой L 2 -кэш. Векторизация происходит после L 1 через векторные регистры. Каждая стрелка означает передачу данных: время передачи уменьшается в порядке слева направо.

У разных программ узкое место производительности может быть в разных местах. При этом используются различные приемы оптимизации. В частности, если в программе самые глубоко вложенные циклы имеют в теле много операций с небольшим объемом данных, то вполне интересна оптимизация регистров. Но большинство используемых современных программ имеет много данных, с которыми выполняется относительно малое число операций. Для таких программ узким местом является доступ к памяти.

В данной работе рассматривается преобразование программ «слияние циклов». Это преобразование может способствовать локализации данных для оптимизации использования кэш-памяти. В современных оптимизирующих компиляторах такое преобразование используется, но для очень простых случаев.

• 1.    Условия корректности и эффективности преобразования «слияние циклов»

Преобразование «слияние циклов» является обратным к преобразованию программ «разбиение цикла». Поэтому условие эквивалентности слияния циклов может быть выражено через условие эквивалентности разбиения циклов: если после слияния циклов результирующий цикл можно разбить так, что в результате получатся исходные циклы (которые были до слияния) – значит, слияние эквивалентно. Для разбиения циклов условие эквивалентности состоит в том, чтобы в исходном цикле между разбиваемыми частями не было дуг графа информационных связей, направленных снизу-вверх (см., например, [5] ).

Эффект полезности слияния циклов известен, опишем его для полноты изложения. Пусть имеются два последовательно записанных (в конкатенации) цикла, обрабатывающих общие массивы b, c:

----------------------------------------------------------------------------------- C++ —

1 for	(i = 1; i < N;	i++)
2	LoopBody1(a[i]	, b[i], c[i], ... );                                      (1)
3
4 for	(i = 1; i < N;	i++)
5	LoopBody2(b[i]	, c[i], d[i], ... );                                      (2)

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

Предположим, что (1) и (2) можно слить в один цикл:

----------------------------------------------------------------------------------- C++ — 1 for (i = 1; i < N; i++){

• 2     a[i] = LoopBody1(b[i], c[i], ... );

• 3     b[i] = LoopBody2(c[i], d[i], ... );

• 4    }

• 2.    Слияние циклов с использованием вспомогательных преобразований

■

Тогда элементы массивов b, c считываются в кэш-память один раз и используются для выполнения каждого исходного тела цикла.

Использование слияния циклов для локализации данных отмечено в работах [6] , [7] , [8] . Однако, в этих работах либо не рассмотрены случаи, при которых сливаемые циклы связаны информационными зависимостями относительно вышестоящих циклов, либо лишь упоминается о том, что основную сложность при слиянии циклов вызывает анализ возникших зависимостей, при этом сам анализ остается нерассмотренным. Слияние циклов – известное преобразование, поэтому входит в список оптимизаций большинства современных компиляторов. Например, компилятор компании Oracle проводит анализ информационных зависимостей при слиянии цикло в1, однако циклы, содержащие такие зависимости, признаются компилятором небезопасными для слияния. В документации приводится следующий пример:

----------------------------------------------------------------------------------- C++ —

• 1    for (i=0; i < 100; i++){

• 2    a[i] = a[i] + b[i];

• 3    }

• 4    for (i=0; i < 100; i++){

• 5     a[i+1] = a[i] * d[i];

• 6    }

.

Безусловно, слияние циклов при некорректном применении (в случае возникновения дополнительной информационной зависимости) может привести к неэквивалентной программе. Однако к элементам класса циклов, содержащих зависимости, подобные рассмотренным в документации Oracle, может быть применено слияние после дополнительных преобразований, например, расщепления цикла. Не рассматривается и использование цепочки вспомогательных преобразований (таких как «введение временных массивов», «растягивание скаляров», «перестановка операторов») для слияния. Распараллеливаю щая система Plut o2 и система анализа и преобразований пространства итераций гнезда циклов Poll y3 изучают гнезда циклов с точки зрения распараллеливания и локализации данных. В работе [6] рассматриваются как тайлинг, так и слияние циклов.

Алгоритм заключается в поиске пространства итераций, для которого возможно произвести слияние циклов с сохранением эквивалентности программы. Для этого для каждой информационной зависимости (кроме входной) определяются множества значений индексных выражений, далее вычисляется пересечение этих множеств. Затем для каждого цикла находится подмножество пространства итераций, для которого множество значений индексных выражений совпадает с этим пересечением. Итоговое пространство итераций для каждого цикла является пересечением всех найденных для этого цикла подмножеств.

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

C++ —

1 for (i = 10; i < 20;i++)

2     a[i] = b[2 * i -9];

3 for (i = 10; i < 20;i++)

4     b[2 * i - 7] = d[i];

Но если от первого цикла отщепить начальные итерации (в данном случае одну), а во втором цикле отщепить последние итерации (в данном случае тоже только одну), затем все полученные циклы привести к каноническому виду (левая граница и шаг цикла равны единице), то слияние циклов будет корректно.

Информационную зависимость образуют вхождения переменной b, обозначим множество значений индексных выражений массива b в первом цикле как B 1 , во втором цикле как B ₂ . I 1 и I 2 - пространства итераций, для которых возможно провести слияние.

B 1 = { 11 , 13 , 15 ,..., 29 }, B 2 = { 13 , 15 , 17 ,..., 31 }

B 1 П B 2 = { 13 , 15 ,..., 29 }

I 1 = [11 , 19] , I 2 = [10 , 18]

Расщепим циклы, опираясь на найденные множества:

----------------------------------------------------------------------------------- C++ —

• 1    for (i = 10; i < 11;i++)

• 2    a[i] = b[2 * i -9];

• 3    for (i = 11; i < 20;i++)

• 4    a[i] = b[2 * i -9];

• 5    for (i = 10; i < 19;i++)

• 6     b[2 * i - 7] = d[i];

• 7    for (i = 19; i < 20; i++)

• 8     b[2 * i - 7] = d[i];

Проведем канонизацию второго и третьего циклов:

----------------------------------------------------------------------------------- C++ —

• 1    for (i = 10; i < 11; i++)

• 2     a[i] = b[2 * i - 9];

• 3    for (i = 0; i < 9; i++)

• 4    a[i + 11] = b[2 * i + 13];

• 5    for (i = 0; i < 9; i++)

• 6     b[2 * i + 13] = d[i + 10];

• 7    for (i = 19; i < 20; i++)

• 8     b[2 * i - 7] = d[i];

• 3.    О выборе вспомогательных преобразований, позволяющих выполнить слияние циклов, имеющих информационные зависимости относительно внешнего цикла

После этого можно провести слияние второго и третьего циклов:

C++ —

1	for	(i =	10; i < 11; i++)
2		a[i]	= b[2 * i - 9];
3	for	(i =	0; i < 9; i++){
4		a[i	+ 11] = b[2 * i + 13]
5		b[2	* i + 13] = d[i + 10]
6	}
7	for	(i =	19; i < 20; i++)
8		b[2	* i - 7] = d[i];

Далее для упрощения кода можно сделать раскрутки коротких первого и последнего циклов.

Иногда, если сливаемые циклы находятся внутри некоторого объемлющего цикла, то можно к внешнему циклу применить преобразование циклического сдвига [9] , после чего слияние может стать возможным (эквивалентным).

Рассмотрим псевдокод, в котором блоки B1 , B2 – это циклы, слияние которых целесообразно.

----------------------------------------------------------------------------------- C++ —

• 1    for (i = 1; i

• 2     B1(i);

• 3     B2(i);

• 4    } .

Для слияния циклов (соответствующих блокам B1, B2) необходимо устранить ведущие «снизу-вверх» информационные зависимости между ними. Рассмотрим более задачу устранения зависимостей («ведущих снизу-вверх») между блоками, которые в данном конкретном случае являются циклами. В общем случае эта задача решения не имеет, поскольку, например, рассматриваемые блоки могут быть связаны рекуррентной зависимостью. Известен ряд приемов (вспомогательных преобразований), которые позволяют выполнить устранение таких зависимостей в некоторых ситуациях. Эти приемы описаны для задач автоматической векторизации циклов и для разбиения циклов (loop distribution), в которых также требуется устранение дуг информационной зависимости, ведущих «снизу-вверх». Такими преобразованиями программ являются «круговой сдвиг», «перестановка операторов», «введение временного массива», «растягивание скаляров» [9], [5]. Таким образом, алгоритм выполнения слияния циклов, имеющих зависимости относительно внешнего цикла, подобны алгоритмам разбиения цикла, описанным в [5] и [9].

Пример 2. Следующие два цикла нельзя слить непосредствен но ( нарушится корректность, результирующий цикл не будет эквивалентен исходному ) .

Исходная программа:

----------------------------------------------------------------------------------- C++ —

• 1    for (i = 0; i < 1000; i++){

• 2    for (j = 2; j < 1000; j++){

• 3         a[i][j] = b[i][j];

• 4          c[i][j] = b[i][j - 2];

• 5       }

• 6      for (j = 2; j < 1000; j++)

• 7          b[i][j + 2] = d[i][j] + e[i][j];

• 8    }

После кругового сдвига:

----------------------------------------------------------------------------------- C++ —

• 1    for (j = 2; j < 1000; j++)

• 2      b[0][j + 2] = d[0][j] + e[0][j];

• 3    for (i = 0; i < 999; i++){

• 4    for (j = 2; j < 1000; j++)

• 5          b[i + 1][j + 2] = d[i + 1][j] + e[i + 1][j];

• 6      for (j = 2; j < 1000; j++){

• 7          a[i][j] = b[i][j];

• 8         c[i][j] = b[i][j - 2];

• 9       }

• 10    }

• 11    for (j = 2; j < 1000; j++){

• 12      a[999][j] = b[999] [j];

• 13     c[999][j] = b[999][j - 2];

• 14    }

Пример 3. Следующие два внутренних цикла нельзя слить как непосредственно, так и после их перестановки. Для слияния используется введение временного массива. Следует отметить, что дополнительно введенный массив одномерный, а слиянию будут подвергаться циклы, содержащие вхождения двумерного массива. Т.е., расходы на обработку одномерного массива могут окупиться уменьшением передвижений двумерного. Несложно построить аналогичные примеры и для трехмерных массивов.

Исходная программа:

----------------------------------------------------------------------------------- C++ — 1 for (i = 0; i < 1000; i++){

• 2    for (j = 2; j < 1000; j++)

• 3         a[i][j] = b[i] * c[i][j] - b[i + 2];

• 4    for (j = 2; j < 1000; j++)

• 5           b[i + 1] = b[i + 1] * d[i][j] + e[i][j];

• 6    }

.

Шаг 1 (введение временных массивов):

----------------------------------------------------------------------------------- C++ - 1 temp_b[0] = b[1];

2 for (i = 0; i < 1000; i++){ temp_b[i + 1] = b[i + 2];

• 4    for (j = 2; j < 1000; j++)

• 5          a[i][j] = b[i] * c[i][j] - temp_b[i + 1];

• 6    for (j = 2; j < 1000; j++)

• 7          b[i + 1] = temp_b[i] * d[i][j] + e[i][j];

• 8    }

Шаг 2 (перестановка операторов):

----------------------------------------------------------------------------------- C++ -

• 1    temp_b[0] = b[1];

• 2    for (i = 0; i < 1000; i++){ temp_b[i + 1] = b[i + 2];

• 4    for (j = 2; j < 1000; j++)

• 5          b[i + 1] = temp_b[i] * d[i][j] + e[i][j];

• 6    for (j = 2; j < 1000; j++)

• 7          a[i][j] = b[i] * c[i][j] - temp_b[i + 1];

• 8    }

Шаг 3 (слияние циклов):

----------------------------------------------------------------------------------- C++ —

• 1    temp_b[0] = b[1];

• 2    for (i = 0; i < 1000; i++){ temp_b[i + 1] = b[i + 2];

• 4    for (j = 2; j < 1000; j++){

• 5          b[i + 1] = temp_b[i] * d[i][j] + e[i][j];

• 6          a[i][j] = b[i] * c[i][j] - temp_b[i + 1];

• 7        }

• 8    }

Шаг 4 (разбиение цикла):

----------------------------------------------------------------------------------- C++ —

• 1    temp_b[0] = b[1];

• 2    for (i = 0; i < 1000; i++) temp_b[i + 1] = b[i + 2];

• 4    for (i = 0; i < 1000; i++)

• 5    for (j = 2; j < 1000; j++){

• 6          b[i + 1] = temp_b[i] * d[i][j] + e[i][j];

• 7          a[i][j] = b[i] * c[i][j] - temp_b[i + 1];

• 8       }

Пример 4. Слияние циклов со скалярной переменной с использованием кругового сдвига.

Исходная программа:

----------------------------------------------------------------------------------- C++ —

• 1    for (i = 0; i < 1000; i++){

• 2    for (j = 0; j < 1000; j++)

• 3          a[i][j] = c[i][j] - b;

• 4     for (j = 0; j < 1000; j++){

• 5          d[i][j] = e[i]*b + f[i][j];

• 6          b = g[i]*h[i][j] + k[i][j];

• 7        }

• 8    }

Шаг 1 (круговой сдвиг, отщепление итерации):

----------------------------------------------------------------------------------- C++ — for (i = 0; i < 1000; i++){ for (j = 0; j < 999; j++) a[i][j] = c[i][j] - b; a[i][999] = c[i][999] - b; d[i][0] = e[i] * b + f[i][0]; for (j = 0; j < 999; j++){ b = g[i] * h[i][j] + k[i][j]; d[i][j + 1] = e[i] * b + f[i][j + 1]; } b = g[i] * h[i][999] + k[i][999];

}

Шаг 2 (перестановка операторов):

C++ — for (i = 0; i < 1000; i++){

a[i][999] = c[i][999] - b;

d[i][0] = e[i] * b + f[i][0];

for (j = 0; j < 999; j++) a[i][j] = c[i][j] - b;

for (j = 0; j < 999; j++){ b = g[i] * h[i][j] + k[i][j];

d[i][j + 1] = e[i] * b + f[i][j + 1]; } b = g[i] * h[i][999] + k[i][999];

}

Шаг 3 (переименование переменной):

----------------------------------------------------------------------------------- C++ - for (i = 0; i < 1000; i++){ a[i][999] = c[i][999] - b; d[i][0] = e[i] * b + f[i][0]; for (j = 0; j < 999; j++) a[i][j] = c[i][j] - b;

for (j = 0; j < 999; j++){ b1 = g[i] * h[i][j] + k[i][j]; d[i][j + 1] = e[i] * b1 + f[i][j + 1]; } b = g[i] * h[i][999] + k[i][999];

}

.

Шаг 4 (слияние циклов):

C++ —

• 1    for (i = 0; i < 1000; i++){

• 2      a[i][999] = c[i][999] - b;

• 3     d[i][0] = e[i] * b + f[i][0];

• 4    for (j = 0; j < 999; j++){

• 5           a[i][j] = c[i][j] - b;

• 6          b1 = g[i] * h[i][j] + k[i][j];

• 7           d[i][j + 1] = e[i] * b1 + f[i][j + 1];

• 8      }

• 9     b = g[i] * h[i][999] + k[i][999];

• 10    }

Шаг 5 (разбиение цикла):

C++ —

• 1    for (i = 0; i < 1000; i++){

• 2      a[i][999] = c[i][999] - b;

• 3     d[i][0] = e[i] * b + f[i][0];

• 4    }

• 5    for (i = 0; i < 1000; i++){

• 6    for (j = 0; j < 999; j++){

• 7           a[i][j] = c[i][j] - b;

• 8         b1 = g[i] * h[i][j] + k[i][j];

• 9          d[i][j + 1] = e[i] * b1 + f[i][j + 1];

• 10      }

• 11    }

Заключение

В представленной статье предлагаются новые алгоритмы слияния программных циклов. Эти алгоритмы существенно расширяют множество пар циклов, допускающих слияние. Представленные алгоритмы позволяют выполнять слияние циклов благодаря вспомогательным преобразованиям. Корректность выполняемых преобразований основана на анализе информационных зависимостей.

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

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

Полученные результаты вносят вклад в теорию преобразования программ и могут быть использованы при разработке оптимизирующих компиляторов.