Prüfungsfragen HSO mit Lösung v2 PDF

Preview

Summary

HSO 1. Scheduling: a. Was ist Scheduling? zeitliche Zuordnung einer Menge von Aufgaben. Planung, wann eine Operation wird. b. Welche Prinzipien gibt es das (begrenzte Ressourcen, Zeit), (begrenzte Zeit, wenig HW), feasible (begrenzte Zeit und begrenzte Ressourcen) c. Welche Algorithmen, die time bzw...

Description

Prüfungsfragen HSO 1. Scheduling: a. Was ist Scheduling? -> zeitliche Zuordnung einer Menge von Aufgaben. Planung, wann eine Operation durchgeführt wird. b. Welche Prinzipien gibt es für das Scheduling-Problem? -> resource-constraint (begrenzte Ressourcen, kürzeste Zeit), time-constrained (begrenzte Zeit, möglichst wenig HW), feasible (begrenzte Zeit und begrenzte Ressourcen) c. Welche Algorithmen, die time - bzw. resource-constraint, feasible sind, gibt es? -> resource-constrained: ASAP-HC, List-Scheduling (Hu und allgemein) time-constrained: FDS, feasible: ILP, AFAP? d. Ist das Scheduling-Problem ein NP-schweres Problem? -> allgemein Ja. e. Wie funktioniert ASAP-HC? -> Input: DFG, Output: Schedule mit minimalem D, Ablauf: stack und von oben nach unten Nachfolgeoperation von o_i betrachten und Schedulezuweisung (Folie22) f. Wie funktioniert List-Scheduling? -> Sortieren nach Prioritätsfunktion, PF bestimmt Verschiebung von Operation im Konfliktfall, Prioritäten: Urgency (Pfadlänge zum Ende), Mobility (kritischer Pfad) Folie27 i. Hu-Algo? Wie durchgeführt? 1. Durchführung? -> V = alle Knoten, V_ready = einplanbare Op. (Vorgänger abgearbeitet), V_sched = Op., die in c noch eingeplant werden müssen, V_sel = in c bereits schon eingeplant. Sortiere nach PF, solange noch Op. und FE für c verfügbar plane o_i ein. 2. Einschränkung? -> nur ein Typ von funktionellen Einheiten u. Nachfolgerknoten DFG, Aufstellung mit Prioritätsfunktion, 4. Was ist der Vorteil von Hu zu ASAP-HC? -> Beachtung des kritischen Pfads durch PF (bei ASAP-HC keine Priorität für Op. von kritischem Pfad) 5. Wie wird der kritische Pfad berücksichtigt? -> durch Prioritätsfunktion Mobility 6. Kritischer Pfad auf Folie 27 zeigen. -> längster Pfad von unten angefangen, kritischer Pfad ist der Pfad, durch den die Gesamtzeit der Ausführung verlängert wird ii. Allgemein? 1. Durchführung? -> V_mult = bereits geplant, aber im aktuellen Zeitschritt noch nicht beendet, phicycle = Zeitpunkt der Ausführung bezogen auf Beginn von Taktzyklus c (Taktzyklus c wird in Zeitschritte unterteilt), Ablauf: Sortieren nach PF, prüfe auf freie HW, wenn Op. zu Beginn von c ausführbar dann ausführen + prüfen auf Multicycle und evtl. Markierung als Multicycle, ansonsten prüfen, ob Op. mit Chaining in c ausführbar ist, am Ende noch prüfen, ob Multicycle fertig in aktuellem Zeitschritt 2. Multi-cycle-OPs: Wie? Welcher Code/Variablen tut das? Wie wird realisiert, dass Multi-cycle über mehrere Taktschritte gehen? -> Op. dauert vielfaches k von einem Taktzyklus, Hinzufügen zu V_mult wenn Verzögerung/Ausführungszeit > t cycle und am Ende vom Algo immer aktuelles c prüfen, ob eine Multicycle fertig ist, um HW freizugeben

1

3. Chaining: Wie? Welcher Code/variablen tut das? Kann HW nach einer Operation dann freigegeben werden? Zeige im Code. Was ist phicycle(c, o_i)? (Formel auf Folie 32) -> mehrere Op. in einem Zeitschritt, falls Op. nicht in c ausführbar ist, prüfen ob Chaining Op. (phicycle + Ausführzeit Urgency = Pfadlänge bis zum Ende, Mobility = kritischer Pfad, Prioritätsfunktionen für Hu und allgemein List-Algo, Mobility berücksichtigt kritischen Pfad g. Erkläre Force-Directed-Scheduling, auch anhand Folie 39/40, i. Durchführung? -> 1. Berechnung ASAP u. ALAP 2. Erstellung Distributionsgraph für jede optype, 3. Berechnung SelfForce (globale Veränderung) 4. Berechnung Auswirkung von Vorgänger u. Nachfolger (PredForce, SuccForce), 5. Berechnung Gesamtkraf ii. Was sind die Distributionsgraphen? Was ist DG(op)? -> Aufsummierte Wahrscheinlichkeiten einer Op. für einen Zeitschritt i iii. Wie ergeben sich die Wahrscheinlichkeiten? -> prop(op,i) = 1/(alap(op)-asap(op)+1), zwischen asap(op) und alap(op), sonst 0 iv. Begriffe: Selforce (qualitativ erklären) anhand CG erklären, Force, TotalForce (SuccForce u. PreForce), Kann Force auch null werden? Auch anhand Folie 37 -> Selforce = hypothetische Festlegung einer Operation op auf Zeitschritt i, globale Veränderung jedes DG(i), globale Optimierung für alle Op. separat ber. Force = Ber. Auswirkung auf Vor- u. Nachfolger-Op., Op. auf Zeitbereich festgel. PredForce = Summe der Forces für Predecessor (Vorgänger-Op.) SuccForce = Summe der Forces für Successor (Nachfolger-Op.) TotalForce(op) = SelfForce(op) + PredForce(op) + SuccForce(op) v. Komplexität von FDS? -> O(D*n^3), D = Timing Constraints, n = Anzahl Operationen h. AFAP: i. Durchführung? -> CFG u. Nebenbedingungen (Single-Assignment, Frequenz- o. Ressourcenvorgabe) gegeben, Intervalle durch Verletzung der NB, Bilde Cliquen über Intervalle (für jeden Pfad einzeln), Bestimme cuts der Cliquen auf Pfad (gleichzeitige Überlagerung aller Cliquenknoten im Intervallgraph), Cutgraph erstellen, daraus FSM ableiten (jeder Cut bedeutet Zustandsänderung) ii. Auf welchem Graph wird das ausgeführt? Was bedeutet der Graph? -> Kontrollflussgraph (CFG), V = Operationen, E = Präzedenzrelationen, Kante von oi nach oj, wenn oj nach oi ausgeführt werden muss iii. Welches Problem wird gelöst? -> Maximum Cliquen Problem 2. Allokation/Binding a. Welche Ansätze gibt es?

2

-> gleichzeitige Betrachtung aller Allokations-/Bindingaufgaben und Dekompositionsansatz b. Wie funktioniert ILP/globale Ansatz? i. Vier Gleichungen erklären bzw. Folie 16 bei Allokation/Binding ->1. xi,c = 1, wenn Op. i in c beginnt, über alle Zeitschritte summiert, muss für o i xi,c = 1 sein, 2. Zeitschritt in dem o i beginnt – Zeitschritt in dem o j beginnt wenn Schedule von Objekt in c und c ist aktuell, wenn Variable in c lebendig v. Nebenbedingungen? -> jedes Objekt i genau auf ein Modul m j (Entscheidungsvariable xi,i=1 wenn i auf mj), jedes Modul j zu beliebigen Zeitpunkt höchstens ein Objekt i

vi.

Kostenfunktion mit doppelter Summe erklären. Wie/Warum wird linearisiert? -> Verbindung zwischen mj1 und mj2 mit Kosten cj1,j2. Gesamtkosten:

vii. viii.

Multiplexerkosten? -> sind proportional zu Anzahl von 2-Punkt-Verbindungen, die an Modul j

enden: ix. Was macht man um Formal als ILP darzustellen? x. Greedy als erste Lösung dann iterative Optimierung c. Was ist Branch&Bound? (aus der Übung) -> mathematisches Verfahren, um für gegebenes ganzzahliges Optimierungsproblem eine beste Lösung zu finden (Entscheidungsbaum-Verfahren) i. Was wird dadurch erreicht? Was bedeutet Linearität bezüglich der Lösung? -> Lösungsraum wird eingegrenzt ii. Ablauf? -> Branch (Verzweigung) und Bound (Abgrenzung), Ziel ist es, Zweige des Entscheidungsbaums als suboptimal zu identifizieren und dadurch das Problem immer weiter einzuschränken d. Was ist der Dekompositionsansatz? -> getrennte Betrachtung von Allokation- und Binding-Aufgaben i. Wie funktioniert der? (Folie 21)

3

-> Konstruktion Compatibility Graph für Ops., Verträglichkeitsrelation: Kante wenn Ops. in unterschiedlichen Zeitschritten oder auf unterschiedlichen Programmpfaden liegen, Bestimmung eines Minimum Cique Partitionings ii. Was genau wird betrachtet? Was gibt es für Einheiten? -> Operationen und funktionelle Einheiten, Variablen und Register e. Was für ein Problem löst man bei der Optimierung? Welches Problem wird bei Tseng/Siewiorek gelöst? -> Minimum Clique Problem f. Womit wird das Minimum Clique Problem gelöst? -> mit Heuristik bspw. Tseng/Siewiorek g. Tseng/Siewiorek: i. Wie geht der Algo? (auch anhand Folie 21/22) Warum zuerst Knotenpaar 13 und nicht zb. 2-3? -> Bestimme die Menge gemeinsamer Nachbarn von je zwei Knoten, Kanten löschen von zwei Knoten, Knoten verschmelzen zu Superknoten, Knaten wieder hinzufügen. Knotenpaar mit meisten gemeinsamen Nachbarn zuerst ii. Was bedeutet Common Neighbor? -> gemeinsamer Nachbar, wenn Knoten v1 u. v2 mit v3 verbunden sind ist v3 gemeinsamer Nachbar von v1 u. v2 iii. Was gilt für die Operationen innerhalb einer Clique? Was bedeuten die Cliquen? Werden Operationen im gleichen Zeitschritt ausgeführt? Was ist eine Clique? -> Op. innerhalb einer Clique werden auf gleicher FE ausgeführt, Clique entspricht somit einem HW-Modul, Operationen derselben Clique werden zu unterschiedlichen Zeitschritten ausgeführt (Verträglichkeitsrelation) iv. Was könnte noch für die Operationen gelten? v. Welche Kante wird gelöscht, welche ersetzt? -> Kante zwischen s1 u. s2 wird gelöscht: Superknoten, Kante zwischen Common Neighbors wird ersetzt vi. Wie viele FEs entsprechen einem Superknoten? -> eine FE entspricht einem Superknoten vii. Wie viele FEs sind am Ende notwendig? -> Anzahl der Cliquen = Anzahl der FEs viii. Nimmt man Tseng/Siewiorek auch für Variablen-Register? -> ist möglich, dann aber kein Intervallgraph mehr, Alternative ist Lef-EdgeAlgo (auch für nicht zusammenhängende Lebenszeiten von Variablen) ix. Ist die endgültige Lösung optimal? -> Tseng Siewiorek ist nur Heuristik, Lef-Edge ist optimal h. Left-Edge-Algo? -> Zur Allokation/Binding von Datenträgern(=Register) i. Ablauf? -> ausgehend von Lebenszeiten der Variablen, Sortierung von links nach rechts, Intervall untereinander wenn keine Überschneidung, dann nächstes Intervall, jedes Intervall entspricht dann einem Register i. Wie funktioniert der Realloktionsalgorithmus (anhand Folie)? -> Ähnlich Kernighan-Lin Verfahren, Iterativer Algorithmus, Ablauf: ausgehend von Initiallösung aus Dekompositionsansatz, zwei Operationen desselben Typs vertauschen und schauen, ob Kosten geringer, wenn ja dann merke dir neue Position der Ops. und vertausche am Ende des Algo wirklich i. Warum macht man Reallokation? -> iterative Verbesserung des Dekompositionsansatzes (noch kein optimales Ergebnis geliefert)

4

ii.

Warum kann man den Datenpfad noch optimieren? Nach was wird optimiert? -> weil Dekompositionsansatz kein optimales Ergebnis liefert (Tseng/Siewiorek ist Heuristik) iii. Wie wird vorgegangen? Kann man alles wild vertauschen? -> Vertauschung von zwei Operationen, die denselben Typ haben und im gleichen Zeitschritt geplant sind (da sonst HW doppelt belegt), Operationen dürfen vertauscht werden, also auf welcher HW sie ausgeführt werden iv. Was verbessert sich? -> Kosten (hypothetische HW-Kosten bezüglich Verbindungskosten für Busse/Multiplexer) v. Ist die Lösung optimal? 3. Register-Transfer-Synthese: Retiming: a. Was ist Retiming? Was ist das Ziel/Warum macht man das? -> Transformation einer sequentiellen Schaltung auf RT-Ebene, Register über kombinatorische Blöcke bewegen, Ziel: Minimierung von Anzahl Register und Zyklendauer b. Was ist legales Retiming? Wann macht man das? -> Legales Retiming: wenn Knoten Zeitbedingung verletzt (bzw. gegebene Zyklendauer eingehalten werden soll), Verschieben von Registern über Ausgang zu Eingang i. In welche Menge werden Knoten, die die Zeitbedingung verletzen verschoben? (anhand Code Parameter zeigen), legales Retiming anhand Algo zeigen -> Vv, Ablauf: ti für jeden Block berechnen, Blöcke mit Zeitbedingungsverletzung in Vv, Prüfen auf V v = leer, Prüfen auf Schaltung in Ausgangszustand, Prüfen ob Block von Eingang zu Ausgang Zeitbedingung verletzt, Retiming aller Knoten, die Zeitbedingung verletzen, wenn Ausgangknoten geretimed dann... ii. Welche Bedingungen/Eigenschaften gelten für legales Retiming? -> die Anzahl der über den Ausgang bzw. Eingang geschobenen Register müssen gleich sein, neue Anzahl der Register nach Retiming iii.

Abbruchbedingungen des Algo? Erkläre zweite for-Schleife innerhalb der Haupt-for-Schleife für das legale Retiming? -> 1. Abbruchbed.: postiv, wenn Retiming gefunden, 2. Abbruchbed.: negativ, wenn Schleifendurchläufe > Anzahl Blöcke, also Schaltung wieder in Ausgangszustand, kein Retiming gefunden, 3. Abbruchbed.: negativ, wenn registerfreier Pfad mit logischem Block von PI zu PO mit Zeitbedingungsverletzung, weil kein Registerschieben auf registerfreiem Pfad mgl., kein Retiming gefunden iv. Beispiel zu legalem Retiming c. Was ist peripheral Retiming? -> alle Register innerhalb der Schaltung entfernt und vor Eingänge/Ausgänge gesetzt, wenn zuerst peripheral Retiming und anschließend legales Retiming, dann ist I/OVerhalten gleich der Originalschaltung i. Welche Bedingungen gelten für Peripheral Retiming? -> wenn mehrere Pfade zwischen Eingang i und Ausgang j, dann müssen alle gleiches Gewicht (Pfadgewicht = Anzahl Register auf Pfad, Kantengewicht = Anzahl Register auf Kante) haben. Anzahl Register auf Weg von i zu j muss gleich alphai (Register nach jedem Eingang) + betaj (Register vor jedem

ii.

Ausgang) sein. Welche Eigenschaften gelten für peripheral Retiming?

5

-> Über Ausgang u. Eingang geschobenen Register sind 0, Anzahl der Register auf den Kanten e + über v geschobene Register + über u geschobene Register müssen gleich 0 sein, für die Kanten aller Knoten u und v außer PI und PO iii.

Ablauf von peripheral Retiming? Was wird im 4. Schritt von peripheral Retiming gemacht? -> 1. Prüfe Theorem 1 für jeden Eingang/Ausgangpfad, 2. Für alle Eingänge i und Ausgänge j alpha_i und beta_j bestimmen, 3. Alpha_i Register hinter jeden Eingang i, beta_j Register vor jeden Ausgang j, entferne alle anderen Register, 4. Resynthetisiere die kombinatorische Schaltung mit Logikoptimierung, 5. Prüfen auf synchrone Schaltung, 6. Bestimme legales Retiming iv. Beispiel zu peripheral Retiming v. Was ist eine kombinatorische Schaltung und wie erhält man sie? -> kombinatorische Schaltung besitzt keine Speicherblöcke (Register), sondern nur Kombinatorik, erhält man durch ein peripheral Retiming d. Was darf sich nicht verändern? -> I/O-Verhalten der Schaltung, funktionales Verhalten der Schaltung 4. Technologieabbildung -> drei Teilprobleme: Partitionierung (Aufeilung in Untergraphen), Dekomposition (Untergraph umsetzen in Graph, der aus Basisgattern der Zellbibliothek aufgebaut ist), Covering (Aufbau des Untergraphen aus Bibliothekszellen, Kostenminimierung) a. Was für ein Verfahren für Standardzellen? -> Dynamisches Programieren (Tree-Covering): bottom-up Strategie liefert optimale Teillösungen, die zur optimalen Gesamtlösung(Teilbaum) führen, jedoch dann nicht optimal mehr bei Zusammensetzen der Teilbäume zur Gesamtschaltung b. Was ist das charakteristische an diesem Verfahren? -> optimale Lösung des Gesamtproblems setzt sich aus den optimalen Lösungen der Teilprobleme zusammen c. Wie ergeben sich die Kosten? Wieso sind größere Bäume günstiger? -> selbe Fläche mehr Funktionen, statt einzelne Funktionalität wird diese gemeinsam in einer Standardzelle integriert d. Erkläre Vorgehen anhand Folie 8/18. Wovon abhängig, ob das alles gut funktioniert? -> Folie18 Algo: Gatter, Kosten für jeden Knoten aufstellen von unten nach oben, alle Möglichkeiten, Auswahl der Mgl. mit geringsten Kosten, Kosten addieren, Qualität der Zellenbibliothek e. Warum werden Bibliothekszellen eingesetzt? -> um Kosten zu verringern: größere Bäume bringen mehr Funktionalität auf gleicher Fläche f. Was unterscheidet Subject Graph vom ursprünglichen Graph? -> Partitionierung in Teilbäumen Wald setzt sich aus Bäumen zusammen g. Wovon ist das Ganze abhängig? -> vorhandene Bibliothekszellen, Qualität der Zellen h. Was wird dabei optimiert? -> Fläche, Timing, Verlustleistung i. FPGA Logikabbildung 4-Eingang-LUT vs. 5-Eingang-LUT -> Bibliothekgestützes Mapping nicht sinnvoll, daher Ziel: Dekomposition in realisierbare Knoten (Minimierung Anzahl LUTs, evtl. Minimierung Anzahl Eingänge des Root-LUTs) 5. Physikalischer Entwurf -> drei Basisschritte: Partitionierung (Teile und Herrsche), Floorplanning und Platzierung (Anordnung der Komponenten), Verdrahtung (Festlegen der Verbindungsanordnung) a. Unterschied zwischen Floorplanning und Platzierung? -> variable Modulgrößen und Drehbarkeit bei Floorplanning

6

b. Netzlängen/Netzdichte-Modelle -> Netzlänge: Source-Drain Baum, MAB, Minimaler Steinerbaum, Gewichteter Umfang, Netzdichte: Maximum-Cut-Line (Anzahl Signalnetze, die vertikale bzw. horizontale Linie schneiden und diese minimieren), Maximale Dichte (Netze pro Kanal und möglichst gleichmäßige Verteilung) c. Welche Arten von Platzierungsalgorithmen gibt es? Was für Ansätze für Platzierung? (alle aufzählen) Wie mache ich die Anordnung? -> ILP-Verfahren (quadratische Zuweisung), Stochastische Verfahren (Simulated Annealing), Mincut Verfahren, Kräfe-basierende Verfahren d. Erkläre quadratische Zuweisung (Folie 37). Warum diese Formeln? -> s Slots und n Module, bilde s auf n ab bzw. Zuweisung mit Ziel Verdrahtungslänge zu minimieren, Formel: Summiert über alle Mgl. von Slots zu Modulen bzw. umgekehrt, Entscheidungsvariable = 1 wenn Modul auf Slot und dann mit Länge und Anzahl Verbindunge multipliziert, NP-schweres Problem i. Ist quadratische Zuweisung Netzlängen/-dichten basiert? -> Länge, da diese in der Kostenfunktion berücksichtigt (d ij) e. Erkläre das Simulated Annealing. -> stochastisches Verfahren aus Festkörperphysik, Festkörper stark erhitzt und dann langsam abgekühlt, über Temperaturabschwächung neue Lösungen geprüf und evtl. (Metropolis-Kriterium) angenommen i. Ablauf? -> Startzustand und Starttemperatur festlegen, dann wiederhole bis Konvergenz (also keine Verbesserung nach drei aufeinanderfolgenden Abkühlungen) whileSchleife und Update Temperatur, while-Schleife: solange kein stationärer Zustand erreicht, modifiziere aktuellen Zustand und prüfe Verbesserung mit Metropolis-Kriterium und einem Vergleich mit Zufallszahl zwischen 0 und 1, wenn bessere Lösung behalte modifizierten Zustand bei ii. Formeln von Simulated Annealing erklären -> Kostenfunktion c: k1*cost1+k2*cost2+k3*cost3, cost1 = Summe über xSpannweite * Breite + ySpannweite* Höhe, cost2 = Summe aller Überlappungen von Modulen, cost3 = Summe der Überschreitungen der Reihenlängen aller Reihen iii. Wie wird M gewählt bei Stationarystate? -> Anzahl der Module? Stationary_state: [100...1000]* |M| iv. Was sagen random_modify und Stationarystate aus? -> random_modify: Veränderung des aktuellen Zustands (Verschieben eines einzelnen Moduls, Vertauschen zweier Module, Rotieren eines Moduls), stationary_state: Schleife so of ausführen, bis stationärer Zustand erreicht, dann Temperatur updaten v. Was sagen die eingebetten Schleifen (Folie 50) aus? -> modifiziere aktuellen Zustand prüfe mit Zufallszahl und Metropolis-Kriterium, ob neuer Zustand besser, wenn ja behalte neuen Zustand bei vi. Was ist das Metropolis-Kriterium? -> steuert Akzeptanz neuer Lösungen, Algo konvergiert theoretisch asysptotisch gegen globales Optimum, unter Umständen auch Verschlechterungen akzeptiert, umso höher T wird, umso kleiner wird der Ausdruck vii.

Abbruchbedingungen? -> zuerst while-Schleife keine Verbesserung mehr (stationary_state bleibt) dann durch Erreichung convergence (also drei Mal aufeinanderfolgende Temperaturabkühlungen keine Verbesserung mehr)

7

f. Welche beiden Schritte zur Verdrahtung? -> globales Routing, detailliertes Routing g. Was ist globales/detailliertes Routing? -> globales Routing: „loser“ Weg für jedes Netz, jedem Netz eine Liste von Kanälen zugeteilt, ohne exaktes Layout der Leitungen im Kanal, detailliertes Routing: exaktes Layout für jedes Netz innerhalb der zugeteilten Kanäle h. Welche Netzklassen/-typen? -> 2-Terminal, Mehrterminal i. Beispiel für globales Routing? -> Steinerbaum, Lees/Maze-Algo (für 2-Terminal-Netze), Hightower-Algo j. Was ist das Steinerbaum-Problem? Wie wird es gelöst? Wofür verwendet? -> für endlich viele gegebene Punkte (Terminals) findet der minimale Steinerbaum einen Graphen, der diese Punkte verbindet und das kürzeste Wegnetz bildet. S ist Teilmenge der Knoten von G (>1), Steinerbaum Ts bezüglich S ist ein Baum in G der S aufpspannt, minimaler Steinerbaum ist Baum mit minimalen Kantengewicht unter allen möglichen Steinerbäumen i. Ablauf? -> 1. Bestimmung Shortest-Distance-Graph + Länge als Gewicht, 2. Berechnung MAP, 3. Pfade auf MAP wieder einfügen, 4. Wiederum MAP von neuem Baum berechnen, 5.alle Blätter löschen die nicht die nicht Knoten von S sind ii. Warum ist Steinerbaum NP-vollständig? -> Falls die Anzahl der Steinerknoten nicht beschränkt bzw. exponentiell groß ist iii. Steinerknoten auf Folie 69 zeigen -> Steinerknoten ist definiert als Knoten v in Ts dessen Kantenanzahl >= 2 ist und v nicht zur Menge S gehört k. Beispiel für detailliertes Routing? -> Lef-Edge-Algorithmus, Greedy, Constraint-Graph basierende Algos, Hierarchische Routingalgos. l. Wie funktioniert Left-Edge? -...