Incremental retiming for FPGA physical synthesis

ABSTRACT

In this paper, we present a new linear-time retiming algorithm that produces near-optimal results. Our implementation is specically targeted at Altera's Stratix [1] FPGA-based designs, although the techniques described are general enough for any implementation medium. The algorithm is able to handle the architectural constraints of the target device, multiple timing constraints assigned by the user and implicit legality constraints. It ensures that register moves do not create asynchonous problems such as creating a glitch on a clock/reset signal.

REFERENCES

• 1: Altera. Altera Databook.
• 2: Klaus Eckl , Jean Christophe Madre , Peter Zepter , Christian Legl, A practical approach to multiple-class retiming, Proceedings of the 36th ACM/IEEE conference on Design automation, p.237-242, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309920]
• 3: C. Leiserson, F. Rose, and J. Saxe. Optimizing synchronous circuitry. Journal of VLSI and Computer Systems, pages 41--67, 1983.
• 4: C. Leiserson and J. Saxe. Retiming synchronous circuitry. Algorithmica, 6(1):5--35, 1991.
• 5: David Lewis , Vaughn Betz , David Jefferson , Andy Lee , Chris Lane , Paul Leventis , Sandy Marquardt , Cameron McClintock , Bruce Pedersen , Giles Powell , Srinivas Reddy , Chris Wysocki , Richard Cliff , Jonathan Rose, The stratixπ routing and logic architecture, Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays, February 23-25, 2003, Monterey, California, USA [doi>10.1145/611817.611821]
• 6: N. Maheshwari and S. S. Sapatnekar. Efficient retiming of large circuits. IEEE Transactions on VLSI Systems, 6(1):74--83, 1998.
• 7: Narendra Shenoy , Richard Rudell, Efficient implementation of retiming, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.226-233, November 06-10, 1994, San Jose, California, United States
• 8: Deshanand P. Singh , Stephen D. Brown, Incremental placement for layout driven optimizations on FPGAs, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.752-759, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774683]
• 9: 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]
• 10: P. Suaris, D. Wang and N. Chou. Smart Move: A placement-aware retiming and replication method for Field Programmable Gate Arrays. ASIC 2003.
• 11: B. van Antwerpen, M. Hutton, G. Baeckler and R. Yuan. ASafe and Complete Gate-Level Register Retiming Algorithm. In IWLS 2003, pages 140--147, 2003.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids

General Terms:
Algorithms, Experimentation, Measurement, Theory

Keywords:
FPGA, physical synthesis, retiming