Optimal prescribed-domain clock skew scheduling

Clock skew scheduling is an efficient technique to minimize the cycle period by properly assigning clock delays to registers in a circuit. But its effectiveness is limited by the difficulty in implementing a large number of arbitrary clock skews. Multi-domain clock skew scheduling and prescribed-domain clock skew scheduling are two alternatives to overcome this shortage by restricting the number of clock domains. While multi-domain clock skew scheduling has been proved to be NP-hard, the hardness of prescribed-domain clock skew scheduling algorithm remains evasive. In this paper, we give a positive answer to the open question by presenting the first efficient and optimal algorithm for prescribed-domain clock skew scheduling. Besides the runtime improvement over the previous method, the experimental results on ISCAS89 benchmarks show comparable quality to those generated by optimal multi-domain clock skew scheduling.