Jump to content

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

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

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

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)) во время каждой итерации. В результате общая производительность может ухудшиться после замены шлейфа.

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

[ редактировать ]

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

См. также

[ редактировать ]
  1. ^ «Обмен шлейфом» (PDF) . Руководство по параллельному программированию для систем HP-UX . ХП. Август 2003 года.

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

[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: fdb10132d0371e7c58a74dd5338e4570__1699959780
URL1:https://arc.ask3.ru/arc/aa/fd/70/fdb10132d0371e7c58a74dd5338e4570.html
Заголовок, (Title) документа по адресу, URL1:
Loop interchange - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)