Show simple item record

Faster Circuits for And-Or Paths and Binary Addition

dc.contributor.advisorHeld, Stephan
dc.contributor.authorHermann, Anna
dc.date.accessioned2020-07-24T14:03:34Z
dc.date.available2020-07-24T14:03:34Z
dc.date.issued24.07.2020
dc.identifier.urihttp://hdl.handle.net/20.500.11811/8481
dc.description.abstractWe consider the problem of constructing fast circuits both for binary addition and And-Or paths. And-Or paths are Boolean functions of the form t0 ∧ ( t1 ∨ ( t2 ∧ ( t3 ∨ ... ))) that occur, e.g., as carry bits in adder circuits and as critical paths on computer chips. Motivated by the application in chip design, we aim at optimizing circuit depth or circuit delay, a natural generalization of depth to prescribed input arrival times.
We significantly improve the best known upper bounds on the optimum delay and depth of adder and And-Or path circuits. For instance, regarding adder circuits where the number of gates is linear in the number n of inputs, we reduce the gap to the best known lower bound from O(√log2 n) to O(log2log2log2n).
Moreover, we develop an exact algorithm for delay optimization of generalized And-Or paths, a generalization of And-Or paths where ∧ and ∨ do not necessarily alternate. For the general problem, our algorithm is the first known exact approach; for the special case of depth optimization of And-Or paths, our algorithm is both theoretically and empirically drastically faster than all previous exact algorithms.
Finally, we present an algorithm for delay optimization of And-Or paths that fulfills the best known delay guarantee and computes optimum solutions on almost all practical instances. We demonstrate the successful application of this algorithm in BonnLogic, a logic optimization tool that is used to optimize critical paths during the chip design flow of IBM.
en
dc.language.isoeng
dc.rightsIn Copyright
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/
dc.subjectAddierer
dc.subjectbinäre Addition
dc.subjectÜbertrag
dc.subjectSchaltkreis
dc.subjectTiefenoptimierung
dc.subjectAnkunftszeiten
dc.subjectadder
dc.subjectbinary addition
dc.subjectAnd-Or path
dc.subjectcarry bit
dc.subjectcircuit
dc.subjectdepth optimization
dc.subjectdelay
dc.subjectarrival times
dc.subject.ddc510 Mathematik
dc.titleFaster Circuits for And-Or Paths and Binary Addition
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-59059
ulbbn.pubtypeErstveröffentlichung
ulbbnediss.affiliation.nameRheinische Friedrich-Wilhelms-Universität Bonn
ulbbnediss.affiliation.locationBonn
ulbbnediss.thesis.levelDissertation
ulbbnediss.dissID5905
ulbbnediss.date.accepted2020-07-10
ulbbnediss.instituteZentrale wissenschaftliche Einrichtungen : Forschungsinstitut für Diskrete Mathematik
ulbbnediss.fakultaetMathematisch-Naturwissenschaftliche Fakultät
dc.contributor.coRefereeHougardy, Stefan


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