Nederlands
Menu

Direct-mapped, set-associative en fully associative: cachearchitecturen vergeleken

Een cache moet bepalen waar elk geheugenblok mag staan. Bij een direct-mapped cache kan elk blok maar op één regel staan, wat eenvoudig en snel is, maar conflicten geeft als twee blokken om dezelfde regel strijden. Bij een fully associative cache kan een blok overal staan en zijn er geen conflicten, maar moet met alle regels worden vergeleken. Set-associative is het compromis: een blok mag in een van de enkele ways van één set staan. De caches van de meeste CPU's zijn set-associative.

KenmerkDirect-mappedSet-associativeFully associative
Waar een blok kan staanEén regel, bepaald door de indexbitsEen van de ways (bijvoorbeeld 4 of 8) in één setElke regel in de cache
Tagvergelijkingen per toegangEénEén per way (bijvoorbeeld 8)Alle regels parallel
HittijdHet snelstIets langzamerHet langzaamst
Hardwarekosten en vermogenHet laagstGemiddeldHet hoogst. Elke regel heeft een comparator nodig
ConflictmissesHet meestNemen af naarmate het aantal ways toeneemtGeen. Alleen compulsory misses en capaciteitsmisses blijven over
VervangingsbeleidNiet nodig. Er is maar één keuzeKiezen binnen de set (LRU of een benadering ervan)Kiezen uit alle regels
Belangrijkste toepassingenKleine, eenvoudige caches, sommige microcontrollersL1-, L2- en L3-caches van de meeste CPU's. Vaak 4 tot 16 waysKleine structuren zoals TLB's en victim caches

De getalswaarden zijn typische ordegroottes en variëren per procesgeneratie en product.

Wanneer welke variant?

Direct-mapped
Wanneer eenvoud, laag vermogen en snelheid belangrijker zijn dan de hitratio.
Set-associative
De realistische keuze voor de meeste caches. Enkele ways nemen het grootste deel van de conflictmisses weg tegen lage kosten.
Fully associative
Bij zeer kleine structuren waar de hitratio telt en de kosten van de vergelijkingen te dragen zijn.

Veelgestelde vragen

Wat is een conflictmiss?

Een miss die ontstaat doordat twee blokken op dezelfde plek worden afgebeeld, terwijl er in de cache nog andere vrije regels zijn. Komt het vaakst voor bij direct-mapped en niet bij fully associative.

Hoeveel tags vergelijkt een 8-way-cache per toegang?

Eén per way van de gekozen set, dus acht.

Waarom zijn de caches van de meeste CPU's set-associative?

Enkele ways nemen het grootste deel van de conflictmisses weg tegen lage kosten, terwijl fully associative een comparator per regel nodig heeft.

Waar wordt fully associative gebruikt?

In kleine structuren zoals TLB's en victim caches, waar de hitratio het belangrijkst is en de kosten van de vergelijkingen te dragen zijn.

Test uw begrip

Hoeveel bits heeft de tag bij een direct-mapped cache met 32-bits adressen, een capaciteit van 32 KB en een regelgrootte van 64 byte?

  1. A15 bits
  2. B19 bits
  3. C17 bits
Antwoord en toelichting tonen

Antwoord: C. 17 bits

Een regelgrootte van 64 byte = 2⁶ betekent een offset van 6 bits. Het aantal regels is 32 KB ÷ 64 B = 32768 ÷ 64 = 512 = 2⁹; bij direct-mapped is het aantal regels gelijk aan het aantal sets, dus de index is 9 bits. De rest vormt de tag: 32 − 9 − 6 = 17 bits. 19 bits is de waarde bij een 4-weg set-associatieve cache, waar de index 2 bits korter is; dat geldt niet voor direct-mapped.

Hoeveel sets heeft een 4-weg set-associatieve cache met 32-bits adressen, een capaciteit van 32 KB en een regelgrootte van 64 byte?

  1. A128
  2. B512
  3. C32
Antwoord en toelichting tonen

Antwoord: A. 128

Het aantal regels is 32 KB ÷ 64 B = 512. Bij 4 wegen passen er 4 regels in één set, dus het aantal sets is 512 ÷ 4 = 128 = 2⁷; de index is dan 7 bits en de tag 32 − 7 − 6 = 19 bits. 512 is het aantal regels zelf en tevens het aantal sets bij direct-mapped. Een hogere associativiteit verlaagt het aantal sets; daardoor neemt het aantal tagbits toe en zijn er meer comparatoren nodig. 32 is het resultaat van de regelgrootte 64 ten onrechte door het aantal wegen te delen.

Hoeveel bits van het adres worden bij een volledig associatieve cache voor de index (het selecteren van de set) gebruikt?

  1. A6 bits, bepaald door de regelgrootte
  2. BEvenveel bits als het aantal regels
  3. C0 bits
Antwoord en toelichting tonen

Antwoord: C. 0 bits

Bij een volledig associatieve cache kan elk gegeven op elke plaats in de cache staan, zodat er in totaal slechts één set is. Omdat er geen set hoeft te worden geselecteerd, is de index 0 bits; het adres bestaat alleen uit offset en tag, en bij elke toegang wordt de tag met die van alle regels vergeleken. Daarom zijn er veel comparatoren nodig, wat ongeschikt is voor grote caches; de opzet wordt gebruikt voor kleine structuren zoals de TLB. De regelgrootte bepaalt het aantal offsetbits, niet de index.

  1. Bij een direct-mapped cache komen elementen van twee arrays op dezelfde cachepositie uit en verdringen elkaar bij elke afwisselende toegang. Tot welke categorie behoort deze miss?
  2. Welke verandering treedt op bij de overstap van direct-mapped naar set-associatief?
  3. Hoeveel tags worden bij een 8-weg set-associatieve cache per toegang parallel vergeleken?

Oefenvragen over Geheugenhiërarchie en prestaties

Belangrijke termen uitgelegd

Direct-mapped cache
Cacheorganisatie waarin voor de data van elk adres precies één plek in de cache is vastgelegd. Eenvoudig circuit en korte hit-tijd, maar conflictmisses doordat adressen om dezelfde plek strijden komen vaak voor.
Set-associatief
Cache-organisatie waarbij gegevens op elke van meerdere plaatsen (ways) binnen één, uit het adres bepaalde set kunnen worden geplaatst. Bij n ways worden bij elke toegang n tags parallel vergeleken.
Fully associative
Cache-opbouw waarin elk gegeven op elke plaats in de cache kan staan. Er zijn geen conflictmissers, maar alle tags moeten worden vergeleken, waardoor het niet geschikt is voor grote caches. Wordt gebruikt in onder meer de TLB.
Cacheregel (cache line)
Eenheid waarin data tussen de cache en het onderliggende niveau worden gelezen en geschreven. Ook cacheblok genoemd. Bij veel CPU's 64 byte, waarbij de laagste adresbits de positie (offset) binnen de regel aangeven.

Verwante vergelijkingen