Institut für Rechnerentwurf und Fehlertoleranz

Prof. Dr. Th. Ungerer
Dirk Eisenbiegler
30. Mai 1996
Loesung3

Musterlösung zum 3. Übungsblatt

1. 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

2. Aufgabe

Alle Adressen außer 1236FFF (logisch) liegen in dem 64k-Segment mit der logischen Anfangsadresse 1234000 und der virtuellen Anfangsadresse 00010000. Auf diesem Segment hat der Prozeß Zugriffsrechte. Die logischen Adressen 1234A000, 1234A00A, 1234A010, 1234A023, 1234B050, 1234A00C und 1234B060 werden in die virtuellen Adressen 0001A000, 0001A00A, 0001A010, 0001A023, 0001B050, 0001A00C bzw. 0001B060 übersetzt.

Die Seite mit der virtuellen Anfangsadresse 0001A000 befindet sich zu Anfang bereits im Hauptspeicher und zwar an der physikalischen Adresse 00001000. Bei den ersten Speicherzugriffen werden deshalb die virtuellen Adressen 0001A000, 0001A00A, 0001A010 und 0001A023 auf die physikalischen Adressen 00001000, 0000100A, 00001010 bzw. 00001023 abgebildet und direkt vom Hauptspeicher gelesen.

Beim Zugriff auf 1234B050 (logisch) bzw. 0001B050 (virtuell) kommt es zu einem Seitenfehler. Eine Betriebssystemroutine behandelt diese Exception und lagert die Seite mit der kleinsten virtuellen Adresse aus. Das ist die Seite mit der virtuellen Adresse 0000A000 bzw. der physikalischen Adresse 00000000. Auf die physikalische Seite 00000000 wird dann vom Sekundärspeicher die Seite mit der virtuellen Adresse 0001B000 kopiert. Danach wird die virtuelle Adresse 0001B050 auf die physikalische Adresse 00000050 abgebildet und das Datenwort aus dem Hauptspeicher gelesen. Der nachfolgende Speicherzugriff auf 0001B060 (virtuell) greift auf die gleiche Seite zu und kann deshalb direkt die physikalische Adresse 00000060 aus dem Hauptspeicher lesen.

Der Zugriff auf 1236FFF (logisch) führt zu einem Segmentfehler der über eine Exceptionroutine des Betriebssystems bearbeitet werden muß. Es kann weder eine virtuelle noch eine logische Adresse erzeugt werden. Üblicherweise reagiert das Betriebssystem damit, daß es es den Prozeß beendet.

Am Anfang sind beide Caches leer. Beim Zugriff auf 00001000 (physikalisch) entsteht deshalb ein Cache-Miss - die Daten müssen vom Hauptspeicher geholt werden. Bei diesem Zugriff werden auf einmal 16 Datenworte mit den physikalischen Adressen 00001000 bis 0000100F in den First-Level Cache und den Secondary-Level Cache kopiert. Der nachfolgende Zugriff auf 0000100A (physikalisch) greift deshalb auf den First-Level Cache zu (cache hit). Beim Zugriff auf 00001010 wird ein weiterer Block in den First- und in den Secondary-Level Cache kopiert. Beim Zugriff auf 00001023 muß wiederum ein Block in den First- und in den Secondary-Level Cache kopiert. Jetzt ist allerdings im First-Level Cache nicht mehr genug Platz vorhanden. Nach dem LRU-Prinzip wird deshalb der Block, in dem zuletzt 0000100- gespeichert wurde, überschrieben. Der nachfolgende Speicherzugriff auf 0000100C (physikalisch) kann deshalb nicht über den First-Level Cache sondern nur über den Secondary-Level Cache realisiert werden. Beim Zugriff auf 00000060 (physikalisch) wird wieder auf den Hauptspeicher zugegriffen.

logische
Adresse 		virtuelle
Adresse 		physik.
Adresse 		First-Level Cache Secondary-Level Cache Seitentabelle
leerleer0001A000 auf 00001000
1234A000 0001A000 00001000
0000100-0000100-"
1234A00A 0001A00A 0000100A
0000100-0000100-"
1234A010 0001A010 00001010
0000100-, 0000101-0000100-, 0000101-"
1234A023 0001A023 00001023
0000102-, 0000101-0000100-, 0000101-,
0000102-		"
1234B050 0001B050 00000050
0000102-, 0000005-0000100-, 0000101-,
0000102-, 0000005-		 0001A000 auf 00001000,
0001B000 auf 00000000
1234A00C 0001A00C 0000100C
0000100-, 0000005-0000100-, 0000101-,
0000102-, 0000005-		 "
1234B060 0001B060 00000060
0000100-, 0000006-0000006-, 0000101-,
0000102-, 0000005-		 "
1236FF60 - -
-- -

3. Aufgabe (Verbindungsnetzwerke)

  1. Wieviele Zeilen und Spalten hat ein Benesnetzwerk der Ordnung d? 
               d-1
#Zeilen = 2   ,     #Spalten = 2 d - 1
  2. Zeigen Sie, daß das Benesnetzwerk universell ist, d.h. jede Permutation erzeugen kann. Ich führe einen Induktionsbeweis. 
    d = 1
    stimmt (trivial) 
    d - 1 -> d
    Annahme: Ein Netzwerk der Ordnung d -1 kann alle Permutationen über 2^(d-1) erzeugen.

    Möchte ich eine vorgegebene Permutation zu einem Netzwerk der Größe d erzeugen gehe ich folgendermaßen vor:

    OBdA stelle ich den Kreuzschalter (Tauscher) links oben auf "parallel". Damit geht der Pfad des Eingangs 0 durch das obere Subnetzwerk. (Jeder Tauscher der äusseren Spalten hat eine Verbindung zum oberen und eine zum unteren Subnetzwerk) Ich lege damit die Stellung des Tauscher in der rechten Spalte fest, der zum entsprechenden Ausgang P(0) gehört. Als nächstes gehe ich vom zweiten Ausgang dieses rechten Tauschers aus, und suche den entsprechenden Eingang auf der linken Seite. Dieser Pfad führt durch das untere Subnetzwerk. Damit lege ich einen zweiten Tauscher in der linken Spalte fest. Nun nehme ich den anderen Eingang dieses Tauschers u.s.w.

    Mit diesem Zick-Zack-Verfahren werden solange Tauscher in den äusseren Spalten festgelegt, bis man wieder beim linken oberen Tauscher ankommt.

    Sind dann noch nicht alle Tauscher in der linken und rechten Spalte festgelegt, so wähle ich den noch freien Eingang mit dem kleinsten Index aus, stelle den zugehörigen Tauscher wieder auf parallel und setze das Verfahren fort.

    Sind alle Tauscher in der linken und rechten Reihe festgelegt, so wird das Verfahren rekursiv auf die Subnetzwerke angewandt.

    Auf dem Weg von links nach rechts wird jeweils das obere Netzwerk durchlaufen, auf dem Rückweg das untere.

    Warum kann es nicht zu Verklemmungen kommen?

    Auf der linken Seite ist immer nur ein Eingang an einem schon festgelegten Tauscher frei (im ersten Schritt ist dies der Eingang 1). Wird dieser irgendwann auf einem Rückweg festgelegt so steht der zugehörige linke Tauscher auf jeden Fall richtig, denn der Pfad dieses Eingangs führt durch das untere Subnetzwerk.

    Auf der rechten Seite wird immer, nachdem ein Tauscher festgelegt wurde der andere Pfad festgelegt, der durch diesen Tauscher führt. Es gehören daher immer alle "offenen" Ausgänge auch zu noch nicht festgelegten Tauschern.

    Anmerkung 1: Das Verfahren wird am Beispiel aus Teilaufgabe 3 deutlich.

    Anmerkung 2: Ruhe bewahren! Ein Beweis dieser Art wird nicht in der Klausur gefordert.

  3. Konstruieren für d = 3 eine Schalterstellung, die die Permutation (3,0,1,2,4,6,5,7) erzeugt.

    Zuerst veranschaulicht man sich die Permutation graphisch:


    Die äußeren Spalten werden im beschriebenen Verfahren konstruiert. Numerierung der Wege in der Reihenfolge, wie sie im Algorithmus erzeugt werden. Rote Wege sind von links nach rechts, also vom Eingang zum Ausgang erzeugt, grüne ungekehrt.



    Wendet man das Verfahren auf die Unternetzwerke rekursiv an, so kommt man zu folgendem Ergebnis:


Dirk Eisenbiegler