Die vorliegende Arbeit beschreibt ein Verfahren zur Optimierung der Signallaufzeit in der Layoutsynthese.
Zunächst wird die Verdrahtung einer Schaltung während des Plaziervorgangs mithilfe von Steinerbäumen realistisch modelliert. Weiterhin wird eine einfache Möglichkeit angegeben, das Elmore-Delay, welches zur Bestimmung der Laufzeit einer Schaltung verwendet wird, für ein Netzmodell mit Baumstruktur zu berechnen. Eine Sensitivitätsanalyse in Bezug auf die Längen der Baumkanten und ein Kriterium zur Analyse der möglichen Signallaufzeitverbesserung werden vorgestellt.
Diese Informationen werden in einem kraftbasierten Algorithmus zur laufzeitoptimierten Plazierung eingesetzt. Bei Tests auf einem Satz realer Schaltungen zeigt sich, daß deutliche Verbesserungen im Vergleich zu früheren Ansätzen erzielt werden können.
Inhaltsverzeichnis
1 Einleitung
2 Plazierproblem
2.1 Eingangsdaten
2.1.1 Module
2.1.2 Netze
2.1.3 Plaziergebiet
2.2 Variablen
2.3 Nebenbedingungen
2.3.1 Dichte
2.3.2 Kraft
2.4 Zielfunktion
2.4.1 Netzmodelle
2.4.2 Berechnung der Netzverzögerung (Elmore-Delay)
2.4.3 Laufzeit des längsten Pfades
2.4.4 Quadrat der Länge der Verdrahtung
2.5 Globalplazierproblem und Hilfsproblem
3 Lösungsverfahren
3.1 Der Algorithmus von Eisenmann [Eis99]
3.2 Laufzeitanpassung von Eisenmann [Eis99]
3.3 Laufzeitoptimierung
3.3.1 Nachteile des bisherigen Lösungsansatzes
3.3.2 Einführung von Kantengewichten
3.3.3 Optimierpotential und Sensitivität der Kanten
3.3.4 Schlupf und kritischer Wert
3.3.5 Gewichtsfunktion und Anpassung des Algorithmus
4 Ergebnisse
A Anhang
A.1 Graphen
A.2 Wege, Kreise und Pfade
A.3 Zusammenhängende Graphen und Bäume
Zielsetzung und Themen
Die vorliegende Arbeit zielt darauf ab, die Signallaufzeit bei der Layoutsynthese für integrierte Schaltungen durch ein verbessertes Plazierverfahren zu minimieren. Die zentrale Forschungsfrage ist, wie bestehende kraftbasierte Algorithmen so optimiert werden können, dass sie gezielt kritische Signalpfade verkürzen, anstatt nur die gesamte Verdrahtungslänge zu minimieren.
- Optimierung der Signallaufzeit mittels kraftbasierter Algorithmen.
- Modellierung der Verdrahtung durch Steinerbäume und Elmore-Delay zur Verzögerungsberechnung.
- Entwicklung einer Sensitivitätsanalyse zur Identifikation und Gewichtung kritischer Netze.
- Implementierung und Validierung des Verfahrens an realen Schaltungs-Benchmarks.
Auszug aus dem Buch
3.3.2 Einführung von Kantengewichten
Um dem im vorigen Kapitel gezeigten Problem entgegenzuwirken, werden die Netze nun, wie in Kapitel 2.4.1 beschrieben, durch Steinerbäume modelliert (siehe beispielsweise in Tabelle 7 Abbildung a) b)). Anschließend werden für alle Kanten e ∈ Evn der Steinerbäume vn (n ∈ N) Kantengewichte ge ∈ R+ eingeführt:
Lgn(p) = Σn∈N Σe∈Evn l²e → Lge(p) := Σn∈N Σe∈Evn ge l²e (46)
Diese Gewichte ermöglichen es uns, gezielt Kanten zu verkürzen, die großen Einfluß auf l(p) haben. In unserem Beispiel aus Tabelle 7 Abbildung b) kann man nun der langen Kante ε* zwischen dem Steinerknoten und dem Modul m3 ein hohes Gewicht ge* geben. ε* verkürzt sich stark und verbessert damit die Laufzeit des längsten Pfades (siehe Tabelle 7 Abbildung c).
Zusammenfassung der Kapitel
1 Einleitung: Beschreibt die Rolle der Layoutsynthese im Entwurfsprozess von integrierten Schaltungen und motiviert die Notwendigkeit laufzeitoptimierter Plazierung.
2 Plazierproblem: Definiert die mathematischen Grundlagen, inklusive Modellen für Module, Netze, das Plaziergebiet sowie die mathematische Formulierung der Zielfunktionen und Nebenbedingungen.
3 Lösungsverfahren: Erarbeitet eine Heuristik zur Optimierung der Signallaufzeit, indem bestehende kraftbasierte Algorithmen um eine laufzeitbasierte Kantengewichtung erweitert werden.
4 Ergebnisse: Präsentiert die praktische Implementierung und evaluiert die Leistungsfähigkeit der Methode anhand von Industriestandard-Benchmarks im Vergleich zu bisherigen Ansätzen.
A Anhang: Bietet ergänzende mathematische Definitionen zu Graphen, Wegen, Kreisen und Bäumen, die als Grundlage für die Modelle dienen.
Schlüsselwörter
Layoutsynthese, Signallaufzeit, Plazierung, Steinerbäume, Elmore-Delay, kraftbasierte Algorithmen, Laufzeitoptimierung, Kantengewichtung, Sensitivitätsanalyse, kritischer Pfad, Schaltungsentwurf, Signalverzögerung, Modulplazierung, Benchmark-Schaltungen, Netzmodellierung.
Häufig gestellte Fragen
Worum geht es in der Arbeit grundsätzlich?
Die Arbeit befasst sich mit der Optimierung der Signallaufzeit bei der Layoutsynthese von integrierten Schaltungen durch die Verbesserung von Plazierverfahren.
Was sind die zentralen Themenfelder?
Im Fokus stehen die mathematische Modellierung von Schaltungen, die Berechnung von Signalverzögerungen (Elmore-Delay) sowie die Entwicklung effizienter Optimierungsalgorithmen für die Modulanordnung.
Was ist das primäre Ziel der Arbeit?
Das primäre Ziel ist es, die Laufzeit des längsten Pfades in einer Schaltung zu minimieren, um die Schaltgeschwindigkeit des Chips zu erhöhen.
Welche wissenschaftliche Methode wird verwendet?
Die Arbeit nutzt kraftbasierte Algorithmen, die durch eine dynamische Gewichtung der Kanten basierend auf einer Sensitivitätsanalyse für kritische Pfade erweitert wurden.
Was wird im Hauptteil behandelt?
Der Hauptteil widmet sich der Modellierung des Plazierproblems, der Analyse des Elmore-Delays, der Vorstellung des Eisenmann-Algorithmus und der Entwicklung der neuen Optimierungsmethode mittels Kantengewichten.
Welche Schlüsselwörter charakterisieren die Arbeit?
Wichtige Begriffe sind Layoutsynthese, Signallaufzeit, Plazierung, Steinerbäume, Elmore-Delay, kraftbasierte Algorithmen und Laufzeitoptimierung.
Warum ist die Unterscheidung zwischen dem globalen Plazierproblem und dem Hilfsproblem wichtig?
Das globale Plazierproblem ist NP-vollständig. Die Arbeit definiert ein quadratiertes Hilfsproblem, das mathematisch effizienter lösbar ist, um als Basis für den heuristischen Optimierungsansatz zu dienen.
Wie genau wird der "Schlupf" (Slack) zur Laufzeitoptimierung eingesetzt?
Der Schlupf berechnet für jedes Netz die Differenz zwischen der geforderten Ankunftszeit und der tatsächlichen Ankunftszeit eines Signals. Ein geringer Schlupf identifiziert kritische Netze, die dann im Optimierungsprozess stärker gewichtet werden.
- Arbeit zitieren
- Milan Chaudhuri (Autor:in), 2003, Laufzeitgesteuertes Plazieren: Minimierung der Verzögerung des längsten Pfades in der Layoutsynthese, München, GRIN Verlag, https://www.grin.com/document/11555