Loading Events

« All Events

  • This event has passed.

CESG Seminar: Steiner Trees in Chip Design

March 17, 2014 @ 3:00 pm - 4:00 pm

Room 324 WEB (Wisenbaker Engineering Building)

Stephan Held, University of Bonn

The construction of minimum length Steiner trees is a classical problem in Combinatorial Optimization with a high practical relevance in chip design. However, besides the total length other objectives like speed or reach awareness play an important role. Steiner trees respectively arborescences are used to broadcast electrical signal from a source r to a set T of sinks. In the shallow light Steiner arborescence problem we look for a minimum length arborescence that obeys delay bounds for each r-t-path (t is a sink in T), where the path delay is imposed by its total edge length and its inner vertices. We present a bicriteria approximation algorithm trading off the conflicting goals of minimizing paths delays and total length. Later repeaters need to be inserted into long Steiner trees to refresh the signals and linearize the signal delay, which otherwise would grow quadratically with the length. However, big macro blocks restrict the insertion of repeaters. This leads to the minimum Steiner tree problem with length restrictions on obstacles. We present a 2-approximation for this problem running in O((k log k)^2) time, where k is the number of terminals plus obstacle corners. Under mild assumptions, as they are prevalent in chip design the running times is O(k log^2 k) and the efficiency is demonstrated on real world instances from chip design that are part of the upcoming 11th DIMACS challenge on Steiner trees. Both algorithms can be combined to build shallow light reach-aware Steiner trees.

The results are joint work with Daniel Rotter, and Sophie Spirkl.

Bio: After studying mathematics and computer science in M√ľnster and Bonn, Stephan Held received a Ph.D. in mathematics from the University of Bonn in 2008. From 2009 to 2010 he was a postdoctoral researcher at the Georgia Institute of Technology (Georgia Tech) in Atlanta, USA. In 2010 Stephan Held became an assistant professor and then in 2013 an associate professor for Discrete Optimization at the Research Institute for Discrete Mathematics at the University of Bonn, where he is leading the group for timing optimization in chip design.

Host: Dr. Hu


March 17, 2014
3:00 pm - 4:00 pm