Retiming and resynthesis with sweep are complete for sequential transformation

Hai Zhou*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

There is a long history of investigations and debates on whether a sequence of retiming and resynthesis is complete for all sequential transformations (on steady states). It has been shown that the sweep operation, which adds or removes registers not used by any output, is necessary for some sequential transformations. However, it is an open question whether retiming and resynthesis with sweep are complete. This paper proves that the operations are complete, but with one caveat: at least one resynthesis operation needs to look through the register boundary into the logic of previous cycle. We showed that this one-cycle reachability is required for retiming and resynthesis to be complete for re-encodings with different code length. This requirement comes from the fact that Boolean circuit is used for a discrete function thus its range needs to be computed by a traversal of the circuit. In theory, five operations in the order of sweep, resynthesis, retiming, resynthesis, and sweep are already complete. However, some practical limitations on resynthesis must be considered. The complexity of retiming and resynthesis verification is also discussed.

Original languageEnglish (US)
Title of host publication9th International Conference Formal Methods in Computer Aided Design, FMCAD 2009
Pages192-197
Number of pages6
DOIs
StatePublished - Dec 7 2009
Event9th International Conference Formal Methods in Computer Aided Design, FMCAD 2009 - Austin, TX, United States
Duration: Nov 15 2009Nov 18 2009

Other

Other9th International Conference Formal Methods in Computer Aided Design, FMCAD 2009
CountryUnited States
CityAustin, TX
Period11/15/0911/18/09

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computer Graphics and Computer-Aided Design

Fingerprint Dive into the research topics of 'Retiming and resynthesis with sweep are complete for sequential transformation'. Together they form a unique fingerprint.

Cite this