stringtranslate.com

Разделение цикла

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

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

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

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

 int p = 10 ; для ( 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 ]; для ( 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] .

Ссылки

  1. ^ Серия релизов GCC 7 — Изменения, новые функции и исправления — проект GNU
  2. ^ Каннингс, К.; Томпсон, Е.А.; Сколник, Х.Х. (1976). «Рекурсивный вывод правдоподобий в сложных родословных». Advances in Applied Probability . 8 (4): 622–625. doi :10.2307/1425918. JSTOR  1425918.
  3. ^ Каннингс, К.; Томпсон, Е.А.; Сколник, Х.Х. (1978). «Вероятностные функции в сложных родословных». Advances in Applied Probability . 10 (1): 26–61. doi :10.2307/1426718. JSTOR  1426718.
  4. ^ Каллахан, Д.; Кеннеди, Кен (1988). «Компиляция программ для мультипроцессоров с распределенной памятью». Журнал суперкомпьютеров . 2 (2): 151–169. doi :10.1007/BF00128175. S2CID  10214341.
  5. ^ Малке, С.А.; Лин, Д.К.; Чен, В.И.; Хэнк, Р.Э.; Брингман, Р.А. (1992). Эффективная поддержка компилятором предикатного выполнения с использованием гиперблока . 25-й ежегодный международный симпозиум по микроархитектуре. С. 45–54.

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