Hierarchical memoryEdit

A hierarchikus memória egy olyan hardveroptimalizálás, amely kihasználja a térbeli és időbeli lokalitás előnyeit, és a memóriahierarchia több szintjén is alkalmazható. A lapozás nyilvánvalóan kihasználja az időbeli és térbeli lokalitás előnyeit. A gyorsítótár az időbeli lokalitás kihasználásának egyszerű példája, mivel ez egy speciálisan kialakított, gyorsabb, de kisebb memóriaterület, amelyet általában a nemrég hivatkozott adatok és a nemrég hivatkozott adatok közelében lévő adatok tárolására használnak, ami potenciális teljesítménynövekedéshez vezethet.

A gyorsítótárban lévő adatelemek nem feltétlenül felelnek meg a főmemóriában térben közel lévő adatelemeknek, azonban az adatelemek egy-egy gyorsítótár soronként kerülnek a gyorsítótárba. Ez azt jelenti, hogy a térbeli lokalitás ismét fontos: ha egy elemre hivatkozunk, akkor néhány szomszédos elem is bekerül a gyorsítótárba. Végül az időbeli lokalitás a legalsó szinten játszik szerepet, mivel a nagyon közel egymáshoz hivatkozott eredmények a gépi regiszterekben tarthatók. Egyes programozási nyelvek (például a C) lehetővé teszik a programozó számára, hogy bizonyos változók regiszterekben tartását javasolja.

Az adatlokalitás a szabályos programok tipikus memóriahivatkozási jellemzője (bár sok szabálytalan memóriaelérési minta létezik). Ez teszi kifizetődővé a hierarchikus memóriaelrendezést. A számítógépekben a memóriát hierarchikusan osztják fel az adatelérések gyorsítása érdekében. A memóriahierarchia alsó szintjei általában lassabbak, de nagyobbak. Így egy program akkor ér el nagyobb teljesítményt, ha a memóriahierarchia felsőbb szintjein tárolt memóriát használ, és elkerüli, hogy a hierarchia felsőbb szintjeire más adatokat hozzon, amelyek a későbbiekben rövidesen használt adatokat kiszorítanák. Ez egy ideál, és néha nem érhető el.

Típusos memóriahierarchia (a hozzáférési idők és a gyorsítótárméretek a 2013-as állapot szerinti, a vita céljából használt tipikus értékek közelítő adatai; a tényleges értékek és a hierarchia tényleges szintjeinek száma változó):

• CPU regiszterek (8-256 regiszter) – azonnali hozzáférés, a processzor legbelső magjának sebességével
• L1 CPU gyorsítótárak (32 KiB és 512 KiB között) – gyors hozzáférés, az egyes magok kizárólagos tulajdonában lévő legbelső memóriabusz sebességével
• L2 CPU gyorsítótárak (128 KiB és 24 MiB között) – valamivel lassabb hozzáférés, a memóriabusz sebességét a magok ikrei között megosztva
• L3 CPU gyorsítótárak (2 MiB-től 32 MiB-ig) – még lassabb hozzáférés, a memóriabusz sebességét ugyanazon processzor még több magja között megosztva
• fizikai főmemória (RAM) (256 MiB-től 64 GiB-ig) – lassú hozzáférés, amelynek sebességét a processzor és az alaplapon lévő memóriamodulok közötti térbeli távolságok és általános hardveres interfészek korlátozzák
• Diszk (virtuális memória, fájlrendszer) (1 GiB-től 256 TiB-ig) – nagyon lassú, a számítógép alaplapja és a lemezeszközök közötti szűkebb (bitszélességben), fizikailag sokkal hosszabb adatcsatorna miatt, és a lassú hardveres interfész tetején szükséges idegen szoftveres protokoll miatt
• Távoli memória (más számítógépek vagy a felhő) (gyakorlatilag korlátlan) – a sebesség a nagyon lassútól a rendkívül lassúig változik

A modern gépek hajlamosak arra, hogy a memóriahierarchia következő szintjére olvassák be az alacsonyabb memóriából származó blokkokat. Ha ez kiszorítja a használt memóriát, az operációs rendszer megpróbálja megjósolni, hogy melyik adathoz férnek hozzá a legkevésbé (vagy legkésőbb), és azt a memóriahierarchiában lejjebb helyezi. A predikciós algoritmusok általában egyszerűek, hogy csökkentsék a hardver bonyolultságát, bár egyre bonyolultabbak.

MátrixszorzásSzerkesztés

Egy gyakori példa a mátrixszorzás:

for i in 0..n for j in 0..m for k in 0..p C = C + A * B;

Az j és k ciklusok sorrendjének megváltoztatásával a nagy mátrixszorzásoknál drámai sebességnövekedés érhető el, legalábbis olyan nyelvek esetében, amelyek az utolsó dimenzióba egybefüggő tömbelemeket tesznek. Ez nem változtatja meg a matematikai eredményt, de javítja a hatékonyságot. Ebben az esetben a “nagy” nagyjából azt jelenti, hogy minden mátrixban több mint 100 000 elem van, vagy annyi címezhető memória, hogy a mátrixok nem férnek be az L1 és L2 gyorsítótárakba.

for i in 0..n for k in 0..p for j in 0..m C = C + A * B;

A gyorsulás oka, hogy az első esetben a A olvasása a gyorsítótárban van (mivel a k indexe az összefüggő, utolsó dimenzió), de a B nem, így a B-ra cache miss büntetést kap. A C irreleváns, mert ki lehet emelni a belső ciklusból — a ciklusváltozó ott k.

for i in 0..n for j in 0..m temp = C for k in 0..p temp = temp + A * B; C = temp

A második esetben a C olvasása és írása egyaránt a gyorsítótárban van, a B olvasása a gyorsítótárban van, és a A olvasása ki lehet emelni a belső ciklusból.

for i in 0..n for k in 0..p temp = A for j in 0..m C = C + temp * B;

Így a második példában nincs cache-kihagyási büntetés a belső ciklusban, míg az első példában van.

Egy 2014-es évjáratú processzoron a második eset körülbelül ötször gyorsabb, mint az első eset, ha C nyelven írjuk és gcc -O3-mal fordítjuk. (A szétszedett kód alapos vizsgálata azt mutatja, hogy az első esetben a GCC SIMD utasításokat használ, a második esetben pedig nem, de a gyorsítótár-büntetés sokkal rosszabb, mint a SIMD-nyereség.)

A fenti példában a blokkolásnak nevezett technikával is javítható az időbeli lokalitás. A nagyobb mátrixot egyenletes méretű részmátrixokra lehet osztani, így a kisebb blokkokra többször lehet hivatkozni (szorozni), amíg a memóriában vannak.

for (ii = 0; ii < SIZE; ii += BLOCK_SIZE) for (kk = 0; kk < SIZE; kk += BLOCK_SIZE) for (jj = 0; jj < SIZE; jj += BLOCK_SIZE) maxi = min(ii + BLOCK_SIZE, SIZE); for (i = ii; i < maxi; i++) maxk = min(kk + BLOCK_SIZE, SIZE); for (k = kk; k < maxk; k++) maxj = min(jj + BLOCK_SIZE, SIZE); for (j = jj; j < maxj; j++) C = C + A * B;

A fenti megoldás időbeli lokalitását az biztosítja, hogy egy blokk többször is felhasználható, mielőtt továbblépne, így ritkábban kerül ki-be a memóriából. A térbeli lokalitás javul, mert az egymást követő memóriacímekkel rendelkező elemek általában együtt húzódnak felfelé a memóriahierarchiában.