\documentclass[times, 10pt,twocolumn,ngerman]{article} \usepackage{latex8} \usepackage{times} %------------------------------------------------------------------------- % Custom Packages \usepackage{ngerman} \usepackage[ngerman]{babel} \selectlanguage{ngerman} \ngermanTeX \usepackage[T1]{fontenc} \usepackage[latin1]{inputenc} \usepackage{graphicx} \catcode`\à=\active \def à{\`a} \catcode`\á=\active \def á{\'a} \catcode`\â=\active \def â{\^a} \catcode`\ä=\active \def ä{\"a} \catcode`\À=\active \def À{\`A} \catcode`\Á=\active \def Á{\'A} \catcode`\Â=\active \def Â{\^A} \catcode`\Ä=\active \def Ä{\"A} \catcode`\ç=\active \def ç{\c c} \catcode`\Ç=\active \def Ç{\c C} \catcode`\é=\active \def é{\'e} \catcode`\è=\active \def è{\`e} \catcode`\ê=\active \def ê{\^e} \catcode`\É=\active \def É{\'E} \catcode`\È=\active \def È{\`E} \catcode`\Ê=\active \def Ê{\^E} \catcode`\ì=\active \def ì{\`\i} \catcode`\í=\active \def í{\'\i} \catcode`\î=\active \def î{\^\i} \catcode`\Ì=\active \def Ì{\`I} \catcode`\Í=\active \def Í{\'I} \catcode`\Î=\active \def Î{\^I} \catcode`\ñ=\active \def ñ{\~n} \catcode`\Ñ=\active \def Ñ{\~N} \catcode`\ô=\active \def ô{\^o} \catcode`\ö=\active \def ö{\"o} \catcode`\Ô=\active \def Ô{\^O} \catcode`\Ö=\active \def Ö{\"O} \catcode`\ù=\active \def ù{\`u} \catcode`\û=\active \def û{\^u} \catcode`\ü=\active \def ü{\"u} \catcode`\Ù=\active \def Ù{\`U} \catcode`\Û=\active \def Û{\^U} \catcode`\Ü=\active \def Ü{\"U} % Custom Packages %------------------------------------------------------------------------- %------------------------------------------------------------------------- % take the % away on next line to produce the final camera-ready version \pagestyle{empty} %------------------------------------------------------------------------- \begin{document} \title{Ein Überblick über Placement und Routing in integrierten Schaltungen und Systemen} \author{Jean-Pierre Schwickerath\\ Technische Universität Darmstadt\\ tud@schwicky.net\\ } \maketitle \thispagestyle{empty} \begin{abstract} Es wird auf die spezifischen Probleme des Placement und des Routings im Entwurf von integrierten Schaltungen eingegangen. Genetische Algorithmen (GA) und stochastische Verfahren bieten eine effiziente Lösung zu diesen meist \textit{NP}-harten Problemen. Die Nachteile der GA und der stochastischen Verfahren können umgangen werden, indem man beiden Ansätze miteinander kombiniert. Diese Idee wird erläutert und anhand eines Beispiels wird ein genetischer Placement und ein Routing Algorithmus erklärt. \end{abstract} \Section{Einleitung} Die meisten Probleme, die beim Entwurf von integrierten Schaltungen auftreten sind sehr schwierige kombinatorische Optimierungsprobleme. Mehrere, voneinander abhängige Kriterien müssen unter Rücksichtnahme einer grossen Menge nicht trivialer Bedingungen optimiert werden. Die Vorgänge bestehen aus Unterproblemen, die selbst \textit{NP}-hart, gross und gegenseitig voneinander abhängig sind \cite{drechsler94genetic}. Meistens beruhen die Berechnungen eines solchen Unterproblems auf weiteren, noch nicht berechneten Schritten. So müssen zur Lösung der Probleme Abschätzungen zur Hilfe genommen werden. Auch Placement und Routing gehören zum Entwurf von Schaltung (siehe Abbildung~\ref{fig:ASICdev}) und zu dieser Kategorie von Problemen. Man kann sie sowohl auf der Ebene einer Platine betrachten (Abbildung~\ref{fig:MCMdev} zeigt beispielhaft den Ablauf des Entwurfs eines Platine, die aus vorgefertigten Funktionsblöcken aufgebaut wird), wo fertige Schaltungen miteinander verbunden werden müssen, wie etwa ein zentraler Prozessor, Speicherchips und Ein- und Ausgabemodule, als auch innerhalb eines solchen Chips (auch ,,Die'' genannt), in dem diverse Funktionsblöcke (Rechenwerk, Steuerwerk, Register) oder eine Grosszahl einzelner Transistoren miteinander verbunden werden müssen. Die zu lösenden Probleme sind die gleichen und die dazu verwendeten Algorithmen ähnlich. Diese Ausarbeitung soll einen Überblick über die Probleme geben, die beim Placement und beim Routing auftreten. Es wird ein genetisches und ein stochastisches Verfahren vorgestellt und besprochen wie die Verfahren den speziellen Problemen im Entwurf von integrierten Schaltungen angepasst werden können. \begin{figure}[h] \includegraphics[width=\columnwidth]{references/asic_procedure} \caption{Entwurf eines Application-specific integrated circuit (ASIC).~\cite{smith-asic}} \label{fig:ASICdev} \end{figure} \Section{Zwei getrennte Probleme mit Gemeinsamkeiten} Beim Placement geht es darum die Komponenten der Schaltung auf dem Substrat zu platzieren und dabei verschiedene Vorgaben einzuhalten. Diese Vorgaben sind unter anderem: Minimierung der Fläche des benötigten Substrats, der Gesamtlänge der Verbindungen, die gleichmässige Verteilung der Hitze und Einhaltung gewisser Laufzeiten. Sie hängen einerseits vom Design ab, andererseits auch vom gewählten Substrat \cite{donald-overview}. Es muss ausserdem genügend Platz für das Routing gelassen werden. Der Platz, der nach dem Placement auf dem Substrat übrig bleibt wird in rechteckige Flächen, so genannten Routingregionen, aufgeteilt. Die Aufgabe des Routings ist, die Verbindungen zwischen den Komponenten (Pins) herzustellen. Auch hier gelten Vorgaben wie die Minimierung der Länge der Verbindungen, der Anzahl an verwendeten Layern (Ebenen) und an Verbindungen zwischen den Layern (Vias), der Störungsquellen (Crosstalk) und des Rauschen. Routing bei VLSI\footnote{Very Large Scale Integrated}-Entwurf wird meistens in globales Routing (Zuteilung von Verbindungsnetzen zu gewissen Routingregionen) und detailliertes Routing (genaue Positionierung der Verbindungsnetze innerhalb einer Routingregion) aufgeteilt \cite{lienig93genetic}. Die Placement- und Routingvorgänge sind voneinander abhängig (während des Placements muss abgeschätzt werden wie viel Platz das Routing für die notwendigen Verbindungen benötigen wird) aber ihre Komplexität verlangt, dass sie getrennt voneinander behandelt werden. Jede Entscheidung, die getroffen wird hat Auswirkungen auf den Rest des Prozesses insofern, dass die Platzierung einer Komponente oder das Routing einer Verbindung weniger Platz für die anderen Komponenten bzw. Verbindungen lässt. Folglich sollten Platzierungen oder Verbindungen, die einen grossen Einfluss auf die Optimierung haben zuerst festgelegt werden. \begin{figure}[h] \includegraphics[width=\columnwidth]{references/mcm_physical_design} \caption{Ablauf des Designs eines Multi-Chip Moduls.~\cite{donald-overview}} \label{fig:MCMdev} \end{figure} \SubSection{Das Placement-Problem} Das Placement-Problem kann folgendermassen definiert werden \cite{ga94cEsbensen}: Unter Verwendung \begin{enumerate} \item einer Menge rechteckiger Komponenten (Zellen), jede mit einer Anzahl an Pins an vorgegebenen Positionen entlang dem Rand der Zelle positioniert, \item einer Netlist, die die Verbindungen zwischen allen Pins spezifiziert, und \item einer ungefähren horizontalen Länge $W$ des zu entwerfenden Chips. \end{enumerate} Berechne \begin{enumerate} \item die absolute Position jeder Zelle, \item die Orientierung und Spiegelung jeder Zelle, \item ein Rechteck $B$, dass die Form des Chips definiert. \end{enumerate} Das Ziel ist es, die Fläche von $B$ zu minimieren unter den Vorgaben, dass keine zwei Zellen sich überlappen, dass das Rechteck $B$ alle Zellen umfasst und ungefähr die Länge $W$ hat, und, dass die Flächen innerhalb von $B$, die nicht von Zellen belegt werden, gross genug sind um das Routing der Verbindungen zu beinhalten. Ein idealer Placementalgorithmus sollte folglich das flächenmässig kleinstmögliche Layout generieren, dass den elektrischen und thermischen Regeln entspricht. \SubSection{Das Routing-Problem} Das Routing-Problem kann als solches definiert werden \cite{donald-overview}: Gegeben sei eine freie Fläche, eine Menge von Pins und eine Netlist. Berechne die Position und den Verlauf aller Verbindungen zwischen den Pins, so dass die minimale Anzahl an Layern benutzt wird, Laufzeiten und Rauschen minimiert werden, sowie Herstellungseinschränkungen eingehalten werden. Diese Einschränkungen beinhalten, dass verschiedene Nets\footnote{Ein Net ist eine Menge von Punkten (Pins), die zu verschiedenen Blöcken gehören und die miteinander verbunden werden müssen.} sich nicht auf einem Layer kreuzen können und, dass sie einen Minimalabstand voneinander haben müssen. Unter Umständen darf nur die Manhattan Geometrie\footnote{Nur horizontale und vertikale Segmente dürfen benutzt werden.} benutzt werden. Abbildung \ref{fig:channelrouting} illustriert dieses Problem. Dort gilt es die Nets zwischen dem Pins mit der gleichen Nummer zu routen. Bei dem Problem handelt es sich um ein so genanntes Channel-Routing-Problem weil sich die Pins ausschliesslich auf zwei gegenüberliegenden Seiten eines für Routing zur Verfügung stehenden Rechtecks, befinden. Dabei stellen die gestrichelten Linien die Verbindungen auf einem ersten Layer, und die durchgezogenen Linien auf einem 2. Layer dar. Die gefüllten Rechtecke sind Vias, also Verbindungen von einem Layer zum anderen. Die Lösung genügt den eben genannten Bedingungen. \begin{figure}[h] \includegraphics[width=\columnwidth]{references/channel_routing} \caption{Beispiel für ein Channel-Routing-Problem (a) und eine mögliche Lösung (b).~\cite{lienig93genetic}} \label{fig:channelrouting} \end{figure} \Section{Grundsätzliche algorithmische Überlegungen zu den Problemen} Sowohl Routing als auch Placement sind \textit{NP}-harte Probleme. Selbst das einfache Berechnen der kürzesten Verbindung zwischen einer Menge von Transistoren ist gleich schwer wie das Lösen des Steiner Problems in einem Graphen (SPG), welches \textit{NP}-hart ist. Als die Anzahl der Transistoren in einer Schaltung immer grösser wurde und man die Placement- und Routing-Probleme nicht mehr effizient lösen konnte, ist man auf die Suche nach neuen Algorithmen gegangen. Mittlerweile werden ist fast allen CAD-Programmen zum Entwurf von Schaltungen genetische Algorithmen und stochastische Verfahren verwendet, die im folgenden kurz vorgestellt werden. \SubSection{Simulated Annealing (SA)} Das in der CAD-Community am beliebtesten stochastische Verfahren ist das ``Simulated Annealing''. Der Algorithmus ist dafür bekannt, dass er auf Kosten übertrieben langer Laufzeit qualitativ hochwertige Lösungen berechnet. Der Algorithmus ist eine Generalisierung der Monte-Carlo-Methode, in der das Einfrieren einer Flüssigkeit oder die Kristallisierung eines Metalls simuliert wird. Eine ursprünglich geschmolzene Substanz wird so langsam abgekühlt, dass sie sich immer beinahe im thermodynamischen Gleichgewicht befindet (Abbildung \ref{fig:sa}). Das Ziel ist eine möglichst gleichmässige Kristallisierung zu erhalten. \begin{figure}[h] \centerline{\includegraphics[width=0.5\columnwidth]{references/sa}} \caption{Globale Struktur des Simulated Annealing Algorithmus.~\cite{mo95}} \label{fig:sa} \end{figure} \SubSection{Genetische Algorithmen (GA)} Genetische Algorithmen, die mit probabilistischen Übergängen nach vorteilhaften Anpassungen in einer sich immer ändernden Umgebung suchen (Abbildung \ref{fig:ga}) werden im Entwurf von integrierten Schaltungen oft verwendet. Dort bilden Chromosome eine abtrakte Darstellung des Problems. Individuen sind potentielle Lösungen dieses Problems. Diese Individuen durchlaufen einen Evolutionsprozess, der aus drei Hauptteilen besteht: \begin{itemize}\label{chap:ga} \item \textit{Selektion} beschreibt die Phase, in der mehrere Individuen für den weiteren Evolutionsprozess ausgewählt werden. Dies geschiet anhand der Fitness eines Individuums, die aussagt wie ,,gut'' dieses Individuum (also die Lösung) ist. \item Diese ausgewählen Individuen werden der \textit{Kreuzung (crossover oder recombination)} unterzogen. Es entstehen neue Individuen mit den besten Eigenschaften der selektierten Vorfahren. \item Während der \textit{Mutation} werden die neuerzeugten Individuen verändert um die Vielfalt der neue Bevölkerung zu garantieren. \end{itemize} Laut \cite{drechsler94genetic} sind GA für CAD-Probleme bestens geeignet, denn: \begin{itemize} \item Die relative Performanz von GA verbessert sich mit der Komplexität, und die Probleme mit denen hier gehandhabt wird, sind sehr komplex. \item GA sind von Natur aus parallelisierbar und beinahe lineare Skalierung wurde auf MIMD-Architekturen\footnote{Multiple Instruction Multiple Data-Architekturen, wie Shared-Memory-Multiprozessorsysteme oder vernetzte Rechner \cite{hoffmann03ra}.} erzielt. Der Grossteil der Rechenzeit fällt bei der Berechnung der Fitness (Kostenfunktion) an. Die Selektion und die Mutation sind nicht rechenintensiv. Folglich kann das Berechnen einzelner Kostenfunktionen auf Clusterknoten ausgelagert werden, da zwischen den Kostenfunktionen kein Datenaustausch stattfinden braucht. In Entwicklungseinrichtungen von integrierten Schaltungen sind oft viele vernetzte Rechner vorhanden auf denen viele parallele GA ausgeführt werden können. Im Gegensatz dazu sind SA basierte Algorithmen an sich sequenziell und dadurch sind viel schlechter parallelisierbar. \item Bei der Entwicklung einer Schaltung werden gewisse Schritte sehr oft iterativ wiederholt. Ein ideales CAD Werkzeug sollte die Möglichkeit bieten zwischen 1) einer überwiegend guten aber sehr schnell berechneten Lösung und 2) einer qualitativ hochwertigen Lösung für die man allerdings mehr Rechenzeit opfern muss, zu wählen. GA berechnen eine sehr gute Lösung, wenn man sie lange laufen lässt, aber dank der schnellen Konvergenz des Algorithmus in den ersten Generationen kann man innerhalb kürzester Zeit eine relativ gute Lösung berechnen. \end{itemize} \begin{figure}[h] \centerline{\includegraphics[width=0.5\columnwidth]{references/ga}} \caption{Globale Struktur eines genetischen Algorithmus.~\cite{mo95}} \label{fig:ga} \end{figure} \SubSection{Die Fusion: SAGA} Ein Problem der GA ist ihr Konvergenzverhalten. Am Anfang verbessert sich die Kostenfunktion sehr schnell aber dann wird es sehr schwer weitere Verbesserungen zu erzielen. Ein Grossteil der Rechenzeit geht im späteren Ablauf des Algorithmus verloren, wo nur sehr kleine Verbesserungen sehr langsam erzielt werden. Ausserdem ist ein GA immer der Gefahr ausgesetzt sich in einem lokalen Optimum zu verfangen. Esbensen und Mazumder beschreiben in \cite{ga94cEsbensen} wie man mit sehr einfachen Mitteln dem entgegenkommen kann. Die Idee ist SA zu verwenden, der auch im späteren Teil der Berechnung immer noch respektable Verbesserungen erzielt aber am Anfang nicht so schnell konvergiert wie ein GA. Dieses SAGA-Verfahren beginnt mit der Ausführung eines reinen GA. Wenn dieser dann beinahe zur Stagnation kommt, wechselt SAGA immer mehr zur Ausführung von SA. Abbildung \ref{fig:SAGA} zeigt, wie man die zwei Algorithmen miteinander kombinieren kann. $\Pi_c$ ist die Bevölkerung, die betrachtet wird. Die \texttt{evaluate()} Routine ist die Kostenfunktion, die bestimmt wie gut eine Lösung ist. Wenn für $R$ Generationen keine messbaren Verbesserungen aufgetreten sind, dann wird die Bevölkerungszahl $M$ reduziert und ihre Mutationsrate $p_{mut}$ wird erhöht. Das ist dann der Übergang zu SA. \begin{figure}[h] \centerline{\includegraphics[width=0.8\columnwidth]{references/outline_SAGA}} \caption{Der Überblick über SAGA.~\cite{ga94cEsbensen}} \label{fig:SAGA} \end{figure} Experimente und Benchmarks (Abbildung \ref{fig:SAGAbench}) belegen, dass der stochastische Optimierungsalgorithmus SAGA mindestens genauso gut ist wie andere Systeme und in vielen Fällen sogar die Fläche der Schaltung weiter reduzieren kann und dabei sogar eine kürzere Laufzeit aufweist. Die verwendeten Benchmarks aus Abbildung \ref{fig:SAGAbench} sind die des MCNC International Workshop on Placement and Routing von 1992. \begin{figure}[h] \centerline{\includegraphics[width=0.8\columnwidth]{references/SAGA_benchmark}} \caption{Vergleich der Flächen der Ergebnisse von SAGA und anderen Algorithmen.~\cite{ga94cEsbensen}} \label{fig:SAGAbench} \end{figure} \Section{Placement} Beim Placement gibt es ein Aspekt, der immer wichtiger wird: die Länge der Verbindungen. Mit steigenden Frequenzen muss immer mehr darauf geachtet werden, dass das Signal lange genug anliegt um von der Quelle (Driver) zur Senke (Terminal, Sink) zu kommen. Sollte dies nicht der Fall sein, müssen Buffer eingebaut werden. Diese kosten wiederum Zeit und Platz. Bei langen Verbindungsleitungen tritt zudem das Problem des Widerstandes und der Kapazität auf. Die Leitungen müssen nahe beim Driver dicker sein als beim Terminal. Das beeinflusst beim Placement den Platz, der für das Routing reserviert werden muss. Auf Grund der Widerstände, die auftreten könne arbeiten Placement-Werkzeuge mit so genannten delay oder performance-oriented Placement \cite{donald-overview}. Dort beschränken Timingbedingungen die obere Schranke der Verbindungslängen, die dann beim Placement berücksichtigt werden. Wenn man mehr als zwei Pins auf einem Net hat, dann bestimmt die Topologie des Netzes dessen Verzögerung. Es ist schwer während des Placements die Verzögerung zu approximieren. Zu diesem Zweck wurde vorgeschlagen das globale Routing und das Placement gleichzeitig zu bearbeiten \cite{burstein89placement}. Weitere Ansätze betrachten stattdessen den Widerstand der Leitung und die Kapazität der Senken. Bei den traditionellen Placement-Ansätzen gibt es zwei Gruppen: konstruktive und iterative. Die konstruktiven nehmen ein unvollständiges Placement als Eingabe an und produzieren dank bestimmten Regeln ein fertiges Placement. Dafür werden oft Min-Cut basierte Algorithmen verwendet, die sukzessive Anwendungen von Partitioning \cite{breuer77mincut} benutzen. Grundsätzlich funktioniert der Algorithmus wie folgt: \begin{enumerate} \item Teile die Placementfläche in zwei. \item Tausche die Logikzellen um die Schnittkosten zu minimieren. \item Wiederhole ab Schritt 1. Teile immer kleinere Stücke bis alle Logikzellen platziert sind. \end{enumerate} Abbildung \ref{fig:mincut} zeigt wie man das Teilen durchführt: \begin{enumerate} \renewcommand{\labelenumi}{(\alph{enumi})} \item Teile den Chip mit einem Gitter in Behälter auf. \item Führe alle Verbindungen zum Mittelpunkt des jeweiligen Behälters. \item Mache einen Schnitt und tausche die Logikzellen um die Kosten des Schnitts zu minimieren. \item Nimm die geteilten Hälften und entferne alle Kanten, die nicht innerhalb einer Hälfte sind. \item Wiederhole den Prozess mit einem neuen Schnitt und fahre fort bis nur noch einzelne Behälter übrig sind. \end{enumerate} \begin{figure}[h] \includegraphics[width=\columnwidth]{references/min_cut} \caption{Min-Cut Placement.~\cite{smith-asic}} \label{fig:mincut} \end{figure} Bei den iterativen Methoden wird ein Annahme für das Placement gemacht und dann wird diese verfeinert indem man Bedingungen für ein besseres Placement berücksichtigt. Die GA- und SA-Ansätze fallen in diese Kategorie. In jeder Iteration wird eine Komponente gedreht oder verschoben und wenn die Konfiguration besser ist als die vorherige, dann wir diese als neue Grundlage genommen. Bei den iterativen Verfahren gibt es grundsätzlich zwei Kriterien: \begin{itemize} \item Das Selektionskriterium, das entscheidet welche Zelle verschoben werden soll. \item Das Messkriterium, das entscheidet ob die ausgewählte Zelle nun verschoben wird. \end{itemize} Wenn man das Simulated Annealing Verfahren auf das Placement anwendet, sieht der Algorithmus folgendermassen aus \cite{smith-asic}: \begin{enumerate} \item Wähle eine Logikzelle für einen potentiellen Tausch, meistens zufällig ausgewählt. \item Berechne die objektive Funktion $E$ für das neue Placement. \item Wenn $\Delta E$ negativ oder Null ist, dann werden die Logikzellen getauscht. Wenn $\Delta E$ positiv ist, dann werden die Zellen mit einer Wahrscheinlichkeit von $e^{-\Delta E / T}$ getauscht (Messkriterium). \item Wiederhole ab Schritt 1 für eine feste Anzahl an Durchläufen und senke die Temperatur $T$ nach einem Abkühlungsschema. Zum Beispiel $T_{n+1} = 0.9 T_n$. \end{enumerate} \Section{Routing} Wenn das Placement abgeschlossen ist geht es beim Routing um die genaue Festlegung der Verbindungsnetze. Alle Bedingungen, die beim Placement eine Rolle spielten, gelten auch hier und müssen zusammen mit weiteren Bedingungen eingehalten werden. Alle diese Bedingungen werden eine nach der anderen auf Erfüllung getestet, wenn es darum geht die Qualität einer generierten Lösung zu bewerten. Es gibt aber auch Algorithmen, die von ihrem Ablauf her bei der Generierung neuer Lösungen gewissen Bedingungen nachkommen. Anhand des Beispiels aus Abbildung \ref{fig:geneticrouting} soll erläutert werden, wie Channel-Routing mit Hilfe von genetischen Algorithmen funktionieren kann. Im Channel-Routing-Problem kann ein Individuum als das Ergebnis eines Routings betrachtet werden. Die Qualität dieses Routings kann anhand der Fitness des Individuums festgestellt werden. Am Anfang wird eine initiale Bevölkerung zufällig erzeugt. Diese Bevölkerung wird einem Evolutionsprozess (wie in \ref{chap:ga} beschrieben) ausgesetzt. Wenn die Simulation funktioniert, dann werden immer bessere Individuen in der Bevölkerung vorherrschen, weil sie eine höhere Wahrscheinlichkeit haben, Nachfahren zu produzieren, die nur die besten Eigenschaften ihrer Vorfahren erben. Diese besten Individuen sind genau die besten Routinglösungen, die den gewünschten Kriterien entsprechen. Die Anzahl der Individuen $|\mathcal{P}_c|$ bleibt konstant über alle Generationen hinweg. Am Ende des Algorithmus wird $p_{best}$ einer Optimierung unterzogen und bildet dann die endgültige Lösung des Routings. \begin{figure}[h] \centerline{\includegraphics[width=0.8\columnwidth]{references/genetic_routing}} \caption{Umriss eines genetischen Routingalgorithmus.~\cite{lienig93genetic}} \label{fig:geneticrouting} \end{figure} Der Erzeugungsprozess der initialen Bevölkerung läuft wie folgt ab. Am Anfang wird eine Bevölkerung aus zufälligen Individuen erzeugt. Nun wünscht man sich die Verbindung zwischen den Pins $s_i$ und $t_j$. Dazu wird von beiden Pins aus eine senkrechte Linie erzeugt bis diese auf ein Hindernis trifft, zum Beispiel den Rand der Routingregion oder ein anderes, schon geroutetes Netz (Abbildung \ref{fig:randomrouting} (a, b)). Zwischen den Endpunkten der gerade erzeugten Erweiterungslinien wird jeweils zufällig ein Punkt bestimmt. Von dort aus werden waagerechte Linien in beide Richtungen erzeugt (Abbildung \ref{fig:randomrouting} (c)). Die Suche geht weiter indem man auf den waagerechten Linien zwei zufällige Punkte auswählt und dort senkrechte Erweiterungslinien verankert (Abbildung \ref{fig:randomrouting} (d)). Das Layer dieser Linien wird wie folgt bestimmt. Jedes Layer hat eine bevorzugte Routingrichtung und sei $r_n$ eine zufällige Zahl zwischen 0 und 1. Wenn $r_n \leq 2/3$ dann wird die Linie auf das Layer gesetzt, dass ihre Routingrichtung bevorzugt. Andernfalls wird die Linie auf das andere Layer gesetzt. Der Erweiterungslinienprozess wird beendet wenn \begin{itemize} \item Erweiterungslinien beider Punkte treffen sich auf dem gleichen Layer \item Die Erweiterungslinie von $s_i$ trifft auf eine Punkt, der schon zum Netz von $t_j$ gehört (wie in Abbildung \ref{fig:randomrouting} (e)) oder umgekehrt. \end{itemize} Sollte die Erzeugung der Erweiterungslinien nicht innerhalb von $i$ Iterationen zum Ende kommen, dann werden alle Erweiterungslinien gelöscht, die Routingregion zufällig um eine Gitterlinie erweitert und die Linien neu erzeugt. Wenn nach zehn Erweiterungen der Routingregion immer noch keine Verbindung hergestellt werden konnte, dann wird diese Bevölkerung komplett ausgelöscht und zufällig neu erzeugt. Der Routingprozess wird abgeschlossen indem der kürzeste Weg auf den Erweiterungslinien gewählt wird. \begin{figure}[h] \centerline{\includegraphics[width=0.8\columnwidth]{references/random_routing}} \caption{Beispiel für ein zufälliges Routing zwischen $s_i$ und $t_j$.~\cite{lienig93genetic}} \label{fig:randomrouting} \end{figure} Dieser Channel-Routing Algorithmus liefert sehr gute Ergebnisse, wie der Vergleich bekannter Channel-Router in Abbildung \ref{fig:channelbench} zeigt. Der Algorithmus wurde nach 150 Generationen unterbrochen und mit jeweils $|\mathcal{P}_c| = 50$ Individuen ausgeführt. Dabei konnte er sogar den Joo6\_16 Benchmark ausführen, an dem der Greedy Algorithmus gescheitert ist. \begin{figure}[h] \centerline{\includegraphics[width=\columnwidth]{references/channel_routing_benchmark}} \caption{Benchmarkergebnisse.~\cite{lienig93genetic}} \label{fig:channelbench} \end{figure} \Section{Zusammenfassung und Ausblick} Bei Placement und Routing hat man es mit \textit{NP}-harten Problemen zu tun. Viele, voneinander abhängige Kriterien müssen unter Berücksichtigung nicht trivialer Bedingungen optimiert werden. Bei der heutigen Grösse und Komplexität der Schaltungen ist es nicht mehr möglich diese mit traditionellen kombinatorischen Verfahren zu bearbeiten. Seit Mitte der 1990er Jahre sind immer mehr genetische und stochastische Verfahren im Einsatz. Sie haben den Vorteil sehr schnell zu konvergieren und, wenn man ihnen genügend Laufzeit zur Verfügung stellt, liefern sie auch qualitativ exzellente Ergebnisse. Ein wichtiges Kriterium der Algorithmen ist ihre inhärente Parallelisierbarkeit. Nur so kann gewährleistet werden, dass sie in vertretbarer Zeit bearbeitet werden können, wie etwa die genetischen Algorithmen, die auf vernetzten Rechner sehr gut skalieren. Was Benchmarks angeht so stellt Smith in \cite{smith-asic} fest, dass man CAD-Algorithmen, die auf Zufallsdaten zurückgreifen sehr schlecht vergleichen kann. Die Ergebnisse sind nicht wiederholbar und Vergleiche aufzustellen ist gewagt, es sei denn man hat statistisch ausreichend viele Testläufe für statistisch ausreichend viele Chips durchgeführt. Chang et al. haben in \cite{chang04optimality} Placement und Routing Werkzeuge (Dragon, Capi, mPL, mPG und QPlace) miteinander verglichen. Sie haben die Werkzeuge auf Probleme angesetzt, deren optimale Verbindungsnetzlängen bekannt sind. Sie sind zu dem Schluss gekommen, dass die Länge der Verbindungen in den Ergebnissen im Durchschnitt 1.62 bis 2.07 Mal länger waren als die optimalen Lösungen. Sie stellten ebenfalls fest, dass die Qualität der Lösungen um 9\% bis 17\% schlechter wurden, wenn das Problem um Faktor 10 vergrössert wurde. Daraus kann mal folgern, dass Werkzeuge zum Entwurf von Schaltungen immer noch verbesserungsfähig sind. Sollte dies gelingen, so kommt es dem Fortschritt mehrerer Generationen an Herstellungsverfahren gleich. \nocite{hathaway96placement, cong96performance, cho-improving} \bibliographystyle{latex8} \bibliography{20040703-ASIC_Routing_Placement.bib} \end{document}