Profile
Profile

Prof. Dr. Stephan Held

E-mail: held(at)or.uni-bonn.de
Phone: +49 228 73 8740
Fax: +49 228 73 8771
Homepage: http://www.or.uni-bonn.de/~held/Stephan_Held.html
Room: 303
Institute: Research Institute for Discrete Mathematics
Bonn International Graduate School - BIGS
Research Areas: Research Area KL
Former Research Area K
Date of birth: 04.May 1976

Academic Career

2008

Dr. rer. nat., University of Bonn

2009 - 2010

Postdoc, Georgia Institute of Technology, Atlanta, GA, USA

2010 - 2013

Junior Professor (W1), University of Bonn

2013 - 2016

Professor (W2), tenure track, University of Bonn

Since 2016

Professor (W2), University of Bonn

Research Profile

My current research focus is on combinatorial optimization and its application in chip design. Here, one of the major problems is the Steiner tree problem, which occurs in various variants. The major problem is to find Steiner trees for fast but economic signal distribution [1,2,3], potentially with obstacles [4], and subsequent repeater insertion [5]. Steiner trees on a chip cannot be designed independently but are mutually dependent in their space consumption and signal speeds. Here we showed how to to incorporate all constraints into a common resource sharing model and solve its continuous relaxation efficiently [6].
Steiner trees occur also in the realization of parity functions and similar commutative functions. Here there are also side terminals besides the major terminals and the problems becomes a two-level Steiner tree problem [7]. However, most logic functions are more complex than parity calculations. One of the most important ones is binary addition, for which we improved the running time for optimizing the depth of carry-bit calculation from cubic to near-linear [8]. Other important aspects of signal speed optimization are the gate placement and sizing [9,10,11,12].
A major challenge in chip design is the huge number of design variables and constraints. While some specific subproblems, such as placement, buffering, gate sizing, and routing can be solved more or less well in practice, approaches tackling several of these steps are mostly build on heuristics. We plan to continue the approach for timing-constrained global routing in [6] to integrate most design variables into a single global mathematical problem formulation, aiming provably good computer chips.
We will continue to find better structures for logic functions. The carry-bit circuits computed by the algorithm from [8] are fastest possible when restricting to so called prefix gates, which are pre-dominantly used in industry. When abandoning this paradigm, faster adders are possible, but were hardly investigated in the last 40 years. We want to characterize the general best tradeoffs between depth, size, and interconnect complexity for adders and other functions on modern computer chips. A new focus is related to the traveling salesman problem (TSP). The major application of the TSP in practice is the vehicle routing problem, where cities have to be partitioned to multiple salesmen, which visit their bounded number of cities in a tour. The total length of all tours is to be minimized. For this problem it is not even clear whether the separation of the so called subtour inequalities is NP-hard or solvable in polynomial time. A polynomial time algorithm would have immediate positive consequences to many practical applications in logistics. Another interesting question in this respect is the best topology of such a tour network. We want to study the benefit of further sub-partitions.

Research Projects and Activities

“Combinatorial Optimization and Chip Design”,
long-term cooperation funded by IBM Corporation, since 2010

Selected Publications

[1] C. Bartoschek, S. Held, D. Rautenbach, J. Vygen
Efficient Generation of Short and Fast Repeater Tree Topologies
Proceedings of the International Symposium on Physical Design
2006
[2] C. Bartoschek, S. Held, J. Maß berg, D. Rautenbach, J. Vygen
The repeater tree construction problem
Inform. Process. Lett. , 110: (24): 1079--1083
2010
[3] Stephan Held, Daniel Rotter
Shallow-light Steiner arborescences with vertex delays
Integer programming and combinatorial optimization
of Lecture Notes in Comput. Sci. : 229--241
Publisher: Springer, Heidelberg
2013
[4] S. Held, S.T. Spirkl
A fast algorithm for rectilinear Steiner trees with length restrictions on obstacles
Proceedings of the International Symposium on Physical Design, ACM : 37--44
2014
[5] C. Bartoschek, S. Held, D. Rautenbach, J. Vygen
Fast buffering for optimizing worst slack and resource consumption in repeater rrees
Proceedings International Symposium on Physical Design
2009
[6] S. Held, D. Müller, D. Rotter, V. Traub, J. Vygen
Global routing with inherent static timing constraints
Proceedings of the IEEE/ACM International Conference on Computer-Aided Design : 102--109
2015
[7] Stephan Held, Nicolas Kämmerling
Two-level rectilinear Steiner trees
Comput. Geom.
,
61: : 48--59
2017
[8] Stephan Held, Sophie Spirkl
Fast prefix adders for non-uniform input arrival times
Algorithmica , 77: (1): 287--308
2017
[9] S. Held
Gate sizing for large cell-based designs
Proceedings Design Automation & Test in Europe 2009
Best Paper Award
2009
[10] S. Held, U. Schorr
Post-routing latch optimization for timing closure
Proc. 51st Design Automation Conference, ACM , 7: (6): 1--7
2014
[11] A. Bock, S. Held, N. Kämmerling, U. Schorr
Local search algorithms for timing-driven placement under arbitrary delay models
Proc. 52th Design Automation Conference, ACM , 29: (6): 1--29
2015
[12] S. Held, J. Hu
Gate sizing
Electronic Design Automation for Integrated Circuits Handbook (2nd edition)
Publisher: CRC press
2016
[13] Stephan Held, William Cook, Edward C. Sewell
Maximum-weight stable sets and safe lower bounds for graph coloring
Math. Program. Comput. , 4: (4): 363--381
2012
[14] S. Held, B. Korte, J. Maßberg, M. Ringe, J. Vygen
Clock scheduling and clocktree construction for high performance ASICs
Proceedings of the IEEE/ACM International Conference on Computer-Aided Design
2003

Publication List

Editorships

• IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (since 2016)

Member in technical program committees of conferences with published proceedings:
• International Symposium on Physical Design (2014 - 2016)
• International Conference on Computer-Aided Design (since 2016)

Selected Invited Lectures

2006

NATO summer school on combinatorial optimization, Montreal, QC, Canada

2009

Spring School on Mathematics of Chip Design, Hangzhou, China

Supervised Theses

  • Master theses: 7, currently 3
  • Diplom theses: 2
  • PhD theses: 2, currently 2
Download Profile