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

Abstract

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.

Keywords

linear-time retiming / sequential optimization / sharing register / field programmable gate array(FPGA)

References

[1] Leiserson C. E., Saxe J. B. Retiming synchronous circuitry [J]. Algorithmica, 1991, 6(1): 5 35

[2] Wang J, Zhou H. An efficient incremental algorithm for min-area retiming[C]. In: Proceedings of the 45th Annual Design Automation Conference. Anaheim, USA, 2008. 528–533.

[3] Hurst A P, Mishchenko A, Brayton R. Minimizing implementation costs with end-to-end retiming[C]. In: Proceedings of the International Workshop on Logic and Synthesis. San Diego, USA, 2007. 9–16.

[4] Debasish Das, Wang J, Zhou H. iRetILP: An efficient incremental algorithm for min-period retiming under general delay model[C]. In: Proceedings of the 15th Asia and South Pacific Design Automation Conference. Taiwan, China, 2010. 61–67.

[5] In-Ho Moon. Compositional verification of retiming and sequential optimizations[C]. In: Proceedings of the 45th Annual Design Automation Conference. Anaheim, USA, 2008. 131–136.

[6] Pan P C, Lin C C. A new retiming-based technology mapping algorithm for LUT-based FPGAs[C]. In: Proceedings of the ACM/SIGDA Sixth International Symposium on Field Programmable Gate Array. Monterey, USA, 1998. 35–42.

[7] Singh D P, Manohararajah V, Brown S D. Incremental retiming for FPGA physical synthesis[C]. In: Proceedings of the 42nd Annual Design Automation Conference. San Diego, USA, 2005. 433–438.

[8] Singh D P, Brown S D. Integrated retiming and placement for field programmable gate arrays[C]. In: Proceedings of the ACM/SIGDA Tenth International Symposium on Field Programmable Gate Arrays(FPGA). Monterey, USA, 2002. 67–76.

[9] Shenoy N, Rudell R. Efficient implementation of retiming[C]. In: Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. San Jose, USA, 1994. 226–233.

[10] Maheshwari N., Sapatnekar S. S. Efficient retiming of large circuits [J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 1998, 6(1): 74-83.

[11] Zhou H. Deriving a new efficient algorithm for min-period retiming [C]. In: Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC). Shanghai, China, 2005. 990–993.

[12] Ray S, Mishchenko A, Brayton R et al. Minimumperturbation retiming for delay optimization [C]. In: Proceedings of the International Workshop on Logic and Synthesis. Irvine, USA, 2010. 90–94.

[13] Touati H. J., Brayton R. K. Computing the initial states of retimed circuits [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1993, 12(1): 157-162.

[14] Mishchenko A., Zhang J. S., Sinha S., et al. Using simulation and satisfiability to compute flexibilities in Boolean networks[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006, 25(5): 743-755.

[15] Eén N., Sörensson N. An extensible SAT-solver[C]. Proceedings of the International Conference on Theory and Applications of Satisfiability Testing, 2003, Italy: Santa Margherita Ligure 502-518.

[16] Hurst A P, Mishchenko A, Brayton R. Scalable min-register retiming under timing and initializability constraints[C]. In: Proceedings of the 45th Annual Design Automation Conference. Anaheim, USA, 2008. 534–539.

[17] Hurst A P, Mishchenko A, Brayton R K. Fast minimumregister retiming via binary maximum-flow[C]. In: Proceedings of the Formal Methods in Computer Aided Design. Austin, USA, 2007. 181–187.

[18] Berkeley Logic Synthesis and Verification Group. ABC: A System for Sequential Synthesis and Verification[EB/OL]. http://www.eecs.berkeley.edu/~alanmi/abc/, 2007.

[19] IWLS 2005 Benchmarks[EB/OL]. http://iwls.org/iwls2005/benchmarks.html, 2005.

[20] Altera QUIP Toolkit 9. 0 Benchmarks [EB/OL]. https://www.altera.com/support/software/download/altera_design/quip/quip-download.jsp, 2009.