Перестановка петель
В теории компиляторов обмен циклами — это процесс обмена порядком двух переменных итерации, используемых во вложенном цикле . Переменная, используемая во внутреннем цикле, переключается на внешний цикл и наоборот. Часто это делается для того, чтобы обеспечить доступ к элементам многомерного массива в том порядке, в котором они присутствуют в памяти, улучшая локальность ссылки .
Например, во фрагменте кода:
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. [1] Оптимизирующие компиляторы могут обнаружить неправильный порядок действий программистов и поменять порядок местами для достижения лучшей производительности кэша.
Предостережение
[ редактировать ]Обмен циклами может привести к ухудшению производительности, поскольку производительность кэша — это только часть проблемы. Возьмем следующий пример:
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)) во время каждой итерации. В результате общая производительность может ухудшиться после замены шлейфа.
Безопасность
[ редактировать ]Обмен переменными итерации не всегда безопасен из-за зависимости между операторами от порядка, в котором они должны выполняться. Чтобы определить, может ли компилятор безопасно обмениваться циклами, анализ зависимостей необходим .
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ «Обмен шлейфом» (PDF) . Руководство по параллельному программированию для систем HP-UX . ХП. Август 2003 года.
Дальнейшее чтение
[ редактировать ]- Кеннеди, Кен ; Аллен, Рэнди (2002). Оптимизация компиляторов для современных архитектур: подход, основанный на зависимостях (цифровая печать 2011 г., 1-е изд.). Academic Press / Morgan Kaufmann Publishers / Elsevier . ISBN 978-1-55860-286-1 . LCCN 2001092381 .