Hyper-threading aneb "Jak sakra může běžet víc vláken na jednom jádře?"

21. 1. 2015

Nedávno jsem narazil na článek, který testoval, jak se pod zátěží chová procesor se zapnutým hyper-threadingem. Autor onoho textu na základě měření a vlastních předpokladů vyslovoval divoké domněnky a spekulace, které bohužel neměly příliš mnoho společného s chladnou realitou křemíku.

Otázka tedy zní: Jak je to vlastně s hyper-threadingem a simultaneous multithreading (SMT) obecně? Jak můžou běžet dvě vlákna na jednom procesorovém jádře zároveň?

Odpověď je jednoduchá: SMT se stará jenom o to, aby procesor měl stálý přísun nezávislých instrukcí k vykonání na out-of-order jádru.

Téměř všechna moderní CPU jsou pipelinované out-of-order superskalární procesory¹ , které dokážou dělat mnoho věcí najednou. Nejde jen o souběžná vlákna běžící na různých jádrech multiprocesoru, ale také o schopnost naráz vykonávat několik instrukcí jednovláknového programu (jde o takzvaný instuction level parallelism, zkráceně ILP). Tohle je možné právě proto, že i když se současné procesory navenek tváří, jako kdyby plně respektovaly Von Neumannovu architekturu, jejich vnitřní fungování v mnohém připomíná data-flow model. Tento způsob práce se označuje jako out-of-order execution (OOO). CPU nezpracovává jednu instrukci za druhou, ale načítá a dekóduje² jich několik v každém taktu. Tyto instrukce jsou poté umístěny do re-order bufferu (ROB), což je ve své podstatě fronta dekódovaných mikrooperací³ , které čekají na vykonání. Out-of-order jádro se poté snaží dynamicky tyto instrukce provést na dostupných funkčních jednotkách procesoru (nejnovější Intely, které je označují jako porty, jich mají osm) a zkouší vybrat co nejvíce instrukcí, které mohou běžet najednou. Když jsou operace nezávislé (tj. nezávisí na žádných předchozích) mohou být vykonány paralelně na různých portech. To je obzvláště výhodné, když jde o load⁴ instrukce načítající data z paměti. Než blok dat dorazí z RAM do cache CPU, může to trvat až několik stovek taktů. Pokud OOO engine dokáže zařídit, aby nezávislé load operace běžely paralelně, může tak dramaticky zrychlit program⁵ . Pokud ale instrukce A závisí na B, A musí počkat ve frontě re-order bufferu dokud B není plně uskutečněna a teprve poté dostane svojí nanosekundu slávy. Moderní procesory vynakládají velké úsilí, plochu a energii na to, aby zaručily, že ve frontě jsou pořád nějaké nezávislé instrukce připravené k vykonání - prefetchují data, odhadují podmíněné skoky a divoce spekulují, jen aby objevily tu další load instrukci a narazily na ten další cache-miss.

Bohužel ILP má své limity a v běžných programech je jen omezené množství nezávislých instrukcí. Ivan Godard z Mill Computing říká "Tajemství out-of-order procesorů je, jak málo out-of-order vlastně jsou"⁶ ". Každé jádro Haswellu je schopné načíst, dekódovat a vykonat 4 instrukce v každém taktu⁸ , mají re-order buffer délky 192¹² a krotí smečku 168 virtuálních general purpose registrů⁷ , ale jen zřídka dokáže tyto prostředky naplno využít. Běžný kód zkrátka neobsahuje dost ILP na to, aby byl procesor plně vytížený. Některé zdroje uvádějí, že běžné maximum ILP je někde kolem 2.5.

Právě v tomto místě přichází ke slovu hyper-threading. Když máme velice paralelní procesory, které většinu času nejsou schopny zcela využít svůj potenciál, je jenom logické před jádro přidat druhý frontend, který načítá a dekóduje instrukce jiného vlákna a který zásobí out-of-order strojovnu novým proudem instrukcí, v němž je s trochou štěstí možné najít dostatečné množství nezávislých operací, které zužitkují kapacitu dostupného hardwaru.

Taková je podstata hyper-threadingu a SMT⁹ . Nejde o hardwarové context-switche¹⁰ , nejde o to, že se Von Neumannovský procesor maskuje za dva (jako je tomu v případě barell temporal multithreading nebo super-threading), jde jen o to využít všechny možnosti procesoru, které by jinak ležely ladem.¹¹

Nevýhodou hyper-threadingu je skutečnost, že najednou běží víc nezávislých vláken, které sdílejí dostupnou cache. Každé hyper-vlákno má tedy k dispozici efektivně poloviční množství cache, než kdyby procesor neměl povolený HT. To může v některých případech mít značný vliv na rychlost programu. I tady platí staré rčení: "Když jsi s rozumem v koncích, použij perf".

Dále k tématu:

Procesory a jejich architektura (sebrané spisy)
Introduction to Multithreading, Superthreading and Hyperthreading - článek z roku 2002, který poslouží jako dobrý úvod, obsahuje několik názorných ilustrací a popisuje implementaci hyper-threadingu.

1) Prvním komerčně úspěšným OOO procesorem bylo Pentium Pro. Průkopníky v této oblasti však byli gangsteři v kravatách z IBM, kteří navrhli první OOO procesor už v šedesátých letech.
2) To že dekódování x86 instrukcí je problém se můžete přesvědčit tady a tady. Současné generace CPU mají kromě instrukční level 1 cache, také μops cache a loop buffer proto, aby eliminovaly režii dekódování instrukcí, které mají prefixy, escape-sekvence a proměnnou délku.
3) Instrukce jsou dekódovány na mikrooperace (μops), které jsou pak vykonány procesorem. Proto i CISC architektury jako x86 se uvnitř chovají jako RISC.
4) Na x86 jde o mov instrukci, která má jako zdroj adresu paměti.
5) Zrychlení je tak dramatické, že všechny optimalizace v procesoru směřují jen a pouze k tomuto cíli - víc souběžných cache-miss (viz).
6) Zdroj se mi nepodařilo vypátrat, ale je to zmíněno někde v sérii přednášek pořádaných Mill Computing. Godard dost možná cituje někoho jiného, pravděpodobně z týmu vyvíjejícího Itanium.
7) A stejný počet floating point virtuálních registrů. Virtuální registry určují jak dalece může jádro spekulovat.
8) Technicky je možné až 6 instrukcí, když program má to štěstí, že procesor dokáže sloučit několik párů operací (macro-op fusion). Čistě teoreticky by mohlo jít až o 8 operací vykonaných na všech osmi portech. Poslední generace procesorů Itanium (Poulson) stabilně zvládá 12 instrukcí za takt (ale v tomto případě nejde o OOO, ale o open pipeline a static scheduling).
9) SMT bývá mnohem divočejší v ne-x86 procesorech. Například Power8 nebo Sparc M7 dokáže provádět osm vláken najednou, nikoli pouhé dvě, jak je běžné ve světě Intelu a AMD. Jde o kompromis mezi agresivitou a paralelismem procesoru. x86 se očividně snaží optimalizovat jednovláknový výkon, kdežto Power a Sparc se svými osmi souběžnými vlákny míří na propustnost a throughput.
10) Hardwarové context-switche a hardwarový scheduling jsou však běžné ve světě GPGPU.
11) Některý, zvláště numerický kód dokáže z procesoru vymáčknout 4 instrukce za takt (IPC). V takovém případě HT nebo SMT nemá žádný pozitivní dopad na výkon.
12) Velikost ROB ve své podstatě udává jak daleko do budoucnosti procesor vidí. Čím dál vidí, tím víc ILP může z kódu získat. Někdy však může nastat divoká souhra okolností, která má překvapivě negativní dopad na výkon, jak je demonstrováno v tomto videu.