Laufzeitgesteuertes Plazieren: Minimierung der Verzögerung des längsten Pfades in der Layoutsynthese

Mémoire (de fin d'études) , 2003 , 49 Pages , Note: 1,8

Electrotechnique

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

• Einleitung
• Plazierproblem
  • Eingangsdaten
    • Module
    • Netze
    • Plaziergebiet
  • Variablen
  • Nebenbedingungen
    • Dichte
    • Kraft
  • Zielfunktion
    • Netzmodelle
    • Berechnung der Netzverzögerung (Elmore-Delay)
    • Laufzeit des längsten Pfades
    • Quadrat der Länge der Verdrahtung
  • Globalplazierproblem und Hilfsproblem
• Lösungsverfahren
  • Der Algorithmus von Eisenmann [Eis99]
  • Laufzeitanpassung von Eisenmann [Eis99]
  • Laufzeitoptimierung
    • Nachteile des bisherigen Lösungsansatzes
    • Einführung von Kantengewichten
    • Optimierpotential und Sensitivität der Kanten
    • Schlupf und kritischer Wert
    • Gewichtsfunktion und Anpassung des Algorithmus
• Ergebnisse
• Anhang
  • Graphen
  • Wege, Kreise und Pfade
  • Zusammenhängende Graphen und Bäume
• Literatur

Zielsetzung und Themenschwerpunkte

Die Diplomarbeit befasst sich mit der Optimierung der Signallaufzeit in der Layoutsynthese. Im Mittelpunkt steht die Entwicklung eines Verfahrens zur Laufzeitgesteuerten Plazierung, das die Verdrahtung einer Schaltung mithilfe von Steinerbäumen realistisch modelliert. Der Fokus liegt auf der Minimierung der Verzögerung des längsten Pfades in der Schaltung, um die Schaltgeschwindigkeit zu verbessern.

• Realitätsnahe Modellierung der Verdrahtung durch Steinerbäume
• Effiziente Berechnung des Elmore-Delays für Baumstrukturen
• Analyse der Sensitivität von Kantenlängen auf die Signallaufzeit
• Entwicklung eines kraftbasierten Algorithmus zur Laufzeitoptimierten Plazierung
• Verbesserung der Laufzeiteffizienz im Vergleich zu früheren Ansätzen

Zusammenfassung der Kapitel

Die Einleitung stellt das Problem der Layoutsynthese und die Bedeutung der Signallaufzeit für die Schaltgeschwindigkeit vor. Kapitel 2 beschreibt das Plazierproblem, indem es die Eingangsdaten, Nebenbedingungen und Zielfunktionen detailliert erläutert. Besonderes Augenmerk liegt auf der neuen Modellierung von Netzen durch Steinerbäume und der Berechnung des Elmore-Delays für diese Strukturen.

Kapitel 3 präsentiert den Algorithmus von Eisenmann, der das Hilfsproblem der Minimierung der Verdrahtungslänge löst. Es wird eine von Eisenmann vorgeschlagene Modifikation zur Laufzeitanpassung vorgestellt, die jedoch einige Nachteile aufweist. Daraufhin wird ein neues Verfahren entwickelt, das die Laufzeitanpassung durch die Einführung von Kantengewichten und die Analyse der Optimierpotential und Sensitivität von Kanten verbessert. Die Gewichtsfunktion zur Bestimmung der Kantengewichte wird erläutert und der Ablauf des neuen Algorithmus skizziert.

Kapitel 4 zeigt die praktischen Ergebnisse der Implementierung des Verfahrens in PLATO und die Ergebnisse der Experimente mit einem Satz von Benchmarkschaltungen. Die Verbesserung der Laufzeiteffizienz im Vergleich zur Laufzeitanpassung von Eisenmann wird anhand von Tabellen und Grafiken dargestellt.

Schlüsselwörter

Die Schlüsselwörter und Schwerpunktthemen des Textes umfassen die Layoutsynthese, Signallaufzeit, Steinerbäume, Elmore-Delay, Laufzeitgesteuerte Plazierung, Kraftbasierte Algorithmen, Optimierung, Sensitivitätsanalyse, Benchmarkschaltungen und Schaltgeschwindigkeit.

• Université: Technical University of Munich (Lehrstuhl für Entwurfsautomatisierung)
• Note: 1,8
• Auteur: Milan Chaudhuri (Auteur)
• Année de publication: 2003
• Pages: 49
• N° de catalogue: V11555
• ISBN (ebook): 9783638176859
• Langue: allemand
• mots-clé: Electronic Design Automation, Layoutsynthese, Layout Synthesis, Plazierverfahren, Placement, Laufzeitanalyse, Timing Analysis