funkcionálně.cz

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

Inkluzivní cache, mnoho vláken a problémy

7. 10. 2015 — k47

Hardware mě nikdy nepřestane udivovat. Když si začnu myslet, že vím už (více méně) všechno, narazím na něco nečekaného. Nedávno mě překvapila jedna záludnost v chování inkluzivní cache v Intelích procesorech.

Inkluzivní cache funguje tak, že všechna data, která jsou v L1, se nachází také v L2, a data v L2 se nacházejí také v L3. Tohle uspořádání funguje, protože L2 je větší než L1 a L3 je větší než L2. Když jsou nějaká data vyhozená z L1, jsou stále k dispozici o úroveň níž, pro případ kdyby byla náhodou zase třeba.1

Současné procesory od Intelu mají tříúrovňovou3 inkluzivní cache: 32KB L1 a 256KB L2 jsou soukromé cache každého jádra a pod nimi leží několik megabajtů sdílené L3 cache (která se také označuje jako LLC - last level cache).

Tohle vypadá na první pohled jako nepřekonatelná kombinace pro běh mnoha vláken najednou: Trochu cache pro každé jádro, trochu sdílené cache, když více vláken potřebuje stejná data. V určitých případech si ale souběžně běžící procesy mohou škodit způsobem, který je mnohem záludnější než obyčejné soupeření o sdílenou LLC. Například když na různých jádrech CPU běží dva procesy - jeden provádí výpočetně složitou úlohu a má všechna potřebná data v soukromých L1 a L2, a druhý streamuje data z paměti a lineárně načítá velký blok dat, ale skoro nic s ním nedělá.

Problém je v tom, že LLC je sdílená a inkluzivní. Když jeden proces načte kus dat z paměti, musí ho uložit do cache. Protože cache je inkluzivní, musí ho napasovat aspoň to L3 (ale nejspíše i do ostatních úrovní). Když v L3 není místo, vybere nějakou cache-line, kterou vyhodí (evict) a nahradí ji novými daty. Protože je cache inkluzivní, může se stát, že tato vyhozená cache-line byla v soukromé cache jiného jádra. V takovém případě musí být vyhozena i z ní. Jedno jádro tedy způsobilo cache-line eviction v soukromé cache úplně jiného jádra.

Zpět k příkladu s dvěma procesy: Druhý proces, který excesivně čte z paměti, způsobí vyhození velkého množství cache-line z LLC, některé z nich jsou následně vystěhované z L1/L2 prvního procesu a to vede ke cache-miss a zpomalení, které by jinak nebylo možné.

Pěkné, žeano? Jedno vlákno, které excesivně čte z paměti2, může zpomalit ostatní vlákna, která z paměti vůbec číst nemusí.

Intel si je tohoto problému vědom a do serverových Broadwellů přidal cache allocation technology (CAT), která může omezit, do jakých části LLC může proces zapisovat. S tímto omezením i proces utržený ze řetězu nemůže narušit chování jiných procesů, které mají dobré využití cache.

CAT je dalším krokem k zlepšení efektivity serverů, které se typicky pohybuje mezi 10% a 50%. Je to z části způsobeno nesouladem mezi mikroarchitekturou procesorů a zátěží, která na nich běží. Na jedné straně jsou velice agresivní out-of-order jádra a na druhé straně výpočetně nepříliš náročné úlohy, které mají mizerné ILP a skoro žádné MLP a spekulativní mašinérii nedokážou využít. Typická serverová úloha potřebuje víc paralelismu ať už ve formě širokého SMT nebo většího počtu hloupých jader), větší instrukční cache (typická horká část programu se nevejde do L1I a ani do L2 a to vede k drastickému propadu výkonu) a dokonce by benefitovala z mělčí cache hierarchie a menší L3 (víc jak 4MB nepřináší skoro žádné zrychlení a jen zbytečně zabírá křemík). Řešením může být ve scale-out situacích nasadit Atomy místo Xeonů nebo ARM čipy s lepší energetickou efektivitu.

V tomto ohledu budoucnost vypadá chmurně. Skylake od Intelu zvládá 5-wide dispatch a chystaný Zen od AMD má 10 pipeline a 4-wide dispatch, ale jen 2x SMT/HyperThreading. Nic jako Power8, který zvládá osm nezávislých vláken na každém jádře nebo moře hloupých in-order jader ve Vega procesorech od Azulu.

Na druhou stranu pro výpočetně náročné úlohy a programy, které dobře využívají cache, čtou z paměti v předvídatelných vzorech a mají dobré ILP a MLP, nemůže být situace lepší.


Dále k tématu:


Pozn:

  1. Opakem je exkluzivní cache, která garantuje, že cache-line bude jen v jedné úrovni cache. Toto uspořádání bylo použité například v Athlonu od AMD. Zlatou střední cestu představuje kompromis, kdy data můžou být v několika úrovních cache, ale také jen v jedné. Výhodou exkluzivní cache je větší kapacita, inkluzivní cache jsou naproti tomu jednodušší.
  2. To může být vyvoláno například častou alokací. Za každou alokaci se navíc (aspoň v případě JVM) platí dvakrát v propustnosti pamětí - jednou když je načtená z paměti do cache a podruhé, když je z cache vyhozená a je třeba objekt zapsat zpátky do paměti.
  3. Některé modely mají i off-chip L4 cache, ale to je pouze tzv. victim cache.
@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články