Hur räkna ut cache träff/miss (assembly)?

Trädvy Permalänk
Medlem
Registrerad
Okt 2015

Hur räkna ut cache träff/miss (assembly)?

Hej, jag har en tenta imorgon och såg att frågor som denna verkar komma på varje tenta. Kan någon förklara vad som händer i varje instruktion och hur man räknar ut nästa steg. Jag förstår när det blir träff och miss men hur kommer man fram till 0xBEDA12D, 0xBEDA12C8, 0xBEDA12D osv? Var kommer dem ifrån?

Fråga: Ett cacheminne har plats för totalt 256 bytes och varje rad är 8 bytes lång. Minnet är direktmappat och en adress är 32 bitar lång. Förutsatt att cacheminnet är tomt från början, bestäm för varje instruktion nedan om det blir en cacheträff eller en cachemiss. Du kan också anta att instruktionerna sker sekventiellt och att data som läggs till i en uppgift finns kvar till nästa.

a.movi r8, 0xBEDA12C4
b.ldw r10, 0(r8)
c.ldw r11, 8(r8)
d.stw r10, 16(r8)
e.ldw r10, 32(r8)
f.ldw r10, 40(r8)
g.ldw r11, 24(r8)
h.stw r10, 4(r8)
i.ldw r10, 64(r8)

Svar: Se bild

Trädvy Permalänk
Datavetare
Plats
Stockholm
Registrerad
Jun 2011

För att förstå denna uppgift måste man förstå några grundläggande koncept i en CPU

  • minne refereras via load/store instruktioner

  • vilken minnescell man refererar bestäms av ett heltal: minnesadressen

  • minsta adresserbara enhet kallas "byte" och är på alla moderna CPUer 8 bitar

Vidare måste man förstå följande om en CPU som har en cache för att snabba upp minnet

  • en cache är organiserad i rader, s.k. "cache-lines", vars storlek typiskt är många bytes. I denna uppgift är en rad 8 bytes, i de flesta moderna CPUer är den 64 bytes (t.ex. dagens x86 och ARM, men finns definitivt variationer här)

  • den enkla CPU som beskrivs här använder sig av en s.k. direktmappad cache, dvs varje rad i cachen kan hantera minnesadresser som är en jämn multipel av cachens storlek i bytes (256 bytes) plus radens nummer (från noll) multiplicerat med radens storlek på 8 bytes

  • en rad håller en minnessekvens från en adress som är en jämn multipel av radlängden upp till radlängd plus radlängd minus ett

Sist men inte minst måste man förstå de assembler-instruktioner som ingår här

  • movi REG,IM laddar ett konstant värde IM och sparar resultatet i CPU-register REG

  • ldw REG_D, OFFSET(REG_A) hämtar innehållet från den minnecell som ligger på adressen REG_A + OFFSET och lägg det i register REG_D

  • stw REG_S, OFFSET(REG_A) sparar innehållet i register REG_Still den minnecell som har adressen REG_A + OFFSET

Läser man assemblerprogrammet får man då

  1. a. här sätts register r8 det konstanta värdet 0xBEDA12C4

  2. b. här laddas minnesinnehållet från 0 + r8 (som är 0xBEDA12C4) och läggs i register r10

  3. c. här laddas minnesinnehållet från 8 + r8 (som är 0xBEDA12CC) och läggs i register r11

  4. d. här sparas innehållet i register r10 till minnesadressen 16 + r8 (som är 0xBEDA12D4)

  5. e. här laddas minnesinnehållet från 32 + r8 (som är 0xBEDA12E4) och läggs i register r10

  6. f. här laddas minnesinnehållet från 40 + r8 (som är 0xBEDA12EC) och läggs i register r10

  7. g. här laddas minnesinnehållet från 24 + r8 (som är 0xBEDA12DC) och läggs i register r11

  8. h. här sparas innehållet i register r10 till minnesadressen 4 + r8 (som är 0xBEDA12C8)

  9. i. här laddas minnesinnehållet från 64 + r8 (som är 0xBEDA1304) och läggs i register r10

Det enda som spelar roll för denna uppgift är vilken adress som man gör load/store till då det avgör vilken cache-rad som påverkas. Är också bara de sista 8 bitarna i adressen man behöver fundera på då det är en direktmappad cache med storlek 256. Så titta bara på de två sista hexsiffrorna i den adress som är resultat av OFFSET + REG_A. Vilken byte i en cache-rad som refereras bestäms av adressens tre minst signifikanta bitar (då 2^3 = 8 vilket är storleken på varje rad) medan nästföljande fem bitar bestämmer vilken rad som avses

  1. är inte en minnesoperation så påverkar inte cache

  2. 0xC4 byte 4 i rad 24

  3. 0xCC byte 4 i rad 25

  4. 0xD4 byte 4 i rad 26

  5. 0xE4 byte 4 i rad 28

  6. 0xEC byte 4 i rad 29

  7. 0xDC byte 4 i rad 27

  8. 0xC8 byte 0 i rad 25

  9. 0x04 byte 4 i rad 0

Då cachen initialt var tom och det är färre minnesaccesser än cache-rader (så inget behövs slängas ut ur cache) så är det nu bara titta på vilken rad som refereras, har den refererats tidigare är det en träff

  1. är inte en minnesoperation så påverkar inte cache

  2. 0xC4 byte 4 i rad 24

  3. 0xCC byte 4 i rad 25

  4. 0xD4 byte 4 i rad 26

  5. 0xE4 byte 4 i rad 28

  6. 0xEC byte 4 i rad 29

  7. 0xDC byte 4 i rad 27

  8. 0xC8 byte 0 i rad 25

  9. 0x04 byte 4 i rad 0

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Trädvy Permalänk
Medlem
Registrerad
Okt 2015

@yoshman
Tack för ditt svar, hann inte läsa det innan tentan. Fick förklarat av en annan student hur man skulle göra igår. Du kanske kan kolla om mitt svar på tentan blev rätt ;)? Om mitt svar är fel så klarade jag nog tyvärr inte tentan.
Jag diskuterade svaret med några andra efteråt och ingen som fått samma som mig.

Fråga: Vi har följande avsnitt ur ett assembler program
1. movia r8, 0x357B40
2. ldw r10, 0 (r8)
3. ldw r11, 16 (r8)
4. ldw r12, 40 (r8)
5. stw r13, 132 (r8)
6. ldw r14, 8 (r8)
Vi har också ett cacheminne med egenskaper enligt tabellen nedan:
Storlek 512 byte
Radlängd 16 byte
Associativitet 2-vägs

För varje instruktion som läser eller skriver till minnet ska du ange om det blir en träff eller miss i cacheminnet.

Svar: 512/16=32 32/2=16 16=2^4 så både byte och rad är 4
1. 0x357B40=[0011 0101 0111 1011] [0100] [0000] tag rad byte

2. 0x357B40=0100 0000 rad 0100 ger MISS 0x357B40-->0x357B4F

3. 0x357B40+16=0x357B50 0101 0000 rad 0101 ger MISS 0x357B50-->0x357B5F

4. 0x357B40+40=0x357B68 0110 1000 rad 0110 ger MISS 0x357B60-->0x357B6F

5. 0x357B40+132=0x357BC4 1100 0100 rad 1100 ger MISS 0x357BC0-->0x357BCF

6. 0x357B40+8=0x357B48 0100 1000 rad+tag ger TRÄFF

Trädvy Permalänk
Medlem
Registrerad
Sep 2016

@R45PB3RRY: kommer du ihåg hur man gör? kan du visa hur man göra denna?
cache minne med dessa egenskaper
Storlek 512 bytes
Radlängd 16 byte
associativitet 2 vägs
adress längd 16 bitar
Följande avsnitt ur ett assembler program:
1. movia r8, 0xBEB4
2. ldw r10, 0(r8)
3. ldw r11, 10(r8)
4. ldw r12, 16(r8)
5. stw r13, 4(r8)
6. ldw r14, 12(r8)
7. stw r15, 8(r8)
Cache minnet är tomt från början och instruktionerna sker sekventiellt
ange för varje instruktion som läser eller skriver till minnet om det blir träff eller miss i cacheminnet