Lösung Übungsblatt 5

1. Aufgabe

a) Das Programm durchläuft zwei Arrays b und c mit jeweils 10 Werten. Hierbei wird immer der größere der beiden Werte b[i] und c[i] in das dritte Array als a[i] geschrieben.

Abhängigkeiten:

Datenabhängigkeiten:
- Echte Datenabhängigkeit (true dependence): Der Befehl Inst1 schreibt sein Ergebnis in ein Register (Speicher), das von Inst2 als Eingabe gelesen wird.
- Gegenabhängigkeit (anti-dependence): Der Befehl Inst 1 liest einen Operanden aus einem Register (Speicher), das von Inst2 anschließend überschrieben wird.
- Ausgabeabhängigkeit (output dependence): Beide Befehle beschreiben das gleiche Register.
Steuerflussabhängigkeit (control dependence): Der Befehl Inst1 muss abgeschlossen sein, bevor die Entscheidung getroffen werden kann, ob Inst2 ausgeführt werden soll oder nicht.

Pipeline-Konflikte:

Lese-nach-Schreibe-Konflikt (read after write, RAW): Verursacht durch echte Datenabhängigkeit.
- Registerzugriff (Ri): RAW -> 3 Stufen
- Auswertung der Sprungbedingung (SR) bei Sprungbefehl -> 2 Stufen
Schreibe-nach-Lese-Konflikt (write after read, WAR): Verursacht durch Gegenabhängigkeit. Konflikt tritt hier nicht auf, da keine Schreibstufe einer Lesestufe vorangeht.
Schreibe-nach-Schreibe-Konflikt (write after write, WAW): Verursacht durch Ausgabeabhängigkeit. Konflikt tritt hier nicht auf, da nicht mehre Stufen zum gleichen Ziel schreiben.
Steuerungskonflikte: Verursacht durch Steuerflussabhängigkeit. Kommt nur bei Sprungbefehlen vor. PC wird in MA-Stufe geschrieben und von IF-Stufe gelesen. -> 3 Stufen

c) Der NOP-Befehl kann beispielsweise durch ADD R0, R0, R0 implementiert werden. (1) func: LDC 1, R1 ; R1 = 1 (2) LDC 4, R2 ; R2 = 4 (3) LDC 10, R3 ; R3 = 10 (4) LDC a, R4 ; R4 = a (5) LDC b, R5 ; R5 = b (6) LDC c, R6 ; R6 = c (6a) NOP ; einmal durchlaufen (6b) NOP ; einmal durchlaufen (7) label1: LOAD R5, R7 ; R7 = *R5 (8) LOAD R6, R8 ; R8 = *R6 (8a) NOP ; 10x durchlaufen (8b) NOP ; 10x durchlaufen (8c) NOP ; 10x durchlaufen (9) SUB R7, R8, R9 ; R9 = R7 - R8 (9a) NOP ; 10x durchlaufen (9b) NOP ; 10x durchlaufen (9c) NOP ; 10x durchlaufen (10) CMP R9, R0 ; SR = R9 - 0 (10a) NOP ; 10x durchlaufen (10b) NOP ; 10x durchlaufen (11) JMP LE, label2 ; if (SR <= 0) goto label2 (11a) NOP ; 10x durchlaufen (11b) NOP ; 10x durchlaufen (11c) NOP ; 10x durchlaufen (12) STORE R7, R4 ; *R4 = R7 (13) JMP T, label3 ; goto label3 (13a) NOP ; 10x durchlaufen (13b) NOP ; 10x durchlaufen (13c) NOP ; 10x durchlaufen (14) label2: STORE R8, R4 ; *R4 = R8 (15) label3: SUB R3, R1, R3 ; R3 = R3 - 1 (15a) NOP ; 10x durchlaufen (15b) NOP ; 10x durchlaufen (15c) NOP ; 10x durchlaufen (16) CMP R3, R0 ; SR = R3 -0 (16a) NOP ; 10x durchlaufen (16b) NOP ; 10x durchlaufen (17) JMP LE, end ; if (SR <= 0) goto end (17a) NOP ; 10x durchlaufen (17b) NOP ; 10x durchlaufen (17c) NOP ; 10x durchlaufen (18) ADD R4, R2, R4 ; R4 = R4 + 4 (19) ADD R5, R2, R5 ; R5 = R5 + 4 (20) ADD R6, R2, R6 ; R6 = R6 + 4 (21) JMP T, label1 ; goto label1 (21a) NOP ; 9x durchlaufen (21b) NOP ; 9x durchlaufen (21c) NOP ; 9x durchlaufen (22) end: ... 27 NOPs eingefügt. Bei der Ausführung des Programms werden (1*2+10*22+9*3)=249 NOPs ausgeführt.

d)

(5) func LDC b, R5 ; R5 = b
(6) LDC c, R6 ; R6 = c
(3) LDC 10, R3 ; R3 = 10 (ein Durchlauf NOP eingespart)
(4) LDC a, R4 ; R4 = a (ein Durchlauf NOP eingespart)
(7) label1: LOAD R5, R7 ; R7 = *R5
(8) LOAD R6, R8 ; R8 = *R6
(1) LDC 1, R1 ; R1 = 1 (ein Durchlauf NOP eingespart, bei den anderen 9 wird diese Anweisung sinnlos ausgeführt, ist also ein ?NOP?)
(2) LDC 4, R2 ; R2 = 4 (ein Durchlauf NOP eingespart, bei den anderen 9 wird diese Anweisung sinnlos ausgeführt, ist also ein ?NOP?))
(8c) NOP ; 10x durchlaufen
(9) SUB R7, R8, R9 ; R9 = R7 - R8
(9a) NOP ; 10x durchlaufen
(9b) NOP ; 10x durchlaufen
(9c) NOP ; 10x durchlaufen
(10) CMP R9, R0 ; SR = R9 - 0
(10a) NOP ; 10x durchlaufen
(10b) NOP ; 10x durchlaufen
(11) JMP LE, label2 ; if (SR <= 0) goto label2
(11a) NOP ; 10x durchlaufen
(11b) NOP ; 10x durchlaufen
(11c) NOP ; 10x durchlaufen
(13) JMP T, label3 ; goto label3
(12) STORE R7, R4 ; *R4 = R7 (10 Durchläufe NOP eingespart)
(13b) NOP ; 10x durchlaufen
(13c) NOP ; 10x durchlaufen
(14) label2: STORE R8, R4 ; *R4 = R8
(15) label3: SUB R3, R1, R3 ; R3 = R3 - 1
(15a) NOP ; 10x durchlaufen
(15b) NOP ; 10x durchlaufen
(15c) NOP ; 10x durchlaufen
(16) CMP R3, R0 ; SR = R3 -0
(16a) NOP ; 10x durchlaufen
(16b) NOP ; 10x durchlaufen
(17) JMP LE, end ; if (SR <= 0) goto end
(17a) NOP ; 10x durchlaufen
(17b) NOP ; 10x durchlaufen
(17c) NOP ; 10x durchlaufen
(19) ADD R5, R2, R5 ; R5 = R5 + 4
(21) JMP T, label1 ; goto label1
(20) ADD R6, R2, R6 ; R6 = R6 + 4 (9 Durchläufe NOP eingespart)
(18) ADD R4, R2, R4 ; R4 = R4 + 4 (9 Durchläufe NOP eingespart)
(21c) NOP ; 9x durchlaufen
(22) end: ...

7 NOPs eingespart. Bei der Ausführung des Programms werden (2+2+10*1+9*2) NOPs = 32 NOPs eingespart!

e) Forwarding: Ergebnisse einer ALU-Operation müssen nicht mehr in Register geschrieben werden, bevor sie gelesen werden können. Sie stehen wieder direkt als Eingabe für die ALU zur Verfügung.
Regsiterbefehle: Keine Datenkonflikte Keine Leerbefehle notwendig.
Speicherzugriffe (LOAD, STORE): Hier muss die WB-Phase noch durchlaufen werden. 3 Leerbefehle notwendig.

(1) func: LDC 1, R1 ; R1 = 1
(2) LDC 4, R2 ; R2 = 4
(3) LDC 10, R3 ; R3 = 10
(4) LDC a, R4 ; R4 = a
(5) LDC b, R5 ; R5 = b
(6) LDC c, R6 ; R6 = c
(7) label1: LOAD R5, R7 ; R7 = *R5
(8) LOAD R6, R8 ; R8 = *R6
(8a) NOP ; 10x durchlaufen
(8b) NOP ; 10x durchlaufen
(8c) NOP ; 10x durchlaufen
(9) SUB R7, R8, R9 ; R9 = R7 - R8
(10) CMP R9, R0 ; SR = R9 - 0
(11) JMP LE, label2 ; if (SR <= 0) goto label2
(11a) NOP ; 10x durchlaufen
(11b) NOP ; 10x durchlaufen
(11c) NOP ; 10x durchlaufen
(12) STORE R7, R4 ; *R4 = R7
(13) JMP T, label3 ; goto label3
(13a) NOP ; 10x durchlaufen
(13b) NOP ; 10x durchlaufen
(13c) NOP ; 10x durchlaufen
(14) label2: STORE R8, R4 ; *R4 = R8
(15) label3: SUB R3, R1, R3 ; R3 = R3 - 1
(16) CMP R3, R0 ; SR = R3 -0
(17) JMP LE, end ; if (SR <= 0) goto end
(17a) NOP ; 10x durchlaufen
(17b) NOP ; 10x durchlaufen
(17c) NOP ; 10x durchlaufen
(18) ADD R4, R2, R4 ; R4 = R4 + 4
(19) ADD R5, R2, R5 ; R5 = R5 + 4
(20) ADD R6, R2, R6 ; R6 = R6 + 4
(21) JMP T, label1 ; goto label1
(21a) NOP ; 9x durchlaufen
(21b) NOP ; 9x durchlaufen
(21c) NOP ; 9x durchlaufen
(22) end: ...

12 NOPs nötig. Bei der Ausführung des Programms werden (9*10+3*9) NOPs = 117 NOPs ausgeführt.

2. Aufgabe

1. Möglichkeit: Beide Automaten in einen eindeutigen Zustand bringen, dann zum ersten Unterschied simulieren: T, T, T; NT, NT, T

2. Möglichkeit (kürzer): NT, NT, T, T, NT

Es gibt keine kürzere Sequenz!

3. Aufgabe

Durchlauf	Sprung 1	Sprung 2	Sprung 3
1	NT	T	-
2	NT	T	-
3	T	NT	T
4	NT	T	-
5	NT	T	-
6	T	NT	NT

b)

Durchlauf Sprung 1 Sprung 2 Sprung 3

Prädiktor Entscheidg Präd. neu Prädiktor Entscheidg Präd. neu Prädiktor Entscheidg Präd. neu

1 NT NT (ok) NT T T (ok) T T - T
2 NT NT (ok) NT T T (ok) T T - T
3 NT T (falsch) T T NT (falsch) NT T T (ok) T
4 T NT (falsch) NT NT T (falsch) T T - T
5 NT NT (ok) NT T T (ok) T T - T
6 NT T (falsch) T T NT (falsch) NT T NT (falsch) NT
Sagt immer die gleiche Richtung wie beim letzten Mal voraus. Bei Fehlannahme wird der Zustand gewechselt. 5 Fehlannahmen beim Verlassen der Schleifen +2 Fehlannahmen beim Wiedereintritt in die Schleifen = 7 Fehlannahmen

c)

Durchlauf Sprung 1 Sprung 2 Sprung 3

Prädiktor Entscheidg Präd. neu Prädiktor Entscheidg Präd. neu Prädiktor Entscheidg Präd. neu

1 SNT NT (ok) SNT ST T (ok) ST ST - ST
2 SNT NT (ok) SNT ST T (ok) ST ST - ST
3 SNT T (falsch) WNT ST NT (falsch) WT ST T (ok) ST
4 WNT NT (ok) SNT WT T (ok) ST ST - ST
5 SNT NT (ok) SNT ST T (ok) ST ST - ST
6 SNT T (falsch) WNT ST NT (falsch) WT ST NT (falsch) ST
Nur 5 Fehlannahmen beim Verlassen der Schleifen. Die Fehlannahmen beim Wiedereintritt in die Schleifen werden nicht gemacht

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
(für *) muss man 0001 0001 1001 0100 0011 1110 einsetzen.

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

Ilia Polian

Last modified: Wed Jun 26 17:43:00 MEST 2002

(1)	func:	LDC 1, R1	; R1 = 1
(2)		LDC 4, R2	; R2 = 4
(3)		LDC 10, R3	; R3 = 10
(4)		LDC a, R4	; R4 = a
(5)		LDC b, R5	; R5 = b
(6)		LDC c, R6	; R6 = c
(6a)		NOP	; einmal durchlaufen
(6b)		NOP	; einmal durchlaufen
(7)	label1:	LOAD R5, R7	; R7 = *R5
(8)		LOAD R6, R8	; R8 = *R6
(8a)		NOP	; 10x durchlaufen
(8b)		NOP	; 10x durchlaufen
(8c)		NOP	; 10x durchlaufen
(9)		SUB R7, R8, R9	; R9 = R7 - R8
(9a)		NOP	; 10x durchlaufen
(9b)		NOP	; 10x durchlaufen
(9c)		NOP	; 10x durchlaufen
(10)		CMP R9, R0	; SR = R9 - 0
(10a)		NOP	; 10x durchlaufen
(10b)		NOP	; 10x durchlaufen
(11)		JMP LE, label2	; if (SR <= 0) goto label2
(11a)		NOP	; 10x durchlaufen
(11b)		NOP	; 10x durchlaufen
(11c)		NOP	; 10x durchlaufen
(12)		STORE R7, R4	; *R4 = R7
(13)		JMP T, label3	; goto label3
(13a)		NOP	; 10x durchlaufen
(13b)		NOP	; 10x durchlaufen
(13c)		NOP	; 10x durchlaufen
(14)	label2:	STORE R8, R4	; *R4 = R8
(15)	label3:	SUB R3, R1, R3	; R3 = R3 - 1
(15a)		NOP	; 10x durchlaufen
(15b)		NOP	; 10x durchlaufen
(15c)		NOP	; 10x durchlaufen
(16)		CMP R3, R0	; SR = R3 -0
(16a)		NOP	; 10x durchlaufen
(16b)		NOP	; 10x durchlaufen
(17)		JMP LE, end	; if (SR <= 0) goto end
(17a)		NOP	; 10x durchlaufen
(17b)		NOP	; 10x durchlaufen
(17c)		NOP	; 10x durchlaufen
(18)		ADD R4, R2, R4	; R4 = R4 + 4
(19)		ADD R5, R2, R5	; R5 = R5 + 4
(20)		ADD R6, R2, R6	; R6 = R6 + 4
(21)		JMP T, label1	; goto label1
(21a)		NOP	; 9x durchlaufen
(21b)		NOP	; 9x durchlaufen
(21c)		NOP	; 9x durchlaufen
(22)	end:	...

(5)	func	LDC b, R5	; R5 = b
(6)		LDC c, R6	; R6 = c
(3)		LDC 10, R3	; R3 = 10 (ein Durchlauf NOP eingespart)
(4)		LDC a, R4	; R4 = a (ein Durchlauf NOP eingespart)
(7)	label1:	LOAD R5, R7	; R7 = *R5
(8)		LOAD R6, R8	; R8 = *R6
(1)		LDC 1, R1	; R1 = 1 (ein Durchlauf NOP eingespart, bei den anderen 9 wird diese Anweisung sinnlos ausgeführt, ist also ein ?NOP?)
(2)		LDC 4, R2	; R2 = 4 (ein Durchlauf NOP eingespart, bei den anderen 9 wird diese Anweisung sinnlos ausgeführt, ist also ein ?NOP?))
(8c)		NOP	; 10x durchlaufen
(9)		SUB R7, R8, R9	; R9 = R7 - R8
(9a)		NOP	; 10x durchlaufen
(9b)		NOP	; 10x durchlaufen
(9c)		NOP	; 10x durchlaufen
(10)		CMP R9, R0	; SR = R9 - 0
(10a)		NOP	; 10x durchlaufen
(10b)		NOP	; 10x durchlaufen
(11)		JMP LE, label2	; if (SR <= 0) goto label2
(11a)		NOP	; 10x durchlaufen
(11b)		NOP	; 10x durchlaufen
(11c)		NOP	; 10x durchlaufen
(13)		JMP T, label3	; goto label3
(12)		STORE R7, R4	; *R4 = R7 (10 Durchläufe NOP eingespart)
(13b)		NOP	; 10x durchlaufen
(13c)		NOP	; 10x durchlaufen
(14)	label2:	STORE R8, R4	; *R4 = R8
(15)	label3:	SUB R3, R1, R3	; R3 = R3 - 1
(15a)		NOP	; 10x durchlaufen
(15b)		NOP	; 10x durchlaufen
(15c)		NOP	; 10x durchlaufen
(16)		CMP R3, R0	; SR = R3 -0
(16a)		NOP	; 10x durchlaufen
(16b)		NOP	; 10x durchlaufen
(17)		JMP LE, end	; if (SR <= 0) goto end
(17a)		NOP	; 10x durchlaufen
(17b)		NOP	; 10x durchlaufen
(17c)		NOP	; 10x durchlaufen
(19)		ADD R5, R2, R5	; R5 = R5 + 4
(21)		JMP T, label1	; goto label1
(20)		ADD R6, R2, R6	; R6 = R6 + 4 (9 Durchläufe NOP eingespart)
(18)		ADD R4, R2, R4	; R4 = R4 + 4 (9 Durchläufe NOP eingespart)
(21c)		NOP	; 9x durchlaufen
(22)	end:	...