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,
bartoschek@or.uni-bonn.de,
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