HSO

Question 1

Dijkstra

Answer 1

Breitensuche, bestimme Distanzen vom Startknoten zu alle anderen Knoten, wiederhole mit dem Knoten, der die geringste Distanz hat. Aktualisiere Vorgänger jedesmal wenn eine geringere Distanz gefunden wird.

Question 2

Overlap-Graph

Answer 2

Kante existiert zwischen Linien, die sich NUR überschneiden

Question 3

Containment-Graph

Answer 3

Kante existiert zwischen Linien, wenn eine Linie die andere überdeckt

Question 4

Intervall-Graph

Answer 4

Kante existiert zwischen Linien, wenn eine Linie die andere überschneidet oder überdeckt

Question 5

Tiefensuche

Answer 5

Globaler Routing,

Question 6

Breitensuche

Answer 6

Dijkstra, Prim

Question 7

Prim Algorithmus

Answer 7

Minimal aufspannender Baum, bestimme Knoten mit kürzesten Weg zum Baum/Startknoten, füge den Knotem dem Baum hinzu. Warum ElogV?

Question 8

Clique-Algorithmus

Answer 8

Findet maximale Clique im Intervallgraph: Sortiere linke und rechte Endpunkte aller Linien und iteriere über Endpunkte. Links: +1, Rechts: -1, die Summe ist gleich der Größe der maximalen Clique

Question 9

Kruskal Algorithmus

Answer 9

Sortiere Kanten, bilde eine Menge für jeden Knoten, vereinige Mengen, die mit der kürzesten Kante verbunden sind

Question 10

High-Level Synthese

Answer 10

Ergebnis: Kontroller- und Datenpfadarchitektur. Scheduling, Allokation und Binding. Optimierung innerhalb mehrere Taktzyklen

Question 11

RTL Synthese

Answer 11

Ergebnis: Logikfunktionen und Register. Optimierung innerhalb eines Taktzyklus

Question 12

Logik Synthese

Answer 12

Ergebnis: minimale Logikfunktionen. Minimierung der kombinatorischen Logik. Optimierung innerhalb komb. Logik

Question 13

Technologieabbildung

Answer 13

Ergebnis: Abbildung auf Standardzellen, FPGA usw. Optimierung von Fläche, Verdrahtung, Performanz

Question 14

Feasible Scheduling

Answer 14

Aufgaben unter Einhalten der Präzedenzrelationen mit M Prozessoren in D Taktzyklen erledigen.

Question 15

Scheduling - ILP Formulierung

Answer 15

1-Präzedenzrelationen einhalten,

2-Anzahl gleichzeitige Operationen vom gleichen Typ

Question 16

ASAP

Answer 16

exakt, Zeitminimierung ohne Ressourceneinschränkung

Question 17

ASAP-HC

Answer 17

Zeitminimierung mit Ressourceneinschränkung: schedule Operation im nächsten Taktzyklus falls keine Module frei sind

Question 18

List-Scheduling

Answer 18

Resource-constrained, sortiert Operationen nach Pfadlänge zum Ende(Urgency) oder kristischer Pfad(Mobility)

Question 19

Hu’s Algorithmus

Answer 19

exaktes List-Scheduling, Einschränkung auf Baumstrukturen mit fanout<=2

Question 20

Allgemeiner List Scheduling

Answer 20

Multicycle und Chaining auch möglich,
V: nicht scheduled Operationen
V_ready: Operationen mit scheduled Vorgänger
V_sched: Opeartionen, die im aktuellen Taktzyklus scheduled werden
V_mult: multicycle Operationen, die scheduled aber nicht beendet sind
freeze(): belege Modul
unfreeze(): gebe Modul frei
unused(): gibt freie Module zurück

Question 21

Force-Directed Scheduling

Answer 21

Berechne ALAP und ASAP, dann SelfForce, PredecessorForce, SuccessorForce. Time-constrained, Ressourcen-optimierung. Distribution-Graph wird für jede Operation berechnet: gibt Informationen zu wie viele Module man vermutlich braucht. Minimierung des Maximums über alle Taktzyklen führt zu minimierung der Ressourcen

Question 22

AFAP

Answer 22

Kontrollfluss orientierter Scheduling, markiere Intervalle, die die Nebenbedingungen verletzen auf allen Programmpfaden(Schleifen, If-Branches). Finde Cliquepartitioning und schneide durch Cliques

Question 23

Urgency

Answer 23

Pfadlänge zum Ende

Question 24

Mobility

Answer 24

0 auf dem kritischen Pfad

Question 25

Binding

Answer 25

Zuordnung von Operationen und Variablen zu FEs und Register

Question 26

Allokation

Answer 26

Auswahl von FEs aus der Bibliothek

Question 27

Ansätze für Allokation und Binding

Answer 27

Globale Optimierung: ILP-Formulierung oder Greedy-Ansatz als Initiallösung Dekompositionsansatz: Bilde Compatibility Graph, finde Clique-Partitioning, jede Clique ist ein Modul

Question 28

Compatibility-Graph

Answer 28

Operationen, die auf demselben Modul gebunden werden können(unterschiedliche Taktzyklen oder Programmpfade), sind verbunden

Question 29

Super-Graph

Answer 29

Graph, wo mehrere Knoten zu einem Knoten zusammengefasst werden können

Question 30

Tseng-Sieworek

Answer 30

Bilde Supergraph, füge Knoten zusammen, die die meiste gemeinsame Nachbarn haben

Question 31

Left-Edge Algorithmus (Binding)

Answer 31

Sortiere Variablen nach Anfang der Lebenszeit, Wähle immer die erste Variable, die nach dem Ende der aktuellen Lebenszeit anfängt

Question 32

Reallokation

Answer 32

Vertausche Operationen im selben Taktzyklus zwischen Modulen paarweise und wähle das Paar aus mit dem höchsten Gewinn. Beende wenn kein Gewinn mehr möglich ist

Question 33

Legales Retiming

Answer 33

r(v) constant über alle PI und PO, alle Kanten haben nichtnegative Anzahl von Register

Question 34

Peripheral Retiming

Answer 34

r(v)=0 für alle PI und PO, keine Register zwischen Module, die kein PI oder PO sind. Nur möglich wenn alle Pfade zwischen Eingang i und Ausgang j gleiche Anzahl von Register haben

Question 35

Retiming

Answer 35

Verschieben von Register zur Optimierung. Peripheral Retiming -> Optimierung der komb. Logik -> legales Retiming