Петлевой обмен - Loop interchange

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

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

для i от 0 до 10 для j от 0 до 20 a [i, j] = i + j

обмен циклами приведет к:

для j от 0 до 20 для i от 0 до 10 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.[1] Оптимизация компиляторов может обнаруживать неправильный порядок программистов и менять порядок для достижения лучшей производительности кеша.

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

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

 делать я = 1, 10000   делать j = 1, 1000     а[я] = а[я] + б[j,я] * c[я]   конец делать конец делать

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

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

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

Смотрите также

Рекомендации

  1. ^ «Петлевая развязка» (PDF). Руководство по параллельному программированию для систем HP-UX. HP. Август 2003 г.

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