Zur Kurzanzeige

Fast Repeater Tree Construction

dc.contributor.advisorVygen, Jens
dc.contributor.authorBartoschek, Christoph
dc.date.accessioned2020-04-20T00:21:31Z
dc.date.available2020-04-20T00:21:31Z
dc.date.issued18.09.2014
dc.identifier.urihttp://hdl.handle.net/20.500.11811/6134
dc.description.abstractRepeaters are used during physical design of chips to improve the electrical and timing properties of interconnections. They are added along Steiner trees that connect root gates to sinks, creating repeater trees. Their construction became a crucial part of chip design. We present a new algorithm to solve the repeater tree construction problem.
We first present an extensive version of the Repeater Tree Problem. Our problem formulation encapsulates most of the constraints that have been studied so far. We also consider several aspects for the first time, for example, slew dependent required arrival times at repeater tree sinks. The employed technology, the properties of available repeaters and metal wires, the shape of the chip, the temperature, the voltages, and many other factors highly influence the results of repeater tree construction. To take all this into account, we extensively preprocess the environment to extract parameters for our algorithms.
We first present an algorithm for Steiner tree creation and prove that our algorithm is able to create timing-efficient as well as cost-efficient trees. Our algorithm is based on a delay model that accurately describes the timing that one can achieve after repeater insertion upfront.
Next, we deal with the problem of adding repeaters to a given Steiner tree. The predominantly used algorithms to solve this problem use dynamic programming. However, they have several drawbacks. Firstly, potential repeater positions along the Steiner tree have to be chosen upfront. Secondly, the algorithms strictly follow the given Steiner tree and miss optimization opportunities. Finally, dynamic programming causes high running times. We present our new buffer insertion algorithm, Fast Buffering, that overcomes these limitations. It is able to produce results with similar quality to a dynamic programming approach but a much better running time. In addition, we also present improvements to the dynamic programming approach that allows us to push the quality at the expense of a high running time.
We have implemented our algorithms as part of the BonnTools physical design optimization suite developed at the Research Institute for Discrete Mathematics in cooperation with IBM. Our implementation deals with all tedious details of a grown real-world chip optimization environment.
We have created extensive experimental results on challenging real-world test cases provided by our cooperation partner. Our algorithm can solve about 5.7 million instances per hour.
dc.language.isoeng
dc.rightsIn Copyright
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/
dc.subjectVLSI
dc.subjectChipdesign
dc.subjectInverterbaum
dc.subjectTimingoptimierung
dc.subjectSteinerbaum
dc.subjectOptimierung
dc.subjectVLSI design
dc.subjectchip design
dc.subjectinverter tree
dc.subjectbuffering
dc.subjecttiming optimization
dc.subjectSteiner tree
dc.subjectoptimization
dc.subjectphysical design
dc.subjectinterconnect
dc.subject.ddc004 Informatik
dc.titleFast Repeater Tree Construction
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-36897
ulbbn.pubtypeErstveröffentlichung
ulbbnediss.affiliation.nameRheinische Friedrich-Wilhelms-Universität Bonn
ulbbnediss.affiliation.locationBonn
ulbbnediss.thesis.levelDissertation
ulbbnediss.dissID3689
ulbbnediss.date.accepted2014-07-11
ulbbnediss.instituteMathematisch-Naturwissenschaftliche Fakultät : Fachgruppe Mathematik / Mathematisches Institut
ulbbnediss.fakultaetMathematisch-Naturwissenschaftliche Fakultät
dc.contributor.coRefereeHeld, Stephan


Dateien zu dieser Ressource

Thumbnail

Das Dokument erscheint in:

Zur Kurzanzeige

Die folgenden Nutzungsbestimmungen sind mit dieser Ressource verbunden:

InCopyright