Optimalizace smyčky - Loop optimization
V kompilátoru teorii , optimalizace smyčka je proces zvyšování rychlosti provádění a snížit režijní náklady spojené se smyčkami . Hraje důležitou roli při zlepšování výkonu mezipaměti a při efektivním využívání možností paralelního zpracování . Většina času provádění vědeckého programu se vynakládá na smyčky; jako takové bylo vyvinuto mnoho technik optimalizace kompilátoru, aby byly rychlejší.
Obsah
Reprezentace výpočtu a transformací
Vzhledem k tomu, že instrukce uvnitř smyček mohou být prováděny opakovaně, často není možné určit omezení počtu spuštění instrukcí, které budou ovlivněny optimalizací smyčky. To představuje výzvy při uvažování o správnosti a výhodách optimalizace smyčky, konkrétně reprezentací optimalizovaného výpočtu a prováděných optimalizací.
Optimalizace pomocí sekvence transformací smyčky
Na optimalizaci smyčky lze pohlížet jako na aplikaci sekvence specifických transformací smyčky (uvedených níže nebo v Transformacích kompilátoru pro vysoce výkonné výpočty ) na zdrojový kód nebo na mezilehlou reprezentaci , přičemž každá transformace má přidružený test zákonnosti. Transformace (nebo sled transformací) obecně musí zachovat časovou posloupnost všech závislostí , má-li zachovat výsledek programu (tj. Být legální transformací). Vyhodnocení přínosu transformace nebo sekvence transformací může být v rámci tohoto přístupu docela obtížné, protože aplikace jedné prospěšné transformace může vyžadovat předchozí použití jedné nebo více dalších transformací, které by samy o sobě vedly ke snížení výkonu.
Mezi běžné transformace smyčky patří:
- Štěpení nebo distribuce - štěpení smyčky se pokouší rozdělit smyčku na více smyček ve stejném rozsahu indexu, ale každá nová smyčka zabírá pouze část těla původní smyčky. To může zlepšit lokalitu odkazu , a to jak k datům, ke kterým se přistupuje ve smyčce, tak k kódu v těle smyčky.
- Fúze nebo kombinování - toto kombinuje těla dvou sousedních smyček, která by iterovala stejný počet opakování (ať už je tento počet znám v době kompilace), pokud na sebe navzájem neodkazují.
- Výměna nebo permutace - tyto optimalizace si vyměňují vnitřní smyčky s vnějšími smyčkami. Když se proměnné smyčky indexují do pole, může taková transformace zlepšit lokalitu odkazu v závislosti na rozložení pole.
- Inverze - tato technika mění standardní while smyčku na smyčku do / while (aka repeat / until ) zabalenou do podmíněného if , čímž se sníží počet skoků o dva pro případy, kdy je smyčka provedena. Tímto způsobem se duplikuje kontrola stavu (zvětšení velikosti kódu), ale je to efektivnější, protože skoky obvykle způsobí zablokování potrubí . Navíc, pokud je počáteční podmínka známa v době kompilace a je známo, že je bez vedlejších účinků , lze počáteční if -guard přeskočit.
- Pohyb kódu invariantního k smyčce - to může výrazně zlepšit efektivitu přesunutím výpočtu zevnitř smyčky na vnější stranu, vypočítáním hodnoty těsně před začátkem smyčky, pokud bude výsledné množství výpočtu pro každou iteraci smyčky stejné ( tj. množství-invariantní množství). To je zvláště důležité u výrazů pro výpočet adres generovaných smyčkami přes pole. Pro správnou implementaci musí být tato technika použita s inverzí, protože ne všechny kódy lze bezpečně přesunout mimo smyčku.
- Paralelizace - jedná se o speciální případ automatické paralelizace se zaměřením na smyčky a jejich restrukturalizaci tak, aby fungovala efektivně na víceprocesorových systémech. To lze provést automaticky kompilátory ( automatická paralelizace ) nebo ručně (vložením paralelních směrnic, jako je OpenMP ).
- Obrácení - jemná optimalizace, která obrátí pořadí, ve kterém jsou hodnoty přiřazeny proměnné indexu. To může pomoci eliminovat závislosti a povolit tak další optimalizace. Určité architektury využívají smyčkové konstrukce na úrovni sestavy, které se počítají pouze v jednom směru (např. Decrement-jump-if-not-zero [DJNZ]).
- Plánování - toto rozděluje smyčku na více částí, které lze spouštět současně na více procesorech.
- Zkosení - tato technika se aplikuje na vnořenou smyčku iterující přes vícerozměrné pole, kde každá iterace vnitřní smyčky závisí na předchozích iteracích, a přeskupuje její přístupy k poli tak, že jediné závislosti jsou mezi iteracemi vnější smyčky.
- Softwarové pipeline - typ out-of-order provádění smyčkových iterací skrýt latence procesorových funkčních jednotek.
- Rozdělení nebo loupání - pokusí se zjednodušit smyčku nebo eliminovat závislosti rozdělením na více smyček, které mají stejná těla, ale iterují přes různé části rozsahu indexu. Zvláštní případ je loupání smyčky , které může zjednodušit smyčku s problematickou první iterací provedením této iterace samostatně před vstupem do smyčky.
- Dlaždice nebo blokování - reorganizuje smyčku pro iteraci přes bloky dat o velikosti, aby se vešly do mezipaměti.
- Vektorizace - pokusí se spustit co nejvíce iterací smyčky současně na systému SIMD .
- Odvíjení - několikrát duplikuje tělo smyčky, aby se snížil počet testů podmínek smyčky a počet skoků, které mohou snížit výkon tím, že naruší potrubí instrukcí. Úplné rozvinutí smyčky eliminuje veškeré režijní náklady (kromě vícenásobného načítání instrukcí a zvýšené doby načítání programu), ale vyžaduje, aby byl v době kompilace znám počet iterací (s výjimkou kompilace Just-in-time ). Je také třeba dbát na to, aby vícenásobný přepočet indexovaných proměnných nebyl větší režií než postupující ukazatele v původní smyčce.
- Unswitching - přesune podmíněný zevnitř smyčky do vnějšku duplikováním těla smyčky a umístěním jeho verze do každé klauzule if a else podmíněné.
- Sekce nebo těžba proužků - zavedená pro vektorové procesory , smyčková sekce je technika transformace smyčky, která umožňuje kódování smyček SIMD (jedna instrukce, více dat) a zlepšuje výkon paměti. To zahrnuje každou operaci vektoru prováděnou pro velikost menší nebo rovnou maximální délce vektoru na daném vektorovém stroji.
Unimodulární transformační rámec
Přístup unimodulární transformace používá jedinou unimodulární matici k popisu kombinovaného výsledku posloupnosti mnoha výše uvedených transformací. V centru tohoto přístupu je pohled na množinu všech provedení příkazu v n smyčkách jako na sadu celočíselných bodů v n -rozměrném prostoru, přičemž body jsou prováděny v lexikografickém pořadí . Například provedení příkazu vnořeného uvnitř vnější smyčky s indexem i a vnitřní smyčky s indexem j lze přidružit k dvojicím celých čísel . Aplikace unimodulární transformace odpovídá vynásobení bodů v tomto prostoru maticí. Například výměna dvou smyček odpovídá matici .
Unimodulární transformace je legální, pokud zachovává časovou posloupnost všech závislostí ; měření dopadu unimodulární transformace na výkon je obtížnější. Nedokonale vnořené smyčky a některé transformace (například obklady) se do tohoto rámce snadno nevejdou.
Polyhedrální rámec nebo rámec založený na omezeních
Mnohostěnný Model zvládá širší třídu programů a transformací než unimodular rámce. Sada provádění sady příkazů v rámci možná nedokonale vnořené sady smyček je považována za sjednocení sady polytopů představujících provádění příkazů. Na tyto polytopy se aplikují afinní transformace , které vytvářejí popis nového pořadí provádění. Hranice polytopů, datové závislosti a transformace jsou často popsány pomocí systémů omezení a tento přístup je často označován jako omezení optimalizace smyčky založené na omezeních . Například jeden příkaz ve vnější smyčce ' pro i: = 0 až n ' a vnitřní smyčka ' pro j: = 0 až i + 2 ' se provede jednou pro každý pár (i, j) tak, že 0 <= i <= na a 0 <= j <= i + 2 .
Transformace je opět legální, pokud zachovává časovou posloupnost všech závislostí . Odhadování výhod transformace nebo nalezení nejlepší transformace pro daný kód na daném počítači zůstávají v době tohoto psaní (2010) předmětem probíhajícího výzkumu.