Constrained clock shifting for field programmable gate arrays

ABSTRACT

Circuits implemented in FPGAs have delays that are dominated by its programmable interconnect. This interconnect provides the ability to implement arbitrary connections. However, it contains both highly capacitive and resistive elements. The delay encountered by any connection depends strongly on the number of interconnect elements used to route the connection. These delays are only completely known after the place and route phase of the CAD flow. We propose the use of Clock Shifting optimization techniques to improve the clock frequency as a post place and route step.Clock Shifting Optimization is a technique first formalized in [4]. It is a cycle-stealing algorithm that allows one to reduce the critical path delay of a synchronous circuit by shifting the clock signals at each register. This technique allows late arriving signals to be sampled at a later point in time by intentionally introducing a skew on the clock input of the sampling register. Typical FPGAs contain a number of special purpose global clock networks that distribute clock signals to every register in the chip. Unused global clock lines in FPGAs can be used to distribute a finite set of clock skews to the entire circuit. We propose an efficient integer programming method to find the optimal circuit improvement for a finite set of clock skews. This technique is modified to consider inherent uncertainties present in the timing models. The uncertainty controls the aggressiveness of the optimizations as we must take great care in ensuring functionality for any range of possible timing characteristics.Our results confirm intuition that more aggressive speed optimizations can be performed as timing models become more accurate. We also show that providing 4 skewed versions of the nominal clock signal results in the best delay--area tradeoff. This result is evocative as it may suggest future FPGA architectures that contain greater numbers of global clock lines, as we tradeoff gains in speed for greater power requirements from increased clock network flexibility.

REFERENCES

• 1: Altera.Altera 2000 Databook .Available from: http://www.altera.com/html/literature/lds.html.
• 2: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 3: J.Cong and Y.Ding.FlowMap:An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA esigns.IEEE Transactions on CAD ,pages 1 -12,Jan 1994.
• 4: John P. Fishburn, Clock Skew Optimization, IEEE Transactions on Computers, v.39 n.7, p.945-951, July 1990 [doi>10.1109/12.55696 ]
• 5: C.Leiserson,F.Rose,and J.Saxe.Optimizing synchronous circuitry.Journal of VLSI and Computer Systems ,pages 41 -67,1983.
• 6: C.Leiserson and J.Saxe.Retiming synchronous circuitry.Algorithmica ,6(1):5 -35,1991.
• 7: 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]
• 8: Deshanand P. Singh , Stephen D. Brown, The case for registered routing switches in field programmable gate arrays, Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays, p.161-169, February 2001, Monterey, California, United States [doi>10.1145/360276.360331]
• 9: Xilinx.Xilinx 2000 Databook .Available from: http://www.xilinx.com/partinfo/databook.htm.
• 10: Xilinx.A ook at "Minimum "Delays .Available from: http://support.xilinx.com/xcell/xl21/xl21-40.pdf.