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

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

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

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

Деление

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

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

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

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

Слияние

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

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

x = 0:999; % Create an array of numbers from 0 to 999 (range is inclusive)
y = sin(x) + 4; % Take the sine of x (element-wise) and add 4 to each element

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

#include <cmath>
#include <cassert>
#include <memory>
#include <iostream>

class Array {
    size_t length;
    std::unique_ptr<float[]> data;
    
    // Internal constructor that produces an uninitialized array
    Array(size_t n) : length(n), data(new float[n]) { }
    
public:
    // Factory method to produce an array over an integer range (the upper
    // bound is exclusive, unlike MATLAB's ranges).
    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;
    }
    
    // Basic array operations
    size_t size() const { return length; }
    float& operator[](size_t i) { return data[i]; }
    const float& operator[](size_t i) const { return data[i]; }

    // Declare an overloaded addition operator as a free friend function (this
    // syntax defines operator+ as a free function that is a friend of this
    // class, despite it appearing as a member function declaration).
    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;
    }
    
    // Similarly, we can define an overload for the sin() function. In practice,
    // it would be unwieldy to define all possible overloaded math operations as
    // friends inside the class like this, but this is just an example.
    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]);
        }
        return b;
    }
};

int main(int argc, char* argv[]) {
    // Here, we perform the same computation as the MATLAB example
    auto x = Array::Range(0, 1000);
    auto y = sin(x) + 4;
    
    // Print the result out - just to make sure the optimizer doesn't remove
    // everything (if it's smart enough to do so).
    std::cout << "The result is: " << 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 чтобы они могли удалить неиспользуемые выделения из кода. Однако, начиная с clang 12.0.0 и gcc 11.1, такого слияния циклов и удаления избыточных выделений не происходит — даже на самом высоком уровне оптимизации.

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

См. также

• Шаблоны выражений
• Преобразование цикла

Ссылки

• Петлевое деление