Faster Circuits for And-Or Paths and Binary Addition
Faster Circuits for And-Or Paths and Binary Addition
dc.contributor.advisor | Held, Stephan | |
dc.contributor.author | Hermann, Anna | |
dc.date.accessioned | 2020-07-24T14:03:34Z | |
dc.date.available | 2020-07-24T14:03:34Z | |
dc.date.issued | 24.07.2020 | |
dc.identifier.uri | https://hdl.handle.net/20.500.11811/8481 | |
dc.description.abstract | We 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.iso | eng | |
dc.rights | In Copyright | |
dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | |
dc.subject | Addierer | |
dc.subject | binäre Addition | |
dc.subject | Übertrag | |
dc.subject | Schaltkreis | |
dc.subject | Tiefenoptimierung | |
dc.subject | Ankunftszeiten | |
dc.subject | adder | |
dc.subject | binary addition | |
dc.subject | And-Or path | |
dc.subject | carry bit | |
dc.subject | circuit | |
dc.subject | depth optimization | |
dc.subject | delay | |
dc.subject | arrival times | |
dc.subject.ddc | 510 Mathematik | |
dc.title | Faster Circuits for And-Or Paths and Binary Addition | |
dc.type | Dissertation oder Habilitation | |
dc.publisher.name | Universitäts- und Landesbibliothek Bonn | |
dc.publisher.location | Bonn | |
dc.rights.accessRights | openAccess | |
dc.identifier.urn | https://nbn-resolving.org/urn:nbn:de:hbz:5-59059 | |
ulbbn.pubtype | Erstveröffentlichung | |
ulbbnediss.affiliation.name | Rheinische Friedrich-Wilhelms-Universität Bonn | |
ulbbnediss.affiliation.location | Bonn | |
ulbbnediss.thesis.level | Dissertation | |
ulbbnediss.dissID | 5905 | |
ulbbnediss.date.accepted | 10.07.2020 | |
ulbbnediss.institute | Zentrale wissenschaftliche Einrichtungen : Forschungsinstitut für Diskrete Mathematik | |
ulbbnediss.fakultaet | Mathematisch-Naturwissenschaftliche Fakultät | |
dc.contributor.coReferee | Hougardy, Stefan |
Dateien zu dieser Ressource
Das Dokument erscheint in:
-
E-Dissertationen (4070)