\documentclass[final,slideColor,total,corners,colorBG,pdf]{prosper}
%\documentclass[final,slideColor,total,corners,colorBG,ps]{prosper}

\usepackage{euscript}

\usepackage{amsmath}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}

\usepackage[english]{babel}
\selectlanguage{english}

\usepackage{graphicx}
\usepackage{longtable}
\usepackage{multicol}
\usepackage{fancyvrb}
\usepackage{url}

%\usepackage{times,mathptmx,helvet,courier}

\renewcommand{\familydefault}{\sfdefault}

\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}

\makeatother


\title{Ein Überblick über Placement und Routing in integrierten Schaltungen und Systemen}
\author{Jean-Pierre Schwickerath}
\institution{Technische Universität Darmstadt\\Entwurf, Technik und Technologie integrierter Schaltungen und Systeme\\Prof. Rolf Hoffmann, Dipl.-Ing. Wolfgang Heenes\\\bigskip \textit{2. Juli 2004}}
\email{http://schwicky.net/projects/2004/asic/}

\slideCaption{Ein Überblick über Placement und Routing in integrierten Schaltungen und Systemen -- Jean-Pierre Schwickerath}


\begin{document}
\maketitle


\begin{slide}{ASIC-Entwurf}

\centerline{\includegraphics[height=6.5cm]{images/asic_procedure}}

\end{slide}




\overlays{6}{%
\begin{slide}{Definitionen}
\begin{itemstep}
	\item \textbf{Placement}: Platzierung von Komponenten auf dem Substrat.
	\begin{itemize}
		\item Vorgaben: Minimierung der Fläche, Länge der Verbindungen. Gleichmässige Hitzeverteilung. Einhalten von Laufzeiten.
		\item Genügend Platz für Routing $\rightarrow$ Routingregionen.
	\end{itemize}
	\item \textbf{Routing}: Verbindung zwischen den Pins der Komponenten.
	\begin{itemize}
		\item Vorgaben: Minimierung der Anzahl an Layern, Vias, Störungsquellen, Rauschen.
		\item Globales Routing und detailliertes Routing.
	\end{itemize}
\end{itemstep}
\end{slide}}



\overlays{2}{%
\begin{slide}{Konsequenzen}
\begin{itemstep}
	\item Beim Placement müsste man schon wissen wie viel Platz das Routing braucht.
	\item Priorität: Platzierung von Komponenten mit wichtigen Auswirkungen.
\end{itemstep}
\end{slide}}



\overlays{6}{%
\begin{slide}{Natur der Probleme}

\begin{itemstep}
	\item Placement und Routing-Probleme können auf mehreren Ebenen betrachtet werden.
	\item Grosse, voneinander abhängige \textit{NP}-harte Probleme:
	\begin{itemize}
		\item Viele voneinander abhängige Kriterien,
		\item Optimierung unter Berücksichtigung nicht trivialer Bedingungen.
	\end{itemize}
	\item Abschätzungen müssen zur Hilfe genommen werden.
	\item Einsatz von genetischen und stochastischen Verfahren.
\end{itemstep}
\end{slide}}



\overlays{2}{%
\begin{slide}{Placement}
Unter Verwendung 
\begin{itemize}
	\item einer Menge an rechteckigen Zellen mit Pins,
	\item einer Netlist (Verbindungsliste),
	\item einer ungefähren Länge $W$ des Chips.
\end{itemize}

\FromSlide{2}
\medskip
Berechne
\begin{itemize}
	\item die absolute Position jeder Zelle,
	\item die Orientierung und Spiegelung jeder Zelle,
	\item ein Rechteck $B$, dass die Form des Chips definiert.
\end{itemize}

\end{slide}}



\overlays{3}{%
\begin{slide}{Placement (2)}
Ziele:
\begin{itemstep}
	\item Minimierung der Fläche von $B$.
	\item Ohne Überlappung.
	\item Alle nicht belegten Flächen reichen fürs Routing.
\end{itemstep}
\end{slide}}




\overlays{2}{%
\begin{slide}{Routing}
Keine zwei Nets dürfen sich auf einem Layer kreuzen.

\FromSlide{2}
Beispiel: Channel-Routing.

\centerline{\includegraphics[height=5cm]{images/channel_routing}}
\end{slide}}



\overlays{4}{%
\begin{slide}{Simulated Annealing}
\begin{itemstep}
	\item Basiert auf Monte-Carlo-Methode.
	\item Einfrieren einer Flüssigkeit oder Kristallisierung eines Metalls wird simuliert.
	\item Die Substanz muss sich immer beinahe im thermodynamischen Gleichgewicht befinden.
	\item Von Natur aus sequenziell.
\end{itemstep}
\end{slide}}




\begin{slide}{Simulated Annealing (2)}
\PDForPS{\includegraphics[height=7cm]{images/sa}}{\includegraphics[angle=90,totalheight=6cm]{images/sa}}
\end{slide}



\overlays{5}{%
\begin{slide}{Genetische Algorithmen}
\begin{itemstep}
	\item Suchen mit probabilistischen Übergängen nach vorteilhaften Anpassungen in einer sich immer ändernden Umgebung.
	\item Bevölkerung, Chromosome, Individuen, Evolutionsprozess:
	\begin{itemize}
		\item Selektion,
		\item Kreuzung (crossover oder recombination),
		\item Mutation.
	\end{itemize}
\end{itemstep}
\end{slide}}




\begin{slide}{Genetische Algorithmen (2)}
\PDForPS{\includegraphics[height=7cm]{images/ga}}{\includegraphics[angle=90,totalheight=6cm]{images/ga}}
\end{slide}




\overlays{4}{%
\begin{slide}{Genetische Algorithmen (3)}
Sind für CAD-Probleme bestens geeignet:
\begin{itemstep}
	\item Relative Performanz verbessert sich mit der Komplexität.
	\item Sehr gut parallelisierbar. Beinahe lineare Skalierung auf MIMD. Rechenintensivste: Kostenfunktion.
	\item Sehr schnell gute Ergebnisse. Bei langer Laufzeit, sehr gute Ergebnisse.
\end{itemstep}
\FromSlide{4}
Aber:
\begin{itemize}
	\item Irgendwann nur noch sehr kleine Verbesserungen.
	\item Probleme mit lokalen Optima.
\end{itemize}
\end{slide}}




\begin{slide}{Die Lösung: SAGA}
\PDForPS{\centerline{\includegraphics[height=7cm]{images/outline_SAGA}}}{\includegraphics[angle=90,totalheight=6cm]{images/outline_SAGA}}
\end{slide}




\begin{slide}{SAGA Benchmarks}
Xerox Benchmark: Anzahl der Durchläufe im Intervall $[27.15+0.3i,\, 27.15+0.3(i+1)[$.

\centerline{\includegraphics[height=6cm]{images/ga_vs_saga}}
\end{slide}




\begin{slide}{SAGA Benchmarks (2)}
\centerline{\includegraphics[height=6cm]{images/SAGA_benchmark}}
\end{slide}





\overlays{4}{%
\begin{slide}{Placement im Detail}
\begin{itemstep}
	\item Länge der Verbindung werden immer wichtiger: Verzögerung von Quelle zu Senke.
	\item Verstärkt durch Widerstand und Kapazität.
	\item Konstruktive Verfahren, meistens mit Min-Cut Algorithmen durch sukzessive Anwendung von Partitioning.
	\item Produzieren ein vollständiges Placement.
\end{itemstep}
\end{slide}}



\begin{slide}{Min-Cut Placement}
\centerline{\includegraphics[height=6cm]{images/min_cut}}
\end{slide}



\overlays{6}{%
\begin{slide}{Placement im Detail (2)}
Iterative Verfahren:
\begin{itemstep}
	\item Selektionskriterium, Messkriterium. 
	\item Simulated Annealing:
	\begin{itemize}
		\item Wähle Zelle für den Tausch.
		\item Berechne Funktion $E$ für das neue Placement.
		\item Anhand des Messkriteriums wird entschieden ob die Zelle getauscht wird.
		\item Senke die Temperatur und wiederhole.
	\end{itemize}
\end{itemstep}
\end{slide}}




\begin{slide}{Genetisches Routing}
\centerline{\includegraphics[height=6.5cm]{images/genetic_routing}}
\end{slide}





\overlays{5}{%
\begin{slide}{Genetisches Routing (2)}
\begin{itemstep}
	\item Bevölkerung: $\mathcal{P}_c$.
	\item Lösung: Individuum ($p_{best}$).
	\item Qualität: Fitness.
	\item Selektion, Crossover, Mutation.
\end{itemstep}
\FromSlide{5}{\centerline{\includegraphics[height=4cm]{images/random_routing-4}}}
\end{slide}}



\begin{slide}{Channel-Routing}
\centerline{\includegraphics[height=6cm]{images/random_routing-1}}
\end{slide}



\begin{slide}{Channel-Routing (2)}
\centerline{\includegraphics[height=6cm]{images/random_routing-2}}
\end{slide}



\begin{slide}{Channel-Routing (3)}
\centerline{\includegraphics[height=6cm]{images/random_routing-3}}
\end{slide}


\begin{slide}{Benchmarks: Channel-Routing}
\centerline{\includegraphics[height=7cm]{images/channel_routing_benchmark}}
\end{slide}


\overlays{5}{%
\begin{slide}{Zusammenfassung}
\begin{itemstep}
	\item Genetische und Stochastische Verfahren sind sehr gut kombinierbar.
	\item Liefern qualitativ sehr gute Ergebnisse.
	\item Optimal für Parallelisierbarkeit.
	\item Untersuchungen haben gezeigt, dass aktuelle Werkzeuge noch sehr verbesserungswürdig sind.
\end{itemstep}
\FromSlide{5}
\bigskip
\bigskip
\centerline{\textbf{Vielen Dank für die Aufmerksamkeit!}}
\end{slide}}


\end{document}