Plánování pokynů - Instruction scheduling

v počítačová věda, plánování instrukcí je optimalizace kompilátoru slouží k vylepšení paralelismus na úrovni instrukcí, což zvyšuje výkon na strojích s instrukční potrubí. Jednoduše řečeno, pokusí se provést následující, aniž by změnil význam kódu:

  • Vyhýbat se stánky potrubí přeskupením pořadí pokynů.[1]
  • Vyhněte se nelegálním nebo sémanticky nejednoznačným operacím (obvykle zahrnují problémy s časováním jemných instrukčních kanálů nebo neblokované prostředky).

Zastavení potrubí může být způsobeno strukturálními riziky (limit zdrojů procesoru), datovými nebezpečími (výstup jedné instrukce je vyžadován jinou instrukcí) a řídicími riziky (větvení).

Datová rizika

Plánování instrukcí se obvykle provádí na jednom základní blok. Abychom mohli určit, zda přeskupení pokynů bloku určitým způsobem zachovává chování tohoto bloku, potřebujeme koncept závislost na datech. Existují tři typy závislostí, kterými se také stávají tři datová rizika:

  1. Číst po zápisu (RAW nebo „True“): V pokynu 1 se zapisuje hodnota použitá později v pokynu 2. V pokynu 1 musí být první, nebo v pokynu 2 bude načtena stará hodnota místo nové.
  2. Zápis po přečtení (WAR nebo „Anti“): Pokyn 1 čte místo, které je později přepsáno Pokynem 2. Pokyn 1 musí být první, jinak přečte novou hodnotu místo staré.
  3. Zápis po zápisu (WAW nebo "Výstup"): Dvě instrukce zapisují do stejného umístění. Musí se vyskytovat v původním pořadí.

Technicky vzato existuje čtvrtý typ Číst po přečtení (RAR nebo „Vstup“): Obě instrukce čte stejné umístění. Závislost vstupu neomezuje pořadí provádění dvou příkazů, ale je užitečné při skalární náhradě prvků pole.

Abychom se ujistili, že respektujeme tři typy závislostí, vytvoříme graf závislostí, který je řízený graf kde každý vrchol je instrukce a je zde hrana z I1 já2 kdybych1 musí přijít dříve než já2 kvůli závislosti. Pokud jsou závislosti nesené smyčkou vynechány, graf závislostí je a směrovaný acyklický graf. Pak jakékoli topologické třídění tohoto grafu je platný plán instrukcí. Okraje grafu jsou obvykle označeny latence závislosti. Toto je počet hodinových cyklů, které musí uplynout, než bude potrubí moci pokračovat v cílové instrukci bez zastavení.

Algoritmy

Nejjednodušší algoritmus k nalezení topologického řazení je často používán a je znám jako seznam plánování. Koncepčně opakovaně vybere zdroj grafu závislostí, připojí jej k aktuálnímu harmonogramu instrukcí a odebere jej z grafu. To může způsobit, že se další vrcholy stanou zdroji, které pak budou také brány v úvahu pro plánování. Algoritmus se ukončí, pokud je graf prázdný.

Abychom dosáhli dobrého harmonogramu, je třeba zabránit stánkům. To je určeno výběrem další instrukce, která má být naplánována. Řada heuristik se běžně používá:

  • Zaznamenávají se prostředky procesoru používané již naplánovanými pokyny. Pokud kandidát používá zdroj, který je obsazený, jeho priorita poklesne.
  • Pokud je kandidát naplánován blíže ke svým předchůdcům, než je přidružená latence, jeho priorita poklesne.
  • Pokud kandidát leží na kritické cestě grafu, jeho priorita vzroste. Tato heuristika poskytuje určitou formu výhledu v jinak místním rozhodovacím procesu.
  • Pokud výběr kandidáta vytvoří mnoho nových zdrojů, zvýší se jeho priorita. Tato heuristika má tendenci generovat více svobody pro plánovače.

Pořadí fází

Plánování instrukcí lze provést před nebo po přidělení registru nebo obojí před a po něm. Výhodou provedení před přidělením registru je, že to má za následek maximální paralelismus. Nevýhodou toho, že to uděláte před přidělením registrů, je, že to může vést k tomu, že alokátor registrů bude muset použít několik registrů, které přesahují dostupné registry. To způsobí, že bude zaveden kód rozlití / vyplnění, což sníží výkon příslušné části kódu.

Pokud má plánovaná architektura sekvence instrukcí, které mají potenciálně nelegální kombinace (kvůli nedostatku blokování instrukcí), musí být instrukce naplánovány po alokaci registru. Tento druhý časový rozvrh také zlepší umístění kódu rozlití / vyplnění.

Pokud je plánování provedeno až po alokaci registru, pak dojde k falešným závislostem zavedeným alokací registru, které omezí množství možného pohybu instrukcí, které plánovač může provést.

Typy

Existuje několik typů plánování instrukcí:

  1. Místní (základní blok) plánování: pokyny se nemohou pohybovat přes hranice základních bloků.
  2. Globální plánování: pokyny se mohou pohybovat přes hranice základních bloků.
  3. Modulo plánování: algoritmus pro generování softwarové pipeline, což je způsob, jak zvýšit paralelismus na úrovni výuky prokládáním různých iterací vnitřního smyčka.
  4. Plánování trasování: první praktický přístup pro globální plánování, plánování trasování se snaží optimalizovat cestu toku řízení, která se provádí nejčastěji.
  5. Plánování Superblocku: zjednodušená forma plánování trasování, která se nepokouší sloučit cesty toku řízení u trasování "postranních vchodů". Místo toho lze kód implementovat více než jedním plánem, což značně zjednodušuje generátor kódu.

Příklady kompilátoru

The Sbírka překladačů GNU je jeden překladač, o kterém je známo, že provádí plánování instrukcí pomocí -březen (sada instrukcí i plánování) nebo - štěstí (pouze plánování) příznaky. Využívá popis latencí instrukcí a to, jaké instrukce lze spouštět paralelně (nebo ekvivalentně, který „port“ každý používá) pro každou mikroarchitekturu k provedení úkolu. Tato funkce je k dispozici téměř všem architekturám, které GCC podporuje.[2]

Do verze 12.0.0 se plánování plánovalo LLVM / Clang mohl přijmout pouze a -březen (volala cílový procesor v jazyce LLVM) přepínač pro sadu instrukcí i plánování. Verze 12 přidává podporu pro - štěstí (tune-CPU) pouze pro x86.[3]

Zdroje informací o latenci a využití portu zahrnují:

LLVM llvm-exegeze by měl být použitelný na všech počítačích, zejména ke shromažďování informací o jiných než x86.[6]

Viz také

Reference

  1. ^ Su, Ching-Long; Tsui, Chi-Ying; Despain, Alvin M. (1994). Nízkoenergetický design a techniky kompilace pro vysoce výkonné procesory (PDF) (Zpráva). Laboratoř pokročilé počítačové architektury. ACAL-TR-94-01. (Chladné plánování)
  2. ^ "Možnosti x86". Používání GNU Compiler Collection (GCC).
  3. ^ "⚙ D85384 [X86] Přidat základní podporu pro volbu příkazového řádku -mtune v klangu". reviews.llvm.org.
  4. ^ „Prostředky pro optimalizaci softwaru. C ++ a montáž. Windows, Linux, BSD, Mac OS X“. Agner Fog.
  5. ^ „Latence instrukcí x86, x64, latence paměti a CPUID výpisy“. instlatx64.atw.hu. Viz také odkaz „Komentáře“ na stránce.
  6. ^ „llvm-exegesis - srovnávací test stroje LLVM“. Dokumentace LLVM 12.

Další čtení