Algoritmusok vizsg´alata hierarchikus mem´ori´aj´u rendszerekben Horv´ath G´abor 2014. december 25.
1. Bevezet´ es Klasszikusan az algoritmusok fut´asi idej´et asszimptotikusan szok´as vizsg´alni. Kell˝oen nagy m´eret˝ u bemenetek eset´en az asszimptotikusan gyorsabb algoritmus lesz a j´o v´alaszt´as. Kisebb m´eret˝ u bemenetekn´el viszont nem ritka, hogy az asszimptotikusan rosszabb fut´asi idej˝ u algoritmus teljes´ıt jobban. Sok esetben a programoz´o el˝ore tudja, hogy egy adott algoritmusnak v´arhat´oan mekkora m´eret˝ u bemenetei lesznek. J´o p´elda erre a felhaszn´al´o ´es a program k¨ozti interakci´okat ´erint˝o algoritmusok egy r´esze, hiszen egy re´alis korl´atot lehet mondani ak´ar a k´eperny˝on megjelen´ıtend˝o grafikus vez´erl˝ok sz´am´ara, mert bizonyos m´eret felett a felhaszn´al´o nem is tudn´a feldolgozni azt az inform´aci´omennyis´eget amit a k´eperny˝on l´at. Ilyen esetekben az algoritmusok o¨sszehasonl´ıt´as´ara egy lehets´eges m´odszer bizonyos l´ep´esek v´arhat´o sz´am´anak az ¨osszehasonl´ıt´asa, p´eld´aul v´arhat´oan h´any ´ert´ekad´ast hajt v´egre az algoritmus. Ez a modell viszont azt felt´etelezi, hogy az ´ert´ekad´asok ugyanannyi id˝ot vesznek ig´enybe f¨ uggetlen¨ ul att´ol, hogy mikor t¨ort´ennek ´es milyen ´ert´eket ´ırnak fel¨ ul. A mai architekt´ ur´ak azonban a teljes´ıtm´eny n¨ovel´ese ´erdek´eben bonyolult gyors´ıt´ot´araz´asi megold´asokat haszn´alnak. Ahogy az az al´abbi t´abl´azatb´ol [3] is l´athat´o, csup´an azzal, hogy az adat amit ´epp el akarunk ´erni, nem csak a mem´ori´aban tal´alhat´o meg, hanem ´eppen az els˝o szint˝ u gyors´ıt´ot´arban is, 200-szor gyorsabban ´erhet˝o el. Ha csup´an egy-egy v´altoz´o el´er´ese lenne jelent˝osen gyorsabb, akkor nem befoly´asoln´a jelent˝osen az algoritmus fut´asi idej´et a gyors´ıt´ot´ar, azonban k¨ ul¨onb¨oz˝o mechanizmusok seg´ıts´eg´evel a processzor megpr´ob´alja kik¨ovetkeztetni, hogy milyen mint´aban olvassuk az adatokat a mem´ori´ab´ol, ´es ez´altal megpr´ob´alja el˝ore bet¨olteni a gyors´ıt´ot´arba azokat az adatokat amikre sz¨ uks´eg¨ unk lehet. Ebb˝ol kifoly´olag amennyiben az algoritmusunk egyszer˝ u mint´at k¨ovetve olvassa az adaL1 cache reference Branch mispredict L2 cache reference Mutex lock/unlock Main memory reference Read 1 MB sequentially from memory Disk seek Read 1 MB sequentially from disk 1
0.5 ns 5 ns 7 ns 25 ns 100 ns 250,000 ns 10,000,000 ns 20,000,000 ns
tokat (lehet˝oleg sorfolytonosan ak´ar el˝ore ak´ar h´atrafel´e), a hivatkozott v´altoz´ok t´ ulnyom´o t¨obbs´ege a gyors´ıt´ot´arban lesz addigra, mire hivatkozni vagy ´ırni akarjuk o˝ket. Az egyes m˝ uveletek idej´et ´erint˝o v´altoz´asokra az algoritmus fut´asi ideje m´eg ´erz´ekenyebb lehet. P´eld´aul, ha egy vonal megjelen´ıt´es´et v´egz˝o rutin k´etszeres´ere gyorsul, egy t´abl´azatot kirajzol´o rutin ak´ar n´egyszeres gyorsul´ast is mutathat. A cache-ek el´er´es´en´el m´eg gyorsabb a registerek el´er´ese, azonban a registerekkel az´ert nincs ´ertelme foglalkozni az algoritmusok teljes´ıtm´eny´enek a vizsg´alatakor, mert a ford´ıt´ok ma m´ar line´aris id˝oben meg tudj´ak a´llap´ıtani azok k¨ozel optim´alis felhaszn´al´as´at [4]. A program v´altoz´oinak a hely´et, illetve azoknak az el´er´esi mint´azat´at viszont nem tudj´ak ma sem a´trendezni a ford´ıt´ok, ez´ert sebess´egkritikus alkalmaz´asok eset´en a programoz´onak kell erre gondolnia.
2. M´ er´ esek metodol´ ogi´ aja A m´er´eseimhez a programokat C++ nyelven [2] ´ırom meg, ´es a gcc ford´ıt´o 4.9.1es v´altozat´aval ford´ıtom le. A k´odokat a C++11-es szabv´any szerint ford´ıtom ´es az O3 kapcsol´oval optimaliz´alom. A m´er´esekhez felhaszn´alt laptopom egy Dell Inspiron N5110, Core i7-2630QM [5] processzorral ´es 8GB DDR3-mas RAM-mal. Az el˝obb eml´ıtett CPU 4 magos, 8 sz´alat t´amogat hardveresen, 6 MB 3. szint˝ u k¨oz¨os gyors´ıt´ot´arral (tov´abbiakban cache), valamit processzormagonk´ent 256KB 2. szint˝ u ´es 32 KB 1. szint˝ u cache-el rendelkezik. Nyelvnek az´ert a C++-t v´alasztottam, mivel ebben a programoz´onak nagy befoly´asa van a program mem´oria ´es utas´ıt´as kioszt´asra. A forr´asf´ajlokban egym´as mellett megtal´alhat´o f¨ uggv´enyekb˝ol a gener´alt bin´arisban a f¨ uggv´enyekb˝ol gener´alt k´od is egym´as mellett lesz. A m´er´esek sor´an a m´erend˝o k´odr´eszletet egy-egy f¨ uggv´enybe ´agyazom ahol a f¨ uggv´eny fut´asi idej´et m´erem. A f¨ uggv´eny, aminek az idej´et m´erem, nem hozhatja l´etre a saj´at adatszerkezeteit, hiszen akkor ez is a m´er´es r´esze lenne. Ehelyett azokat a f¨ uggv´eny futtat´asa el˝ott hozom l´etre. Ebben az esetben azonban ha ugyanazt a f¨ uggv´enyt t¨obbsz¨or futtatom ´es m´erem az eredm´enyeket, akkor a CPU cacheben maradhattak az el˝oz˝o fut´asb´ol adatok, ez torz´ıtja a m´er´es pontoss´ag´at. Ebb˝ol kifoly´olag minden fut´as el˝ott megh´ıvok egy k´odr´eszletet ami a CPU cache-t ki¨ ur´ıti. Hogy ´eletszer˝ u legyen a m´er´es, ez´ert a programokat mindig u ´gy ford´ıtom le, hogy a ford´ıt´o optimaliz´aci´os lehet˝os´egei be vannak kapcsolva. Ez azonban egy vesz´elyt is mag´aban rejt, m´egpedig azt, hogy a cache u ¨r´ıt´es´et v´egz˝o k´odot a ford´ıt´o kioptimaliz´alja, az nem fut le, hiszen nincs megfigyelhet˝o mell´ekhat´asa a k´odnak a program m˝ uk¨od´es´ere. unsigned f l u s h _ c p u _ c a c h e _ f n () { // Reset the cache with 20 mb data read constexpr const int size = 20*1024*1024; static volatile char * data = new char [ size ]{}; unsigned ret = 0; for ( unsigned i = 0; i < size ; ++ i ) ret += data [ i ]; return ret ; } template <... > void benchmark (...) { // ... static unsigned (* volatile fl us h _c pu _c a ch e ) () = f l u s h _ c p u _ c a c h e _ f n ; // ...
2
}
A cache fel¨ ul´ır´as´ahoz egy 20MB m´eret˝ u adatot olvasok v´egig. Ez a mai CPUk cache m´eret´et n´ezve el´eg kell, hogy legyen, ahhoz, hogy annak jelent˝os r´esze fel¨ ul´ır´odjon. Az´ert, hogy az olvas´ast ne optimaliz´alhassa ki a ford´ıt´o, egy volatile mutat´on kereszt¨ ul olvasom az adatot, ami a C++ szabv´anyban annyit jelent, hogy a ford´ıt´onak arra kell sz´am´ıtania hogy k¨ uls˝o program is m´odos´ıthatja az adott mem´oriater¨ uletet. ´Igy hi´aba van a ford´ıt´onak statikus ismerete a t¨omb elemeir˝ol, nem transzform´alhatja ki az olvas´ast m´as m˝ uvelett´e. Hasonl´oan annak c´elj´ab´ol, hogy a ford´ıt´o a f¨ uggv´eny megh´ıv´as´at ne elimin´alja, az egy volatile f¨ uggv´enymutat´on kereszt¨ ul ker¨ ul megh´ıv´asra. Mivel a ford´ıt´onak felt´eteleznie kell, hogy egy k¨ uls˝o program b´armikor a´t´all´ıthatja a mutat´ot egy olyan f¨ uggv´enyre aminek megfigyelhet˝o mell´ekhat´asa lenne, ez´ert nem elimin´alhatja a h´ıv´ast. A m´er´esn´el az o¨sszes fut´as ut´an a fut´as sorsz´am´ahoz tartoz´o indexel egy t¨ombbe elt´arolom a fut´as idej´et amit nanom´asodpercben m´erek. A m´ert f¨ uggv´enynek tetsz˝oleges sz´am´ u param´etere lehet, amit a m´er˝o f¨ uggv´eny tov´abb´ıt neki perfect forwarding-ot haszn´alva. Ez C++-ban a lehet˝o leghat´ekonyabb param´etertov´abb´ıt´as, ´ıgy a m´er´es idej´eben minim´alis torz´ıt´ast jelent a param´eter´atad´as ideje. A m´er´esek megism´etl´es´enek a sz´ama az bemeneti param´etere a m´er˝o f¨ uggv´enynek. template < typename Func , typename ... Args > B en ch ma r kR es ul t benchmark ( unsigned sample_num , Func f , Args &&... args ) { // ... for ( unsigned i = 0; i < sample_num ; ++ i ) { f lu sh _c p u_ ca ch e () ; auto start = chrono :: steady_clock :: now () ; f ( forward < Args >( args ) ...) ; times [ i ] = chrono :: duration_cast < chrono :: nanoseconds >( chrono :: steady_clock :: now () - start ) . count () ; } // ... }
A m´er´esek lefut´asa ut´an a fut´asi id˝oket tartalmaz´o t¨ombben l´ev˝o adatokb´ol a f¨ uggv´eny kisz´amolja a fut´asi id˝ok ´atlag´at (tapasztalati v´arhat´o ´ert´eket), valamint a korrig´alt tapasztalati sz´or´as´at. A sz´or´as alapj´an eld¨ont¨om, hogy az adott m´ert ´ert´eket elfogadom-e, vagy a mintasz´amot valamint a m´ert f¨ uggv´eny bemenet´enek a m´eret´et a´ll´ıtva megism´etlem-e a m´er´est. std :: cout << benchmark (100 , row_major ) << std :: endl ;
A m´er´est v´egz˝o f¨ uggv´eny haszn´alata kifejezetten egyszer˝ u ´es k´enyelmes, minden fejezetben az ismertetett k´odokhoz tartoz´o m´er´est hasonl´o m´odszerekkel v´egeztem uli f¨ uggv´eny fut´asi ideje lesz el. A fenti p´eld´aban egy row major param´eter n´elk¨ m´erve 100 alkalommal, majd az eredm´enyt ki´ırja a szabv´anyos kimenetre.
3. Mem´ oria bej´ ar´ asi mint´ ak Az els˝o p´eld´aban egy eg´eszeket tartalmaz´o m´atrixban sz´amolom meg a p´aratlan sz´amokat. Egy m´atrix bej´ar´as´ara sz´amtalan lehet˝os´eg van, de a leggyakrabban sorfolytonos illetve oszlopfolytonos bej´ar´ast szok´as alkalmazni, mivel ezeket a legegy3
szer˝ ubb implement´alni ´es gyakran nincs kik¨ot´es az elemek megl´atogat´as´anak a sorrendj´ere. Ezzel a k´et bej´ar´assal val´os´ıtottam meg a sz´aml´al´ast, a m´atrixot pedig egyetlen sorfolytonos vektork´ent t´aroltam el. std :: vector < int > matrix ( m_size * m_size ) ; int t ra ve rs e _m at r ix ( Traversal t ) { int ret = 0; if ( t == RowMajor ) { for ( int i = 0; i < m_size ; ++ i ) for ( int j = 0; j < m_size ; ++ j ) ret += matrix [ m_size * i + j ] % 2; } else { for ( int i = 0; i < m_size ; ++ i ) for ( int j = 0; j < m_size ; ++ j ) ret += matrix [ m_size * j + i ] % 2; } return ret ; }
A fenti k´odon futtatott m´er´esi eredm´enyem a 1 grafikonon l´athat´o. ·108 Sorfolytonos Oszlopfolytonos
Fut´asi id˝o (ns)
1 0.8 0.6 0.4 0.2 0
102 103 104 Input m´eret (sor/oszlop sz´am) 1. ´abra. P´aratlan elemek sz´aml´al´asa m´atrixban A grafikonb´ol j´ol l´atszik, hogy a sorfolytonos bej´ar´as k¨ozel k´etszer olyan gyors mint az oszlopfolytonos. Nem t¨ort´ent v´altoztat´as az algoritmusban, csup´an a mem´ori´aban az adatok el´er´esi sorrendje v´altozott. Abban az esetben, ha a m´atrixot nem csak olvasn´ank, hanem ´ırn´ank is, akkor m´eg drasztikusabb k¨ ul¨onbs´egek jelenn´enek meg, a m´er´eseim sor´an ak´ar k¨ozel h´aromszoros k¨ ul¨onbs´eget is tapasztaltam. Klasszikus m´odszerekkel sz´amolva a k´et algoritmus fut´asi ideje az egyszer˝ u cache f¨ uggetlen modellben azonos lenne. Sorfolytonos esetben a mem´oria el´er´ese is sorfolytonosan t¨ort´enik, ez´ert a CPU prefetchere (el˝ot¨olt˝oje) sz´epen sorban bet¨olti a cache-be azokat a mem´oriac´ımeket amikre el˝orel´athat´olag sz¨ uks´eg lesz. Mivel a prefetcher m˝ uk¨od´ese nagyon egyszer˝ u, ez´ert a bonyolultabb mint´azatokat (p´eld´aul konstans mennyis´eggel val´o l´epeget´est a mem´ori´aban) nem k´epes felismerni. Ez a jelens´eg nem csak m´atrixokn´al l´ep fel. Tegy¨ uk fel, hogy rendelkez¨ unk egy t¨ombbel, ami rekordokat tartalmaz. Abban az esetben ha a rekordok egyik mez˝oj´en akarunk m´odos´ıt´ast v´egezni, akkor a t¨omb¨on val´o v´egigiter´al´as k¨ozben a m´atrix oszlopfolytonos bej´ar´as´ahoz hasonl´o mint´azatban olvassuk illetve m´odos´ıtjuk 4
a mem´ori´at. Ez a programoz´asi minta objektum orient´alt programoz´as eset´en gyakran el˝ofordul. A leghat´ekonyabb szimul´aci´os elj´ar´asokn´al valamint a j´at´ekiparban is gyakori optimaliz´aci´onak sz´am´ıt, amikor a rekordok t¨ombj´eb˝ol t¨omb¨ok rekordj´at csin´alnak. Ebben az esetben ha az egyik attrib´ utumnak megfelel˝o t¨omb¨on akarunk valamilyen transzform´aci´ot elv´egezni, akkor a m´atrix sorfolytonos bej´ar´as´ahoz hasonl´o mint´aban fogjuk olvasni illetve ´ırni a mem´ori´at. // Array of structs struct Point { int x , y , z ; }; Point points [200000]; // Struct of arrays struct Points { int x [200000]; int y [200000]; int z [200000]; }; Points pts ;
Az el˝obbi k´odr´eszlet szeml´elteti a k¨ ul¨onbs´eget a rekordok t¨ombje ´es a t¨omb¨ok rekordja k¨oz¨ott. Ez az optimaliz´aci´os lehet˝os´eg n´epszer˝ u, viszont az emberi gondolkod´ashoz a rekordok t¨ombje k¨ozelebb ´all. Ez´ert akt´ıv kutat´asi ter¨ ulet, hogy hogyan lehet ipari k´odb´azisok eset´en az egyik reprezent´aci´or´ol a m´asikra transzform´alni a k´odot automatiz´alt eszk¨oz¨okkel emberi beavatkoz´as n´elk¨ ul. Sajnos az iparban haszn´alt nyelvek komplexit´asa miatt ez nem egy egyszer˝ u feladat.
4. Folytonos ´ es cs´ ucs alap´ u adatszerkezetek A C++-ban k´et gyakran haszn´alat adatszerkezet a list ´es a vector. Az el˝obbi az egy k´et ir´anyban l´ancolt lista, az ut´obbi pedig egy olyan t¨omb, ami dinamikusan tud n˝oni ´es sz´amon tartja a saj´at m´eret´et. Mind a list´aban mind a vektorban a line´aris keres´es asszimptotikusan ugyan u ´gy kellene, hogy viselkedjen, hiszen O(n) m˝ uveletet v´egz¨ unk v´arhat´oan, ahol n az adatszerkezet hossza. A k¨ovetkez˝o m´er´esben felt¨olt¨ottem egy-egy vektort ´es list´at 1..n eg´esz sz´amokkal, majd v´eletlenszer˝ uen ¨osszekevertem ezeket a sz´amokat. Ezut´an egy v´eletlenszer˝ uen kiv´alasztott sz´amot kerestem line´aris keres´est haszn´alva. A 2 grafikon mutatja a m´er´esi eredm´enyeket. L´athat´o az adatokb´ol, hogy igen jelent˝os a vektorban ´es a list´aban val´o keres´es ideje k¨oz¨ott az elt´er´es, pedig asszimptotikusan megegyezik a k´et m˝ uveletig´eny. Az a jelens´eg oka, hogy m´eg a vektorban a keres´es sorfolytonos mem´oriaolvas´ast jelent, addig a l´ancolt list´aban az elemek a mem´ori´aban v´eletlenszer˝ uen helyezkednek el, ´ıgy nem val´osz´ın˝ u, hogy a k¨ovetkez˝onek hivatkozott elem a cache-ben tal´alhat´o. A lista jelent˝osen lassabb, mivel a bej´ar´as minden l´ep´ese v´arhat´oan mem´oria olvas´assal fog j´arni, m´eg a vektor eset´eben a k¨ovetkez˝o elem a cache-ben megtal´alhat´o lesz h´ala a prefetch mechanizmusnak. A m´ert adatok alapj´an r´aad´asul az az ember benyom´asa, hogy a list´an a keres´es sokkal rosszabb a line´arisn´al. Tipikusan hasonl´o jelens´eg zajlik le, ha a lista helyett egy tetsz˝oleges m´asik l´ancolt adatszerkezetet tekint¨ unk. Ez´ert teljes´ıtm´enykritikus alkalmaz´asok eset´en sokszor ker¨ ulend˝o az olyan sz´ot´arak, halmazok haszn´alata, amik f´ak seg´ıts´eg´evel
5
·108
Fut´asi id˝o (ns)
3
Vektor Lista
2
1
0 104
105 106 107 108 Input m´eret (hossz)
109
2. ´abra. V´eletlen elem keres´ese vannak implement´alva. A C++ szabv´anynak is az egyik legnagyobb kritik´aja teljes´ıtm´eny szempontj´ab´ol az, hogy a szabv´anyos k¨onyvt´arban l´ev˝o unordered map, ami egy has´ıt´o t´abla implement´aci´o, l´ancolva t´arolja a v¨odr¨okben az elemeket. Sok alkalmaz´as eset´en gyorsabb egy ny´ılt c´ımz´est alkalmaz´o has´ıt´o t´abla. Hasonl´o okokb´ol gyakran hat´ekonyabbak azok az algoritmusok, amik kev´es adat mozgat´ast v´egeznek, teh´at helyben v´egzik a m´odos´ıt´asokat. Ilyen p´eld´aul a quick sort, ami helyben rendez egy t¨omb¨ot. Az´altal, hogy az adatok nem ker¨ ulnek mozgat´asra, kevesebbszer invalid´al´odik a cache. A Fortran gyors nyelv h´ır´eben a´ll, viszont a gyorsas´ag´anak pont az az egyik oka, hogy tipikusan a Fortran programokban sorfolytonos mem´oriater¨ ulettel rendelkez˝o adatszerkezeteket szoktak haszn´alni.
5. Adatszerkezetek az algoritmusok ellen A mai modern processzorok a cache-sel´esen t´ ul sz´amos tr¨ ukk¨ot alkalmaznak a sebess´eg n¨ovel´es´ere. Ilyen p´eld´aul az out of order execution, ami azt jelenti, hogy a processzor a pipeline-ban l´ev˝o utas´ıt´asok sorrendj´et megv´altoztathatja, ha ez nem okoz v´altoz´ast a program szemantik´aj´aban. Az a´trendez´es az´ert lehet el˝ony¨os, mert a processzor k¨ ul¨on a´ramk¨or¨oket tartalmazhat a k¨ ul¨onb¨oz˝o utas´ıt´asok elv´egz´es´ere, ´es az utas´ıt´asok feldolgoz´as´anak a sorrendj´et˝ol f¨ ugghet, hogy p´arhuzamosan h´any ilyen k¨ ul¨onb¨oz˝o feladatokat ell´at´o ´aramk¨or tud dolgozni egyszerre. Egy m´asik gyakori m´odszer a vektor utas´ıt´asok haszn´alata. A vektor utas´ıt´asok olyan utas´ıt´asok, amik egy adott m˝ uveletet t¨obb ´ert´eken v´egeznek el egyszerre. K´et sz´am ¨osszead´asa helyett p´eld´aul k´epes lehet a processzor egy vektorutas´ıt´assal n´egy sz´amp´art o¨sszeadni, aminek az eredm´enye n´egy u ´j sz´am lesz. Az ilyen utas´ıt´asok v´egrehajt´as´anak az ideje megegyezik a hagyom´anyos utas´ıt´asok´eval, csup´an ugyanannyi id˝o alatt, a munka t¨obbsz¨or¨os´et k´epes elv´egezni. Ezen fel¨ ul olyan speci´alis utas´ıt´ask´eszletek is megjelentek, mint p´eld´aul az FMA, amivel k´epesek vagyunk k´et sz´amot o¨sszeszorozni, majd egy harmadikat hozz´aadni a szorz´as eredm´eny´ehez, mindezt ugyanannyi id˝o alatt, mint amennyit a szorz´as vett 6
volna ig´enybe. Els˝ore el´eg ezoterikusnak hangozhat ez az utas´ıt´as, ugyanakkor el´eg gyakran el˝ofordul ez a m˝ uvelet, p´eld´aul a skal´aris szorz´asban is. R´eszben a fenti technol´ogi´ak miatt, ma m´ar nem ritka, hogy egy kell˝oen optimaliz´alt k´od eset´eben a teljes´ıtm´enyt m´ar nem a processzor sebess´ege korl´atozza, hanem az, hogy milyen gyorsan tudjuk az algoritmus sz´am´ara az adatokat bet¨olteni a mem´ori´ab´ol. Ebben az esetben algoritmikusan m´ar nincs ´ertelme jav´ıtani a programunkon, a mem´oria el´er´esi mint´azatot kell optimaliz´alni. Ebb˝ol ad´od´oan egy kell˝oen gyors algoritmus eset´en m´ar csak az adatok mem´ori´aban val´o elhelyezked´es´et˝ol f¨ ugg ´ a program teljes´ıtm´enye. Eppen ez´ert, egyre nagyobb figyelmet kapnak az adatszerkezetek, hiszen az nagyban befoly´asolj´ak az adatok elhelyezked´es´et. Chandler Carruth Google alkalmazott egy nagyon ´elvezetes el˝oad´asban foglalja ezt ¨ossze [7].
6. Utas´ıt´ as gyors´ıt´ ot´ ar A ma haszn´alt sz´am´ıt´og´epekben a mem´ori´aban nem csup´an az adatok tal´alhat´oak, amiket a programok feldolgoznak, hanem a programok utas´ıt´asai maguk is. Ezt k¨onny˝ u elfelejteni. A processzor m˝ uk¨od´ese k¨ozben nem csup´an az adatokat, ´ hanem az utas´ıt´asokat is a mem´ori´ab´ol t¨olti be. Eppen ez´ert, hasonl´oan mint az adatokn´al, az utas´ıt´asokn´al is gyors´ıt´ot´araz´asi mechanizmusok m˝ uk¨odnek. Ezek a mechanizmusok sokszor kifinomultabbak, mint az adatok eset´en. P´eld´aul egy f¨ uggv´eny megh´ıv´asakor a processzor m´ar ismeri azt is, hogy a f¨ uggv´enyb˝ol val´o visszat´er´es ut´an hol fog folytat´odni a v´egrehajt´as, ´ıgy a megfelel˝o utas´ıt´asokat be tudja t¨olteni a gyors´ıt´ot´arba el˝ore. Alacsony szint˝ u nyelvek eset´en, mint amilyen a C ´es a C++, a gener´alt k´odban azok a f¨ uggv´enyek lesznek egym´ashoz k¨ozel, amik a forr´ask´odban is k¨ozel voltak. Ez´altal az egym´ast gyakran h´ıv´o f¨ uggv´enyeket egym´ashoz k¨ozel helyezve n¨ovelhetj¨ uk az alkalmaz´as teljes´ıtm´eny´et. Egy egyszer˝ u m´er´est v´egeztem az utas´ıt´asok gyors´ıt´ot´araz´as´aval kapcsolatban. A feladat az volt, hogy sz´amoljuk meg, h´any pr´ım sz´am van egy adott fels˝o korl´atig, k´etszer. Az els˝o esetben le´ırtam egym´as al´a k´etszer ugyanazt a k´odot. A m´asodik esetben viszont egy f¨ uggv´enyt h´ıvtam meg k´etszer. Az eredm´enyek a 3 grafikonon l´athat´oak. Az id˝ot most logaritmikus sk´al´an ´abr´azoltam. A f¨ uggv´enyh´ıv´asos megold´as egy´ertelm˝ uen jobb teljes´ıtm´enyt ny´ ujtott, mint a k´odduplik´al´assal j´ar´o megold´as. Ebben az esetben nem j¨ott ki drasztikus k¨ ul¨onbs´eg, ´es ahogy a bement n˝ott, u ´gy ez a k¨ ul¨onbs´eg ar´anyaiban cs¨okkent. A k¨ ul¨onbs´eg apr´os´ag´anak az egyik oka az, hogy a tesztprogram maga kicsi, ez´ert az o¨sszes utas´ıt´as bef´ert az L2 cache-be. Nagyobb programok eset´en sokkal drasztikusabb k¨ ul¨onbs´egek m´erhet˝oek. Gyakran el˝ofordul ipari alkalmaz´asokban, hogy polimorfikus gy˝ ujtem´enyeket haszn´alnak a programoz´ok. Ez azt jelenti, hogy egy olyan gy˝ ujtem´enyt hoznak l´etre, ami egy adott t´ıpusra mutat´o mutat´okat vagy referenci´akat tartalmaz, de ezek a mutat´ok vagy referenci´ak val´oj´aban az adott t´ıpus alt´ıpusainak a p´eld´anyaira mutatnak. Ilyenkor sokszor virtu´alis f¨ uggv´enyh´ıv´as seg´ıts´eg´evel ker¨ ul megh´ıv´asra a dinamikus t´ıpushoz tartoz´o megfelel˝o m˝ uvelet. Abban az esetben, ha a gy˝ ujtem´enyben a t´ıpusok v´altakozva szerepelnek, minden alkalommal, amikor az egyik elemen megh´ıvunk egy virtu´alis tagf¨ uggv´enyt, az j´o es´ellyel olyan f¨ uggv´enyt fog megh´ıvni, ami jelenleg nincs ´ bent az utas´ıt´as gyors´ıt´ot´arban. Eppen ez´ert egy lehets´eges optimaliz´aci´o az, ha a 7
Fut´asi id˝o (ns)
106
Duplik´alt k´od K´et f¨ uggv´enyh´ıv´as
105 104 103
101
102 103 104 Input m´eret (fels˝o korl´at)
3. ´abra. Pr´ımek sz´amol´asa k´etszer gy˝ ujtem´enyben l´ev˝o elemeket a t´ıpusuk szerint rendezz¨ uk. Ebben az esetben az azonos t´ıpus´ u elemek egym´as mell´e ker¨ ulnek, ´ıgy maxim´alisan kihaszn´alj´ak a processzor a´ltal v´egzett gyors´ıt´ot´araz´ast. A [6] cikkben olvashat´o, hogy a Microsoft fejleszt˝oi k´epesek voltak a Windows CE oper´aci´os rendszer h´al´ozati teljes´ıtm´eny´et t¨obb mint h´aromszoros´ara n¨ovelni az´altal, hogy az k´odjukat u ´gy ´ırt´ak u ´jra, hogy figyelembe vett´ek az utas´ıt´as gyors´ıt´ot´araz´ast is.
7. Probl´ em´ ak p´ arhuzamos ´ es elosztott rendszerekben P´arhuzamos ´es elosztott rendszerekben m´eg nagyobb jelent˝os´ege van az adatok lokalit´as´anak. Els˝osorban t¨obb processzormaggal rendelkez˝o rendszerekr˝ol fogok besz´elni, mivel manaps´ag ezek a legelterjedtebb konfigur´aci´ok. A processzor L1 gyors´ıt´ot´ara fel van osztva cache line-nak nevezett egys´egekre. Minden alkalommal, amikor a mem´ori´ab´ol valami beolvas´asra ker¨ ul, vagy ki´ır´odik oda, az egy teljes cache line lesz. Vegy¨ uk el˝o u ´jra azt a feladatot, hogy sz´amoljuk meg egy m´atrixban h´any p´aratlan elem tal´alhat´o. Ebben az esetben p´arhuzamos´ıtsuk a megold´ast. Az itt bemutatott p´elda ´es a m´er´esek mind Herb Suttert˝ol sz´armaznak [11]. A k´od (4) egy thread poolt fog haszn´alni. Mindegyik sz´al meg fogja sz´amolni a m´atrix hozz´a tartoz´o r´esz´eben, hogy h´any p´aratlan sz´am tal´alhat´o. Van egy t¨omb, aminek minden eleme az egyik sz´alhoz van rendelve. Elind´ıtjuk az ¨osszes dolgoz´o sz´alat, majd megv´arjuk, hogy mind befejezze a munk´at. A munk´ajuk v´egezt´evel pedig ¨osszeadjuk a t¨ombben tal´alhat´o sz´amokat, ´ıgy megkapva a v´egeredm´enyt. A m´er´es eredm´enye a 5 grafikonon l´athat´o. A teljes´ıtm´eny t¨obb magon sok esetben romlott, ´es 24 processzormag haszn´alat´aval sem ´erhet˝o el m´eg a k´etszeres teljes´ıtm´eny sem. Pedig a probl´ema maga j´ol p´arhuzamos´ıthat´o. Mi az oka? Az, hogy a processzorok egyszerre egy cache line m´eret´evel megegyez˝o szeletet olvasnak ki a mem´ori´ab´ol, vagy ´ırnak be. Ebb˝ol kifoly´olag, b´ar minden sz´al k¨ ul¨on mem´oriater¨ ule-
8
int result [ P ]; for ( int p = 0; p < P ; ++ p ) pool . run ( [& , p ] { result [ p ] = 0; int chunkSize = DIM / P + 1; int myStart = p * chunkSize ; int myEnd = min ( myStart + chunkSize , DIM ) ; for ( int i = myStart ; i < myEnd ; ++ i ) for ( int j = 0; j < DIM ; ++ j ) if ( matrix [ i * DIM + j ] % 2 != 0 ) ++ result [ p ]; } ); pool . join () ; odds = 0; for ( int p = 0; p < P ; ++ p ) odds += result [ p ];
4. ´abra. P´arhuzamos sz´aml´al´as m´atrixon: els˝o v´altozat tre ´ırja a saj´at eredm´eny´et, a processzorok err˝ol nem tudnak. Csak azt l´atj´ak, hogy mindegyik sz´al ugyanazt a cache line-t haszn´alja, ez´ert annak ´erdek´eben, hogy a mem´ori´aban l´ev˝o ´ert´ek konzisztens maradjon minden sz´al sz´am´ara, minden m´odos´ıt´as ut´an szinkroniz´alj´ak az ´ert´eket a processzormagok cache-ei k¨oz¨ott. Ennek az az eredm´enye, hogy az a cache line, amiben a t¨omb tal´alhat´o, folyamatosan m´asolgatva lesz a mem´oria ´es az egyes processzorok gyors´ıt´ot´ara k¨oz¨ott, holott erre nem lenne sz¨ uks´eg. A processzormagok pedig a legt¨obb idej¨ uket azzal t¨oltik, hogy v´arj´ak, hogy a mem´ori´ab´ol megkapj´ak a friss ´ert´ekeket. Ezt a jelens´eget h´ıvj´ak hamis megoszt´asnak (False Sharing). Az el˝oz˝o k´od k¨onnyen kijav´ıthat´o (6) az´altal, hogy minden sz´al k¨ ul¨on sz´am´ara elk¨ ul¨on´ıtett mem´oriater¨ uleten tartja sz´amon a saj´at eredm´enyeit, majd a v´eg´en lesznek ezek ¨osszes´ıtve egy k¨oz¨os mem´oriater¨ uleten. A jav´ıt´asnak h´ala imm´ar line´arisan fog sk´al´az´odni a teljes´ıtm´eny a felhaszn´alt processzormagok f¨ uggv´eny´eben (7). P´arhuzamos rendszerek fejleszt´esekor teh´at k¨ ul¨on¨osen nagy figyelmet kell ford´ıtanunk az adatok lokalit´as´ara, ugyanis ez lehet a kulcsa a sk´al´azhat´os´agnak. Sajnos sok esetben a fejleszt˝oknek m´aig sz¨ uks´eg¨ uk van alacsony szint˝ u ismeretekre a azokr´ol az eszk¨oz¨okr˝ol, amikre fejlesztenek.
9
5. ´abra. False Sharing
int result [ P ]; for ( int p = 0; p < P ; ++ p ) pool . run ( [& , p ] { int count = 0; int chunkSize = DIM / P + 1; int myStart = p * chunkSize ; int myEnd = min ( myStart + chunkSize , DIM ) ; for ( int i = myStart ; i < myEnd ; ++ i ) for ( int j = 0; j < DIM ; ++ j ) if ( matrix [ i * DIM + j ] % 2 != 0 ) ++ count ; result [ p ] = count ; } );
6. ´abra. P´arhuzamos sz´aml´al´as m´atrixon: jav´ıtott v´altozat
10
7. ´abra. False Sharing megoldva
11
¨ 8. Osszefoglal´ as Az essz´eben bemutattam a modern informatika sz´amos v´ıvm´any´at, amivel egyre jobb teljes´ıtm´enyt ´ernek el az alkalmaz´asok, ´es amit felhaszn´alva egyre hat´ekonyabb ¨ k´odot tudnak gener´alni a ford´ıt´o programok. Osszegy˝ ujt¨ottem n´eh´any optimaliz´aci´os technik´at ´es vez´erelvet, amik t´ampontot adhatnak, mikor teljes´ıtm´eny kri´ tikus alkalmaz´ast fejleszt¨ unk. Altal´ anoss´agban v´eve ma m´ar nem igaz az, hogy egy k´odr´eszlet assembly k´odj´at vizsg´alva meg lehet a´llap´ıtani, hogy mennyire gyors. Az u ´j utas´ıt´ask´eszletek miatt, sz´amos esetben a hosszabb assembly k´od lesz a gyorsabb. Az informatika egy dinamikusan v´altoz´o ´es fejl˝od˝o ter¨ ulet, ezt t¨ urk¨ozi az is, ha valaki m´as ford´ıt´oval, m´as oper´aci´os rendszeren vagy m´asik processzor architekt´ ur´an ism´etli meg az ´altalam v´egzett m´er´eseket, ak´ar l´enyegesen elt´er˝o eredm´enyt is kaphat. Ebb˝ol kifoly´olag nem dolgoztak ki az asszimptotikus anal´ızishez hasonl´o m´odszertant az algoritmusok hat´ekonys´ag´anak a vizsg´alat´ara a modern architekt´ ur´akon. Mivel a v´altoz´as nem lassul, ez´ert hasonl´o m´odszertanra megjelen´es´ere a k¨ozelj¨ov˝oben sem sz´am´ıtok. A legt¨obb szakember egyed¨ ul azt a tan´acsot tudja adni, hogy min´el t¨obb m´er´est v´egezz¨ unk az adott programon, ´es ezt min´el t¨obb k¨ornyezetben ism´etelj¨ uk meg. Gyakran kaphatunk az els˝o intu´ıci´onknak ellent mond´o eredm´enyt. Az alacsony szint˝ u optimaliz´aci´o c´elja nem csup´an a hat´ekonys´ag lehet. A mai processzorok u ´gy takar´ıtanak meg energi´at, hogy amikor nincs sok munk´ajuk, ´ k´epesek korl´atozni az o´rajel¨ uket, vagy ak´ar magokat teljesen lekapcsolni. Eppen ez´ert az ´aramfogyaszt´as visszaszor´ıt´as´ara is az optimaliz´aci´o jelenleg az egyetlen eszk¨oz¨ unk. Ez f˝oleg nagy szerverparkok ´es mobilalkalmaz´asok eset´en l´enyeges. Az el˝obbi esetben a k¨olts´egek jelent˝os r´esz´et m´ar nem a fejleszt˝ok b´ere hanem a szerverfarm ´aramell´at´asa jelenti, a m´asik esetben pedig a felhaszn´al´oi ´elm´eny drasztikus roml´as´ahoz vezet, ha egy alkalmaz´as hamar lemer´ıti a k´esz¨ ul´eket. Emellett a hat´ekony alkalmaz´asokat, a megsp´orolt energi´ab´ol ad´od´oan k¨ornyezetbar´at alkalmaz´asoknak is tekinthetj¨ uk.
Hivatkoz´ asok [1] Lattner, C.: LLVM and Clang: Next Generation Compiler Technology, The BSD Conference, 2008. [2] Stroustrup, B.: The C++ Programming Language Addison-Wesley Publishing Company, fourth edition, 2013. [3] Norvig, P.: Latency numbers every programmer should know http://norvig.com/21-days.html#answers [4] Poletto, M., Sarkar, V.: Linear Scan Register Allocation [5] Intel i7-2630QM specification: http://ark.intel.com/products/52219/ Intel-Core-i7-2630QM-Processor-6M-Cache-up-to-2_90-GHz [6] Importance of the Instruction Cache http://1-800-magic.blogspot.hu/2007/12/ memory-is-not-free-more-on-vista.html 12
[7] Carruth, C.: Efficiency with Algorithms, Performance with Data Structures, https://www.youtube.com/watch?v=fHNmRkzxHWs [8] Is Parallel Programming Hard, And, If So, What Can You Do About It?, https://www.kernel.org/pub/linux/kernel/people/paulmck/ perfbook/perfbook.html [9] Drepper, U.: What every programmer should know about memory, http://www.akkadia.org/drepper/cpumemory.pdf [10] Meyers, S.: CPU Caches and Why You Care, http://www.aristeia.com/TalkNotes/PDXCodeCamp2010.pdf [11] Sutter, H.: Eliminate False sharing http://www.drdobbs.com/parallel/eliminate-false-sharing/217500206
13
