Show simple item record

Global Timing Optimization in Chip Design

dc.contributor.advisorHeld, Stephan
dc.contributor.authorDaboul, Siad
dc.date.accessioned2021-04-14T07:42:23Z
dc.date.available2021-04-14T07:42:23Z
dc.date.issued12.04.2021
dc.identifier.urihttps://hdl.handle.net/20.500.11811/9036
dc.description.abstractIn this thesis, we aim at solving the interconnect optimization problem comprehensively. By balancing global timing, routing, placement, and power constraints in a global model, we obtain solutions which outperform the classic approach in both resource usage and timing quality.
For the time-cost tradeoff problem in chip design, we present a new implementation of a primal-dual optimization algorithm. Instead of requiring separable delay constraints as in previous approaches, it only has mild assumptions on the delay model. The approach allows us to achieve leakage reductions of up to 8% on netlists that were pre-optimized by one of the most successful algorithms.
The Vt assignment problem with separable delays directly corresponds to the discrete time-cost tradeoff problem in directed graphs. If d is the maximum number of vertices in any path, our practical algorithm yields a d approximation. Previously, Svensson showed that for general instances with unbounded values of d no constant factor approximation exists if we assume P≠NP and the Unique Games Conjecture holds. For the discrete time-cost tradeoff problem, we devise an improved algorithm with a guarantee of d/2. We achieve this by reformulating the problem to a vertex cover problem in d-partite hypergraphs. For this more general problem, the approximation ratio of our new algorithm is slightly better than d/2, which is asymptotically best possible under the Unique Games Conjecture and P≠NP. We also study the inapproximability of the time-cost tradeoff problem and show that no better approximation ratio than (d+2)/4 is possible, again assuming the Unique Games Conjecture and P≠NP. Therefore, we settle the approximability of this problem up to a factor of less than 2.
We then focus on the gate sizing problem. It is similar to the time-cost tradeoff problem but optimizes a more involved timing function, which is not linear but only posynomial. Schorr presented a resource-sharing formulation for the gate sizing problem in her dissertation. We give a new runtime analysis for the resource sharing algorithm applied to gate sizing, resolving small inaccuracies in the previous proof.
Finally, we consider the buffering problem. In this problem the interconnect for all nets should be computed. Simultaneously, repeating gates need to be inserted to strengthen electrical signals. We build on the resource sharing formulation for this problem given by Rotter and his initial implementation. On the theoretic side, we modify the model by using a path based formulation for timing proposed by Hähnle. The new implementation is now robust enough to be used in an industrial environment. It outperforms a state-of-the-art design flow in almost all metrics, including netlength, power, congestion and timing. We also implement speedups that reduce the runtime by up to 70%.
en
dc.language.isoeng
dc.rightsIn Copyright
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/
dc.subjectTiming Optimierung
dc.subjectTime-Cost Tradeoff Problem
dc.subjectApproximationsalgorithmen
dc.subjectSteiner-Bäume
dc.subjectResource-Sharing
dc.subjectSignallaufzeiten
dc.subjectVLSI-Design
dc.subject.ddc510 Mathematik
dc.titleGlobal Timing Optimization in Chip Design
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:5-61837
ulbbn.pubtypeErstveröffentlichung
ulbbnediss.affiliation.nameRheinische Friedrich-Wilhelms-Universität Bonn
ulbbnediss.affiliation.locationBonn
ulbbnediss.thesis.levelDissertation
ulbbnediss.dissID6183
ulbbnediss.date.accepted19.03.2021
ulbbnediss.instituteZentrale wissenschaftliche Einrichtungen : Forschungsinstitut für Diskrete Mathematik
ulbbnediss.fakultaetMathematisch-Naturwissenschaftliche Fakultät
dc.contributor.coRefereeVygen, Jens
ulbbnediss.contributor.gnd1084027801


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