Введение

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

for j from 0 to 20
for i from 0 to 10
a[i,j] = i + j

перестановка циклов приведет к следующему:

for i from 0 to 10
for j from 0 to 20
a[i,j] = i + j

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

Полезность взаимного обмена петлями

Основная цель перестановки циклов — использовать кэш процессора при доступе к элементам массива. Когда процессор впервые обращается к элементу массива, он извлекает из памяти в кэш целый блок данных. В этом блоке, скорее всего, содержится множество последовательных элементов, следующих за первым, поэтому при следующем обращении к элементу массива он будет получен непосредственно из кэша (что быстрее, чем из медленной основной памяти). Промахи кэша возникают, если последовательно обращаемые элементы массива в цикле находятся в разных блоках кэша, и перестановка циклов может помочь этого избежать. Эффективность перестановки циклов зависит от модели кэша, используемой аппаратным обеспечением, и модели представления массивов, используемой компилятором, и должна рассматриваться с учетом этих моделей. В языке программирования C элементы массива в одной строке хранятся последовательно в памяти (a[1,1], a[1,2], a[1,3]) — в порядке, ориентированном по строкам. С другой стороны, программы на FORTRAN хранят элементы массива из одного столбца вместе (a[1,1], a[2,1], a[3,1]), используя порядок, ориентированный по столбцам. Таким образом, порядок двух переменных итерации в первом примере подходит для программы на C, а во втором примере — для FORTRAN. Оптимизирующие компиляторы могут обнаруживать неправильный порядок, заданный программистом, и переставлять циклы для достижения более высокой производительности кэша.

Безопасность

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