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

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

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

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

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

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

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

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

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

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

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

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

Многогранная или основанная на ограничениях структура

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

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

См. также

• Оптимизация гнезда циклов
• Модель многогранника
• Масштабируемый параллелизм
• Масштабируемая местность