Algorithmensynthese

  • Überblick digitale Synthese
  • Algorithmensynthese
  • Beispiel für einen Algorithmus
  • Abhängigkeitsgraph
  • Schleifen
  • Bedingte Verzweigungen
  • Schritte der Algorithmensynthese
  • Takt und kombinatorische Verzögerung
  • Scheduling – Erstellung eines Taktschemas
  • Scheduling Variante 1
  • Scheduling Variante 2
  • Scheduling Variante 3
  • Entwurfsraumexploration
  • Signalflussgraph
  • Varianten im Entwurfsraum
  • Pareto-Front
  • Ressourcenreservierung und Ressourcenzuordnung
  • Datenpfad mit Multiplexern
  • Datenpfad mit bidirektionalem Bus
  • Steuerpfad
  • Nachoptimierungsmöglichkeiten
  • Retiming
Startseite
Schritte der Algorithmensynthese Abbildung des Abhängigkeitsgraphen → Zwei Dimensionen: - Taktschema - Hardwareressourcen Abbildung auf Taktschema (Ablaufplanung, Scheduling) → Festlegung, welche Operation in welchem Taktschritt ausgeführt wird Abbildung auf Hardwareressourcen → Festlegung, welche Operation von welcher Ressource durchgeführt wird → Zwei Schritte: - Ressourcenreservierung (resource allocation) - Ressourcenzuordnung (resource assignment)

Um den Algorithmus in eine Schaltung zu überführen, ist es nötig, den Abhängigkeitsgraphen in zwei Dimensionen abzubilden:

  • Taktschema (Performanceoptimierung)
  • Hardwareressourcen (Kostenoptimierung)

Die Abbildung auf ein Taktschema, das so genannte Scheduling, dient der Erstellung eines Zeitplans zur Ausführung des Algorithmus. Die Abbildung auf die vorhandenen Hardwareressourcen legt fest, welche Operation von welcher Ressource ausgeführt wird. Dieses geschieht in zwei Schritten.

  • Ressourcenreservierung (resource allocation)
  • Ressourcenzuordnung (resource assignment)

Die drei Schritte Scheduling, Resource Allocation und Resource Assignment können nicht als unabhängige Teilaufgaben durchgeführt werden, da sie sich gegenseitig stark beeinflussen. So ist die Erstellung eines Taktschemas nur möglich, wenn bereits Ressourcen reserviert sind. Wie viele Ressourcen zu reservieren sind, hängt jedoch vom erstellten Taktschema ab.