В теории компиляторов , циклический обмен — это процесс обмена порядком двух итерационных переменных, используемых вложенным циклом . Переменная, используемая во внутреннем цикле, переключается на внешний цикл, и наоборот. Это часто делается для того, чтобы гарантировать, что элементы многомерного массива доступны в том порядке, в котором они присутствуют в памяти, что улучшает локальность ссылок .
Например, во фрагменте кода:
для j от 0 до 20 для i от 0 до 10 а[i,j] = i + j
Перестановка циклов приведет к следующему:
для i от 0 до 10 для j от 0 до 20 а[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. [1] Оптимизирующие компиляторы могут обнаружить неправильный порядок, установленный программистами, и поменять порядок, чтобы добиться лучшей производительности кэша.
Циклическое взаимозаменяемость может привести к ухудшению производительности, поскольку производительность кэша — это только часть истории. Возьмем следующий пример:
сделать i = 1 , 10000 сделать j = 1 , 1000 a [ i ] = a [ i ] + b [ j , i ] * c [ i ] конец сделать конец сделать Циклический обмен в этом примере может улучшить производительность кэша при доступе к b(j,i), но он разрушит повторное использование a(i) и c(i) во внутреннем цикле, поскольку он вводит две дополнительные загрузки (для a(i) и для c(i)) и одно дополнительное сохранение (для a(i)) во время каждой итерации. В результате общая производительность может ухудшиться после циклического обмена.
Не всегда безопасно менять итерационные переменные из-за зависимостей между операторами для порядка, в котором они должны выполняться. Чтобы определить, может ли компилятор безопасно менять циклы, требуется анализ зависимостей .