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 wurd mir 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.

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 erüllen, ASICs nur eine bestimmte Funktion. P: Wo ordnet man in dem Diagram 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 lönnen abe rauch 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 einem 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 entä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?
P: Ein 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 Kommmunikation 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 untereinande vernetzt sind und so weniger Kommunikations Overhead. P: Können sie solge Geräte nennen?
S: Z.B. der ACM oder das Tightly Coupled Processing Array.
P: Was würde man dennzum Implementieren von Neuronalen Netzen verwenden?
S: Einen CGRD, man braucht mehere Level von Multipkliktionseinheiten. Dafür wäre z.B. der XPP sehr gut geeignet, der streamt Daten durch ein Netz von ALUs.

P: Was passiert nachdem man eine boolsche Funktion synthetisiert hat?
S: Eventuell passt die Funtion nicht auf einen FPGA oder man hat mehere Module, dnan muss man partitionieren.
P: Was gibt es für Arten von partitionierung?
S: Spatial und Temporal Partitioning.
P: Gegeben ist folgende Funtion, die soll auf LUTs gemappt werden. Was gibt es dafür für Verfahren?
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
S: Flowmap, das optimiert das Delay/Latenz.
P: Wie?
S: Die maximale Länge eines Pfades zwischen primärenn Inputs und Outputs wird minimiert.
P: Hier ist ein Beispielgraph:

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

P: Wie hoch ist die Latenz bei diesem 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 a dem Beispiel?
S: <Cone malen, transformieren, Fehler gemacht>
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?
… P: Sie fangen am Output Knoten an?
S: Ja.

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, welches schon zur Compilezeit festegelgt 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 aufwändig für on-line Verwendung, vor allem wenn andere Module Hindernisse für die Gfade 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 plazieren, um die Kosten zu verbessern?
… P: Was sind denn die Kosten der ersten und die kosten 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 rekonfigueiren.
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.

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 heraus kommt?
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äts übernehmen kann.
S: Oder mit partieller Rekonfigiration 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 aufzecihnen, 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 (schien falsch zu sein, wahrscheinlich weil Output auch noch berechnet werden muss)
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 Schaltungsdiagram 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, wnen 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-Flip Kette anpassen.

Fazit: Ich hatte erwartet, dass die Prüfung sich an der Struktur der Übungen orientiert und viele Anwendungsaufgaben enthält. Insgesamt lag der Fokus aber auf Verständnisfragen über den Stoff der Vorlesung. Es ist ratsam, nicht nur die Aufgaben aus den Übungen durchzugehen, sondern die Algorithmen auch an anderen Beispielen anzuwenden, damit man dann nicht wie ich in der Prüfung durcheinanderkommt.