Plánování pokynů - Instruction scheduling

Ve vědě o počítačích , plánování instrukcí je optimalizace kompilátoru používají ke zlepšení na úrovni instrukcí paralelismus , což zlepš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:

  • Zabraňte zablokování potrubí změnou pořadí pokynů.
  • 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ím bloku . Abychom mohli určit, zda přeskupení pokynů bloku určitým způsobem zachovává chování tohoto bloku, potřebujeme koncept datové závislosti . Existují tři typy závislostí, kterými se také stávají tři rizika dat :

  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í obě stejné 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 závislostní graf, což je směrovaný graf, kde každý vrchol je instrukcí a existuje hrana od I 1 do I 2, pokud I 1 musí přijít před I 2 kvůli závislost. Pokud jsou závislosti nesené smyčkou vynechány, graf závislostí je směrovaný acyklický graf . Poté je jakýkoli topologický druh tohoto grafu platným plánem instrukcí. Okraje grafu jsou obvykle označeny latencí 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í se často používá a je znám jako plánování seznamu . 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á obsazený zdroj, jeho priorita poklesne.
  • Pokud je kandidát naplánován blíže ke svým předchůdcům, než je související 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.

Fázové pořadí plánování instrukcí

Plánování instrukcí lze provádět buď před a po alokaci registru, nebo 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ů převyšujících ty, které jsou k dispozici. 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í), instrukce musí být naplánovány po alokaci registru. Tento druhý plánovací průchod také zlepší umístění kódu rozlití / vyplnění.

Pokud je plánování provedeno až po alokaci registru, dojde k alokaci registru zavedením falešných závislostí, které omezí množství možného pohybu instrukcí plánovačem.

Druhy plánování instrukcí

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 scheduling : algoritmus pro generování softwarového pipeline , což je způsob, jak zvýšit paralelismus na úrovni instrukcí prokládáním různých iterací vnitřní smyčky .
  4. Plánování trasování : první praktický přístup pro globální plánování, plánování trasování se pokouší optimalizovat cestu toku řízení, která se provádí nejčastěji.
  5. Superblock plánování : zjednodušená forma plánování trasování, která se nepokouší sloučit cesty toku řízení u trasovacích „vedlejších vstupů“. Místo toho může být kód implementován více než jedním plánem, což značně zjednodušuje generátor kódu.

Viz také

Reference

Další čtení

  • Fisher, Joseph A. (1981). „Trace Scheduling: a Technique for Global Microcode Compaction“ . Transakce IEEE na počítačích . 30 (7): 478–490.( Plánování trasování )
  • Nicolau, Alexandru; Fisher, Joseph A. (1984). "Měření paralelismu dostupného pro velmi dlouhé instrukční architektury Wordu". Transakce IEEE na počítačích . 33 (11).( Plánování perkolace )
  • Bernstein, David; Rodeh, Michael (červen 1991). "Globální plánování instrukcí pro superskalární stroje". Sborník konference ACM, konference SIGPLAN '91 o programování a implementaci programovacích jazyků .( Globální plánování )