Разделение цикла
Разделение цикла — это метод оптимизации компилятора . Он пытается упростить цикл или устранить зависимости, разбивая его на несколько циклов, которые имеют одинаковые тела, но перебирают разные смежные части диапазона индексов.
Петлевой пилинг
[ редактировать ]Очистка цикла — это особый случай разделения цикла, при котором любые проблемные первые (или последние) несколько итераций цикла отделяются и выполняются вне тела цикла.
Предположим, цикл был написан следующим образом:
int p = 10;
for (int i=0; i<10; ++i)
{
y[i] = x[i] + x[p];
p = i;
}
Обратите внимание, что p = 10 только для первой итерации и для всех остальных итераций, p = i - 1. Компилятор может воспользоваться этим, раскручивая (или «очищая») первую итерацию цикла.
После очистки первой итерации код будет выглядеть так:
y[0] = x[0] + x[10];
for (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]
Ссылки
[ редактировать ]- ^ Серия выпусков GCC 7 — Изменения, новые функции и исправления - Проект GNU
- ^ Каннингс, К.; Томпсон, Э.А.; Сколник, Х.Х. (1976). «Рекурсивный вывод вероятностей по сложным родословным». Достижения в области прикладной теории вероятности . 8 (4): 622–625. дои : 10.2307/1425918 . JSTOR 1425918 .
- ^ Каннингс, К.; Томпсон, Э.А.; Сколник, Х.Х. (1978). «Вероятностные функции на сложных родословных». Достижения в области прикладной теории вероятности . 10 (1): 26–61. дои : 10.2307/1426718 . JSTOR 1426718 .
- ^ Каллахан, Д.; Кеннеди, Кен (1988). «Компиляция программ для мультипроцессоров с распределенной памятью». Журнал суперкомпьютеров . 2 (2): 151–169. дои : 10.1007/BF00128175 . S2CID 10214341 .
- ^ Мальке, 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 .