UTILIZING THE RETIMING-SKEW EQUIVALENCE IN A PRACTICAL ALGORITHM FOR RETIMING LARGE CIRCUITS

The introduction of clock skew at an edge-triggered flip-flop has an e ffect that is similar to the movement of the flip-flop across combinat ional logic module boundaries, and these are continuous and discrete o ptimizations with the same effect, While this fact has been recognized before, this paper, for the first time, utilizes this information to find an optimal retiming efficiently, The clock period is guaranteed t o be at most one gate delay larger than the optimal clock period found using skew alone; note that since skew is a continuous optimization, it is possible that the optimal period may not be achievable, The meth od views the circuit hierarchically, first solving the clock skew prob lem at one level above the gate level, and then using local transforma tions at the gate level to perform retiming for the optimal clock peri od, The solution is thus divided into two phases, In Phase A, the cloc k skew optimization problem is solved with the objective of minimizing the clock period, while ensuring that the difference between the maxi mum and the minimum skew is minimized, Next, in Phase B, retiming is e mployed and some flip-flops are relocated across gates in an attempt t o set the values of all skews to be as close to zero as possible.