Rozdělení smyčky - Loop splitting

Rozdělení smyčky je optimalizace kompilátoru technika. Pokouší se zjednodušit a smyčka nebo eliminujte závislosti rozdělením do více smyček, které mají stejná těla, ale iterují přes různé sousedící části rozsahu indexu.

Loupání smyčky

Loupání smyčky je speciální případ rozdělení smyčky, který rozděluje všechny problematické první (nebo poslední) několik iterací ze smyčky a provádí je mimo tělo smyčky.

Předpokládejme, že smyčka byla napsána takto:

 int p = 10; pro (int i=0; i<10; ++i) {   y[i] = X[i] + X[p];   p = i; // přidat i do proměnné p }

Všimněte si toho p = 10 pouze pro první iteraci a pro všechny ostatní iterace, p = i - 1. Kompilátor to může využít tím, že odvíjení (nebo „peeling“) první iterace ze smyčky.

Po odlupování první iterace by kód vypadal takto:

 y[0] = X[0] + X[10]; pro (int i=1; i<10; ++i) {   y[i] = X[i] + X[i-1]; }

Tato ekvivalentní forma vylučuje potřebu proměnné p uvnitř těla smyčky.

V roce byl zaveden peeling smyčky gcc ve verzi 3.4. V GCC 7 bylo přidáno obecnější dělení smyček.[1]

Stručná historie pojmu

Zřejmě tento termín poprvé použili Cannings, Thompson a Skolnick[2] ve své práci z roku 1976 o výpočetních modelech pro (lidské) dědictví. Tam byl tento termín použit k označení metody sbalení fenotypových informací na rodiče. Odtamtud byl tento termín znovu použit ve svých dokumentech, včetně jejich seminární práce o pravděpodobnostních funkcích na komplexních rodokmenech.[3]

V technologii překladačů se tento termín poprvé objevil v dokumentech z konce 80. let o VLIW a superskalární kompilaci [4] a.[5]

Reference

  1. ^ https://gcc.gnu.org/gcc-7/changes.html
  2. ^ Cannings, C .; Thompson, E. A .; Skolnick, H. H. (1976). "Rekurzivní odvození pravděpodobností na složitých rodokmenech". Pokroky v aplikované pravděpodobnosti. 8 (4): 622–625. doi:10.2307/1425918.
  3. ^ Cannings, C .; Thompson, E. A .; Skolnick, H. H. (1978). "Pravděpodobnostní funkce na komplexních rodokmenech". Pokroky v aplikované pravděpodobnosti. 10 (1): 26–61. doi:10.2307/1426718.
  4. ^ Callahan, D .; Kennedy, Ken (1988). "Kompilace programů pro multiprocesory s distribuovanou pamětí". The Journal of Supercomputing. 2 (2): 151–169. doi:10.1007 / BF00128175.
  5. ^ Mahlke, S. A .; Lin, D. C .; Chen, W. Y .; Hank, R.E .; Bringman, R. A. (1992). Efektivní podpora kompilátoru pro predikované spuštění pomocí hyperbloku. 25. výroční mezinárodní sympozium o mikroarchitektuře. str. 45–54.

Další čtení