Перестановка петель

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

Например, во фрагменте кода:

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]), используя столбец-major . Таким образом, порядок двух переменных итерации в первом примере подходит для программы на языке C, а второй пример лучше подходит для FORTRAN. Оптимизирующие компиляторы могут обнаружить неправильный порядок действий программистов и поменять порядок местами для достижения лучшей производительности кэша.

Предостережение

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

 do i = 1, 10000
   do j = 1, 1000
     a[i] = a[i] + b[j,i] * c[i]
   end do
 end do

Обмен циклов в этом примере может улучшить производительность кэша при доступе к b(j,i), но это разрушит повторное использование a(i) и c(i) во внутреннем цикле, поскольку это вводит две дополнительные нагрузки (для a( i) и для c(i)) и одно дополнительное хранилище (для a(i)) во время каждой итерации. В результате общая производительность может ухудшиться после замены шлейфа.

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

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

См. также

• Разделение цикла
• Перекос петли
• Петлевое деление и синтез
• Развертывание цикла

Дальнейшее чтение

• Кеннеди, Кен ; Аллен, Рэнди (2002). Оптимизация компиляторов для современных архитектур: подход, основанный на зависимостях (цифровая печать 2011 г., 1-е изд.). Academic Press / Morgan Kaufmann Publishers / Elsevier . ISBN  978-1-55860-286-1 . LCCN   2001092381 .