Clock Skew Scheduling: Avoiding the Runtime Cost of Mixed-Integer Linear Programming

Clock Skew Scheduling has become a common practice in state-of-the-art FPGAs with the introduction of delay chains on the clock path in the hardware of both Xilinx and Intel
^®
FPGAs, as well as clock skew scheduling algorithms in the CAD tools. Ideally, globally optimal solutions are sought to find the best solution across the entire design. However, using Mixed-Integer Linear Programming (MILP) to find such optimal solutions has a large and sometimes unrealistic runtime cost, especially for bigger designs. Besides, a high runtime does not necessarily correlate to improved performance. We present, in this paper, techniques to reduce the runtime of mixed-integer linear programming approaches to clock skew scheduling, and provide alternatives that can achieve optimal or near-optimal performance gain with a fraction of the MILP runtime cost.