A revisit to the primal-dual based clock skew scheduling algorithm

Clock skew scheduling is a useful sequential circuit optimization method. The run time efficiency of this problem becomes crucial if it must be repeated iteratively in a higher level optimization. The widely recognized Burns' algorithm proposed to solve this problem suffers from high runtime complexity, which makes it unsuitable to be deployed in iterative optimization loops. This algorithm is based on the general concept of primal-dual optimization. In this paper, we demonstrate that a more efficient approach to the clock skew scheduling problem can be developed by designing a new algorithm using the same primal-dual optimization concept. The basic idea of the algorithm is to avoid creating new admissible graph and recalculating θ values for each iteration of the primal-dual optimization. The asymptotic runtime efficiency of our algorithm is of O(|V||E| + |V|²log|V|), which is improved from O(|V|²|E|) thanks to the heap data structure used in our proposed algorithm. The experimental results show that our algorithm is on average 95 times faster than Burns' implementation. In best case, we can observe as much as 189 times speedup.