cache hit rate

[Verwijderd]

Ik heb een vraag over een opdracht die in mijn reader staat. hierbij staat ook het antwoord maar met het antwoor snap ik er eigenlijk nog niks van. Zou iemand wat extra uitleg kunnen geven.

dit is de vraag:
Given a MIPS processor with an 8 kbyte level-1 direct-mapped date cache. On this processor the following code is running:

sum = 0;
for (i=0; i<4; i++)
sum = sum + A[i] + A[i+2];

'A' is an array of (32-bit) integers, word aligned in memory. All other variables used in this program are located in registers.
What is the data cache hit-rate for this program, assuming that the cache has a) 1-word (32-bit) blocks, or b) 2-word, or c) 4-word blocks?

antwoord:
There are no capacity problems or conflict problems.
The access pattern for A is: 0, 2, 1, 3, 2, 4, 3, 5
The hit (H) and miss (M) patterns are indicated below.
a. 1-word block: M M M M H M H M -> 2/8 * 100 = 25 % hit-rate
b. 2-word block: M M H H H M H H -> 5/8 * 100 = 62.5 %
c. 4-word block: M H H H H M H H -> 6/8 * 100 = 75 %

maar hoe komen ze aan die acces pattern en wanneer is het een hit en een mis?

alvast bedankt

Groetjes Gijsbert

[Verwijderd]

iemand die me kan helpen?

[Barryvdh]

Heb je geen docent die uitleg geeft over de stof?

[Donderpoes]

Ik zou even uitzoeken wat een access pattern is en de code op papier even uitvoeren. Dus alle waardes voor onderstaande invullen.

code:

 for (i=0; i<4; i++)
sum = sum + A[i] + A[i+2];

Dan krijg je al wat antwoorden.

[ Voor 10% gewijzigd door Donderpoes op 28-10-2014 16:41 ]

[Creepy]

Wat snap je er niet aan? Want als dit in je reader staat, dan staat er hopelijk ook in uitgelegd wat een cache is, en hoe deze werkt. En anders idd aan je docent vragen, zoals Barryvdh voorstelt.

[Thralas]

Verwijderd schreef op dinsdag 28 oktober 2014 @ 00:53:
maar hoe komen ze aan die acces pattern

Ga eens na welke indices van A worden gelezen als het stukje code wordt uitgevoerd.

en wanneer is het een hit en een mis?

Dat lijkt me elementaire terminologie bij het onderwerp caches. Staat in je reader. Of op de slide na de generieke beschrijving van een cache

De hit/miss ratio is ook verklaarbaar; hoewel deze theorie alweer even geleden voor me is, lijkt het me makkelijk afleidbaar. Bij een cache miss van een single word cached hij ook de adjacent words: een block.

Het is me alleen niet duidelijk of een access pattern van '2 1' 'M H' of 'M M' op zou leveren (bij multi-word cache blocks). Volgens mij is dat hier niet gedefinieerd, maar ik gok dat het in de praktijk 'M H' is.

EDIT: @hieronder: scherp mbt. access pattern!

[ Voor 3% gewijzigd door Thralas op 30-10-2014 14:03 ]

[MSalters]

Sowieso is de claim dat het access pattern bekend is onjuist. Een equivalente mogelijkheid is 2,0,3,1,4,2,5,3. Je weet niet in welke volgorde A[i] en A[i+2] worden geëvalueerd.

@Thralas: Multi-word cache lines zijn altijd aligned op cache line size. A is dat echter niet (hier simpelweg word-aligned). Dat is het volgende probleem met deze vraag. Als de cache line 4 words is, dan worden er bij de eerste access 4 words gelezen rondom A[0] of A[2], maar dat zou dus ook A[-3] kunnen zijn. En in het geval dat A[2] eerst gelezen wordt, weet je bij een 4-word cache line size dus niet of A[0] ook gelezen wordt. Het is voorstelbaar dat de eerste cache line dan A[2]-A[5] bevat.