Parallelisierung von Routingalgorithmen

Während des Routings wird festgelegt, wie die Verbindungen zwischen den einzelnen Funktionseinheiten eines Chips durch die Metalllagen geführt werden. Eine hohe Qualität der erzeugten Verdrahtung ist essentiell für die Einhaltung von Designzielen, insbesondere von Timingconstraints. Das Auffinden einer optimalen Verdrahtung für ein gegebenes Layout ist allerdings extrem schwierig. Aus diesem Grund ist die hohe Laufzeit ein wesentliches Problem aktueller Routingwerkzeuge.

Ein Teil dieses Problems ist, dass die sequentielle Rechenleistung von Prozessoren in den letzten Jahren nur noch langsam gesteigert werden konnte. Die durch Parallelität erreichbare Rechenleistung ist zwar deutlich stärker gestiegen, kann von bisherigen Routingalgorithmen allerdings üblicherweise nicht ausgenutzt werden, da diese vornehmlich sequentiell arbeiten.

Ziel dieses Forschungsprojektes ist die Beschleunigung dieses Vorgangs durch die Ausnutzung von Parallelrechnern zu beschleunigen, insbesondere hochparalleler Architekturen, wie Graphical Processing Units. Zu diesem Zweck sollen Algorithmen und Datenstrukturen gefunden werden, die eine effiziente Aufteilung des Problems auf eine große Anzahl an Recheneinheiten erlauben.