A practical cut-based physical retiming algorithm for field programmable gate arrays

ABSTRACT

This paper presents a heuristic cut-based retiming algorithm for FPGA designs. It handles complex retiming constraints including timing, architectural and structural constraints; improves retimeability by incorporating logic resynthesis; and efficiently integrates with incremental placement. Thus, the algorithm improves timing compliance by allowing groups of registers to be rapidly retimed across blocks of combinational logic in the physical domain without violating any complex constraints. Experiments have shown that this algorithm can improve the performance of FPGA designs by 16% on average, while achieving a 61.7% speedup in terms of runtime compared with classic retiming algorithms.

REFERENCES

• 1: C. Leiserson, F. Rose and J. Saxe, "Optimizing Synchronous Circuitry". J. VLSI and Computer Systems, pp. 41--67, 1983.
• 2: S. Sapatnekar and R. Deokar, "Utilizing the retiming skew equivalence in a practical algorithm for retiming large circuits", IEEE Trans. on CAD of ICAS, pp. 1237--1248. Oct. 1996.
• 3: G. Even, I. Y. Spillinger and L. Stok, "Retiming revised and reversed", IEEE Trans. on CAD of ICAS, pp. 348--357, mar., 1996.
• 4: Kumar N. Lalgudi , Marios C. Papaefthymiou, DELAY: an efficient tool for retiming with realistic delay modeling, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.304-309, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217546]
• 5: Jason Cong , Sung Kyu Lim, Physical planning with retiming, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 6: Deshanand P. Singh , Stephen D. Brown, Integrated retiming and placement for field programmable gate arrays, Proceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays, February 24-26, 2002, Monterey, California, USA [doi>10.1145/503048.503059]
• 7: P. Suaris, D. Wang and N. Chou, "Smart Move: A Placement-aware Retiming And Replication Method for Field Programmable Gate Arrays", Proc. ASICON'2003, pp. 67--70, Beijing, China.
• 8: Ulrich Seidl , Klaus Eckl , Frank Johannes, Performance-Directed Retiming for FPGAs Using Post-Placement Delay Information, Proceedings of the conference on Design, Automation and Test in Europe, p.10770, March 03-07, 2003
• 9: Chris Chu , Evangeline F. Y. Young , Dennis K. Y. Tong , Sampath Dechu, Retiming with Interconnect and Gate Delay, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.221, November 09-13, 2003 [doi>10.1109/ICCAD.2003.118]
• 10: "Altera Stratix FPGA family", Altera corporation, 2004.
• 11: Virtex-II 1.5V Field-Programmable Gate Arrays, Xilinx, 2001.