|
|
|
| 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 |
|
|
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.
|
|
“Combinatorial Optimization and Chip Design”,
long-term cooperation funded by IBM Corporation, since 2010
|
|
[ 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
DOI: 10.1016/j.ipl.2010.08.016[ 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
DOI: 10.1007/978-3-642-36694-9_20[ 8] Stephan Held, Sophie Spirkl
Fast prefix adders for non-uniform input arrival times
Algorithmica , 77: (1): 287--308
2017
DOI: 10.1007/s00453-015-0067-x[ 13] S. Held, S.~T. Spirkl
Binary Adder Circuits of Asymptotically MinimumDepth, Linear Size, and Fan-Out Two
arxiv: 1503.08659v2
ACM Transactions on Algorithms, to appear
2017[ 14] Stephan Held, Dirk Muller, Daniel andScheifele, Rudolf Rotter, Vera Traub, Jens Vygen
Global Routing with Timing Constraints
IEEE Transactions on Computer-Aided Design ofIntegrated Circuits and Systems
Publisher: IEEE
2017[ 15] Stephan Held, Sophie Spirkl
Fast Prefix Adders for Non-uniform Input Arrival Times
Algorithmica , 77: (1): 287--308
Publisher: Springer US
2017[ 16] Stephan Held, Daniel Rotter
Shallow-Light Steiner Arborescences with VertexDelays.
IPCO
2013[ 17] Stephan Held, William Cook, Edward C Sewell
Maximum-weight stable sets and safe lower bounds forgraph coloring
Mathematical Programming Computation : 1--19
Publisher: Springer Berlin/Heidelberg
2012[ 18] Christoph Bartoschek, Stephan andMaÃ?berg, Jens Held, Dieter Rautenbach, Jens Vygen
The repeater tree construction problem
Information Processing Letters , 110: (24): 1079--1083
Publisher: Elsevier
2010[ 19] Stephan Held
Gate sizing for large cell-based designs
Proceedings of the Conference on Design, Automationand Test in Europe
Best paper award at DATE'09
2009[ 20] Stephan Held, Bernhard Korte, Jens Maβberg, Matthias Ringe, Jens Vygen
Clock scheduling and clocktree construction for highperformance ASICs
Proceedings of the 2003 IEEE/ACM internationalconference on Computer-aided design
2003 |
|
|
|
• 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 (2016)
|
|
| 2006 | NATO summer school on combinatorial optimization, Montreal, QC, Canada | | 2009 | Spring School on Mathematics of Chip Design, Hangzhou, China |
|
|
- Master theses: 13, currently 3
- Diplom theses: 2
- PhD theses: 3, currently 2
|
|
Download Profile  |
