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.
Reference
Deshanand Singh and Stephen D. Brown, "Constrained Clock Shifting for Field Programmable Gate Arrays," International Symposium on FPGAs (FPGA.2002), Monterey, CA, Feb 2002, pp. 121-126.
(Download Full Paper)