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

Hard­ware mě nikdy ne­pře­stane udi­vo­vat. Když si začnu myslet, že vím už (více méně) všechno, na­ra­zím na něco ne­če­ka­ného. Ne­dávno mě pře­kva­pila jedna zá­lud­nost v cho­vání in­klu­zivní cache v In­te­lích pro­ce­so­rech.

In­klu­zivní cache fun­guje tak, že všechna data, která jsou v L1, se na­chází také v L2, a data v L2 se na­chá­zejí také v L3. Tohle uspo­řá­dání fun­guje, pro­tože L2 je větší než L1 a L3 je větší než L2. Když jsou nějaká data vy­ho­zená z L1, jsou stále k dis­po­zici o úroveň níž, pro případ kdyby byla ná­ho­dou zase třeba.1

Sou­časné pro­ce­sory od Intelu mají tří­úrov­ňo­vou3 in­klu­zivní cache: 32KB L1 a 256KB L2 jsou sou­kromé cache kaž­dého jádra a pod nimi leží ně­ko­lik me­ga­bajtů sdí­lené L3 cache (která se také ozna­čuje jako LLC – last level cache).

Tohle vypadá na první pohled jako ne­pře­ko­na­telná kom­bi­nace pro běh mnoha vláken na­jed­nou: Trochu cache pro každé jádro, trochu sdí­lené cache, když více vláken po­tře­buje stejná data. V ur­či­tých pří­pa­dech si ale sou­běžně běžící pro­cesy mohou škodit způ­so­bem, který je mnohem zá­lud­nější než oby­čejné sou­pe­ření o sdí­le­nou LLC. Na­pří­klad když na růz­ných já­drech CPU běží dva pro­cesy – jeden pro­vádí vý­po­četně slo­ži­tou úlohu a má všechna po­třebná data v sou­kro­mých L1 a L2, a druhý stre­a­muje data z paměti a li­ne­árně načítá velký blok dat, ale skoro nic s ním nedělá.

Pro­blém je v tom, že LLC je sdí­lená a in­klu­zivní. Když jeden proces načte kus dat z paměti, musí ho uložit do cache. Pro­tože cache je in­klu­zivní, musí ho na­pa­so­vat aspoň to L3 (ale nej­spíše i do ostat­ních úrovní). Když v L3 není místo, vybere ně­ja­kou cache-line, kterou vyhodí (evict) a na­hradí ji novými daty. Pro­tože je cache in­klu­zivní, může se stát, že tato vy­ho­zená cache-line byla v sou­kromé cache jiného jádra. V ta­ko­vém pří­padě musí být vy­ho­zena i z ní. Jedno jádro tedy způ­so­bilo cache-line eviction v sou­kromé cache úplně jiného jádra.

Zpět k pří­kladu s dvěma pro­cesy: Druhý proces, který ex­ce­sivně čte z paměti, způ­sobí vy­ho­zení vel­kého množ­ství cache-line z LLC, ně­které z nich jsou ná­sledně vy­stě­ho­vané z L1/L2 prv­ního pro­cesu a to vede ke cache-miss a zpo­ma­lení, které by jinak nebylo možné.

Pěkné, žeano? Jedno vlákno, které ex­ce­sivně čte z paměti2, může zpo­ma­lit ostatní vlákna, která z paměti vůbec číst nemusí.

Intel si je tohoto pro­blému vědom a do ser­ve­ro­vých Broadwellů přidal cache allo­cation tech­no­logy (CAT), která může omezit, do jakých části LLC může proces za­pi­so­vat. S tímto ome­ze­ním i proces utr­žený ze řetězu nemůže na­ru­šit cho­vání jiných pro­cesů, které mají dobré vy­u­žití cache.

CAT je dalším krokem k zlep­šení efek­ti­vity ser­verů, které se ty­picky po­hy­buje mezi 10% a 50%. Je to z části způ­so­beno ne­sou­la­dem mezi mik­ro­ar­chi­tek­tu­rou pro­ce­sorů a zátěží, která na nich běží. Na jedné straně jsou velice agre­sivní out-of-order jádra a na druhé straně vý­po­četně ne­pří­liš ná­ročné úlohy, které mají mi­zerné ILP a skoro žádné MLP a spe­ku­la­tivní ma­ši­né­rii ne­do­ká­žou využít. Ty­pická ser­ve­rová úloha po­tře­buje víc pa­ra­le­lismu ať už ve formě ši­ro­kého SMT nebo vět­šího počtu hloupých jader), větší in­strukční cache (ty­pická horká část pro­gramu se ne­ve­jde do L1I a ani do L2 a to vede k dras­tic­kému pro­padu výkonu) a do­konce by be­ne­fi­to­vala z mělčí cache hi­e­rar­chie a menší L3 (víc jak 4MB ne­při­náší skoro žádné zrych­lení a jen zby­tečně zabírá křemík). Ře­še­ním může být ve scale-out si­tu­a­cích na­sa­dit Atomy místo Xeonů nebo ARM čipy s lepší ener­ge­tic­kou efek­ti­vitu.

V tomto ohledu bu­douc­nost vypadá chmurně. Sky­lake od Intelu zvládá 5-wide dispatch a chys­taný Zen od AMD má 10 pi­pe­line4-wide dispatch, ale jen 2x SMT/Hy­perThrea­ding. Nic jako Power8, který zvládá osm ne­zá­vis­lých vláken na každém jádře nebo moře hloupých in-order jader ve Vega pro­ce­so­rech od Azulu.

Na druhou stranu pro vý­po­četně ná­ročné úlohy a pro­gramy, které dobře vy­u­ží­vají cache, čtou z paměti v před­ví­da­tel­ných vzo­rech a mají dobré ILP a MLP, nemůže být si­tu­ace lepší.


Dále k tématu:


Pozn:

  1. Opakem je ex­klu­zivní cache, která ga­ran­tuje, že cache-line bude jen v jedné úrovni cache. Toto uspo­řá­dání bylo po­u­žité na­pří­klad v Athlonu od AMD. Zlatou střední cestu před­sta­vuje kom­pro­mis, kdy data můžou být v ně­ko­lika úrov­ních cache, ale také jen v jedné. Vý­ho­dou ex­klu­zivní cache je větší ka­pa­cita, in­klu­zivní cache jsou na­proti tomu jed­no­dušší.
  2. To může být vy­vo­láno na­pří­klad častou alo­kací. Za každou alo­kaci se navíc (aspoň v pří­padě JVM) platí dva­krát v pro­pust­nosti pamětí – jednou když je na­čtená z paměti do cache a po­druhé, když je z cache vy­ho­zená 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