Show simple item record

Timing-Constrained Global Routing with RC-Aware Steiner Trees and Routing Based Optimization

dc.contributor.advisorVygen, Jens
dc.contributor.authorScheifele, Rudolf
dc.date.accessioned2020-04-26T14:20:47Z
dc.date.available2020-04-26T14:20:47Z
dc.date.issued14.06.2019
dc.identifier.urihttps://hdl.handle.net/20.500.11811/7945
dc.description.abstractIn this thesis we consider the global routing problem, which arises as one of the major subproblems in the physical design step in VLSI design. In global routing, we are given a three-dimensional grid graph G with edge capacities representing available routing space, and we have to connect a set of nets in G without overusing any edge capacities. Here, each net consists of a set of pins corresponding to vertices of G, where one pin is the sender of signals, while all other pins are receivers.
Traditionally, next to obeying all edge capacity constraints, the objective has been to minimize wire length and possibly via (edges in z-direction) count, and timing constraints on the chip were only modeled indirectly.
We present a new approach, where timing constraints are modeled directly during global routing: In joint work with Stephan Held, Dirk Mueller, Daniel Rotter, Vera Traub and Jens Vygen, we extend the modeling of global routing as a Min-Max Resource Sharing Problem to also incorporate timing constraints. For measuring signal delays we use the well-established Elmore delay model.
One of the key subproblems here is the computation of Steiner trees minimizing a weighted sum of routing space usages and signal delays. For k pins, this problem is NP-hard to approximate within o(log k), and even the special case k = 2 is NP-hard, as was shown by Haehnle and Rotter. We present a fast approximation algorithm with strong approximation bounds for the case k = 2. For k > 2 we use a multi-stage approach based on modifying the topology of a short Steiner tree and using our algorithm for the two-pin case for computing new connections. Moreover, we present a layer assignment algorithm that assigns z-coordinates to the edges of a given two-dimensional tree.
We also discuss the topic of routing based optimization. Here, the starting point is a complete routing, and timing optimization tools make changes that require incremental adaptations of the underlying routing. We investigate several aspects of this problem and derive a new routing flow that includes our timing-aware global router and routing based optimization steps.
We evaluate our results from this thesis in practice on industrial 14nm microprocessor designs from IBM. Our theoretical results are validated in practice by a strong performance of our timing-aware global routing framework and our new routing flow, yielding significant improvements over the traditional global routing method and the previously used routing flow. Therefore, we conclude that our approaches and results from this thesis are not only theoretically sound but also give compelling results in practice.
dc.language.isoeng
dc.rightsIn Copyright
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/
dc.subjectGlobal Routing
dc.subjectSteiner-Bäume
dc.subjectPfadsuche
dc.subjectResource-Sharing
dc.subjectInkrementelles Routing
dc.subjectSignallaufzeiten
dc.subjectVLSI-Design
dc.subjectSteiner trees
dc.subjectpath search
dc.subjectincremental routing
dc.subjectRC delay
dc.subject.ddc510 Mathematik
dc.titleTiming-Constrained Global Routing with RC-Aware Steiner Trees and Routing Based Optimization
dc.typeDissertation oder Habilitation
dc.publisher.nameUniversitäts- und Landesbibliothek Bonn
dc.publisher.locationBonn
dc.rights.accessRightsopenAccess
dc.identifier.urnhttps://nbn-resolving.org/urn:nbn:de:hbz:5n-54922
ulbbn.pubtypeErstveröffentlichung
ulbbnediss.affiliation.nameRheinische Friedrich-Wilhelms-Universität Bonn
ulbbnediss.affiliation.locationBonn
ulbbnediss.thesis.levelDissertation
ulbbnediss.dissID5492
ulbbnediss.date.accepted07.06.2019
ulbbnediss.instituteZentrale wissenschaftliche Einrichtungen : Forschungsinstitut für Diskrete Mathematik
ulbbnediss.fakultaetMathematisch-Naturwissenschaftliche Fakultät
dc.contributor.coRefereeHeld, Stephan


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

The following license files are associated with this item:

InCopyright