Retiming for the global optimization of synchronous sequential circuit

Peripheral retiming (if it exists) is a method for resynthesising synchronous sequential circuits in which all registers are moved to the peripheral edges. In this paper, we propose a simple approach which considers the retiming of a whole circuit and which can be applied to any arbitrary sequential circuit (i.e. where the usual peripheral retiming concept does not hold). This approach consists in moving the maximum number of registers to the peripheral edges of the whole circuit. First, we model the circuit by means of a Petri net (PN) and show that retiming corresponds to fire transitions in the PN. The theoretical results can then be easily justified. Second, we prove that peripheral retiming is equivalent to solving a transportation problem in a weighted bipartite graph (inputs/outputs) and propose an algorithm for the global optimization of sequential circuits. Some examples of circuits are optimized to show the effectiveness of our approach