Za jak dlouho procesor vynásobí tisíc čísel

17. 5. 2015

Jednoduchá otázka: Jak rychle dokáže počítač vynásobit tisíc celých čísel? Odpověď, která přijde na mysl jako první: jde o tisíc instrukcí a tedy o tisíc taktů, není tak úplně správná.

Tak předně instrukce celočíselného násobení na x86 procesorech (které nepatří mezi single cycle procesory) trvá 3 takty.

Dohromady to tedy musí trvat 3000 taktů.

Ne tak docela. Moderní procesory jsou pipelinované a i když instrukce trvá 3 takty procesor umí začít s jednou novou operaci každý takt. V každém taktu se tedy můžou překrývat tři fáze třech různých mul instrukcí.

Ok, takže to znamená 1002 taktů. Tisíc instrukcí započatých v tisíci taktech a pak počkat dva takty než doběhne ta úplně poslední.

Ono je to o něco málo složitější. Takhle jednoduše to funguje, pouze když na sobě nejsou jednotlivé instrukce závislé. Pokud nastane situace, že každá instrukce závisí na výsledku té předchozí, musí je procesor vykonávat jednu po druhé. Existují různé hardwarové triky, které v téhle situaci pomůžou jako třeba operand forwarding, kdy se výsledek nezapisuje do registru, ale rovnou se přesměruje do následující instrukce, ale ty pomůžou jen částečně a neodstraní hlavní problém, kterým je závislost operací.

I když v určitých případech nemusí závislost mezi instrukcemi představovat nutně velkou překážku. Pokud na výsledku jedné instrukce nezávisí tři následující, ale až ta za nimi, není nic ztraceno, jak ukazuje následující schéma (čas je na vodorovné ose).

 nezávislé operace

 +--------+
 | 1      |
 +--+-----+--+
    | 2      |
    +--+-----+--+
       | 3      |
       +--+-----+--+
          | 4      |
          +--+-----+--+
             | 5      |
             +--+-----+--+
                | 6      |
                +--------+



 operace v řádcích na sobě závisí

 +--------+  +--------+
 | 1      |  | 5      |
 +--+-----+-----+-----+--+
    | 2      |  | 6      |
    +--+-----+-----+-----+--+
       | 3      |  | 7      |
       +--+-----+-----+-----+--+
          | 4      |  | 8      |
          +--------+  +--------+


 oprace závisí na výsledku předchozí

 +--------+--------+--------+--------+--------+
 | 1      | 2      | 3      | 4      | 5      |
 +--------+--------+--------+--------+--------+

Takže to bude něco v rozmezí 1002-3000 taktů.

Ani tohle není úplná pravda. Mainstreamové procesory od doby Pentia Pro jsou out-of-order superskalární CPU. Dokáží tedy vykonat několik instrukcí najednou a OOO jádro dynamicky vybírá ty nezávislé, které na nic nečekají a ty provede. Současná generace procesorů má 4 ALU a dokáže tedy provést 4 mul instrukce každý takt (pokud na sobě nejsou závislé a nic jiného nestojí v cestě).

To tedy znamená, že tisíc čísel se dá vynásobit v 252 až 3000 taktech.

Skoro. Problém je v tom, že předchozí kalkulace počítají s tím, že operandy instrukcí jsou okamžitě k dispozici. Ale to není pravda. Data, která jsou násobena, se nachází někde v paměti a před použitím musí být natažena do procesoru a cesta z RAM do CPU je zatraceně dlouhá. Může trvat i něco kolem 100 ns, což může pro změnu odpovídat 300 taktům procesoru. CPU se snaží, co může, aby tyto prodlevy a latance eliminovalo - má hlubokou cache hierarchii, data načítá ve větších blocích (cache line), data přednačítá a může provádět několik load operací paralelně (tedy spíš na ně čekat). Přesto v nejhorším případě může utrpět prodlevu 300 taktů na každé slovo paměti. V nejlepším případě procesor rozjede svojí magii a latence nebude vůbec patrná.

Takže když budeme předpokládat, že každá instrukce násobení načte jedno slovo z RAM¹ , může jich tisíc trvat od 252 taktů do 300000.

Skoro, ale může to být ještě lepší. Pokud kód násobí data, která jsou extrémně regulární - například násobí mezi sebou odpovídající elementy dvou polí - může kompilátor použít SIMD instrukce, které provádějí stejnou operaci mezi několika různými položkami vektoru nejednou (SIMD znamená Single Instruction Multiple Data).² Poslední generace x86 procesorů přidávají do instrukční sady rozšíření AVX2, které pracuje s vektorovými registry délky 256 bitů a umí provádět většinu operací i s celými čísly (původní SIMD rozšíření SSE umělo pracovat jen s floaty). Jedna SIMD instrukce dokáže vynásobit dva registry ve kterých je 8 čtyřbajtových integerů - tedy provést 8 násobení najednou. I když latence těchto operací je 10 taktů, CPU dokáže začít jednu takovou operaci každý takt³ .

To tedy znamená, že to v nejlepším případě bude trvat 129 taktů a v nejhorším pak 300 tisíc.

Takové rozmezí vypadá že je skoro správné. Zanedbává ostatní operace, které budou s největší pravděpodobností v takovém kódu přítomné jako třeba mov instrukce nebo instrukce smyček, ale když nejde o užitečný odhad, je aspoň reálný. Všechno záleží na detailech. Nebo jak řekl Linus Torvalds: Talk is cheap. Show me the code.

A to je možné, protože x86 je register-memory architektura a instrukce můžou pracovat jak s registry tak i přímo s pamětí.
Pro detailní rozbor SIMD, array/vector procesorů doporučuji tuto přednášku kurzu Computer Architecture
Jde o instrukci VPMULLD. V případě floatů je situace ještě lepší: Procesor může začít dvě VFMADD (která toho dělá trochu víc, ale dá se použít jako jednoduché násobení) v každém taktu a trvají 5 taktů (viz. instruction tables).

Dále k tématu: