Smyčka štěpení a fúze - Loop fission and fusion
V počítačové vědě je štěpení smyčky (nebo distribuce smyčky ) optimalizace kompilátoru, ve které je smyčka rozdělena do více smyček ve stejném rozsahu indexu, přičemž každá bere pouze část těla původní smyčky. Cílem je rozdělit velké smyčkové tělo na menší, aby bylo dosaženo lepšího využití referenční lokality . Tato optimalizace je nejefektivnější u vícejádrových procesorů, které mohou rozdělit úkol na více úkolů pro každý procesor .
Naopak smyčková fúze (nebo smyčka rušení ) je optimalizace kompilátoru a transformace smyčky, která nahrazuje více smyček jednou. Fúze smyčky nemusí vždy zlepšit rychlost běhu. Na některých architekturách mohou dvě smyčky ve skutečnosti fungovat lépe než jedna smyčka, protože například v každé smyčce je zvýšená datová lokalita . Jednou z hlavních výhod slučovací smyčky je, že umožňuje vyhnout se dočasným alokacím, což může vést k obrovským nárůstům výkonu v numerických výpočetních jazycích, jako je Julia, při provádění elementárních operací na polích (Julia's loop fusion však není technicky optimalizace kompilátoru , ale syntaktická záruka jazyka).
Další výhody slučovací smyčky spočívají v tom, že se vyhýbá režii řídicích struktur smyčky, a také v tom, že umožňuje tělu smyčky paralelizovat procesor využitím výhod rovnoběžnosti na úrovni instrukcí . To je možné, pokud mezi těly obou smyček neexistují žádné datové závislosti (to je v příkrém kontrastu k další hlavní výhodě smyčkové fúze popsané výše, která se projevuje pouze v případě, že existují datové závislosti, které vyžadují přechodnou alokaci pro uložení Výsledek). Pokud je smyčková fúze schopna odstranit nadbytečné alokace, zvýšení výkonu může být velké. V opačném případě dochází ke složitějšímu kompromisu mezi datovou lokalitou, rovnoběžností na úrovni instrukcí a režií smyčky (větvení, inkrementace atd.), Což může způsobit preferovanou optimalizaci fúze smyčky, štěpení smyčky nebo žádného z nich.
Štěpení
Příklad v C.
int i, a[100], b[100];
for (i = 0; i < 100; i++) {
a[i] = 1;
b[i] = 2;
}
je ekvivalentní:
int i, a[100], b[100];
for (i = 0; i < 100; i++) {
a[i] = 1;
}
for (i = 0; i < 100; i++) {
b[i] = 2;
}
Fúze
Příklad v C ++ a MATLAB
Zvažte následující kód 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
Stejné syntaxe byste v C ++ mohli dosáhnout pomocí přetížení funkcí a operátorů:
#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;
}
Výše uvedený příklad však zbytečně přiděluje dočasné pole pro výsledek sin(x). Efektivnější implementace by přidělila jediné pole pro ya počítala yv jedné smyčce. Chcete -li to optimalizovat, kompilátor C ++ bude muset:
- Vložte volání funkce
sinaoperator+. - Spojte smyčky do jedné smyčky.
- Odeberte nepoužívaná úložiště do dočasných polí (místo toho můžete použít registr nebo proměnnou zásobníku).
- Odstraňte nepoužitou alokaci a uvolněte ji.
Všechny tyto kroky jsou možné jednotlivě. I krok čtvrtý je možný navzdory skutečnosti, že funkce mají malloca freemají globální vedlejší efekty, protože některé kompilátory hardkódové symboly jako malloca freetak, že mohou odstranit nepoužité přidělení z kódu. Nicméně, jak zařinčením 12.0.0 a gcc 11.1, nedochází tato smyčka fúze a redundantní odstranění alokace - a to i na nejvyšší úrovni optimalizace.
Některé jazyky specificky zaměřené na numerické výpočty, jako je Julia, mohou mít na vysoké úrovni integrovaný koncept smyčkové fúze, kde si překladač všimne sousedních elementárních operací a spojí je do jediné smyčky. V současné době k dosažení stejné syntaxe v jazycích pro obecné účely, jako je C ++, musí funkce sina operator+pesimisticky přidělovat pole pro ukládání svých výsledků, protože nevědí, z jakého kontextu budou voláni. Tomuto problému se lze v C ++ vyhnout pomocí jiné syntaxe, která nespoléhá na to, že kompilátor odebere zbytečná dočasná přidělení (např. Pomocí funkcí a přetížení pro operace na místě, jako operator+=nebo std::transform).
