Schnellere Computerchips durch Graphentheorie

Erneuter "Best Paper Award" für die Diskrete Mathematik in Bonn

Der Bonner Master-Student Benjamin Rockel und sein Betreuer Stephan Held, Professor am Bonner Forschungsinstitut für Diskrete Mathematik, erhielten auf der Design Automation Conference in San Francisco, einer weltweit führenden Konferenz zum Chip-Design, einen Preis für die beste Forschungsarbeit ("Best Paper Award"). Die Arbeit mit dem Titel "Exact Algorithms for Delay-Constrained Steiner Arborescences" beschäftigt sich mit der schnellen, ressourcenschonenden Verteilung von Signalen auf einem Chip.

Beim Chipdesign verwendet man Werkzeuge aus der Graphentheorie: gerichtete Baumstrukturen, sogenannte Steiner-Arboreszenzen. Ziel ist es, die Signale durch solche Arboreszenzen optimal zu verteilen. Optimal heißt: Die Signalübertragung soll natürlich möglichst schnell, hinsichtlich des Stromverbrauchs aber auch möglichst ressourcenschonend sein. Ein Teilproblem bei diesem Verfahren besteht darin, wie man eine Steiner-Arboreszenz optimal in die zweidimensionale Ebene einbetten kann. In diesem Bereich setzt die Arbeit von Benjamin Rockel und Stephan Held an: Die beiden Bonner Wissenschaftler modellieren das Problem als Flussproblem, bei dem die Kanten der Arboreszenz mit Gewichten (Kosten) versehen werden. Auf diese Weise kann die Suche nach einer optimalen Baumtopologie verbessert und die Laufzeit des gesamten Algorithmus erheblich verkürzt werden. 

Prämierte Veröffentlichung:

Held, Stephan; Rockel, Benjamin (2018) "Exact Algorithms for Delay-bounded Steiner Arborescences", Proceedings of the 55th Annual Design Automation Conference 44:1-44:6, DOI:10.1145/3195970.3196048