Петлевое деление и слияние

В информатике деление цикла (или распределение цикла ) — это оптимизация компилятора , при которой цикл разбивается на несколько циклов в том же диапазоне индексов, каждый из которых занимает только часть тела исходного цикла. [1] [2] Цель состоит в том, чтобы разбить большое тело цикла на более мелкие, чтобы добиться лучшего использования локальности ссылок . Такая оптимизация наиболее эффективна в многоядерных процессорах , которые могут разбить задачу на несколько задач для каждого процессора .

Напротив, слияние циклов (или заклинивание циклов ) — это оптимизация компилятора и преобразование циклов , которое заменяет несколько циклов одним. [3] [2] Слияние циклов не всегда улучшает скорость выполнения. На некоторых архитектурах два цикла могут фактически работать лучше, чем один цикл, потому что, например, в каждом цикле увеличивается локальность данных . Одним из главных преимуществ слияния циклов является то, что оно позволяет избегать временных выделений, что может привести к огромному приросту производительности в числовых языках вычислений, таких как Julia, при выполнении поэлементных операций над массивами (однако слияние циклов Julia технически не является оптимизацией компилятора, а синтаксической гарантией языка). [4]

Другие преимущества слияния циклов заключаются в том, что оно позволяет избежать накладных расходов структур управления циклом, а также в том, что оно позволяет процессору распараллеливать тело цикла [5] за счет использования преимуществ параллелизма на уровне инструкций . Это возможно, когда нет зависимостей данных между телами двух циклов (это резко контрастирует с другим основным преимуществом слияния циклов, описанным выше, которое проявляется только тогда, когда есть зависимости данных, требующие промежуточного выделения для сохранения результатов). Если слияние циклов способно удалить избыточные выделения, рост производительности может быть значительным. [4] В противном случае существует более сложный компромисс между локальностью данных, параллелизмом на уровне инструкций и накладными расходами цикла (ветвление, приращение и т. д.), что может сделать слияние циклов, деление циклов или ни то, ни другое предпочтительной оптимизацией.

Деление

Пример на языке Си

int i , a [ 100 ], b [ 100 ]; для ( i = 0 ; i < 100 ; i ++ ) { a [ i ] = 1 ; b [ i ] = 2 ; }

эквивалентно:

int i , a [ 100 ], b [ 100 ]; для ( i = 0 ; i < 100 ; i ++ ) { a [ i ] = 1 ; } для ( i = 0 ; i < 100 ; i ++ ) { b [ i ] = 2 ; }

Слияние

Пример на C++ и MATLAB

Рассмотрим следующий код MATLAB:

x = 0 : 999 ; % Создать массив чисел от 0 до 999 (диапазон включительно) y = sin ( x ) + 4 ; % Взять синус x (поэлементно) и добавить 4 к каждому элементу

Того же синтаксиса можно добиться в C++, используя перегрузку функций и операторов:

#include <cmath> #include <cassert> #include <memory> #include <iostream>    class Array { size_t length ; std :: unique_ptr < float [] > data ; // Внутренний конструктор, создающий неинициализированный массив Array ( size_t n ) : length ( n ), data ( new float [ n ]) { } public : // Фабричный метод для создания массива в целочисленном диапазоне (верхняя граница // является исключающей, в отличие от диапазонов MATLAB). static Array Range ( size_t start , size_t end ) { assert ( end > start ); size_t length = end - start ; Array a ( length ); for ( size_t i = 0 ; i < length ; ++ i ) { a [ i ] = start + i ; } return a ; } // Базовые операции с массивами size_t size () const { return length ; } float & Operator []( size_t i ) { return data [ i ]; } const float & оператор []( size_t i ) const { return data [ i ]; }                                                                                  // Объявляем перегруженный оператор сложения как свободную функцию-друг (этот // синтаксис определяет оператор+ как свободную функцию, которая является другом этого // класса, несмотря на то, что он появляется как объявление функции-члена). friend Array Operator + ( const Array & a , float b ) { Array c ( a . size ()); for ( size_t i = 0 ; i < a . size (); ++ i ) { c [ i ] = a [ i ] + b ; } return c ; } // Аналогично мы можем определить перегрузку для функции sin(). На практике // было бы громоздко определять все возможные перегруженные математические операции как друзей // внутри класса, как это, но это всего лишь пример. friend Array sin ( const Array & a ) { Array b ( a . size ()); for ( size_t i = 0 ; i < a . size (); ++ i ) { b [ i ] = std :: sin ( a [ i ]); } вернуть б ; } };                                                            int main ( int argc , char * argv []) { // Здесь мы выполняем те же вычисления, что и в примере MATLAB auto x = Array :: Range ( 0 , 1000 ); auto y = sin ( x ) + 4 ; // Выводим результат — просто чтобы убедиться, что оптимизатор не удалит // все (если он достаточно умен, чтобы сделать это). std :: cout << "Результат: " << std :: endl ; for ( size_t i = 0 ; i < y . size (); ++ i ) { std :: cout << y [ i ] << std :: endl ; } return 0 ; }

Однако приведенный выше пример без необходимости выделяет временный массив для результата sin(x). Более эффективная реализация выделила бы один массив для yи вычислила бы yв одном цикле. Чтобы оптимизировать это, компилятору C++ необходимо:

  1. Встройте вызовы функций sinи operator+.
  2. Соедините петли в одну.
  3. Удалите неиспользуемые хранилища во временные массивы (вместо этого можно использовать регистр или стековую переменную).
  4. Удалите неиспользуемое выделение и освободите.

Все эти шаги возможны по отдельности. Даже шаг четыре возможен, несмотря на то, что функции вроде mallocи freeимеют глобальные побочные эффекты, поскольку некоторые компиляторы жестко кодируют символы вроде mallocи, freeчтобы они могли удалять неиспользуемые выделения из кода. [6] Однако, начиная с clang 12.0.0 и gcc 11.1, это слияние циклов и удаление избыточных выделений не происходит — даже на самом высоком уровне оптимизации. [7] [8]

Некоторые языки, специально ориентированные на численные вычисления, такие как Julia, могут иметь концепцию слияния циклов, встроенную в него на высоком уровне, где компилятор будет замечать смежные поэлементные операции и объединять их в один цикл. [9] В настоящее время для достижения того же синтаксиса в языках общего назначения, таких как C++, функции sinи operator+должны пессимистически выделять массивы для хранения своих результатов, поскольку они не знают, из какого контекста они будут вызваны. Эту проблему можно избежать в C++, используя другой синтаксис, который не полагается на компилятор для удаления ненужных временных выделений (например, используя функции и перегрузки для операций на месте, таких как operator+=или std::transform).

Смотрите также

Ссылки

  1. ^ YN Srikant; Priti Shankar (3 октября 2018 г.). Справочник по проектированию компиляторов: оптимизация и генерация машинного кода, второе издание. CRC Press. ISBN 978-1-4200-4383-9.
  2. ^ ab Kennedy, Ken & Allen, Randy. (2001). Оптимизирующие компиляторы для современных архитектур: подход, основанный на зависимостях . Морган Кауфманн. ISBN 1-55860-286-0.
  3. ^ Стивен Мучник; Muchnick and Associates (15 августа 1997 г.). Advanced Compiler Design Implementation . Морган Кауфманн. ISBN 978-1-55860-320-2. петлевое слияние.
  4. ^ ab Johnson, Steven G. (21 января 2017 г.). «Больше точек: синтаксическое слияние циклов в Julia». julialang.org . Получено 25 июня 2021 г. .
  5. ^ "Loop Fusion". Intel . Получено 2021-06-25 .
  6. ^ Godbolt, Matt. "Compiler Explorer - C++ (x86-64 clang 12.0.0)". godbolt.org . Получено 25.06.2021 .
  7. ^ Godbolt, Matt. "Compiler Explorer - C++ (x86-64 clang 12.0.0)". godbolt.org . Получено 25.06.2021 .
  8. ^ Годболт, Мэтт. "Compiler Explorer - C++ (x86-64 gcc 11.1)". godbolt.org . Получено 25.06.2021 .
  9. ^ "Функции · Язык Julia". docs.julialang.org . Получено 2021-06-25 .
  • Деление петли
Взято с "https://en.wikipedia.org/w/index.php?title=Петлевое_деление_и_слияние&oldid=1250197896"