Nederlands
Menu

Geheugenhiërarchie en prestaties

Een tweedimensionale C-array a[i][j] wordt doorlopen met j als binnenste lus. Dit is doorgaans sneller dan met i als binnenste lus. Wat is de reden?

for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
        sum += a[i][j];
  1. AOmdat de array rij-voor-rij is opgeslagen, worden opeenvolgende adressen achtereenvolgens gelezen en worden de cacheregels effectief benut
  2. BOmdat de compiler de optellingen in de lus samenvoegt en verwijdert, zodat de berekening zelf tijdens de uitvoering wordt overgeslagen
  3. COmdat met j als binnenste lus de TLB helemaal niet meer wordt geraadpleegd en vertaling van virtueel naar fysiek adres niet nodig is
Antwoord en toelichting tonen

Antwoord: A. Omdat de array rij-voor-rij is opgeslagen, worden opeenvolgende adressen achtereenvolgens gelezen en worden de cacheregels effectief benut

Tweedimensionale arrays in C worden rij-voor-rij (row-major) opgeslagen, zodat a[i][0], a[i][1], ... in het geheugen naast elkaar liggen. Met j als binnenste lus worden opeenvolgende adressen gelezen, zodat de rest van de cacheregel van 64 byte die bij één miss is binnengehaald direct wordt gebruikt. Met i als binnenste lus worden telkens adressen gelezen die een hele rij uit elkaar liggen; van elke regel wordt dan maar een klein deel benut voordat deze wordt verdrongen. De TLB blijft in gebruik; adresvertaling is niet overbodig geworden.

Dit onderwerp oefenen Naar de onderwerppagina

Meer vragen over Geheugenhiërarchie en prestaties

  1. 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?
  2. Hoeveel sets heeft een 4-weg set-associatieve cache met 32-bits adressen, een capaciteit van 32 KB en een regelgrootte van 64 byte?
  3. Hoeveel bits van het adres worden bij een volledig associatieve cache voor de index (het selecteren van de set) gebruikt?
  4. De hittijd van de L1-cache is 1 ns, de missratio 5%, de hittijd van de L2-cache 10 ns, de lokale missratio van L2 20% en de toegangstijd van het hoofdgeheugen 100 ns. Wat is de gemiddelde geheugentoegangstijd?
  5. 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?

Vergelijkingen bij dit onderwerp