Preserving synchronizing sequences of sequential circuits after retiming

We propose a novel approach to preserve the synchronizing sequences of a circuit after retiming. The significance of this problem stems from the necessity of maintaining correct initialization of circuits after retiming optimizations. It has been previously shown that forward retiming moves across fanout stems can destroy a synchronizing sequence. We build on this observation and introduce the notion of "invalid states" that might arise due to forward moves. We show that the set of synchronizing sequences of a given circuit can be preserved by modifying transitions from those invalid states. We present an algorithm that implicitly computes the set of invalid states. Then, we describe a post-retiming synthesis step that incrementally resynthesizes some next-state functions to alter the behavior of invalid states to ensure correct post-retiming initialization. We report promising experimental results on the ISCAS 89 benchmarks and on a set of retimed circuits from an Intel Pentium-III class microprocessor.