SmipRef: An efficient method for multi-domain clock skew scheduling

Conventional clock skew scheduling (CSS) for sequential circuits can be solved effectively using methods including the parametric shortest path algorithm and Howard's algorithm. Nevertheless, its application is practically limited due to the difficulties in reliably implementing a large set of arbitrary dedicated clock delays for flip-flops. Thus multi-domain clock skew scheduling (MDCSS) was proposed to tackle this by constraining the total number of clock delays. However, this new problem is hard to solve optimally in general. In this paper, we propose a novel method to efficiently solve it. Under mild restrictions, the problem is transformed into a special mixed integer linear programming problem, which can be solved optimally using similar techniques for the CSS problem. Then the solution quality is further improved by a critical-cycle-oriented refinement. As a result, our method obtains optimal solutions for 88 of the 93 tests on ISCAS89 benchmarks. The experimental results on large circuits in Opencores benchmarks also demonstrate its efficiency of at least one order faster than existing algorithms. To improve the runtime performance, we also devise a graph pruning algorithm that can be applied to methods for the MDCSS problem as a preprocessing step. Its application on our method shows a speedup of 2.66X on average.

► We propose a novel method to solve the multi-domain clock skew scheduling (MDCSS) problem.
► We propose to transform the MDCSS problem into a special MILP under mild restrictions.
► We devise a generalized Howard's algorithm to efficiently solve the MILP problem.
► Experimental results demonstrate both the solution quality and efficiency of our method.
► We also propose a graph pruning algorithm to further improve the performance of MDCSS algorithms.