Разделение цикла - это метод оптимизации компилятора . Он пытается упростить цикл или устранить зависимости, разбив его на несколько циклов, которые имеют одинаковые тела, но повторяются по разным смежным частям диапазона индексов.
Петлевой пилинг
Удаление цикла - это особый случай разделения цикла, при котором любые проблемные первые (или последние) несколько итераций из цикла отделяются и выполняются за пределами тела цикла.
Предположим, цикл был написан так:
int p = 10 ; для ( int i = 0 ; i < 10 ; ++ i ) { y [ i ] = x [ i ] + x [ p ]; р = я ; }
Обратите внимание, что p = 10
только для первой итерации и для всех остальных итераций p = i - 1
. Компилятор может воспользоваться этим, раскрутив (или «отсоединив») первую итерацию от цикла.
После очистки первой итерации код будет выглядеть так:
у [ 0 ] = х [ 0 ] + х [ 10 ]; для ( int i = 1 ; i < 10 ; ++ i ) { y [ i ] = x [ i ] + x [ i -1 ]; }
Эта эквивалентная форма устраняет необходимость в переменной p
внутри тела цикла.
Отслаивание петель было введено в gcc в версии 3.4. Более обобщенное разделение цикла было добавлено в GCC 7. [1]
Краткая история термина
По-видимому, этот термин впервые был использован Каннингсом, Томпсоном и Сколником [2] в их статье 1976 года о вычислительных моделях для (человеческого) наследования. Там термин использовался для обозначения метода передачи фенотипической информации родителям. Отсюда этот термин снова использовался в их статьях, включая основополагающую статью о функциях вероятности в сложных родословных. [3]
В технологии компиляторов этот термин впервые появился в конце 1980-х годов в статьях по VLIW и суперскалярной компиляции, включая [4] и. [5]
Рекомендации
- ^ https://gcc.gnu.org/gcc-7/changes.html
- ^ Cannings, C .; Томпсон, EA; Сколник, HH (1976). «Рекурсивный вывод правдоподобия по сложным родословным». Достижения в прикладной теории вероятностей . 8 (4): 622–625. DOI : 10.2307 / 1425918 .
- ^ Cannings, C .; Томпсон, EA; Сколник, HH (1978). «Вероятностные функции на сложных родословных». Достижения в прикладной теории вероятностей . 10 (1): 26–61. DOI : 10.2307 / 1426718 .
- ^ Callahan, D .; Кеннеди, Кен (1988). "Компиляция программ для мультипроцессоров с распределенной памятью". Журнал суперкомпьютеров . 2 (2): 151–169. DOI : 10.1007 / BF00128175 .
- ^ Mahlke, SA; Лин, округ Колумбия; Чен, Вайоминг; Хэнк, RE; Брингман, Р.А. (1992). Эффективная поддержка компилятором для предсказуемого выполнения с использованием гиперблока . 25-й ежегодный международный симпозиум по микроархитектуре. С. 45–54.
дальнейшее чтение
- Кеннеди, Кен ; Аллен, Рэнди (2002). «Глава 5.7. Разделение набора индексов - Глава 5.7.2. Отслаивание петель». Оптимизация компиляторов для современных архитектур: подход, основанный на зависимостях (цифровая печать 2011 г., 1-е изд.). Academic Press / Morgan Kaufmann Publishers / Elsevier . стр. 211 -212. ISBN 978-1-55860-286-1. LCCN 2001092381 . ISBN 1-55860-286-0 .