Forschungsinstitut für Diskrete Mathematik

Programmierpraktikum für das Grundstudium

Sommersemester 2003

Thema: Graphenalgorithmen

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.
Eine Zwischenbesprechung, in der Ergebnisse aus der Einarbeitungsaufgabe und Fragen zur eigentlichen Programmieraufgabe besprochen werden sollen, findet am

Freitag, den 16. Mai 2003 um 16 Uhr c.t.
im Seminarraum des Institutes für Diskrete Mathematik

statt.
Studenten, die Interesse an einem Praktikumsplatz haben, aber nicht an der Vorbesprechung zu dieser Veranstaltung teilnehmen konnten, werden gebeten, sich mit

Dirk Müller
Tel. 0228 / 73 87 86

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) Bilden Sie für jedes Netz jeweils den vollständigen Graphen auf der Menge seiner Terminalknoten, und geben Sie jeder Kante als Gewicht die Distanz (d.h. die Länge eines kürzesten Weges) zwischen ihren Endknoten im ursprünglichen Graphen. Implementieren Sie den Algorithmus von Kruskal oder Prim, um einen Spannbaum minimalen Gewichts in dem so konstruierten Graphen zu finden.
Geben Sie für jedes Netz jeweils die Nummer des Netzes und das Gewicht eines minimalen Spannbaums aus.

3) Implementieren Sie den Dijkstra-Steiner-Algorithmus, der in der Ihnen ausgehändigten bzw. zugesandten Literatur beschrieben wird. Statt eines minimalen Spannbaumes soll nun ein minimaler Steinerbaum konstruiert werden. Beachten Sie die Hinweise im Beweis über die Laufzeit des Verfahrens, die nicht nur die asymptotische Laufzeit verbessern, sondern auch die Implementierung vereinfachen sollten.
Berücksichtigen Sie hier zunächst noch keine Future Cost.

4) Erweitern Sie die in 3) entworfene Implementierung um die Berücksichtigung von Future Costs: Verwenden Sie wie im Text beschrieben die halbe Länge eines minimalen Spannbaums als Future Cost, um eine untere Schranke für die Kosten zu berechnen, die zum Anschluss der noch nicht verbundenen Terminale anfallen.

Die Einarbeitungsaufgabe besteht aus Teil 1). Geben Sie bitte bis Donnerstag, den 15.05.2003 eine korrekte und funktionsfähige Implementierung in ANSI-C oder C++ ab.
Abgabeschluss für die übrigen Aufgabenteile ist der 01.08.2003.

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 Nets)
chip2.data.bz2 (nx = 112, ny = 99, 34987 Nets)
chip3.data.bz2 (nx = 200, ny = 204, 334951 Nets)
chip4.data.bz2 (nx = 543, ny = 579, 1531558 Nets)

Es sei angemerkt, dass das eigentliche Routinggitter viel größer ist: 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 Knoten des Global-Routing-Gitters (innerhalb einer Verdrahtungsebene). Üblicherweise werden heute 6-8 Verdrahtungsebenen verwendet, von denen diejenigen mit gleicher Verdrahtungsrichtung (s. oben) darüberhinaus ebenfalls zusammengefasst werden, so dass das Global-Routing-Gitter nur noch zwei Ebenen hat.

Bei Fragen oder Problemen mit den Daten wenden Sie sich bitte einfach an die oben angegebene E-Mail-Adresse.



B. Korte
Dr. M. Müller-Hannemann,
Dr. J. Vygen