Alle hatten die gleiche Klausur. Es gab 40 Punkte zu holen. Die Punktzahl wird am Ende mit 1.5 multipliziert. Dementsprechend werden allgemein auch halbe Punkte vergeben. 1. Aufgabe gegebene Tabelle von Prozessorentwürfen Entwurf | MIPS | Kosten ------------------------------ 1 | 150 | 20€ 2 | 200 | 80€ 3 | 300 | 70€ 4 | 400 | 100€ 5 | 50 | 30€ a) Trage die Entwürfe in das Diagramm ein und markiere die Pareto-Front. (leeres Diagramm ist gegeben ohne Beschriftung) TIPPs: - die Richtung der Achsen (aufsteigende Werte/absteigende Werte) und welche Achse unten aufgetragen wird, ist nicht so wichtig, der Rest muss aber passen - Achseneinteilung und Beschriftung - eingezeichnete Punkte müssen gekennzeichnet/benannt werden (hab deswegen einen halben Punkt verloren) - die Richtung, in der die Punkte (Entwürfe) besser bewertet werden, muss eingezeichnet werden - die Paretofront verbindet die Achsen mit allen pareto-optimalen Punkten; alle pareto-dominierte Punkte müssen sich in der eingeschlossenen Fläche der Achsen mit der Pareto-Front befinden b) welche Entwürfe sind nicht pareto-optimal und warum? === SPOILER ===: Wenn sowohl die Kosten besser (d.h. niedriger) und die Rechenleistung eines Entwurfs in MIPS besser (d.h. höher) ist als die eines anderen, dann dominiert dieser Entwurf einen anderen Entwurf. E2 wird pareto-dominiert von E3. E5 wird pareto-dominiert von E1. =============== ----------------------- 2. Aufgabe nennen sie 3 Besonderheiten der ARM-Prozessorarchitektur === SPOILER ===: * viele Instruktionen mit unterschiedlichen Operandenformaten und integriertem Barrelshifter * viele unterschiediche Adressierungsmodi * full predication (d.h. für (fast) alle Befehle gibt es eine bedingte Ausführbarkeit, Ausnahme) * Thumb-Mode (De-/Aktivierung über BX-Befehl) =============== ---------------------- 3. Aufgabe a) Nennen sie 2 wesentliche Unterschiede zwischen VLIW- und Superskalar-Architekturen b) Es war ein C-Code gegeben, der ziemlich so aussah wie der von VL-Kapitel 3 Seite 39, also ungefähr so: x = *ap; if (x < 0) { t = *bp + 1; } else { t = x - 1; } *zp = t; Danach wurde der zugehörige normale (nicht optimierte) MIPS(-ähnliche) ASM-Code gezeigt (vereinfacht, ohne Pipeline-Hazards und Delay-Slots zu betrachten) lw r1, 0(r10) bgtz r1, if else: addi r2, r1, -1 b endif if: lw r3, 0(r11) addi r2, r3, 1 endif: sw r2, 0(r12) und der optimierte Code: lw r1, 0(r10) lw r3, 0(r11) bgtz r1, if else: addi r2, r1, -1 b endif if: addi r2, r3, 1 endif: sw r2, 0(r12) Welches Problem könnte in der optimierten MIPS-Version auftreten? Wie könnte man das beheben? === SPOILER === -> In der Klausur war die Antwort für mich nicht so schnell ersichtlich, aber Lösung muss natürlich sein, dass Exceptions auftreten können (non-recoverable -> Segmentation Fault, recoverable -> Page Fault) durch das vorgezogene lw, und das, obwohl nicht gewusst wird, ob der Pfad für x < 0 ausgeführt werden wird oder nicht. Allgemein lösen kann man das Problem über die in Kap. 3 besprochenen Ansätze: * entweder non-recoverable Exception model (silent instructions mit 'dissmissible Bit', welches silent instruction kennzeichnet, Exceptions können "nicht wiederhergestellt werden" und sind nach Unterdrückung "tot".) * recoverable Exception model (vorgezogene Instruktionen sind als solche markiert, dass sie keine Exceptions werfen und eigene Check instruction werden später im zugehörigen Zweig eingefügt und es existiert eine Exception Flag für jedes Register, sodass diese durch die check-Instruktion für jedes Register kontrolliert werden kann und, falls gesetzt, zu einem Fixup-Code gesprungen werden kann) Musterlösung sieht recoverable Exception model vor. Der interne Mechanismus muss dabei nicht wie oben erklärt werden. Die Musterlösung sieht als Lösung nur eine Architektur, mit der: * Ladebefehl ausgeführt wird (ohne Exception) * check-Befehl im Basic-Block, aus der der Ladebefehl kommt, wo dann für den Fehlerfall eine Exception generiert wird. =============== ---------------------- 4. Aufgabe (8 Punkte) Gegeben ist ein C-Code, der Teiler und Rest einer Division berechnet. Variablen mit Endung _i sind Eingänge, mit Endung _o sind Ausgänge. (Auffällig war, dass ein Bestätigungssignal nach Abschluss der Berechnung in der Klausuraufgabe vergessen wurde. Das ist nicht weiter schlimm.) gegebener C-Code: while(1) { while(!go_i); divident = x_i; divisor = y_i; quotient_o = 0; rest_o = 0; if (divisor == 0) { quotient_o = -1; } else { while(divident >= divisor) { divident = divident - divisor; quotient_o = quotient_o + 1; } rest_o = divident; } } Zustandsautomaten und Datenpfad war dazu zu erstellen (Zeichen-Vorlagen waren dafür nicht gegeben, beides musste man auf den freien Platz unter der Aufgabe oder auf der freien Rückseite des Blattes zeichnen). Steuerwerk ist nicht gefordert. TIPP von mir: * Aufgabe erst nach den anderen Aufgaben bearbeiten (die Zeit ist insgesamt ausreichend) * am besten gesamten Platz ausnutzen und größer zeichnen * Code vereinfachen, falls sinnvoll möglichst wenig Variablen (hier zum Beispiel kann man quotient_o = 0 in den else-Block machen und rest_o = 0 in den if-Block), sonst überflüssige Variablen rausschmeißen (z.B. unterschiedliche temporäre Variablen, die nur einmal genutzt werden zu einer zusammenfassen) * dann zuerst den Zustandsautomaten als Flussdiagramm erstellen; dieser muss die Abhängigkeit der Register und Reihenfolge von Rechenoperationen beinhalten, quasi ein Kontrolflussgraph * Datenpfad: jede benötigte Rechenoperation braucht eine Komponente im Datenpfad, die die Rechnung durchführt; (Un)Gleicheit lässt sich über n-Bit-NOR-Gatter feststellen. Ungleichungs-Vergleiche für den Zustandsautomaten erfordern einen Subtrahierer und häufig davon nur das oberste Bit. In anderen Fällen ist ein zusätzlicher Komparator unbedingt nötig, eventuell bei vorzeichenlosen Vergleichen, wenn gemischte Vergleiche auftreten (z.B. in einem Fall Gleichheit, im anderen Fall >=) oder wenn ein "General-Purpose"-Subtrahierer nicht benötigt wird. >=, <= entspricht msb == 0, < und > entspricht msb == 1 (Subtrahend und Minuent am Subtrahierer auch kennzeichnen). Wenn man die zu vergleichenden Variablen ohnehin subtrahieren muss (wie in diesem Beispiel), braucht man für den gleichzeitigen Vergleich und die Subtraktion nur einen Subtrahierer (in der Einsicht hab ich einen halben Punkt noch bekommen, weil übersehen wurde, dass ich Subtraktion und Vergleich gleichzeitig mache, vielleicht lässt sich das als Kommentar anbringen) für jede Variablenabhängigkeit im Zustandsautomat (in Verzweigungsbedingungen) wird ein Signal benötigt, das im Datenpfad berechnet wird und als Output an den Zustandsautomaten geht. Für Schnittstellensignale kann man es genau andersrum machen, als mit Registern. Je mehr Signale, desto einfacher der Entwurf. Dadurch, dass kein Steuerwerk gefordert ist, kann man sich den Design vereinfachen, indem Signale vom Datenpfad zum Steuerwerk nicht durch boolsche Algebra im Datenpfad zusammengefasst werden und im Datenpfad keine zusätzlichen Multiplexer brauchen, weil man für jeden Zustand im Automaten Extra-Signale für die Schnittstelle nutzen kann. Die Zusammenfassung passiert durch Multiplexer und Logikfunktionen im Steuerwerk. Durch Verzicht auf Zusammenfassung der Signale, überträgt man Komplexität und Bauteile in das Steuerwerk. Dadurch ist auch weniger einzuzeichnen und spart Zeit. Inputs vom Zustandsautomaten in den Datenpfad werden für Steuersignale benötigt (weil die Multiplexer ja abhängig vom aktuellen Zustand im Steuerwerk sind) Multiplexer im Datenpfad verwenden, um Ressourcen zu sparen; die Fallunterscheidungszahlen und Steuersignale für den Multiplexer sollten jeweils eingezeichnet werden * wichtige Hinweise von eigenen Optimierungsentscheidungen und Designentscheidungen (Register-Arten) können Punkte retten und die Kontrolle vereinfachen * konstante Additionen, insbesondere die inkrementelle Addition, kann man häufig optimieren; für +1 kann man ein Zählregister verwenden ---------------------- 5. Aufgabe rekonfigurierbare Systeme a) Nennen sie 2 Vorteile UND Nachteile von FPGAs gegenüber ASICs === SPOILER ===: Vorteile des FPGAs (Eselsbrücke: FPGAs besitzen bessere Bedingungen für die Produktentwicklung) * Wiederprogrammierbarkeit erlaubt Änderungen und Anpassungen; weniger Perfektionismus erforderlich -> resultierend daraus wahrscheinlich auch geringere Entwicklungszeit, also kürzere Time-To-Market * Entwicklungskosten von Hardwarefunktionalität: Zeitpunkt (Design Freeze), an dem der Design nicht mehr änderbar ist, ist beim ASIC sehr früh, aber beim FPGA erst sehr spät. * Herstellungskosten: Herstellungsprozesse für ASICs zu entwickeln sind sehr teuer, FPGAs sind durch systematische Struktur und Massenproduktion für bestimmte Anwendungen günstiger (oder eben auch nicht) Vorteile von Asics (Eselsbrücke: Asics besitzen allgemein bessere Eigenschaften in der Verwendung): * energie-effizienter * bessere Leistung und ressourcen-schonender * kompakter, vor allem, da auf bestimmte Anwendung zugeschnitten werden können =============== b) Nennen sie die 2 wichtigsten Bestandteile, mit denen FPGAs funktionieren. === SPOILER ===: * Configurable Logic Blocks (CLBs) + IO-Buffer * Verschaltungsnetzwerk (PSM bei Xilinx) gibt keine Punkte: * Lookup-Tables * Multiplexer (* Register) =============== [Als Frage denkbar wäre auch: Nennen Sie die Schritte und Teilprodukte bei der Synthese von bspw. HDL-Code zu einer direkten Binärdatei für FPGAs] ---------------------- 6. Aufgabe Control Systems a) Nennen sie 2 Vorteile von Computersystemen gegenüber analogen Schaltkreisen === SPOILER ===: * Robustheit und Schutz vor Temperaturen ist günstiger zu realisieren als bei analogen Schaltungen. (Daraus folgt nicht, dass die Robustheit allgemein besser ist. Dafür gibt es keine Punkte.) * bessere Flexibilität / Anpassbarkeit im Nachhinein durch Programmierbarkeit möglich, aber nicht empfohlen: * kaum HW-Designaufwand, da HW-Technik bekannt; Aufwand reduziert auf Software geht nicht: * Fertigungskosten/Herstellungsaufwand =============== b) gegeben sei ein open-loop System, wobei v_t Ausgangsgeschwindigkeit, r_t eine Geschwindigkeitsvorgabe und P eine Konstante ist, mit v_(t+1) = 0.6*v_t + 0.4*u_t; u_t = P*r_t Berechnen sie die Regelverstärkung P zum erreichen für die Steady-State-Geschwindigkeit. === SPOILER ===: v_ss = v_(t+1) = v_t soll = r_t <=> v_ss = 0.6*v_ss + 0.4*P*v_ss <=> 1 = 0.6 + 0.4*P <=> P = 1 =============== gegeben sei nun ein closed-loop-System (das fälschlicherweise als open-loop-System bezeichnet wurde) mit u_t = P(v_t - r_t) und einer Störung w_t. Wenn man die Formeln ineinander einsetzt (so ähnlich der Wortlaut), erhält man diese Funktion für die Strecke: v_t = (0.6-0.4*P)^t*v_0 + ((0.6-0.4*P)^t + (0.6-0.4*P)^(t-1) + ... + (0.6-0.4*P) + 1.0)(P*r_0 - w_0) c) Für welches P ist die Ausgangsgröße stabil und konvergiert die Ausgangsgröße? === SPOILER ===: Stabilität: abs(0.6 - 0.4*P) < 1 (Betrag nicht vergessen!) (Rechenweg gibt Punkte!) Fall 1: 0.6 - 0.4*P > -1 <=> -0.4*P > -1.6 <=> P < 4 Fall 2: 0.6 - 0.4*P < 1 <=> -0.4*P < 0.4 <=> P > -1 <=> P > -1 =============== d) Für welches P oszilliert die Ausgangsgröße nicht? === SPOILER ===: Oszillation: 0.6 - 0.4*P >= 0 <=> P < 0.6/0.4 = 3/2 =============== [denkbär wären auch Fragen zur Bedeutung und zum Rechenmodell von PI, PD und PID-Reglern] ---------------------- 7. Aufgabe, Real Time Scheduling gegeben ist die Tabelle an Prozessen Prozess | Ausführungszeit | Periodendauer -------------------------------------------- a | 8 | 16 b | 2 | 8 c | 1 | 4 a) Berechnen sie die Auslastung des Schedules für die Prozesse aus der Tabelle und prüfen sie mit dem Liu-Lyland-Kriterium (ein bis dato völlig neuer Begriff), ob ein RMS-Schedule machbar (feasible) ist. === SPOILER ===: Auslastung = Summe aus Ausführungszeit / Periodendauer für jeden Prozess Auslastung = 100% <= 1 Das Liu-Lyland-Kriterium ist eigentlich folgendes: Auslastung <= n*(2^(1/n) - 1) = 0.8 (mit n = 3 = Anzahl der Prozesse) -> Kriterium nicht erfüllt (und es hieß vor der Klausur, wir würden keinen Taschenrechner benötigen, war glücklicherweise aber zugelassen) Ich weil dieses in dem Beispiel nicht erfüllt war, habe ich geschlussfolgert, ein optimaler Schedule wird nicht garantiert. Dafür habe ich scheinbar einen halben Punkt verloren. =============== b) Zeigen sie den RMS-Ablauf für die Prozesse aus der Tabelle wie der RMS-Schedule aussehen würde, indem sie die Prozess-Bezeichner in die Kästchen schreiben (16 leere quadratische kästchen mit je einer gleichlangen Zeitscheibe und Time-line waren gegeben, wo man zu jedem Zeitpunkt ins Kästchen den aktuell laufenden Prozess eintragen sollte). === SPOILER ===: Die Aufgabe sah sehr einfach aus, RMS war in der Vorlesung immer präemptiv, war im erklärenden Musterbeispiel aber nicht offensichtlich. c b b a c a a a c b b a c a a a =============== Hält dieser Ablauf alle Deadlines ein? (Versteht sich von selbst.)