Hierarkisk hukommelseRediger

Hierarkisk hukommelse er en hardwareoptimering, der udnytter fordelene ved rumlig og tidsmæssig lokalitet og kan bruges på flere niveauer i hukommelseshierarkiet. Paging drager naturligvis fordel af tidsmæssig og rumlig lokalitet. En cache er et simpelt eksempel på udnyttelse af tidsmæssig lokalitet, fordi det er et specielt designet, hurtigere, men mindre hukommelsesområde, der generelt bruges til at opbevare data, der for nylig er refereret, og data i nærheden af data, der for nylig er refereret, hvilket kan føre til potentielle ydelsesstigninger.

Dataelementer i en cache svarer ikke nødvendigvis til dataelementer, der ligger rumligt tæt på hinanden i hovedhukommelsen; dataelementer føres dog ind i cachen én cache-linje ad gangen. Det betyder, at den rumlige lokalitet igen er vigtig: hvis der henvises til et element, vil et par naboelementer også blive bragt ind i cachen. Endelig spiller tidsmæssig lokalitet en rolle på det laveste niveau, da resultater, der refereres meget tæt på hinanden, kan gemmes i maskinens registre. Nogle programmeringssprog (f.eks. C) giver programmøren mulighed for at foreslå, at visse variabler skal opbevares i registre.

Datalokalitet er et typisk hukommelsesreferencegrundlag i almindelige programmer (selv om der findes mange uregelmæssige hukommelsesadgangsmønstre). Det gør det hierarkiske hukommelseslayout rentabelt. I computere er hukommelsen opdelt i et hierarki med henblik på at fremskynde dataadgange. De lavere niveauer i hukommelseshierarkiet har tendens til at være langsommere, men større. Et program vil således opnå større ydeevne, hvis det bruger hukommelse, mens den er cachet i de øverste niveauer i hukommelseshierarkiet, og undgår at bringe andre data ind i de øverste niveauer i hierarkiet, som vil fortrænge data, der vil blive brugt kortvarigt i fremtiden. Dette er et ideal, og det kan undertiden ikke opnås.

Typisk hukommelseshierarki (adgangstider og cachestørrelser er tilnærmelser af typiske værdier, der er anvendt fra 2013 til brug for diskussionen; de faktiske værdier og det faktiske antal niveauer i hierarkiet varierer):

• CPU-registre (8-256 registre) – øjeblikkelig adgang, med hastigheden for den inderste kerne i processoren
• L1 CPU-caches (32 KiB til 512 KiB) – hurtig adgang, med hastigheden for den inderste hukommelsesbus, der udelukkende ejes af hver enkelt kerne
• L2 CPU-caches (128 KiB til 24 MiB) – lidt langsommere adgang, med hastigheden af hukommelsesbussen delt mellem to kerner
• L3 CPU-caches (2 MiB til 32 MiB) – endnu langsommere adgang, med hastigheden af hukommelsesbussen delt mellem endnu flere kerner i den samme processor
• Fysisk hovedhukommelse (RAM) (256 MiB til 64 GiB) – langsom adgang, hvis hastighed er begrænset af de rumlige afstande og generelle hardwaresnitflader mellem processoren og hukommelsesmodulerne på bundkortet
• Disk (virtuel hukommelse, filsystem) (1 GiB til 256 TiB) – meget langsom, på grund af den smallere (i bitbredde), fysisk meget længere datakanal mellem computerens hovedkort og diskenhederne, og på grund af den uvedkommende softwareprotokol, der er nødvendig oven på den langsomme hardwareinterface
• Fjernhukommelse (andre computere eller skyen) (praktisk talt ubegrænset) – hastigheden varierer fra meget langsom til ekstremt langsom

Moderne maskiner har en tendens til at læse blokke af lavere hukommelse ind i det næste niveau i hukommelseshierarkiet. Hvis dette fortrænger brugt hukommelse, forsøger operativsystemet at forudsige, hvilke data der vil blive tilgået mindst (eller senest), og flytte dem nedad i hukommelseshierarkiet. Forudsigelsesalgoritmer har tendens til at være enkle for at reducere hardwarekompleksiteten, selv om de er ved at blive noget mere komplicerede.

MatrixmultiplikationRediger

Et almindeligt eksempel er matrixmultiplikation:

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

Ved at skifte løkkerækkefølgen for j og k bliver hastighedsforøgelsen i store matrixmultiplikationer dramatisk, i det mindste for sprog, der sætter sammenhængende arrayelementer i den sidste dimension. Dette ændrer ikke det matematiske resultat, men det forbedrer effektiviteten. I dette tilfælde betyder “stor” omtrent mere end 100.000 elementer i hver matrix eller tilstrækkelig meget adresserbar hukommelse til, at matricerne ikke passer i L1- og L2-cacher.

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

Grunden til denne hastighedsforøgelse er, at i det første tilfælde er læsningerne af A i cache (da k-indekset er den sammenhængende, sidste dimension), men B er ikke, så der er en cache-miss-straffe på B. C er irrelevant, fordi den kan hejses ud af den indre løkke — løkkevariablen der er 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 andet tilfælde er læsningerne og skrivningerne af C begge i cache, læsningerne af B er i cache, og læsningen af A kan hejses ud af den indre løkke.

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

Det andet eksempel har således ingen cache-miss-straffe i den indre løkke, mens det første eksempel har en cache-straffe.

På en processor fra år 2014 er det andet tilfælde ca. fem gange hurtigere end det første tilfælde, når det er skrevet i C og kompileret med gcc -O3. (En omhyggelig undersøgelse af den disassemblerede kode viser, at GCC i det første tilfælde bruger SIMD-instruktioner og i det andet tilfælde ikke gør det, men cache-straffen er meget værre end SIMD-gevinsten.)

Temporal lokalitet kan også forbedres i ovenstående eksempel ved at bruge en teknik kaldet blokering. Den større matrix kan opdeles i undermatricer af jævn størrelse, således at de mindre blokke kan refereres (multipliceres) flere gange, mens de befinder sig i hukommelsen.

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æssige lokalitet i ovenstående løsning er givet, fordi en blok kan bruges flere gange, før den går videre, så den flyttes ind og ud af hukommelsen sjældnere. Den rumlige lokalitet forbedres, fordi elementer med på hinanden følgende hukommelsesadresser har tendens til at blive trukket sammen opad i hukommelseshierarkiet.