Forschungsinstitut für Diskrete Mathematik
Programmierpraktikum für das Grundstudium
Sommersemester 2006
Thema: Steinerbäume im Chipdesign
In diesem Programmierpraktikum soll ein Teilproblem aus der Verdrahtung
höchstintegrierter Logikchips behandelt werden: es geht darum, eine
Menge von Anschlusspins verschiedener Bauelemente auf einem Chip
kürzestmöglich miteinander zu verbinden. Die Konstruktion eines
minimalen Spannbaumes führt im allgemeinen nicht zu einer optimalen
Lösung - durch das Einfügen zusätzlicher sogenannter Steinerpunkte kann
man meist eine kürzere Verdrahtungslänge erreichen. Daraus ergibt sich
das Steinerbaumproblem, dass zwar NP-schwer ist, aber in unserem
Anwendungsfall nur auf Instanzen mit wenigen Terminalen (Anschlusspins)
zu lösen ist.
Ziel des Praktikums ist die effiziente Implementierung eines
Algorithmus, der eine Verallgemeinerung des wohlbekannten
Kürzeste-Wege-Algorithmus von Dijkstra darstellt und das
Steinerbaumproblem mittels dynamischer Programmierung auf Graphen mit
beliebigen nichtnegativen Kantengewichten exakt löst. Trotz der geringen
Größe jeder einzelnen Probleminstanz kommt einer effizienten
Implementierung hohe Bedeutung zu, da das Problem auf den größten
derzeit entwickelten Chips millionenfach zu lösen ist.
Studenten, die Interesse an einem Praktikumsplatz haben,
aber nicht an der Vorbesprechung zu dieser Veranstaltung teilnehmen
konnten, werden gebeten, sich mit
Christoph Bartoschek,
[email protected],
Tel. 0228 / 73 87 34
in Verbindung zu setzen.
Aufgabenstellung
1) Implementieren Sie den Algorithmus von Dijkstra für ungerichtete Graphen. Sie sollten eine Laufzeit von
O((n+m) log n) erreichen, wobei n die Anzahl der Knoten und m die Anzahl der Kanten des Eingabegraphen bezeichnen.
Lesen Sie die unten stehenden Testinstanzen ein und berechnen Sie für jedes Paar von Terminalen eines
Netzes einen kürzesten Weg, der diese miteinander verbindet (eine Erläuterung des Eingabeformats finden
Sie unten bei den Testdaten). Geben Sie jeweils die Nummern der beiden Terminalknoten und
die Länge eines kürzesten Weges zwischen diesen durch Leerzeichen getrennt auf einer Zeile aus.
Viele Terminale eines Netzes liegen sehr nah beisammen. Um einen kürzesten Weg zu finden, müssen in
einem solchen Fall nur sehr wenige Knoten des Graphen gelabelt werden, insbesondere ist die Initialisierung
aller Knotenlabel dann im Vergleich zur eigentlichen Suche sehr teuer.
Wie können Sie kürzeste Wege für alle Terminalpaare aller Netze finden, wenn Sie nur einmal zu Beginn alle
Knoten initialisieren?
2) Implementieren Sie den Dijkstra-Steiner-Algorithmus zur Konstruktion eines minimalen Steinerbaumes, der in der Ihnen ausgehändigten Literatur
beschrieben wird.
Berücksichtigen Sie hier zunächst noch keine Future Cost.
3) Erweitern Sie die in 2) entworfene Implementierung um die Berücksichtigung von Future Costs:
Als Future Cost können Sie die sogenannte Bounding-Box-Netzlänge verwenden, die als die Hälfte
des Umfangs des kleinsten umschreibenden Rechtecks der auf die x/y-Ebene projizierten Pins definiert ist.
Da die Kanten des Eingabegraphen kein Einheitsgewicht haben, nehmen Sie das Gewicht einer Kante auf dem Rand der Bounding Box
als das kleinste Kantengewicht in der entsprechenden Zeile bzw. Spalte im Gittergraphen an, um eine untere Schranke zu
erhalten.
Beachten Sie, dass Sie hier natürlich immer Teilmengen der Pins (die noch nicht angeschlossenen) betrachten.
Wenn Sie möchten, können Sie alternativ auch wie im Text beschrieben die halbe Länge eines minimalen Spannbaums
als Future Cost verwenden.
Die Einarbeitungsaufgabe besteht aus Teil 1). Geben Sie bitte bis Mittwoch, den 19. April 2006 eine korrekte
und funktionsfähige Implementierung in Java, C oder C++ ab.
Abgabeschluss für die übrigen Aufgabenteile ist Mittwoch, der 12. Juli 2006. Für die Aufgaben
2 und 3 reicht es aus, wenn Sie sich auf Netze mit höchstens sechs Terminalen beschränken, da sonst die
Laufzeit sehr hoch wird.
Datenformat und Testdaten
Jede Testinstanz besteht aus der Beschreibung eines (gitterförmigen) ungerichteten Graphen und einer Netzliste.
Die Struktur des Graphen ist immer wie folgt: Die Knoten sind in einem ganzzahligen Gitter der Größe
nx * ny * nz mit nz = 2 angeordnet.
Ein Knoten an Position (px, py, pz),
0 ≤ px ≤ nx - 1,
0 ≤ py ≤ ny - 1,
0 ≤ pz ≤ 1,
erhält die Nummer pz * nx * ny + py * nx + px.
Kanten verlaufen nur zwischen Knoten, die sich in genau einer Koordinate um 1 unterscheiden, und bezüglich der
übrigen Koordinaten an derselben Position liegen. In jeder der beiden Ebenen pz = 0 bzw.
pz = 1 verlaufen entweder nur Kanten in x- oder in y-Richtung. Wir können einer Ebene also eine
Richtung zuordnen, und alle in dieser Richtung verlaufenden Kanten zwischen benachbarten Knoten in dieser Ebene sind
im Graphen enthalten. Außerdem enthält der Graph alle Kanten zwischen in z-Richtung benachbarten Knoten.
Knoten werden durch ihre Nummer referenziert, Kanten durch die Nummern ihrer Endknoten.
nx und ny werden in der Eingabedatei angegeben.
Darüberhinaus ist die Kenntnis der oben beschriebenen Struktur eigentlich nicht notwendig,
um den Graphen einzulesen, ermöglicht Ihnen aber eine effiziente Speicherung (insbesondere
den Verzicht auf explizite Speicherung von Inzidenzinformationen).
Das Eingabeformat ist nun wie folgt:
nx ny
v(e1) w(e1) c(e1)
v(e2) w(e2) c(e2)
.
.
.
v(em) w(em) c(em)
Net 0: v0,1 v0,2 ... v0,k0
Net 1: v1,1 v1,2 ... v1,k1
.
.
.
Net p: vp,1 vp,2 ... vp,kp
Für jede Kante ei des Eingabegraphen, 1 ≤ i ≤ m, sind jeweils ihre Endknoten
v(ei) und w(ei) sowie die Kosten (oder Länge) c(ei) der Kante angegeben.
Auf die Beschreibung der Kanten folgt die Liste der Netze. Ein Netz besteht aus einer
Menge von miteinander zu verbindenden Terminalknoten, deren Nummern jeweils für jedes Netz
in einer durch Leerzeichen getrennten Liste angegeben sind.
Hier sind einige Testdaten von Chips verschiedener Größe:
chip1.data.bz2 (nx = 20, ny = 22, 1292 Netze)
chip2.data.bz2 (nx = 112, ny = 99, 34987 Netze)
chip3.data.bz2 (nx = 200, ny = 204, 334951 Netze)
chip4.data.bz2 (nx = 543, ny = 579, 1531558 Netze)
Anmerkung: Das eigentliche Routinggitter ist sehr viel größer; das Gitter, auf dem Sie in diesen Testinstanzen arbeiten,
wird im Global Routing ("Grobverdrahtungsphase") verwendet und entsteht durch Kontraktion von
jeweils ca. 60 x 60 Knoten des eigentlichen Routinggitters zu einem Global-Routing-Gitterknoten.
Bei Fragen oder Problemen mit den Daten wenden Sie sich bitte einfach an die oben angegebene E-Mail-Adresse.
Prof. Dr. B. Korte,
Prof. Dr. D. Rautenbach,
Prof. Dr. J. Vygen