Technische Universität München
Lehrstuhl für Rechnergestütztes Entwerfen

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

Diplomarbeit

von

Milan Martin Chaudhuri

Zusammenfassung
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 ... 5

2 Plazierproblem ... 9
2.1 Eingangsdaten ... 9
2.1.1 Module ... 10
2.1.2 Netze ... 13
2.1.3 Plaziergebiet ... 14
2.2 Variablen ... 14
2.3 Nebenbedingungen ... 14
2.3.1 Dichte ... 14
2.3.2 Kraft ... 16
2.4 Zielfunktion ... 17
2.4.1 Netzmodelle ... 17
2.4.2 Berechnung der Netzverzögerung (Elmore-Delay) ... 19
2.4.3 Laufzeit des längsten Pfades ... 23
2.4.4 Quadrat der Länge der Verdrahtung ... 24
2.5 Globalplazierproblem und Hilfsproblem ... 26

3 Lösungsverfahren ... 27
3.1 Der Algorithmus von Eisenmann [Eis99] ... 27
3.2 Laufzeitanpassung von Eisenmann [Eis99] ... 30
3.3 Laufzeitoptimierung ... 31
3.3.1 Nachteile des bisherigen Lösungsansatzes ... 31
3.3.2 Einführung von Kantengewichten ... 32
3.3.3 Optimierpotential und Sensitivität der Kanten ... 32
3.3.4 Schlupf und kritischer Wert ... 36
3.3.5 Gewichtsfunktion und Anpassung des Algorithmus ... 39

4 Ergebnisse ... 41

A Anhang ... 44
A.1 Graphen ... 44
A.2 Wege, Kreise und Pfade ... 44
A.3 Zusammenhängende Graphen und Bäume ... 45

1 Einleitung
In der langen Kette der Entwurfsschritte einer integrierten Schaltung, befaßt sich die Layoutsynthese damit, aus einer formalen Schaltkreisbeschreibung (zum Beispiel durch einen  Schaltplan gegeben) eine genaue geometrische Beschreibung (Layout) zu erstellen, die dann als Konstruktionsplan für die industrielle Fertigung dient. Abbildung 1 zeigt einen Ausschnitt des Entwicklungsprozesses eines Chips.

!! Abbildung ist nur in der PDF-Download-Version enthalten !!

Abbildung 1: Ausschnitt des Entwicklungsprozesses einer integrierten Schaltung: Die Layoutsynthese behandelt die Erstellung eines Layouts aus einem Schaltplan. Sie kann in mehrere Schritte unterteilt werden (Globalplazierung, Endplazierung und Verdrahtung).

In der Halbleiterentwicklung spielt die Layoutsynthese eine entscheidende Rolle, da das Layout wichtige Größen wie Entwurfsdauer, Herstellungskosten und Schaltgeschwindigkeit maßgeblich bestimmt.

Für den Entwurf eines Digital-Chips wird die Schaltung in funktionelle Einheiten (Module) aufgeteilt. Die elektrischen Verbindungen zwischen den Modulen werden durch Netze charakterisiert. Die Abbildungen in Tabelle 1 zeigen die Module (Rechtecke mit Diagonalen) und Netze (Verbindungslinien zwischen den Modulen) einer Schaltung.

!! Tabelle  ist nur in der PDF-Download-Version enthalten !!

Tabelle 1: Die global plazierten Module der Schaltung ”fract“ [ben92], links netzlängenminimiert mit dem Sternmodell (Stand der Technik vor dieser Diplomarbeit), rechts laufzeitoptimiert mit dem Steinerbaummodell (Ergebnis dieser Diplomarbeit)

Die Layoutsynthese erfolgt in zwei Schritten. Zuerst werden die Module in einem vorgegebenen Bereich angeordnet (Plazierung) und danach durch elektrische Leitungen verbunden (Endverdrahtung/Routing).

Bei einem Schaltvorgang des Chips kommt es durch Umladezeiten von parasitären Kapazit äten zu Verzögerungen bei der Berechnung einzelner Signale. Bevor ein neuer Zyklus begonnen werden kann, ist es notwendig, daß sich alle Signalspannungen eingeschwungen haben. Man nennt die Dauer dieses Einschwingvorgangs Taktperiode, Schalt- oder (Signal-)laufzeit.¹ Wird die Schaltung abstrahiert und im Signalflußgraph untersucht, so spricht man von der Laufzeit des längsten Pfades (siehe Kapitel 2.4.3).

Die Taktperiode der Schaltung wird durch die Signale, die zum Erreichen ihrer eingeschwungenen Spannung die längste Zeit benötigen, nach unten beschränkt. Speziell die Laufzeiten dieser Signale müssen so kurz wie möglich gehalten werden, um einen schnellen Chip zu erhalten.

Je kleiner die Strukturen werden und je mehr Funktionalität in ihnen vereint wird, um so größer sind die parasitären Einflüsse auf die Signallaufzeit. In erster Linie ist die Signallaufzeit von der Plazierung abhängig, da diese das Routing und damit die parasitären Effekte bestimmt. Deshalb kommt der schaltzeitoptimierten Plazierung der Module (Laufzeitgesteuerte
Plazierung) eine immer größere Bedeutung zu.

Der Plaziervorgang selbst wird ebenfalls in zwei Schritte unterteilt. Der Globalplazierschritt optimiert die Plazierung im wesentlichen nach der Zielfunktion, in unserem Falle nach der Signallaufzeit, ohne auf technologische Randbedingungen einzugehen. Die Module in den Abbildungen in Tabelle 1 sind global plaziert, was sich in der leichten Überlappung einiger Module zeigt.

Aufgrund der technologischen Unabhängigkeit des Globalplazierschritts, können Globalplazierverfahren auch für zukünftige Rechnergenerationen in Nicht-Halbleiter-Technologien eingesetzt werden.

Im Endplazierschritt wird die Globalplazierung nur lokal leicht verändert, um technologische Realisierbarkeitsbedingungen zu erfüllen, ohne dabei viel Signallaufzeit einzubüßen. Unter diese Randbedingungen fallen zum Beispiel die Überlappungsfreiheit der Module, die Verdrahtbarkeit, die Einhaltung des Plaziergebietes und die Anordnung auf vorgesehenen Plätzen oder Reihen.

[...]

1 Um Verwechslungen mit Laufzeiten von Algorithmen zu vermeiden, wird in diesem Zusammenhang der Begriff Komplexität verwendet.