WikiDer > Расщепление петли

Loop splitting

Расщепление петли это оптимизация компилятора техника. Он пытается упростить петля или устраните зависимости, разбив его на несколько циклов, которые имеют одни и те же тела, но перебирают разные смежные части диапазона индекса.

Петлевой пилинг

Отслаивание цикла - это особый случай разделения цикла, при котором любые проблемные первые (или последние) несколько итераций из цикла отделяются и выполняются за пределами тела цикла.

Предположим, цикл был написан так:

 int п = 10; за (int я=0; я<10; ++я) {   у[я] = Икс[я] + Икс[п];   п = я; // добавляем i к переменной p }

Заметь р = 10 только для первой итерации, а для всех остальных итераций р = я - 1. Компилятор может воспользоваться этим, раскручивание (или «отслаивание») первая итерация цикла.

После очистки первой итерации код будет выглядеть так:

 у[0] = Икс[0] + Икс[10]; за (int я=1; я<10; ++я) {   у[я] = Икс[я] + Икс[я-1]; }

Эта эквивалентная форма устраняет необходимость в переменной п внутри тела цикла.

Петлевой пилинг был введен в gcc в версии 3.4. В GCC 7 было добавлено более общее разделение цикла.[1]

Краткая история термина

По-видимому, этот термин впервые использовали Каннингс, Томпсон и Сколник.[2] в своей статье 1976 года о вычислительных моделях для (человеческого) наследования. Там термин использовался для обозначения метода передачи фенотипической информации родителям. Отсюда этот термин снова использовался в их статьях, в том числе в их основополагающей статье о функциях вероятности в сложных родословных.[3]

В технологии компиляторов этот термин впервые появился в конце 1980-х годов в статьях по VLIW и суперскалярной компиляции, включая [4] и.[5]

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

  1. ^ https://gcc.gnu.org/gcc-7/changes.html
  2. ^ Cannings, C .; Томпсон, Э. А .; Сколник, Х. Х. (1976). «Рекурсивный вывод правдоподобия по сложным родословным». Достижения в прикладной теории вероятностей. 8 (4): 622–625. Дои:10.2307/1425918.
  3. ^ Cannings, C .; Томпсон, Э. А .; Сколник, Х. Х. (1978). «Вероятностные функции на сложных родословных». Достижения в прикладной теории вероятностей. 10 (1): 26–61. Дои:10.2307/1426718.
  4. ^ Callahan, D .; Кеннеди, Кен (1988). "Компиляция программ для мультипроцессоров с распределенной памятью". Журнал суперкомпьютеров. 2 (2): 151–169. Дои:10.1007 / BF00128175.
  5. ^ Mahlke, S.A .; Lin, D. C .; Chen, W. Y .; Hank, R.E .; Брингман, Р. А. (1992). Эффективная поддержка компилятором для предиктивного выполнения с использованием гиперблока. 25-й ежегодный международный симпозиум по микроархитектуре. С. 45–54.

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