Incremental min-period retiming algorithm for FPGA synthesis based on influence of fan-outs.

An improved linear-time retiming algorithm is proposed to incrementally optimize the clock period, especially considering the influence of the in-out degree of the critical combinational elements. Firstly, the critical elements are selected from all the critical combinational elements to retime. Secondly, for the nodes that cannot be performed with such retiming, register sharing is implemented while the path delay is kept unchanged. The incremental algorithm can be applied with the technology mapping to minimize the critical path delay and obtain fewer registers in the retimed circuit with the near-optimal clock period. Compared with Singh's incremental algorithm, experiments show that the proposed algorithm can reduce the flip-flop count by 11% and look-up table(LUT) count by 5% while improving the minimum clock period by 6%. The runtime is also reduced by 9% of the design flow. [ABSTRACT FROM AUTHOR]