Institut für Rechnerentwurf und Fehlertoleranz

Prof. Dr. Th. Ungerer
Dirk Eisenbiegler
5. Juni 1997
Loesung3

Musterlösung zum 3. Übungsblatt

1. Aufgabe

Cachespeicher

In der Regel werden für den Hauptspeicher die langsamere, aber kostengünstigere DRAM-Technologie (dynamischer Speicher) und für den Cache die schnellere, aber teurere SRAM-Technologie (statischer Speicher) eingesetzt.

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 32 Bits für die Verwaltung eines Cacheblocks.

Das Beispiel

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 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 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 werden. 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-0000100-, 0000006-,
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.

    Es wird nun ein Algorithmus beschrieben, mit dem zu einer beliebigen Permutation die Einstellungen für die Zweierschalter in der ersten und letzten Spalte berechnet wird. Durch die Einstellung der Zweierschalter in der ersten und letzten Spalte ergeben sich auch die Permutationen für die beiden Benesnetzwerke, von denen gemäß Induktionsvoraussetzung bereits bekannt ist, daß sie jede beliebige Permutation realisieren können.

    In dem Algorithmus wird pro Schleifendurchlauf die Belegung für genau einen Zweierschalter bestimmt. Der Schleifenrumpf wird also 2^d mal durchlaufen. Während der Abarbeitung gibt es zwei Zustände A und B.

    Zustand A: Es sind für alle Pfade entweder sowohl der erste als auch der letzte Zweierschalter bereits eingestellt oder keiner von beiden.
    Zustand B: Es gibt zwei Anschlüsse x und y (jeweils Ein- oder Ausgänge) bei denen zwar die angrenzenden Zweierschalter bereits eingestellt sind, nicht jedoch die zugehörigen Zweierschalter am anderen Ende des Pfades.

    Der Algorithmus befindet sich zu Anfang im Zustand A.

    Befindet sich der Algorithmus im Zustand A, so wird ein beliebiger noch nicht eingestellter Zweierschalter aus der ersten oder letzten Spalte ausgewählt, und dessen Einstellung beliebig auf "Kreuzschaltung" oder "Parallelschaltung" eingestellt. Der Algorithmus wechselt danach in den Zustand B, wobei x und y die Anschlüsse des gerade eingestellten Zweierschalters sind.

    Befindet sich der Algorithmus im Zustand B, so wird für x die Einstellung des am anderen Ende des Pfades liegenden Zweierschalters bestimmt. Diese ist eindeutig, denn durch die Einstellung des an x angrenzenden Zweierschalters, wird bestimmt, ob der Pfad über das obere oder das untere der beiden Benes-Subnetze der Ordnung n-1 verläuft. Der am anderen Ende des Pfades von x liegende Anschluß sei x'. Der an x' angrenzende Zweierschalter hat - wie alle anderen Zweierschalter der ersten und letzten Spalte - genau eine Verbindung zum oberen und genau eine Verbindung zum unteren Subnetz. Durch den Pfad von x nach x' ergibt sich deshalb seine Einstellung in eindeutiger Weise. Der zweite Anschluß zu diesem Zweierschalter sei x''. Ist x'' das andere Ende des Pfades von y, so wechselt der Algorithmus nachfolgend in den Zustand A, ansonsten bleibt er im Zustand B und x wird durch x'' ersetzt.

  3. Konstruieren Sie 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