funkcionálně.cz

Přední český blog o funkcionálním programování, kde se o funkcionálním programování nepíše
««« »»»

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

17. 5. 2015 — k47

Jed­no­du­chá otázka: Jak rychle dokáže po­čí­tač vy­ná­so­bit tisíc celých čísel? Od­po­věď, která přijde na mysl jako první: jde o tisíc in­strukcí a tedy o tisíc taktů, není tak úplně správná.

Tak předně in­strukce ce­lo­čí­sel­ného ná­so­bení na x86 pro­ce­so­rech (které ne­patří mezi single cycle pro­ce­sory) trvá 3 takty.

Do­hro­mady to tedy musí trvat 3000 taktů.

Ne tak docela. Mo­derní pro­ce­sory jsou pi­pe­li­no­vané a i když in­strukce trvá 3 takty pro­ce­sor umí začít s jednou novou ope­raci každý takt. V každém taktu se tedy můžou pře­krý­vat tři fáze třech růz­ných mul in­strukcí.

Ok, takže to zna­mená 1002 taktů. Tisíc in­strukcí za­po­ča­tých v tisíci tak­tech a pak počkat dva takty než do­běhne ta úplně po­slední.

Ono je to o něco málo slo­ži­tější. Takhle jed­no­duše to fun­guje, pouze když na sobě nejsou jed­not­livé in­strukce zá­vislé. Pokud na­stane si­tu­ace, že každá in­strukce závisí na vý­sledku té před­chozí, musí je pro­ce­sor vy­ko­ná­vat jednu po druhé. Exis­tují různé hard­wa­rové triky, které v téhle si­tu­aci po­mů­žou jako třeba ope­rand for­war­ding, kdy se vý­sle­dek ne­za­pi­suje do re­gis­tru, ale rovnou se pře­smě­ruje do ná­sle­du­jící in­strukce, ale ty po­mů­žou jen čás­tečně a ne­od­straní hlavní pro­blém, kterým je zá­vis­lost ope­rací.

I když v ur­či­tých pří­pa­dech nemusí zá­vis­lost mezi in­struk­cemi před­sta­vo­vat nutně velkou pře­kážku. Pokud na vý­sledku jedné in­strukce ne­zá­visí tři ná­sle­du­jící, ale až ta za nimi, není nic ztra­ceno, jak uka­zuje ná­sle­du­jící schéma (čas je na vo­do­rovné 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 roz­mezí 1002-3000 taktů.

Ani tohle není úplná pravda. Ma­in­stre­a­mové pro­ce­sory od doby Pentia Pro jsou out-of-order su­per­ska­lární CPU. Dokáží tedy vy­ko­nat ně­ko­lik in­strukcí na­jed­nou a OOO jádro dy­na­micky vybírá ty ne­zá­vislé, které na nic ne­če­kají a ty pro­vede. Sou­časná ge­ne­race pro­ce­sorů má 4 ALU a dokáže tedy pro­vést 4 mul in­strukce každý takt (pokud na sobě nejsou zá­vislé a nic jiného ne­stojí v cestě).

To tedy zna­mená, že tisíc čísel se dá vy­ná­so­bit v 252 až 3000 tak­tech.

Skoro. Pro­blém je v tom, že před­chozí kal­ku­lace po­čí­tají s tím, že ope­randy in­strukcí jsou oka­mžitě k dis­po­zici. Ale to není pravda. Data, která jsou ná­so­bena, se na­chází někde v paměti a před po­u­ži­tím musí být na­ta­žena do pro­ce­soru a cesta z RAM do CPU je za­tra­ceně dlouhá. Může trvat i něco kolem 100ns, což může pro změnu od­po­ví­dat 300 taktům pro­ce­soru. CPU se snaží, co může, aby tyto pro­dlevy a la­tance eli­mi­no­valo – má hlu­bo­kou cache hi­e­rar­chii, data načítá ve vět­ších blo­cích (cache line), data před­na­čítá a může pro­vá­dět ně­ko­lik load ope­rací pa­ra­lelně (tedy spíš na ně čekat). Přesto v nej­hor­ším pří­padě může utrpět pro­dlevu 300 taktů na každé slovo paměti. V nej­lep­ším pří­padě pro­ce­sor roz­jede svojí magii a la­tence nebude vůbec patrná.

Takže když budeme před­po­klá­dat, že každá in­strukce ná­so­bení načte jedno slovo z RAM1, 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 ex­trémně re­gu­lární – na­pří­klad násobí mezi sebou od­po­ví­da­jící ele­menty dvou polí – může kom­pi­lá­tor použít SIMD in­strukce, které pro­vá­dějí stej­nou ope­raci mezi ně­ko­lika růz­nými po­lož­kami vek­toru ne­jed­nou (SIMD zna­mená Single In­struction Mul­tiple Data).2 Po­slední ge­ne­race x86 pro­ce­sorů při­dá­vají do in­strukční sady roz­ší­ření AVX2, které pra­cuje s vek­to­ro­vými re­gis­try délky 256 bitů a umí pro­vá­dět vět­šinu ope­rací i s celými čísly (pů­vodní SIMD roz­ší­ření SSE umělo pra­co­vat jen s floaty). Jedna SIMD in­strukce dokáže vy­ná­so­bit dva re­gis­try ve kte­rých je 8 čtyř­baj­to­vých in­te­gerů – tedy pro­vést 8 ná­so­bení na­jed­nou. I když la­tence těchto ope­rací je 10 taktů, CPU dokáže začít jednu ta­ko­vou ope­raci každý takt3.

To tedy zna­mená, že to v nej­lep­ším pří­padě bude trvat 129 taktů a v nej­hor­ším pak 300 tisíc.

Takové roz­mezí vypadá že je skoro správné. Za­ne­dbává ostatní ope­race, které budou s nej­větší prav­dě­po­dob­ností v ta­ko­vém kódu pří­tomné jako třeba mov in­strukce nebo in­strukce smyček, ale když nejde o uži­tečný odhad, je aspoň reálný. Všechno záleží na de­tai­lech. Nebo jak řekl Linus Tor­valds: Talk is cheap. Show me the code.


  1. A to je možné, pro­tože x86 je re­gis­ter-memory ar­chi­tek­tura a in­strukce můžou pra­co­vat jak s re­gis­try tak i přímo s pamětí.
  2. Pro de­tailní rozbor SIMD, array/vector pro­ce­sorů do­po­ru­čuji tuto před­nášku kurzu Com­pu­ter Ar­chi­tecture
  3. Jde o in­strukci VP­MULLD. V pří­padě floatů je si­tu­ace ještě lepší: Pro­ce­sor může začít dvě VFMADD (která toho dělá trochu víc, ale dá se použít jako jed­no­du­ché ná­so­bení) v každém taktu a trvají 5 taktů (viz. in­struction tables).

Dále k tématu:

@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články