Sie befinden sich hier: Termine » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 12 » Prüfungsprotokoll Reconfigurable Computing   (Übersicht)

Prüfungsprotokoll Reconfigurable Computing

Prüfer: Prof. Teich
Beisitzer: Khosravi

Verlauf: Es wird am Anfang der Prüfung eine zufälliges Paket mit 4 Fragen bzw. Themen gezogen. Am Anfang wurde gesagt, dass ich mir beim Beantworten der Fragen ruhig Zeit lassen soll. Nach wiederholten Schusselfehlern wurde ich noch einmal darauf hingewiesen, dass ich meine Antworten erst durchdenken soll, weil es für jede Aussage, die korrigiert werden muss, Punktabzug gibt.
Es wird auf jede der vier Themenbereiche eine Punktzahl gegeben und der Durchschnitt bestimmt die Prüfungsnote.

1. Einordnung, Coarse-Grain Reconfigurable Devices

P: Es gibt Von-Neuman Rechner und ASICs, können sie die auf einem Spektrum einordnen?
S: Zeichnet Spektrum mit Effizienz und Flexibilität auf
VN Rechner sind sehr flexibel aber sehr ineffizient, ASICS sind effizient aber nicht flexibel. CPUS können praktisch alle Aufgaben erfüllen, ASICs nur eine bestimmte Funktion.
P: Wo ordnet man in dem Diagramm FPGAS ein?
S: Dazwischen, sie sind effizienter als CPUS und flexibler als ASICS.
P: Wodurch sind CPUs so flexibel?
S: Sie haben verschiedene Einheiten, z.B. ALUs und FPUs
P: ASICS könnenn allerdings auch ALUs haben.
S: CPUs arbeiten verschiedene Instruktionen ab.
P: Wie genau funktioniert das?
S: Zuerst wird die Instruktion geladen, dann dekodiert.
P: Was bedeutet das?
S: Sie wird in Unteraufgaben aufgeteilt, ersten Daten laden, dann irgendwie verarbeiten, dann speichern.
P: Was ist genau der Unterschied zwischen einer CPU und einem FPGA? Beides wird programmiert.
S: Ja, aber ein FPGA verhält sich nach der Programmierung wie ein ASIC, er erfüllt genau die Funktion, die im Bitstream beschrieben ist.
P: Was enthält der Bitstream genau?
S: Die Inhalte der LUTs und die Konfiguration der Switching Matritzen.
P: Was ist der Vorteil von FPGAS?
S: Sie verhalten sich als wäre die Funktion in Hardware implementiert.
P: Was bedeutet das genau?
S: Eine CPU arbeitet Instruktionen sequenziell ab. Bei einem FPGA passiert die Berechnung innerhalb eines Cycles.

P: Was sind Coarse-Grain Reconfigurable Device(CGRD) und wofür braucht man inh?
S: Die haben gröbere Prozesselemente. Beim FPGA ist jeder LUT mit einer Switching-Matrix verbunden und große Funktionen werden auf viele LUTs verteilt. Dadurch wird sehr viel Kommunikation zwischen des PEs nötig. Für Berechnungen mit Integern oder Floats, würde die nötige Logik den ganzen FPGA belegen. Bei CGRD hat man vollständige Rechen- oder Logikeinheiten, die untereinander vernetzt sind und so weniger Kommunikations-Overhead.
P: Können sie solche Geräte nennen?
S: Z.B. der Quicksilver ACM, der wird konfiguriert oder das Tightly Coupled Processing Array, das bekommt Instruktionen.
P: Was würde man zum Implementieren von Neuronalen Netzen verwenden?
S: Einen CGRD, man braucht mehrere Level von Multipklikationseinheiten. Dafür wäre z.B. der XPP sehr gut geeignet, der streamt Daten durch ein Netz von ALUs.

2. Partitionierung, Mapping

P: Was passiert, nachdem man eine boolsche Funktion synthetisiert hat?
S: Eventuell passt die Funktion nicht auf einen FPGA oder man hat mehrere Module, dnan muss man partitionieren.
P: Was gibt es für Arten von partitionierung?
S: Spatial und Temporal Partitioning.
P: Gegeben ist folgende Funktion, die soll auf LUTs gemappt werden. Was gibt es dafür für Verfahren?

         ______
        /      \
Inputs: a   b  |  c
        |\ / \ \ / 
        | d  |  e
         \|   \/
          f   g
           \ /
Output:     h

S: Es gibt Chortle, das optimiert die Anzahl der LUTs, also die Fläche.
P: Was hat man davon?
S: Dann wird weniger Strom verbraucht.
P: Nicht direkt Strom, sondern was?
S: Energie? pro Cycle?
P: Ja, z.B. OPS/Watt.

P: Was ist das Ziel von Flowmap?
S: Es optimiert das Delay/Latenz.
P: Wie?
S: Die maximale Länge eines Pfades zwischen primären Inputs und Outputs wird minimiert.
P: Wie hoch ist die Latenz bei dem Beispiel?
S: 3 Logic Gates.
P: Wie funktioniert Flowmap genau?
S: Ausgehen von den Inputs wird jeder Node ein Label zugewiesen, das aussagt, ob es mit seinen Vorgängern in ein LUT passt. Die primären Inputs bekommen das Label 0, dann beginnt man mit den Nodes darunter. Man sucht nach einem Cut mit Node Cut Size ⇐ K, indem man den Graph transformiert, die Nodes dupliziert etc. und schaut, ob der minimale Cut eine Edge Cut Size ⇐ K hat.
P: Im ganzen Graph?
S: Nein, man betrachten nur die Vorgänger und deren Vorgänger usw.
P: Wie heißt das genau?
S: Cone, der geht vom der aktuellen Node bis zu den primären Inputs.
P: Wie funktioniert das konkret an dem Beispiel?
S: Mal Graph von Cone für d, transformiert ihn, Fehler bei Labeling
P: Sie können die Labels auch direkt an die Grafik machen.
P: Und dann?
S: Dann kommt die Mapping Phase. Hier verwendte man die cuts aus der vorherigen Phase. Gab es einen geeigneten Cut, wird der Knoten mit den Nodes, die auf seiner Seite des Cuts waren auf ein LUT gemappt. Ansonsten kommt der Knoten alleine in einen LUT.
P: Können Sie das an der Grafik zeigen?
S: Ordnet h einem LUT zu, g einem, f zusammen mit d einem, und e einem
P: Sie fangen am Output Knoten an?
S: Ja.
P: Wie viele LUTs braucht man also?
S: Vier.

3. On-Line Communication

P: Was ist das Problem bei partieller Rekonfiguration?
S: Man weiß vorher nicht, wohinein Modul platziert werden wird und wo die Module liegen, mit denen es kommunizieren muss.
P: Was gibt es für Ansätze um das Problem zu lösen?
S: Man kann einen Bus verwenden. Das ist ein statische Struktur, welche schon zur Compilezeit festgelegt wird.
Alle Module wissen, wo der Bus liegt und können sich anschließen. P: Was gibt es noch für Alternativen?
S: Circuit switching. Bei der Rekonfiguration, wird ein Verbindungspfad zwischen zu verbindenden Module gesucht.
P: Geht das in der Praxis?
S: Nein, das ist zu aufwendig für on-line Verwendung, vor allem wenn andere Module Hindernisse für die Pfade darstellen.
P: Gibt es einen Ansatz, der das trotzdem möglich macht?
S: Ja, man kann einen extra Switching Layer haben, über die Kommunikationspfade laufen, dass blockieren Module die Verbindungen nicht mehr.
P: Und noch etwas anderes?
S: Es gibt den Reconfigurable Multi Bus, der partielle 1-D Rekonfiguration erlaubt.

P: Hier ist ein Beispiel und eine Kostenfunktion. Was bedeutet die Formel?

cost = SUM over (i,c)elem E : |delta(i) - delta(j)|
Slot: | S1 | S2 | S3 | S4 | S5 | S6 |
Modul:| M1 | M2 |    | M4 |    | M3 |
Kanten: 1-//4, 2-//3, 3-//1, 3-//2

S: Die Kosten sind die Summe der Segmentlängen zwischen zu verbindenden Modulen.
P: Wofür stehen i und j?
S: Für die Indizes der Module, zwischen denen eine Kante existiert.
P: Wofür steht delta(i)?
S: Für den Slot des Moduls.
P: Wo würden sie die Module platzieren, um die Kosten zu verbessern?
P: Was sind denn die Kosten der ersten und der optimierten Platzierungen?
S: 16 und 4.
P: Warum macht man solch eine Optimierung?
S: Damit man einen kürzeren Pfad und somit ein geringeres Delay hat.
P: Die Länge der Verbindung macht in dem Fall nicht viel aus, was ist entscheidend?
S: Bei der ersten Platzierung werden bis zu 4 Segmente gleichzeitig verwendet, bei der optimierten nur 2.
P: Ist der Bus mit auf der FPGA Fläche oder extern?
S: Er ist auf der FPGA Fläche und alle Module müssen die Buslogik mit enthalten.
P: Und wenn man 2-D rekonfigurieren kann?
S: Dann kann man auch den Bus fest als Block in einem Bereich lassen und nur die umliegenden Bereiche rekonfigurieren.
P: Was gibt es noch für eine Form der On-Line Kommunikation?
S: Networks on Chip mit paketbasierter Kommunikation. Hier kümmern sich die Router zur Laufzeit um den Austausch von Daten.

4. Anwendungen, Pattern Matching

P: Was gibt es für Arten von Rekonfiguration?
S: Statische und dynamische. Statisch bedeutet, dass selten rekonfiguriert wird.
P: Welche Anwendungen fallen in diese Kategorie?
S: Rapid Prototyping, Low-volume Produktion, wenn ASIC Herstellung zu teuer ist.
P: Was gibt es noch, wenn z.B. ein neues Funkprotokoll herauskommt?
S: Man kann nachträglich noch Updates und Upgrades aufspielen.
P: Was sind Anwendungen mit häufiger Rekonfiguration?
S: Fault Tolerance, sodass ein Gerät die Funktionalität eines ausgefallenen Gerätes übernehmen kann. Oder mit partieller Rekonfiguration kann das gleiche Modul mehrmals geladen und die Ergebnisse vergleichen werden.

P: Man kann FPGAs auch für Pattern Matching verwenden. Hier ist ein Beispiel Input und Output:

Input: KTFJKFFAUFAU
Output:000000001001

S: Das System sucht nach der Zeichenfolge „FAU“.
P: Wie kann man das implementieren?
S: Mit einem Sliding Window und einer Finite State Machine.
P: Können Sie eine FSM aufzeichnen, die dieses Ergebnis liefert?
S: Zeichnet mit Hilfe FSm mit 4 States
P: Wie heißt so eine FSM, deren Output nur nur vom State abhängig ist?
S: Deterministischer Endlicher Automat.
P: Das ist es auch, aber der richtige Begriff ist Moore Machine.
P: Wie kann man eine FSm auf dem FPG implementieren?
S: Man kann mit Flip-Flops die States kodieren.
P: Wie viele bräuchte man dafür?
S: 2 (Das schien falsch zu sein)
P: Ja, wahrscheinlich wenn optimiert wird.
P: Was gibt es noch für eine andere Art der Implementierung?
S: One-Hot?
P: Wie funktioniert die? Können sie das Schaltungsdiagramm dazu aufmalen?
S: Zeichnet Kette von Flip-Flops
P: Das ist falsch, der Input für den nächsten Flip-Flop hängt nicht nur vom vorherigen Flip-Flop ab.
S: zeichnet Verundung von vorherigem Flip-Flop und Charakter-Komparator ein
P: Was muss man verändern, wenn man nach anderen Wörtern suchen will?
S: Für Wörter der gleichen Länge nur die Komparatoren. Für längere oder kürzere Wörter muss man die Flip-Flop Kette anpassen.

Fazit: Ich hatte erwartet, dass die Prüfung sich an der Struktur der Übungen orientiert und viele Anwendungsaufgaben enthält. Insgesamt ging es aber viel um Verständnisfragen über den Stoff der Vorlesung. Es ist hilfreich, nicht nur die Aufgaben aus den Übungen durchzugehen, sondern die Algorithmen auch an anderen Beispielen anzuwenden. Dann kommt man nicht wie ich in der Prüfung durcheinander, wenn die gegebenen Beispiele von dem Schema der Übung abweichen.