Hierarkiskt minneRedigera

Hierarkiskt minne är en hårdvaruoptimering som utnyttjar fördelarna med rumslig och tidslig lokalitet och kan användas på flera nivåer i minneshierarkin. Paging drar självklart nytta av temporal och spatial lokalitet. En cache är ett enkelt exempel på utnyttjande av temporal lokalitet, eftersom det är ett speciellt utformat, snabbare men mindre minnesområde, som i allmänhet används för att bevara nyligen refererade data och data i närheten av nyligen refererade data, vilket kan leda till potentiella prestandaförstärkningar.

Dataelement i en cache motsvarar inte nödvändigtvis dataelement som ligger rumsligt nära varandra i huvudminnet; dataelement förs dock in i cacheminnet en cache-linje i taget. Detta innebär att den rumsliga lokaliseringen återigen är viktig: om ett element refereras kommer några angränsande element också att föras in i cacheminnet. Slutligen spelar tidsmässig lokalitet en roll på den lägsta nivån, eftersom resultat som refereras mycket nära varandra kan hållas i maskinregistren. Vissa programmeringsspråk (t.ex. C) gör det möjligt för programmeraren att föreslå att vissa variabler ska förvaras i register.

Datalokalitet är en typisk minnesreferensfunktion i vanliga program (även om det finns många oregelbundna minnesåtkomstmönster). Den gör den hierarkiska minneslayouten lönsam. I datorer delas minnet in i en hierarki för att påskynda dataåtkomsten. De lägre nivåerna i minneshierarkin tenderar att vara långsammare, men större. Ett program uppnår alltså bättre prestanda om det använder minnet medan det är cachat i de övre nivåerna av minneshierarkin och undviker att föra in andra data i de övre nivåerna av hierarkin som kommer att tränga undan data som kommer att användas inom kort i framtiden. Detta är ett ideal och kan ibland inte uppnås.

Typisk minneshierarki (åtkomsttider och cachestorlekar är approximationer av typiska värden som används från och med 2013 i diskussionssyfte; de faktiska värdena och det faktiska antalet nivåer i hierarkin varierar):

• CPU-register (8-256 register) – omedelbar åtkomst, med hastigheten hos processorns innersta kärna
• L1 CPU-caches (32 KiB till 512 KiB) – snabb åtkomst, med hastigheten hos den innersta minnesbuss som uteslutande ägs av varje kärna
• L2 CPU-caches (128 KiB till 24 MiB) – något långsammare åtkomst, med hastigheten på minnesbussen som delas mellan tvillingar av kärnor
• L3 CPU caches (2 MiB till 32 MiB) – ännu långsammare åtkomst, med hastigheten på minnesbussen som delas mellan ännu fler kärnor i samma processor
• Fysiskt huvudminne (RAM) (256 MiB till 64 GiB) – långsam åtkomst, hastigheten begränsas av de rumsliga avstånden och de allmänna maskinvarugränssnitten mellan processorn och minnesmodulerna på moderkortet
• Disk (virtuellt minne, filsystem) (1 GiB till 256 TiB) – mycket långsam, på grund av den smalare (i bitbredd), fysiskt mycket längre datakanalen mellan datorns huvudkort och diskenheterna, och på grund av det extra mjukvaruprotokoll som behövs ovanpå det långsamma hårdvarugränssnittet
• Fjärrminne (andra datorer eller molnet) (praktiskt taget obegränsat) – hastigheten varierar från mycket långsam till extremt långsam

Moderna maskiner tenderar att läsa in block av lägre minnen till nästa nivå i minneshierarkin. Om detta förskjuter använt minne försöker operativsystemet förutse vilka data som kommer att nås minst (eller senast) och flytta dem nedåt i minneshierarkin. Förutsägelsealgoritmer tenderar att vara enkla för att minska hårdvarukomplexiteten, även om de håller på att bli något mer komplicerade.

MatrismultiplikationRedigera

Ett vanligt exempel är matrismultiplikation:

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

Genom att byta loopordning för j och k blir hastighetsökningen i stora matrismultiplikationer dramatisk, åtminstone för språk som lägger sammanhängande matriselement i den sista dimensionen. Detta ändrar inte det matematiska resultatet, men det förbättrar effektiviteten. I det här fallet betyder ”stor” ungefär mer än 100 000 element i varje matris, eller tillräckligt med adresserbart minne så att matriserna inte får plats i L1- och L2-cacher.

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

Anledningen till den här hastighetsökningen är att i det första fallet finns läsningen av A i cacheminnet (eftersom k-indexet är den sammanhängande, sista dimensionen), men B är inte det, så det finns en cachemissstraff på B. C är irrelevant, eftersom den kan lyftas ut ur den inre slingan – slingvariabeln där är k.

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

I det andra fallet finns både läsningar och skrivningar av C i cacheminnet, läsningarna av B finns i cacheminnet och läsningen av A kan lyftas ut ur den inre slingan.

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

Det andra exemplet har alltså ingen cachemissstraff i den inre slingan medan det första exemplet har ett cachemissstraff.

På en processor från år 2014 är det andra fallet ungefär fem gånger snabbare än det första fallet, när det är skrivet i C och kompilerat med gcc -O3. (En noggrann undersökning av den demonterade koden visar att GCC i det första fallet använder SIMD-instruktioner och i det andra fallet inte, men cache-straffet är mycket värre än SIMD-vinsten.)

Temporal lokalitet kan också förbättras i exemplet ovan genom att använda en teknik som kallas blockering. Den större matrisen kan delas upp i jämnstora delmatriser, så att de mindre blocken kan refereras (multipliceras) flera gånger medan de befinner sig i minnet.

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;

Den tidsmässiga lokaliteten i lösningen ovan ges eftersom ett block kan användas flera gånger innan det flyttas vidare, så att det flyttas in och ut ur minnet mindre ofta. Den rumsliga lokaliteten förbättras eftersom element med på varandra följande minnesadresser tenderar att dras uppåt i minneshierarkin tillsammans.