Оптимизация цикла

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

Эта статья посвящена оптимизации компилятора для циклов. Более конкретный метод уменьшения накладных расходов на гнезда циклов см. В разделе Оптимизация гнезда циклов.

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

Содержание

1 Представление вычислений и преобразований
2 Оптимизация с помощью последовательности преобразований цикла
- 2.1 Каркас унимодулярного преобразования
- 2.2 Многогранный каркас или каркас на основе ограничений
3 См. Также
4 ссылки

Представление вычислений и преобразований

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

Оптимизация с помощью последовательности преобразований цикла

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

Общие преобразования цикла включают в себя:

Деление или распределение - деление цикла пытается разбить цикл на несколько циклов в одном диапазоне индексов, но каждый новый цикл занимает только часть тела исходного цикла. Это может улучшить локальность ссылок, как данных, к которым осуществляется доступ в цикле, так и кода в теле цикла.
Слияние или объединение - это объединяет тела двух смежных циклов, которые будут повторяться одинаковое количество раз (независимо от того, известно это число во время компиляции), пока они не ссылаются на данные друг друга.
Обмен или перестановка - эти оптимизации меняют внутренние циклы на внешние. Когда переменные цикла индексируются в массиве, такое преобразование может улучшить локальность ссылки в зависимости от макета массива.
Инверсия - этот метод изменяет стандарт во время цикла в Do / в то время (он же повтор / до ) цикл обернуты в случае условно, уменьшая число скачков на два для случаев, когда выполняется цикл. Это дублирует проверку условий (увеличивает размер кода), но более эффективно, поскольку переходы обычно вызывают остановку конвейера. Кроме того, если начальное условие известно во время компиляции и известно, что оно не имеет побочных эффектов, начальное условие if -guard можно пропустить.
Инвариантное к циклу движение кода - это может значительно повысить эффективность, перемещая вычисление изнутри цикла за его пределы, вычисляя значение только один раз перед началом цикла, если результирующее количество вычислений будет одинаковым для каждой итерации цикла ( т.е. величина, инвариантная для петель). Это особенно важно для выражений вычисления адресов, генерируемых циклами по массивам. Для правильной реализации этот метод должен использоваться с инверсией, потому что не весь код можно безопасно вывести за пределы цикла.
Распараллеливание - это особый случай автоматического распараллеливания, в котором основное внимание уделяется циклам, реструктурируя их для эффективной работы в многопроцессорных системах. Это может быть сделано автоматически компиляторами ( автоматическое распараллеливание ) или вручную (вставка параллельных директив, таких как OpenMP ).
Реверсирование - тонкая оптимизация, которая меняет порядок, в котором значения присваиваются индексной переменной. Это может помочь устранить зависимости и, таким образом, включить другие оптимизации. Некоторые архитектуры используют конструкции цикла на уровне сборки, которые учитываются только в одном направлении (например, декремент-скачок-если-не-ноль [DJNZ]).
Планирование - это делит цикл на несколько частей, которые могут выполняться одновременно на нескольких процессорах.
Наклон - этот метод применяется к итерации вложенного цикла по многомерному массиву, где каждая итерация внутреннего цикла зависит от предыдущих итераций, и переупорядочивает доступ к его массиву так, чтобы единственные зависимости были между итерациями внешнего цикла.
Программная конвейерная обработка - разновидность внепланового выполнения итераций цикла для сокрытия задержек функциональных блоков процессора.
Разделение или отслаивание - это попытка упростить цикл или устранить зависимости, разбив его на несколько циклов, которые имеют одинаковые тела, но повторяются по разным частям диапазона индекса. Особым случаем является очистка цикла, которая может упростить цикл с проблемной первой итерацией, выполняя эту итерацию отдельно перед входом в цикл.
Мозаика или блокировка - реорганизует цикл для перебора блоков данных, размер которых соответствует размерам кеша.
Векторизация - пытается выполнить как можно больше итераций цикла одновременно в системе SIMD.
Развертывание - дублирует тело цикла несколько раз, чтобы уменьшить количество проверок условия цикла и количество переходов, что может снизить производительность из-за нарушения конвейера команд. Полное развертывание цикла устраняет все накладные расходы (за исключением множественных выборок инструкций и увеличения времени загрузки программы), но требует, чтобы количество итераций было известно во время компиляции (за исключением случая своевременной компиляции ). Также необходимо позаботиться о том, чтобы многократное повторное вычисление индексированных переменных не привело к большим накладным расходам, чем продвижение указателей в исходном цикле.
Отключение - перемещает условие изнутри цикла за его пределы, дублируя тело цикла и помещая его версию внутри каждого из предложений if и else условного выражения.
Секционирование или анализ полосы - представленный для векторных процессоров, секционирование цикла - это метод преобразования цикла для включения SIMD- кодирования циклов (одна инструкция, несколько данных) и повышения производительности памяти. Это включает в себя выполнение каждой векторной операции для размера, меньшего или равного максимальной длине вектора на данной векторной машине.

Каркас унимодулярного преобразования

Подход унимодулярного преобразования использует одну унимодулярную матрицу для описания комбинированного результата последовательности многих из вышеупомянутых преобразований. Центральным в этом подходе является взгляд на набор всех выполнений оператора в n циклах как на набор целочисленных точек в n- мерном пространстве, причем эти точки выполняются в лексикографическом порядке. Например, выполнение оператора, вложенного во внешний цикл с индексом i и внутренний цикл с индексом j, можно связать с парами целых чисел. Применение унимодулярного преобразования соответствует умножению точек в этом пространстве на матрицу. Например, матрице соответствует чередование двух петель. ${\ displaystyle (я, j)}$ $(я, j)$ ${\ displaystyle {\ begin {bmatrix} 0 amp; 1 \\ 1 amp; 0 \ end {bmatrix}}}$ ${\ displaystyle {\ begin {bmatrix} 0 amp; 1 \\ 1 amp; 0 \ end {bmatrix}}}$

Унимодулярное преобразование допустимо, если оно сохраняет временную последовательность всех зависимостей ; измерить влияние унимодулярного преобразования на производительность сложнее. Неидеально вложенные циклы и некоторые преобразования (например, мозаика) не вписываются в эту структуру.

Многогранный каркас или каркас на основе ограничений

Модель полиэдра обрабатывает более широкий класс программ и преобразований, чем унимодулярная структура. Набор выполнений набора операторов внутри, возможно, несовершенно вложенного набора циклов рассматривается как объединение набора многогранников, представляющих выполнение операторов. К этим многогранникам применяются аффинные преобразования, производящие описание нового порядка выполнения. Границы многогранников, зависимости данных и преобразования часто описываются с помощью систем ограничений, и этот подход часто называют подходом на основе ограничений к оптимизации цикла. Например, один оператор во внешнем цикле « для i: = от 0 до n » и во внутреннем цикле « для j: = от 0 до i + 2 » выполняется один раз для каждой пары (i, j), так что 0 lt;= i lt;= n и 0 lt;= j lt;= i + 2.

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