Optimal and Efficient Algorithms for Multidomain Clock Skew Scheduling

Clock skew scheduling is an effective technique to improve the performance of sequential circuits. However, with process variations, it becomes more difficult to implement a large number of clock delays in a precise manner. Multidomain clock skew scheduling (MDCSS) is one way to overcome this limitation. In this paper, we prove the NP-completeness of multidomain clock scheduling problem and design a practical optimal algorithm to solve it. Given the domain number, we bound the number of all possible skew assignments and develop an optimal algorithm with efficient pruning techniques as well as a very efficient heuristics based on the optimal framework. The experimental results on ISCAS89 sequential benchmarks show the optimality and efficiency of our method compared with the most recent approaches to MDCSS.