Citiraj:
Autor Sinac
Može li itko navesti barem jedan primjer gdje takva raspodjela cachea donosi osjetan napredak u brzini u odnosu na klasičan CPU?
|
Slijedi me, pokazat cu ti.
Naime kaj; prije svega, ima jedan mali uvod u pricu. Ljudi koji su ucili programiranje od nekih drugih ljudi koje su pak ucili neki treci (a nije dalek put odakle je to zapravo pocelo, pa se u krivce moze uprjeti poimence prstom) imaju principijelno lose i klimavo znanje o tematici o kojoj pricaju. Zamisli ih kao subspecijaliste neke grane medicine koji mozda mogu reci nesto o specificnom dijelu tijela, ali holisticki, vrlo lako mogu ubiti pacijenta neobazirajuci se na ostatak funkcioniranja organizma kao cjeline. Malo plasticno, ali to ti je prica o uspjesnoj operaciji i mrtvom pacijentu. No vratimo se na temu...
Oni isti s pocetka ove pricice vjesto ce prikriti svoj manjak znanja opskurnim primjerima i tepnjom po nebitnom. Tako ces vrlo cesto naletiti na zlostavljanje ucenika sa mracnim primjerima oneliner programiranja kao prikazom omnipotentnosti ucitelja nad ucenikom. Tu vec stvari krecu monotono nizbrdo. Prva lekcija koju ce dobiti svaki nadobudni ucenik je "manje koda, vise performansi", sto moze biti istina samo igrom slucaja, nikako kao pravilo. Ti isti ljudi koji to govore uopce ne poznaju nacin rada racunala u smislu arhitekture i gradje procesora i popratnih dijelova, a kamo li da bi se dotakli specificnosti operativnog sustava pa onda eventualno presli na dodatne specificnosti jezika ili kompajlera. Dakle, sve u svemu, uvesti nekoga u elementarno programiranje mozda i nije najjednostavnija stvar ako sam ne poznajes tematiku dovoljno dobro. Ne zelim biti dosadan, ali dat cu vrlo lijep primjer za to.
Znas li cime se tvoj procesor bavi... pa, zaista vecinu vremena. Memorijom. Da. Svo to silno "racunanje" i "racunska snaga" kojom se utegnut celulit tvoje omiljene porno glumice kleberi po velikom LCD platnu u principu kosta pristupa memoriji naspram racunanja, ovako cu dati jednu slobodnu statisticku laz, 1:10 u korist troska pristupa memoriji na ustrb matematicke operacije kojom piksel sise upada na odgovarajuce mjesto na tvojoj matrici.
Uzmes li kao primjer procesor iz vec stare i dobrano razvaljene i dokumentirane Sandy Bridge arhitekture, imas 6 pipelinea (odnosno, efektivno do 6 IPC-a, kojih su nadrim samoprozvanim informaticarima puna usta), 64kB L1 cachea, 256kB L2 cachea, 4 jezgre i do 20MB L3 cachea. I sad kada pogledas broj tranzistora, ta skalamerija jede preko trecine chipa. E sad, koliko ti je potrebno za jednu obicnu, malu, smrdljivu i naoko nebitnu load instrukciju? Iz L1 cachea, 4 ciklusa. Za to vrijeme, mozes napraviti 32 bitno mnozenje. 12 ciklusa da potegnes pricu iz L2 cachea, gdje vec mozes korjenovati 32 bitni broj, a 26 ciklusa za L3 cache, gdje mozes sam iskombinirati sto sve mozes. Srecom, pametni inzenjeri su uspjeli smisliti nacin da prilikom dohvata nekog podatka, njegova okolina ide u cache, pa ako imas kontinuitet podataka, cesto se dogodi da je do njih puno jeftinije doci, jer ih caching sistem ne promasi, nego dohvati.
A znas koliko ti treba za napraviti load iz memorije? Precizno matematicki receno - pun kurac i jos malo ako si se rodio sa srecom da iz vrece picaka izvuces taj isti kurac; nemoj zaboraviti da je danas NUMA siroko u primjeni i samo bozansko bice i pokoji inzenjer koji je proizveo racunalo na kojemu radis zna gdje bi, teoretski, mogao biti neki podatak koji ces posrkati iz te iste memorije. Ako jos tu ukljucis i disk... Uplati godisnji. To se buzzwordom zove "performance hell".
I opet cu ti povezati to s pocetkom price i ucenjem ljudi kako programirati. Za matrice si cuo. Ako nisi, mozes se na Googleu vrlo brzo informirati i shvatiti koncept. Zgodne su jer putem njih mozes matematicki modelirati veliki skup problema. Ljudi ih vrlo cesto mnoze. Zajebano je to sto generalno to isto mnozenje nije komutativno, odnosno A*B != B*A. Ako nemas matematicara u gore navedenoj osobi koja te uci programirati, zapeo si sa prljavim algoritmom koji otprilike kaze sljedece:
Code:
C[i][j] += A[i][j] * B[k][j]
Slozenost mu je O(n^3), sto ce reci da za kvadratnu matricu 1000x1000 imas 1000^3 iteracija i jos matematickih operacija iz gore navedenog izraza pride.
Sada ide zabavni dio. Gornjoj operaciji prethodi, kao sto rekoh, n^3 iteracija, pa stoga imas 3 petlje:
Code:
for(i=0; i manje_od_jebem_ti_kuću_u_pičku_ko_ne_sredi_forum N; ++i)
for(j=0; j manje_od_jebem_ti_kuću_u_pičku_ko_ne_sredi_forum N; ++j)
for(k=0; k manje_od_jebem_ti_kuću_u_pičku_ko_ne_sredi_forum N; ++k)
Da si olaksas vizualizaciju problema, zamisli onu istu matricu gore o kojoj smo pricali kao razmotani skup brojeva u memoriji. Prvih 1000 redaka, drugih 1000 redaka... I tako dalje. Ako to raspises na papir, vidjet ces da ti je element [1, 1] odmah iza elementa [1, 2] na papiru, ali u memoriji, oni su udaljeni, u slucaju da se bavis integerima, 8 * 1000 bajtova. Pomaknes li se samo 10 redaka nize... Do the maths. Zapunio si vecinu L1 cacheova modernih x86 procesora.
A sto ako napravis ovo:
Code:
for(i=0; i manje_od_jebem_ti_kuću_u_pičku_ko_ne_sredi_forum N; ++i)
for(k=0; k manje_od_jebem_ti_kuću_u_pičku_ko_ne_sredi_forum N; ++j)
for(j=0; j manje_od_jebem_ti_kuću_u_pičku_ko_ne_sredi_forum N; ++k)
Jednostavnom zamjenom iteriranja, uspio si fragmentirane dijelove memorije skupiti, i ustedjeti vrijeme loada. Koliko?
https://www.banelli.biz/tmp/MMul(non_opt).exe (prva petlja)
https://www.banelli.biz/tmp/MMul(opt).exe (druga petlja)
Kako to izgleda na mojem Xeonu?
Ista stvar ti se lijepo moze vidjeti u paralelizaciji nekih procesa, gdje dodavanjem jezgara dobivas vrlo male napretke u performansama. I onda puf - mađija - dodjes na neku multisocket/multicore bestiju i sa "jednom jezgrom vise" (odnosno, pristupom dodatnoj L1/L2/L3 memoriji) dobivas red velicine bolje performanse.
Ako procitas malo postove iz
ove dretve, vidjet ces da sam upravo tu tupio kakva su poboljsanja dobivena nakon SB-a bas po tim "sitnim" pitanjima, koja su sve samo ne sitna kada udjes malo dublje u pricu. Unatoc cinjenici da vektorizacijom mozes postici negdje gore spomenuto "smanjenje koda" za 8 puta, usporedis li obicne skalarne operacije sa modernim AVX-om, rijetko kad ces dobiti vise od 2-3 puta vece performanse. Jer se to sve i dalje sporo dohvaca. Zbog toga se bojim da u trenutku kada ce brzine memorija rasti, latencije i dalje padati a kompajleri postati pametniji u optimizaciji petlji, AMD-ov put rezavanj YMM registara postat ce jako vidljiv, odnosno penali ce biti dramaticno osjetniji nego sto su danas...
Zasto sam nasrnuo ognjem i macem na ucitelje programiranja? Pa zato sto ja ovu jednostavnu optimizaciju vrlo popularnog i zaista pitkog problema, koji je eklatantan primjer za sijaset tema u programiranju, saznajem godinama nakon sto sam treba, sto u srednjoj skoli, sto na faksu. 2013. godina je bila, ako se ne varam.
Nadam se da sam ti barem malo uspio odgovoriti na pitanje. Ako je tvoje pitanje zasto je cijena takva kakva je, parafrazirat cu jedan grafit koji sam prije puno godina vidio na Plavim horizontima kraj Budve: "Milice, volim te JER MI SE MOŽE"