Hiërarchisch geheugenEdit

Hiërarchisch geheugen is een hardware-optimalisatie die de voordelen van ruimtelijke en temporele lokaliteit benut en op verschillende niveaus van de geheugenhiërarchie kan worden gebruikt. Paging profiteert uiteraard van temporele en ruimtelijke lokaliteit. Een cache is een eenvoudig voorbeeld van het benutten van temporele lokaliteit, omdat het een speciaal ontworpen, sneller maar kleiner geheugengebied is, dat in het algemeen wordt gebruikt om recent geraadpleegde gegevens en gegevens in de buurt van recent geraadpleegde gegevens te bewaren, wat tot potentiële prestatieverhogingen kan leiden.

Gegevenselementen in een cache komen niet noodzakelijk overeen met gegevenselementen die ruimtelijk dicht bij elkaar in het hoofdgeheugen liggen; gegevenselementen worden echter één cache-regel per keer in de cache gebracht. Dit betekent dat ruimtelijke lokaliteit weer van belang is: als naar één element wordt verwezen, zullen ook enkele aangrenzende elementen in het cachegeheugen worden binnengebracht. Tenslotte speelt temporele lokaliteit een rol op het laagste niveau, omdat resultaten waarnaar zeer dicht bij elkaar wordt verwezen, in de machineregisters kunnen worden bewaard. Sommige programmeertalen (zoals C) staan de programmeur toe voor te stellen dat bepaalde variabelen in registers worden bewaard.

Gegevenslokalisatie is een typisch kenmerk van geheugenverwijzing in gewone programma’s (hoewel er veel onregelmatige geheugentoegangspatronen bestaan). Het maakt de hiërarchische geheugenindeling rendabel. In computers wordt het geheugen in een hiërarchie verdeeld om de toegang tot de gegevens te versnellen. De lagere niveaus van de geheugenhiërarchie zijn meestal langzamer, maar groter. Een programma zal dus beter presteren als het geheugen gebruikt terwijl het in de cache zit in de hogere niveaus van de geheugenhiërarchie en vermijdt andere gegevens in de hogere niveaus van de hiërarchie te brengen die gegevens zullen verdringen die kort in de toekomst zullen worden gebruikt. Dit is een ideaal, dat soms niet kan worden bereikt.

Typische geheugenhiërarchie (toegangstijden en cachegrootten zijn benaderingen van typische waarden die in 2013 zijn gebruikt voor discussiedoeleinden; de werkelijke waarden en het werkelijke aantal niveaus in de hiërarchie variëren):

• CPU-registers (8-256 registers) – onmiddellijke toegang, met de snelheid van de binnenste kern van de processor
• L1 CPU-caches (32 KiB tot 512 KiB) – snelle toegang, met de snelheid van de binnenste geheugenbus die exclusief eigendom is van elke kern
• L2 CPU-caches (128 KiB tot 24 MiB) – iets langzamere toegang, met de snelheid van de geheugenbus gedeeld door een tweetal kernen
• L3 CPU caches (2 MiB tot 32 MiB) – nog tragere toegang, met de snelheid van de geheugenbus gedeeld door nog meer kernen van dezelfde processor
• Main fysiek geheugen (RAM) (256 MiB tot 64 GiB) – trage toegang, waarvan de snelheid wordt beperkt door de ruimtelijke afstanden en de algemene hardware-interfaces tussen de processor en de geheugenmodules op het moederbord
• Schijf (virtueel geheugen, bestandssysteem) (1 GiB tot 256 TiB) – zeer traag, vanwege het smallere (in bitbreedte), fysiek veel langere gegevenskanaal tussen het moederbord van de computer en de schijfapparaten, en door het extra software protocol dat nodig is bovenop de trage hardware interface
• Op afstand geheugen (andere computers of de cloud) (praktisch onbeperkt) – snelheid varieert van zeer traag tot extreem traag

Moderne machines hebben de neiging om blokken van lager geheugen in te lezen in het volgende niveau van de geheugenhiërarchie. Als hierdoor gebruikt geheugen wordt verplaatst, probeert het besturingssysteem te voorspellen welke gegevens het minst (of het laatst) zullen worden benaderd en deze naar beneden in de geheugenhiërarchie te verplaatsen. Voorspellingsalgoritmen zijn meestal eenvoudig om de hardware-complexiteit te verminderen, hoewel ze steeds ingewikkelder worden.

MatrixvermenigvuldigingEdit

Een veelvoorkomend voorbeeld is matrixvermenigvuldiging:

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

Door de looping-volgorde voor j en k om te wisselen, wordt de snelheid van grote matrixvermenigvuldigingen dramatisch, althans voor talen die aaneengesloten array-elementen in de laatste dimensie plaatsen. Dit zal het wiskundige resultaat niet veranderen, maar het verbetert de efficiëntie. In dit geval betekent “groot”, ongeveer, meer dan 100.000 elementen in elke matrix, of genoeg adresseerbaar geheugen zodat de matrices niet in L1 en L2 caches passen.

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

De reden voor deze versnelling is dat in het eerste geval, de lezingen van A in cache zijn (omdat de k index de aaneengesloten, laatste dimensie is), maar B is dat niet, dus is er een cache miss penalty op B. C is irrelevant, omdat het uit de binnenste lus kan worden getakeld — de lusvariabele daar is k.

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

In het tweede geval zijn de reads en writes van C beide in cache, de reads van B zijn in cache, en de read van A kan uit de binnenste lus worden getakeld.

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

Dus, het tweede voorbeeld heeft geen cache miss penalty in de binnenste lus, terwijl het eerste voorbeeld een cache penalty heeft.

Op een processor uit het jaar 2014 is het tweede geval ongeveer vijf keer zo snel als het eerste geval, wanneer geschreven in C en gecompileerd met gcc -O3. (Een zorgvuldig onderzoek van de gedemonteerde code laat zien dat GCC in het eerste geval SIMD-instructies gebruikt en in het tweede geval niet, maar de cache-straf is veel erger dan de SIMD-winst.)

Temporele lokaliteit kan in bovenstaand voorbeeld ook worden verbeterd door een techniek te gebruiken die blokkeren heet. De grotere matrix kan worden verdeeld in submatrices van gelijke grootte, zodat de kleinere blokken meerdere malen in het geheugen kunnen worden gebruikt (vermenigvuldigd).

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;

De temporele lokalisatie van de bovenstaande oplossing wordt verbeterd doordat een blok meerdere malen kan worden gebruikt voordat het verdergaat, zodat het minder vaak in en uit het geheugen wordt verplaatst. De ruimtelijke lokalisatie wordt verbeterd doordat elementen met opeenvolgende geheugenadressen de neiging hebben samen omhoog te worden getrokken in de geheugenhiërarchie.