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

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 2× 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.

Flattr this!

This entry was posted in CPU, Paměť. Bookmark the permalink.

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

  1. Tomáš says:

    pěkný článek, jako obvykle plný hodnotných odkazů, díky.

    Jinak ve spojení s Sandy Bridge se ještě objevuje L0 cache jako taková forma dřívější trace cache.

    Ještě bych doplnil, že Java má s tímhle velké problémy, její všudepřítomný array of references dokáže pěkně rychle pročistit sdílenou cache jenom při drobném iterování struktur. U kritických aplikací se to občas obchází denormalizací struktur do array of primitives…

    Jen pro zajímavost, jak detekuješ tohle chování? Dají se vůbec v komplexních aplikacích najít žravá vlákna?

    • O L0 je zmínka tady.

      U pole referencí je mnohem větší problém omezená lokalita dynamicky alokovaných objektů, která vede k nekonečné sérii cache-miss, která bude naprosto dominovat.

      Tohle chování nijak nedetekuji, protože nikdy nebylo třeba. V cestě vždycky stojí tisíc jiných drobných překážek, které přinesou mnohem znatelnější zrychlení.
      Zdrojem soupeření o LLC v prostředí JVM může být každé vlákno, které hodně alokuje nebo provádí GC. Ale protože jde o cache sdílenou všemi jádry na daném socketu, neplatí to jen o různých vláknech, ale i o různých procesech a o různých virtuálních systémech. Doslova napříč celým systémem.

      VisualVM umí měřit per thread allocations, což může být v určitých situacích dobré vodítko, ale neumí měřit per thread memory traffic. Na to je potřeba něco jako perf.

Leave a Reply

Your email address will not be published. Required fields are marked *