Loesung2

Musterlösung zum 2. Übungsblatt

4. Aufgabe

Cachespeicher

Der technologische Unterschied zwischen Hauptspeicher und Cache besteht darin, daß Hauptspeicher meist in DRAM realisiert sind und Cache in der teureren aber schnelleren SRAM-Technologie.

Wieviel Bits werden für die Verwaltung der verschiedenen Cachearten gebraucht?

Da jeder Datenblock im Cache 4 Bytes umfaßt, sind die letzten 2 Adreßbits in allen drei Cachearten für die Verwaltung irrelevant. Das erste Byte eines Cacheblocks entspricht immer einer durch vier teilbaren Adresse n, die anderen drei Bytes entsprechen n+1, n+2, n+3.

Direkt mapped Cache DM

Wird der Cache direkt abgebildet, so kann in den ersten Block des Caches nur jeder achte 4-Byte-Block des Speichers abgebildet werden, nämlich genau die Blöcke mit Adressen

xxxx xxxx xxxx xxxx xxxx xxxx xxx0 00xx.

In den zweiten Cacheblock können nur die Blöcke mit Adressen

xxxx xxxx xxxx xxxx xxxx xxxx xxx0 01xx

usw. D.h. für die Verwaltung eines Blocks muß der Cachetag nur die ersten 27 Adreßbits speichern.

|               Tag               |Index|Off|
|                                 |     |set|
|31,30          ...            6,5|4,3,2|1,0|

Vollassoziativer Cache AV:

Beim vollassoziativen Cache kann jeder Block des Speichers auf jeden Block des Caches abgebildet werden. D.h. Der Tag muß alle Adreßbits, bis auf die letzten 2 enthalten.

|               Tag                     |Off|
|                                       |set|
|31,30          ...            6,5,4,3,2|1,0|

2-fach assoziativer Cache A2

Der zweifach assoziative stellt ein Zwischending der beiden ersten dar. Jeder 4-Byte-Block des Speichers kann auf 2 der 8 Cacheblöcke abgebildet werden. Dadurch ist der Tag um ein Bit länger als beim direkt abgebildeten, aber um 2 kürzer als beim vollassoziativen.

|               Tag                 |In-|Off|
|                                   |dex|set|
|31,30          ...            6,5,4|3,2|1,0|

Zusätzlich kommen bei allen drei Cachearten noch die beiden Gültigkeitsbits Valid und Dirty dazu. Damit benötigt DM 29 Bits, A2 30 Bits und AV 31 Bits für die Verwaltung eines Cacheblocks.

Das Beispiel

Achtung: Bei der folgenden Lösung handelt es sich um die "Least-Frequently-Used-Strategie". In der Aufgabenstellung war die "Least-Recently-Used-Strategie" verlangt. Dadurch ergibt sich eine geringfügig andere Lösung.

Dezimal        32-Bit      Mögliche Cacheblöcke
           Binäradresse    DM    A2          AV

294928070  * 110 0 01 10   001   01-0,01-1   000,001,010,011,100,101,110,111
294928009  * 100 0 10 01   010   10-0,10-1   000,001,010,011,100,101,110,111
294928039  * 101 0 01 11   001   01-0,01-1   000,001,010,011,100,101,110,111
294928083  * 110 1 00 11   100   00-0,00-1   000,001,010,011,100,101,110,111
294928066  * 110 0 00 10   000   00-0,00-1   000,001,010,011,100,101,110,111
294928068  * 110 0 01 00   001   01-0,01-1   000,001,010,011,100,101,110,111
294928035  * 101 0 00 11   000   00-0,00-1   000,001,010,011,100,101,110,111
294928080  * 110 1 00 00   100   00-0,00-1   000,001,010,011,100,101,110,111
294928093  * 110 1 11 01   111   11-0,11-1   000,001,010,011,100,101,110,111
294928067  * 110 0 00 11   000   00-0,00-1   000,001,010,011,100,101,110,111
294928079  * 110 0 11 11   011   11-0,11-1   000,001,010,011,100,101,110,111
294928037  * 101 0 01 01   001   01-0,01-1   000,001,010,011,100,101,110,111
294928084  * 110 1 01 00   101   01-0,01-1   000,001,010,011,100,101,110,111
294928009  * 100 0 10 01   010   10-0,10-1   000,001,010,011,100,101,110,111
* = 0001 0001 1001 0100 0011 1110

Adressen:
2949280..    70  09  39  83  66  68  35  80  93  67  79  37  84  09 
DM:
Cacheblock: 001 010 001 100 000 001 000 Hit 111 000 011 001 101 Hit

liest:       68  08  36  80  64  68  32  80  92  64  76  36  84  08
             69  09  37  81  65  69  33  81  93  65  77  37  85  09
             70  10  38  82  66  70  34  82  94  66  78  38  86  10
             71  11  39  83  67  71  35  83  95  67  79  39  87  11

A2:
Cacheblock:  01  10  01  00  00 Hit  00  00  11  00  11 Hit  01 Hit
              0   0   1   0   1       0   1   0   0   1       0   
liest:       68  08  36  80  64  68  32  80  92  64  76  36  84  08
             69  09  37  81  65  69  33  81  93  65  77  37  85  09
             70  10  38  82  66  70  34  82  94  66  78  38  86  10
             71  11  39  83  67  71  35  83  95  67  79  39  87  11

AV:
Cacheblock: 
            000 001 010 011 100 Hit 101 Hit 110 Hit 111 Hit 001 101
liest:       68  08  36  80  64  68  32  80  92  64  76  36  84  08
             69  09  37  81  65  69  33  81  93  65  77  37  85  09
             70  10  38  82  66  70  34  82  94  66  78  38  86  10
             71  11  39  83  67  71  35  83  95  67  79  39  87  11

Nach den Leseoperationen sind die Caches folgendermaßen belegt:

DM:
    s  Tag    
000     * 110      294928064,65,66,67
001     * 101      294928036,37,38,39
010     * 100      294928008,09,10,11
011     * 110      294928076,77,78,79
100     * 110      294928080,81,82,83
101     * 110      294928084,85,86,87
110     *  -          - - -
111     * 110      294928092,93,94,95

A2:
   s    Tag    
00 0    * 1100     294928064,65,66,67
00 1    * 1101     294928080,81,82,83
01 0    * 1101     294928084,85,87,87
01 1    * 1010     294928036,37,38,39
10 0    * 1000     294928008,09,10,11
10 1    *  -          - - -
11 0    * 1101     294928092,93,94,95
11 1    * 1100     294928076,77,78,79

AV:
  s     Tag    
 000    * 110001   294928068,69,70,71
 001    * 110101   294928084,85,86,87
 010    * 101001   294928036,37,38,39
 011    * 110100   294928080,81,82,83
 100    * 110000   294928064,65,66,67
 101    * 100010   294928008,09,10,11
 110    * 110111   294928092,93,94,95
 111    * 110011   294928076,77,78,79

5. Kontrollfragen

Die Lösung der Kontrollfragen sollte aus dem Skript und weiterführender Literatur erfolgen.

6. Aufgabe (Cachekohärenz, MESI-Protokoll)

Kodierung der Zustände:

    Valid   Dirty  Shared
M     1       1       0
E     1       0       0
S     1       0       1
I     0       0       0

Das Beispiel:

                  Cache 1    Cache 2    Cache 3   
      
   Operation      E  Z  A    E  Z  A    E  Z  A
                  -  I  -    -  I  -    -  I  -
P1: read  4711   RME E  ^    -  I  -    -  I  -
P2: read  4711   SHR S  -   RMS S  ^    -  I  -
P3: write 4711   SHW I  -   SHW I  -   WM  M  -
P3: write 4711    -  I  -    -  I  -   WH  M  -
P2: write 4711    -  I  -   WM  M  -   SHW I  v
P1: read  4711   RMS S  ^   SHR S  v    -  I  -

^    Cache line fill
v    Dirty line copyback
RH   Read Hit
RMS  Read Miss Shared
RME  Read Miss Exclusive
WH   Write Hit
WM   Write Miss
SHR  Snoop Hit on a Read
SHW  Snoop Hit on a Write

Felix Holderied