Vlákno názorů k článku Test: paměti mají čtyřistakrát delší latenci než procesory od BLEK. - To opakované měření přístupu k paměti pomocí pitch...
-
BLEK. (neregistrovaný)To opakované měření přístupu k paměti pomocí pitch mi přijde dost divné --- je to dost ovlivněno asociativitou cache.
Pokud máme v testu 512MiB ram a čteme z toho s pitch 1MiB-4, tak tak načteme 513 řádek. To celkem dává (při velikosti řádky 64) 32832 bytů. To by se normálně do cache vlézt mělo. Jenomže se to tam nevleze proto, že cache není ideálně asociativní paměť, ale je adresovaná.
Z fyzické adresy se vezme několik bitů (5 nebo 6) jako offset v řádce. Další bity (až do log2(velikost cache)/asociativita) určují adresu v cachi --- podle této adresy se cache adresuje podobně, jako nomální paměť. Na každé adrese se nachází tolik řádek, jaká je asociativita cache (je tam plná adresa řádky a její obsah) --- všechny tyhle řádky se porovnají s požadovanou adresou a pokud některý z nich sedí, tak se data v cachi nalezla.
Takže pokud např. AMD má L1 cache 2-cestně asociativní o velikosti 64KiB s řádkou 64 bytů, znamená to, že se bity 0-5 berou jako offset v řádce, bity 6-14 jako adresa v cache a na každé adrese jsou dva řádky. Důsledek je ten, že pokud budeme opakovaně číst pouze 3 hodnoty na adresách 0, 32768 a 65536, tak se nám do L1 cache nevejdou! (všechny tři se totiž namapujou na stejnou adresu, na níž jdou uložit však pouze dvě řádky)
U zmíněného testu, kde se 512MiB prochází s krokem 1MiB-4 pak výsledek na asociativitě a algoritmu na vyměňování jednotlivých řádek na dané adrese může záviset --- na každou adresu v cachi přečteme 16 (64/4) hodnot --- tedy na 16-cestně asociativní cachi by měl test projít zcela z cache, na méněcestně asociativní se bude část číst z paměti a část z cache.
Navíc je to ještě zamícháno tím, že cache se indexuje fyzickými adresami a program pracuje s virtuálními --- ihned po bootu program dostane jakž takž souvislý úsek paměti, po nějaké době běhu však stránky budou náhodně rozházeny. Ihned po bootu nám tedy více paměťových míst s pitchem 1MiB bude ležet na konfliktních adresách v cachi, po nějaké době běhu systému se však bity "12 a výše" v adrese stanou náhodné a bude docházet k méně konfliktům v cachi.
Test měřící hrubou dobu přístupu do paměti by měl být udělán tak, aby se data opravdu četla z paměti, tedy přečíst několikrát víc fyzických dat než je velikost cache, tak že to jakákoli organizace cache to není schopna zachytit. Test v programu bych upravil tak, že po dojetí na horních 512MB začne číst zase od začátku, ale o několik cacheline posunutý a takhle pořád dokola, dokud nepřečte několikrát více dat než je velikost cache.
Procesory Intel taky mají prefetch, jsou schopny se naučit na průchod pamětí s konstantním krokem a dělat podle toho prefetch. Pokud nechceme efekt tohoto prefetche měřit, tak by se i samotná hodnota pitch měla měnit během běhu. -
Asi jsem blbej, ale nejak vas prispevek uplne nechapu. Myslel jsem ze kdyz to udelam tak, ze nejprve nejak vyprazdnim cache a pak budu cist s takovou pitch aby mi preread nemohl moc pomahat (tim ze by dostal data do L2 cache driv nez si o ne program rekne) tak dostanu (kdyz se zanedba TLB-miss) zhruba dobu latence pameti krat pocet prectenych cisel. A to by nemelo na cachich zaviset vubec, protoze stejnou adresu (ani z jejiho okoli) uz podruhy nectu. Kdyz to pak 20* opakuju tak to opakuju i s tim vyprazdnovanim (proto to tak dlouho trva). Jeste takova technicka drobnost: data z toho 512MB pole se musi na zacatku aspon na kazdem 4tem KB precist/zapsat aby se prislusna stranka v linuxu vubec namapovala a nezdrzovalo to az pri testovani. Pri kazdem opakovani se zminena pole alokuji a znovu uvolnuji.
Takze problem je hlavne v tom, jak delat vyprazdnovani cache, abych z ni data temer urcite dostal pryc. Zjistil jsem, ze jen zapsat 150MB (s pitch=4) a zase je precist na nekterych CPU nestaci.
Kdyby bylo vypnute strankovani tak zapsanim a opetovnym prectenim 150MB (s pitch=4) je cache vyprazdnena urcite. Se zapnutym strankovanim je to slozitejsi, protoze mi alokace pameti muze vratit stranky jejihz fyzicke adresy se mapuji na stejne misto v cache. V extremnim pripade by se mohlo stat, ze diky takovemuto sdileni zustane jine misto cache zcela netknute a jako na potvoru v nem preziji data co pak budu cist (kterych jak jste spravne podotkl je pomerne malo).
Obecne je toto problem i operacniho systemu, protoze kdyz se to stane, tak se tim zhorsi vyuziti cache. Proto se tomu nektere UNIXy se snazi zabranit tzv. barvenim stranek, kdy se snazi alokovat stranky ktere v cache pak nekoliduji. Jenze pokud si vzpominam, tak ma Linux pouze barveni objektu uvnitr slabu. Takze se po nejake dobe da ocekavat, ze fyzicke stranky budou pridelovany vicemene nahodne. Rekneme ze je to nas pripad a zeptejme se jaka je pravdepodobnost, ze se celou cache nepodari vyprazdnit, tj. ze existuje aspon 1 adresa stanky uvnitr cache ktera nebude zasazena.
Nejdriv obarvim stranky pameti tak ze 2 dostanou stejnou barvu pokud se mapuji na stejnou adresu v cache. Barev je C=velikost_cache/velikost_stranky coz v pripade 4KB stranky a 4MB L2-cache je C=1024. Pak me zajima horni odhad na pravdepodobnost ze ani po K=150MB/4KB=150*256 nahodnych vyberech (bez vraceni) stranky nezasahnu barvu 1.
Pri prvnim vyberu je to zjevne (1-1/C). V dalsim vyberu je o neco mene nez (1-1/C) protoze uz jsem jednu non-1 barvu pouzil. Me ale jde jen o horni odhad takze budu brat (1-1/C). Z toho mam pravdepodobnost (1-1/C)^K ze minu barvu 1 (ostatni barvy muzu nebo nemusim minout).
Nakonec mi jde o to jaka je pravdepodobnost ze minu NEJAKOU barvu. To se da zhora odhadnout jako C*(1-1/C)^K. Neformalne receno je to diky tomu ze bud minu barvu 1, nebo 2, nebo... C. Horni odhad je to proto, ze nejde o disjunktni jevy (vzorec (1-1/C)^K pouzity pro barvu 1 v sobe ma i prispevek jevu ze minu barvu 1 i 2 a neminu ostatni, stejne tak jako vzorec (1-1/C)^K pouzity pro barvu 2 --- tim tam napr. tyto jevy zapocitam vickrat).
Po dosazeni
gnuplot> C=1024.0 gnuplot> print C*(1-1.0/C)**(150*1024/4) 5.20354763762773e-14
Takze pravdepodobnost, ze se nepodari vyprazdnit cache je temer zanedbatelna.
Pekne je videt v praxi, ze moc nezalezi na velikosti toho vyprazdovaciho pole. At je to 150MB nebo 2GB tak jsou vysledky pri dukladnem vyprazdnovani stejne. Vysledky pri 1pass-flush se lisi, ale to myslim je nejaky dalsi efekt.
model name : Intel(R) Xeon(R) CPU 5160 @ 3.00GHz cpu MHz : 2992.494 cache size : 4096 KB cache_alignment : 64 AVG CPU CLOCKS FOR DEPENDENT INDEPENDENT pro mazaci blok velikosti 150MB: 32bit load from L1-cache 1.001 pitch=4B typical L1-miss load 64.689 pitch=74B load from RAM 142.65ns 426.877 pitch=1048572B load from RAM 9.65ns 28.889 pitch=1048572B (1-pass cache flush) pro mazaci blok velikosti 1GB: 32bit load from L1-cache 1.001 pitch=4B typical L1-miss load 64.366 pitch=74B load from RAM 142.02ns 424.983 pitch=1048572B load from RAM 58.34ns 174.595 pitch=1048572B (1-pass cache flush) pro mazaci blok velikosti 2GB: 32bit load from L1-cache 1.001 pitch=4B typical L1-miss load 64.672 pitch=74B load from RAM 142.19ns 425.489 pitch=1048572B load from RAM 98.33ns 294.239 pitch=1048572B (1-pass cache flush) -
BLEK. (neregistrovaný)Pokud jsou na těch řádkách v L2 cache nějaká počítadla přístupu, tak tenhle kus kódu ta počítadla napumpuje na maximum (protože do L1 se to nevejde kvůli asociativitě):
for(int rep=0; rep<32; rep++)
for(int i=0; i<mem_size; i+=pitch) acc+=*(u32*)(&adr[i]);
--- takže se pak stane, že ani lineární přístup to nevyprázdní, pokud cache vyhazuje stránky s nejmenším počítadlem přístupu.
"Kdyby bylo vypnute strankovani tak zapsanim a opetovnym prectenim 150MB (s pitch=4) je cache vyprazdnena urcite."
--- nemusí, protože z těch řádek na jedné adrese si procesor vybere jednu, kterou vyprázdní. Může si pořád vybírat tu stejnou (s nejmenším počítadlem přístupu), takže pak vyprázdní pouze (velikost cache/asociativita) bytů v cache.
"Barev je C=velikost_cache/velikost_stranky"
Nikoli. Barev je velikost cache/asociativita_cache/velikost_stranky.
"Pak me zajima horni odhad na pravdepodobnost ze ani po K=150MB/4KB=150*256 nahodnych vyberech (bez vraceni) stranky nezasahnu barvu 1."
Jednou ji zasáhnout nestačí. Je třeba dotyčnou barvu zasáhnout tolikrát, kolik je asociativita cache. A ani to stačit nemusí, procesor může při všech těchto zásazích vyhodit tu samou řádku a ostatních (asociativita-1) řádek tam nechat (což se asi opravdu děje vzhledem k tomu, že lineárním přístupem se tu cache nepodařilo vyprázdnit).
Ja vyprázdnit cache? instrukce wbinvd (ale ta jde volat jen z kernel módu) nebo clflush (ta jde i uživatelským procesem, ale je až od SSE2). -
klusacek (neregistrovaný)
"Nikoli. Barev je velikost cache/asociativita_cache/velikost_stranky"
To ano, ale intuitivne ocekavam ze ta pravdepodobnost moc nezmeni. I kdyby to bylo 1000* horsi tak to porad bude zanedbatelne.
"--- takže se pak stane, že ani lineární přístup to nevyprázdní, pokud cache vyhazuje stránky s nejmenším počítadlem přístupu."
ano je spravna pripominka. Takze jsem to prelozil bez toho for(rep...) a vysledek pro pocitac fireball je zde. Temer nelisi od puvodni verze. chce vymyslet duvod proc 1-pass flush nevyprazdni local-multi-pass ano (a jeste jenom na intelech)
model name : Intel(R) Xeon(R) CPU 5160 @ 3.00GHz cpu MHz : 2992.494 cache size : 4096 KB cache_alignment : 64 AVG CPU CLOCKS FOR DEPENDENT INDEPENDENT rdtsc 65.011 64.011 32bit add 1.003 0.343 32*32->64bit imul 4.771 1.528 0*0 imul 4.769 64/32->32.32 div 41.051 64bit fadd 2.252 1.031 64bit NaN+x fadd 195.300 214.651 64bit fmul 5.000 2.031 64bit fdiv 37.471 37.002 32bit load from L1-cache 1.001 pitch=4B typical L1-miss load 64.667 pitch=74B load from RAM 140.63ns 420.839 pitch=1048572B load from RAM 10.07ns 30.127 pitch=1048572B (1-pass cache flush)Kdyby se to ridilo jen pomoci LRU citacu, tak by pak 3* opakovany one-pass flush mel zvitezit nad 1* opakovanym zapisem a ctenim dat. Jenze se to nestane:
model name : Intel(R) Xeon(R) CPU 5160 @ 3.00GHz cpu MHz : 2992.494 cache size : 4096 KB cache_alignment : 64 AVG CPU CLOCKS FOR DEPENDENT INDEPENDENT rdtsc 65.011 64.011 32bit add 1.003 0.343 32*32->64bit imul 4.768 1.528 0*0 imul 4.769 64/32->32.32 div 41.056 64bit fadd 2.252 1.031 64bit NaN+x fadd 195.300 214.584 64bit fmul 5.000 2.031 64bit fdiv 37.471 37.002 32bit load from L1-cache 1.001 pitch=4B typical L1-miss load 64.604 pitch=74B load from RAM 141.97ns 424.833 pitch=1048572B load from RAM 11.21ns 33.558 pitch=1048572BDokonce i kdyz jsem opakovani udelal uvnitr smycky, tj. ze jsem cetl 10* po sobe totez misto z pameti (ovsem nevim jestli se to bude zapocitavat do counteru L2 cache kdyz to jde tak rychle po sobe), tak se vysledek posledni radky testu moc nezmenil --- vychazelo 14.22 ns.
Takze bud se ty countery v L2 cache updatuji nejak pomaleji, nebo je tam jeste jiny mechanismus. V te posledni verzi mohla mit data co chci vyprazdnit counter maximalne 2, oproti datum kterymi to vyprazdnuju, ktere ho mely maximalne 10. Musi tam byt jeste jiny mechanismus (treba nejaky pomaly update counteru, nebo kdovico jinyho) ktery by to vysvetlil.
-
anonymníMozne vysvetleni Intelovskeho chovani by mohlo byt v interakci L1 a L2 cache.
Kdyby se citace v L2 incrementovaly pouze kdyz se data z L2 stehuji do L1, tak pokud data pouzivam vickrat avsak pouze lokalne, zvysilo by to L2 citace jen o 1, a zbytek by sel na L1 citace. Pri globalnim opakovani bych sice teoreticky mohl zvysovat citace L2, ale nez to pole cele projdu tak dojde k periodickemu vynulovani citacu (lepe receno vydeleni 2ma).
Takze ani ciste lokalni ani ciste globalni pristup ke cache flush nezafunguje, protoze citace L2 stranek budou neco jako 1 nebo 2 a bude se proto prepisovat stale ta stejna stranka.
Naopak kombinovany pristup, ktery pouziva mensi bloky, ktere se vejdou do L2 ale nevejdou do L1, nuti k castemu pohybu mezi L1 a L2, coz vede ke zvysovani citacu v L2 a naslednemu vyhazovani ostatnich stranek.
Ted je jen otazka v cem se AMD lisi, ze se v tomto ohledu chova hur. Jak jsem se dival na vysledky tak i Phenomy se chovaji podobne jako Opterony. -
BLEK. (neregistrovaný)Teď jsem ten program zkoumal důkladněji a přišel jsem ještě na jednen zásadní problém:
pokus o vyprazdňování cache pomocí calloc() a čtení této paměti.
calloc() totiž pro větší velikost zavolá pouze mmap() a nenuluje tu paměť (ze specifikace mmap musí být vrácená paměť již vynulovaná). Při pokusu o čtení stránky, na kterou se nikdy nezapisovalo, Linux vrátí připravenou nulovou stránku a namapuje ji read-only; až když se na stránku zapíše, tak ji Linux fyzicky alokuje. Takže celý cyklus
for(int i=0; i<L; i++) acc+=dummy[i];
čte vlastně pouze z jedné nulové stránky. Takže to cache nevyprázdní skoro vůbec.
Když jsem ten cyklus nahradil:
for(int i=0; i<L; i++) dummy[i] = 1;
--- tak sice rozdíly mezi one-pass a multi-pass flush byly (asi vlivem jevů popsaných výše), ale už ne 10-násobné:
model name : Intel(R) Xeon(R) CPU 5110 @ 1.60GHz
cpu MHz : 1595.929
cache size : 4096 KB
cache_alignment : 64
load from RAM 232.22ns 370.602 pitch=1048572B
load from RAM 195.94ns 312.702 pitch=1048572B (1-pass cache flush)
[ předtím to bylo:
load from RAM 222.61ns 355.277 pitch=1048572B
load from RAM 16.06ns 25.627 pitch=1048572B (1-pass cache flush)
] -
klusacek (neregistrovaný)To je ono! Vynikajici detektivni prace ;-) Uprimne gratuluju (a zaroven mlatim hlavou o stul ze jsem zapomel jak presne jsem kdysi implementoval vlastni funkci c_alloc()).
Jenom jeste nerozumim, proc pro AMDcka vychazely oba casy skoro stejne. Ze by mmap() fungoval jinak u Intelu a AMD?
