Fast algorithms for retiming large digital circuits

dc.contributor.advisor Sachin Sapatnekar Maheshwari, Naresh
dc.contributor.department Electrical and Computer Engineering 2018-08-23T06:17:37.000 2020-06-30T07:14:28Z 2020-06-30T07:14:28Z Thu Jan 01 00:00:00 UTC 1998 1998
dc.description.abstract <p>The increasing complexity of VLSI systems and shrinking time to market requirements demand good optimization tools capable of handling large circuits. Retiming is a powerful transformation that preserves functionality, and can be used to optimize sequential circuits for a wide range of objective functions by judiciously relocating the memory elements. Leiserson and Saxe, who introduced the concept, presented algorithms for period optimization (minperiod retiming) and area optimization (minarea retiming). The ASTRA algorithm proposed an alternative view of retiming using the equivalence between retiming and clock skew optimization;The first part of this thesis defines the relationship between the Leiserson-Saxe and the ASTRA approaches and utilizes it for efficient minarea retiming of large circuits. The new algorithm, Minaret, uses the same linear program formulation as the Leiserson-Saxe approach. The underlying philosophy of the ASTRA approach is incorporated to reduce the number of variables and constraints in this linear program. This allows minarea retiming of circuits with over 56,000 gates in under fifteen minutes;The movement of flip-flops in control logic changes the state encoding of finite state machines, requiring the preservation of initial (reset) states. In the next part of this work the problem of minimizing the number of flip-flops in control logic subject to a specified clock period and with the guarantee of an equivalent initial state, is formulated as a mixed integer linear program. Bounds on the retiming variables are used to guarantee an equivalent initial state in the retimed circuit. These bounds lead to a simple method for calculating an equivalent initial state for the retimed circuit;The transparent nature of level sensitive latches enables level-clocked circuits to operate faster and require less area. However, this transparency makes the operation of level-clocked circuits very complex, and optimization of level-clocked circuits is a difficult task. This thesis also presents efficient algorithms for retiming large level-clocked circuits. The relationship between retiming and clock skew optimization for level-clocked circuits is defined and utilized to develop efficient retiming algorithms for period and area optimization. Using these algorithms a circuit with 56,000 gates could be retimed for minimum period in under twenty seconds and for minimum area in under 1.5 hours.</p>
dc.format.mimetype application/pdf
dc.identifier archive/
dc.identifier.articleid 12630
dc.identifier.contextkey 6455595
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath rtd/11631
dc.language.iso en
dc.source.bitstream archive/|||Fri Jan 14 18:54:47 UTC 2022
dc.subject.disciplines Computer Sciences
dc.subject.disciplines Electrical and Electronics
dc.subject.keywords Electrical and computer engineering
dc.subject.keywords Computer engineering
dc.title Fast algorithms for retiming large digital circuits
dc.type article
dc.type.genre dissertation
dspace.entity.type Publication
relation.isOrgUnitOfPublication a75a044c-d11e-44cd-af4f-dab1d83339ff dissertation Doctor of Philosophy
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
3.29 MB
Adobe Portable Document Format