Institut für Rechnerentwurf und Fehlertoleranz

Dr. W. Karl

Frank Beeh

17. Juli 2002

6. Übungsblatt zur Vorlesung Rechnerstrukturen

Die Besprechung dieses Übungsblattes findet am Donnerstag, den 17. Juli 2002 um 14.00 Uhr im HMU statt. Die Musterlösung ist nach der Übung im WWW unter http://wwwipr.ira.uka.de/~lehre/RS/index.html zu finden.

1. Aufgabe VHDL

(Klausur SS 2001, Aufgabe 1)

(a) Für welchen Bereich lässt sich VHDL neben Dokumentation, Datenaustausch, Simulation und Verifikation noch einsetzen?

(b) Welche drei Entwurfsebenen unterscheidet man?

(d) Füllen Sie die Lücken in den vier nachfolgenden VHDL Codes korrekt aus!

___________ _________ IS

     PORT (a, b : IN  bit;

           y    : OUT bit);

 END something;

___________ v1 OF something IS

 BEGIN

     PROCESS (a,b)

     BEGIN

         IF (a == '1') THEN y <= b;

         ELSE               y <= NOT b;

         END IF;

     END PROCESS;

 END v1;

___________ test OF somethingelse IS

 FOR structural

     FOR ALL : halfadder

         USE ENTITY work.halfadder(behavior);

     END FOR;

     FOR oder : or2

         USE ENTITY work.or2(behavior);

     END FOR;

 END FOR;

 END test;

___________ v2 OF something IS

     COMPONENT and

         PORT (a, b    : IN  bit;

               y       : OUT bit);

     END COMPONENT;

     COMPONENT inv

         PORT (a       : IN  bit;

               y       : OUT bit);

     END COMPONENT;

     SIGNAL s;

 BEGIN

     K1 : _______ PORT MAP (s,b,y);

     K2 : _______ PORT MAP (a,s);

 END v2;

(e) Verbinden Sie die Ein- und Ausgänge der Komponenten in der Strukturzeichnung des Lösungsblattes gemäß nachfolgendem Modell. Geben Sie fehlende Signalnamen in ihrer Zeichnung an!

ENTITY all IS

PORT (clk, x : IN bit;

y : OUT bit);

END all;

ARCHITECTURE all_structural OF all IS

COMPONENT dff

PORT (clk, d : IN bit;

q : OUT bit);

END COMPONENT;

COMPONENT inv

PORT (a : IN bit;

y : OUT bit);

END COMPONENT;

COMPONENT nand2

PORT (a, b : IN bit;

y : OUT bit);

END COMPONENT;

SIGNAL q1, q2, q1n, q2n, y1, y2 : bit;

BEGIN

dff1 : dff PORT MAP (clk, x, q1);

dff2 : dff PORT MAP (clk, q1, q2);

inv1 : inv PORT MAP (y => q1n, a => q1);

inv2 : inv PORT MAP (q2, q2n);

n1 : nand2 PORT MAP (b => q2, a => q1n, y => y1);

n2 : nand2 PORT MAP (a => q1, y => y2, b => q2n);

n3 : nand2 PORT MAP (y1, y2, y);

END all_structural;

(f) Was geschieht im nachfolgenden Modell behavior mit den Signalen x1 und x2, wenn die Signale a und b wie angegeben wechseln?

Signalname	Vor Wechsel	Nach Wechsel
a	0	1
b	1	1
x1	0
x2	0

ENTITY anything IS

END anything;

ARCHITECTURE behaviour OF anything IS

SIGNAL a, b, x1, x2 : bit;

BEGIN

PROCESS (a)

BEGIN

x1 <= a AND b;

END PROCESS;

PROCESS (b)

BEGIN

x2 <= a AND b;

END PROCESS;

END behaviour;

2. Aufgabe (Pipelining)

(Übung 2, SS 2002, Aufgabe 1)

Für diese Aufgabe wird im Folgenden eine vereinfachte RISC-Maschine definiert. Sie verfüge über die Register R0-R31, wobei das Register R0 mit der Konstanten 0 belegt ist. Die Maschine besitze außerdem ein Statusregister SR und den Befehlszähler PC. Die einzelnen Befehle werden in einer fünfstufigen Befehls-Pipeline verarbeitet, wie sie in der Vorlesung vorgestellt wurde. (Befehl-Holen, Befehl-Dekodieren, Operation-Ausführen, Speicherzugriff und Resultat-Speichern). Sprungbefehle werten die Bedingung in der Ausführphase aus und ändern gegebenenfalls den Befehlszähler in der Speicherzugriffsphase. In den folgenden Tabellen sind die Befehle des Prozessors angegeben. Die Semantik wird durch Pseudo-C-Code dargestellt. Dabei bezeichnet Ri ein Register, Addr eine Adresse, Val eine Konstante und Cond eine Bedingung.

Arithmetische Befehle		Vergleichsbefehl
`ADD` `R`i, `R`j, `R`k	`R`k `=` `R`i `+` `R`j	`CMP` `R`i, `R`j	`SR = R`i `-` `R`j
`SUB` `R`i, `R`j, `R`k	`R`k `=` `R`i `-` `R`j	Sprungbefehl
`MUL` `R`i, `R`j, `R`k	`R`k `=` `R`i `*` `R`j	`JMP` Cond, Addr	`if(` Cond `) PC =` Addr
`OR` `R`i, `R`j, `R`k	`R`k `=` `R`i `\|` `R`j	Bedingungen für `JMP`
`AND` `R`i, `R`j, `R`k	`R`k `=` `R`i `&` `R`j	`T`	`true`
`NOT` `R`i, `R`j	`R`j `= ~ R`i	`F`	`false`
Ladebefehle		`LT`	`SR < 0`
`LDC` Val, `R`i	`R`i `=` Val	`LE`	`SR <= 0`
`LOAD` `R`i, `R`j	`R`j `= *R`i	`GT`	`SR > 0`
`LOAD` Addr, `R`i	`R`i `= `Addr*	`GE`	`SR >= 0`
`STORE` `R`i, `R`j	`*R`j `= R`i	`Z`	`SR == 0`
`STORE` `R`i, Addr	``Addr* `= R`i	`NZ`	`SR != 0`

Auf dem oben angegeben Prozessor soll ein Programm ausgeführt werden. Die folgende Codesequenz enthält noch Pipelinekonflikte, welche die in den Kommentaren angedeutete Arbeitsweise der einzelnen Befehle beeinflussen. Die Adressen a, b und c zeigen jeweils auf einen Speicherbereich mit 10 Vier-Byte-Werten.

(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
(9)		SUB R7, R8, R9	; R9 = R7 - R8
(10)		CMP R9, R0	; SR = R9 – 0
(11)		JMP LE, label2	; if (SR <= 0) goto label2
(12)		STORE R7, R4	; *R4 = R7
(13)		JMP T, label3	; goto label3
(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
(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
(22)	end:	...

(a) Erläutern Sie die Funktion des Programms (gemäß den Kommentaren).

(b) Nennen Sie alle möglichen Abhängigkeiten zwischen Befehlen. Überprüfen Sie, welche bei der obigen Pipeline zu Konflikten führen können. Zwischen welchen Stufen der Pipeline können diese Konflikte auftreten?

(c) Finden Sie eine Assembler-Anweisung, mit der ein NOP-Befehl realisiert werden kann, und lösen Sie alle Pipelinekonflikte durch das Einfügen einer minimalen Anzahl von NOP- Befehlen auf.

(d) Optimieren Sie dieses mit NOPs ergänzte Programm weiter, indem Sie durch Verschiebung von Anweisungen NOP-Befehle einsparen.

(e) Die Pipeline soll nun Forwarding unterstützen. An welchen Stellen kann die Ausführungszeit damit verkürzt werden? Beziehen Sie sich auf die Lösung aus Aufgabenteil (c).

3. Aufgabe (Sprungvorhersage)

(Übung 2, SS 2002, Aufgabe 2)

Gegeben sei untenstehendes Programmfragment. Die Semantik wird durch Pseudo-C-Code dargestellt.

Hinweis: In R0 ist die Konstante 0 fest gespeichert.

...

( 1)        LDC 1,  R1      ; const1 = 1

( 2)        LDC 2,  R4      ; counter1 = 2

( 3) loop1:

( 4)        LDC 3,  R3      ; counter2 = 3

( 5)        LDC 2,  R2      ; var1 = 2

( 6) loop2:

( 7)        CMP R2, R0      ; SR = var1 - 0

( 8)        JMP Z,  label   ; if (SR == 0) goto label (Sprung 1)

( 9)        SUB R2, R1, R2  ; R2 = R2 - 1

(10) label:

(11)        SUB R3, R1, R3  ; R3 = R3 - 1

(12)        CMP R3, R0      ; SR = R3 - 0

(13)        JMP GT, loop2   ; if (SR > 0) goto loop2 (Sprung 2)

(14)        SUB R4, R1, R4  ; R4 = R4 - 1

(15)        CMP R4, R0      ; SR = R4 - 0

(16)        JMP GT, loop1   ; if (SR > 0) goto loop1 (Sprung 3)

...

(a) Ermitteln Sie den Verlauf der Sprünge 1 bis 3.

(b) Verwenden Sie jeweils einen 1-Bit-Prädiktor (0,1) zur Vorhersage jedes Sprunges. Diese seien wie folgt initialisiert: Sprung 1 (NT); Sprung 2 (T), Sprung 3 (T). Übernehmen Sie zunächst den Verlauf der Sprünge aus Aufgabenteil a). Tragen Sie weiterhin den Verlauf der Zustände der Prädiktoren ein und unterstreichen Sie den jeweils ausgewählten Prädiktor. Heben Sie weiterhin die falsch vorhergesagten Sprünge durch Unterstreichen hervor. Wie viele Fehlannahmen werden insgesamt gemacht? Worauf sind diese zurückzuführen?

(c) Verwenden Sie nun 2-Bit-Prädiktoren (0,2) mit Sättigungszähler zur Sprungvorhersage. Diese seien wie folgt initialisiert: Sprung 1(SNT), Sprung 2 (ST), Sprung 3 (ST). Wieso werden nun weniger Fehlannahmen gemacht?

(d) Verwenden Sie nun (1,1)-Korrelations-Prädiktoren zur Sprungvorhersage. Gehen Sie hierbei von Folgendem aus:

· Der Sprung vor Eintritt in das Programmfragment wurde genommen (T).

· Die Prädiktoren der einzelnen Sprünge sind wie folgt initialisiert: Sprung 1 (NT,NT), Sprung 2 (T,NT), Sprung 3 (T,T).

Hinweis: Falls der vorherige Sprung nicht genommen wurde, wird der erste Teil des Tupels (x, y) verwendet, andernfalls der zweite.

Wie viele Fehlannahmen werden nun gemacht? Wodurch sind diese begründet?

(e) Können die Fehlannahmen bei Sprung 1 durch einen (2,1)-Korrelations-Prädiktor vermieden werden? Begründen Sie Ihre Meinung!

(f) Welches Verhalten erwarten Sie bei der Verwendung eines (1,2)-Korrelations-Prädiktors? Begründen Sie Ihre Meinung!

4. Aufgabe (Virtuelle Speicherverwaltung)

(Auszüge aus Übung 3, SS 2002, Aufgabe 4)

Der folgende aus der digitalen Signalverarbeitung stammende Algorithmus soll auf einem Prozessor mit virtueller Speicherverwaltung ausgeführt werden:

(01) FOR i = 0 TO 2^13-1

(02) y = 0;

(03) FOR j = 0 TO 2

(04) y = y + x[i+j] * w(j);

(05) END

(06) y[i] = y;

(07) END

Der Prozessor verfügt über drei Segmentregister: CS für Programmcode, DS für Datenstrukturen und SS für den Stapel. Die Auswahl eines Segmentregisters erfolgt implizit durch den auszuführenden Befehl. Die Bildung der virtuellen Adresse erfolgt durch Addition der Basisadresse mit der logischen Adresse. Die Seitengröße beträgt 4096 Worte, wobei der Hauptspeicher maximal 4 Seiten aufnehmen kann. Seiten der CS- und der SS-Segmente werden vom Betriebssystem nicht ausgelagert. Als Ersetzungsstrategie kommt LRU zum Einsatz. Die Segmentregister sind wie folgt belegt:

Segment	Basisadresse (hex.)	Länge (hex.)
CS	3A17C000	1000
DS	D29E4000	4000
SS	51F60000	1000

Das Feld x im obigen Programm beginnt an der logischen Adresse 2000, y bei 0. Die Seitentabelle enthält zu Beginn folgende Einträge:

Virtuelle Adresse	Physikalische Adresse	Hauptspeicher
3A17C	0	ja
51F60	1	ja
D29E6	2	ja
D29E7	3	ja

(a) Erstellen Sie ein Protokoll der ein- und ausgelagerten Seiten während der Ausführung des Programms solange keine Zugriffsverletzung auftritt. Geben Sie jeweils die Iteration und die Zeilennummer an, bei der ein Seitenfehler auftritt. Wie viele Seitenwechsel werden insgesamt durchgeführt?

5. Aufgabe (MESI-Protokoll)

(Übung 4, SS 2002, Aufgabe 1)

Gegeben sei ein speichergekoppeltes Multiprozessorsystem mit zwei Prozessoren, die über einen Bus mit einem globalen Speicher verbunden sind. Zur Wahrung der Cache Kohärenz wird das MESI Protokoll verwendet. Die Caches der beiden Prozessoren haben je eine Größe von drei Cache-Lines die genau ein Speicherwort aufnehmen können. Die Caches werden von der niedrigsten Cache-Line aufwärts gefüllt, falls noch freie Lines zur Verfügung stehen. Im Falle eines voll besetzten Caches werden sie nach der Strategie LRU (least recently used) überschrieben. Ergänzen Sie die folgende Tabelle, wobei die Buchstaben die Zustände: M = exclusive modified, E = exclusive unmodified, S = shared unmodified, I = invalid repräsentieren. Die Zahlen hinter den Aktionen und Zuständen bezeichnen Speicheradressen.

Prozessor	Aktion	Cache1 Line1	Cache1 Line2	Cache1 Line3	Cache2 Line1	Cache2 Line2	Cache2 Line3
-	-	E/8	E/12	I/-	E/6	I/-	I/-
2	read 10
1	write 8
1	read 10
2	read 8
1	write 8
1	write 8
1	read 18
2	write 10
2	write 18

6. Aufgabe (Verbindungsstrukturen)

(Auszüge aus Übung 4, SS 2001, Aufgabe 2)

Gegeben sei ein Verbindungsnetzwerk, dessen Topologie in der nebenstehenden Abbildung dargestellt ist.

(a) Bestimmen Sie den Verbindungsgrad, den Diameter, die minimale Bisektionsbreite, die Diskonnektivität und die Kosteneffektivität.

(b) Um welche Form eines Verbindungsnetzwerkes handelt es sich in diesem Fall?