TY - GEN
T1 - Optimal prescribed-domain clock skew scheduling
AU - Li, Li
AU - Lu, Yinghai
AU - Zhou, Hai
PY - 2012/4/26
Y1 - 2012/4/26
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84859946868&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84859946868&partnerID=8YFLogxK
U2 - 10.1109/ASPDAC.2012.6165008
DO - 10.1109/ASPDAC.2012.6165008
M3 - Conference contribution
AN - SCOPUS:84859946868
SN - 9781467307727
T3 - Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC
SP - 523
EP - 527
BT - ASP-DAC 2012 - 17th Asia and South Pacific Design Automation Conference
T2 - 17th Asia and South Pacific Design Automation Conference, ASP-DAC 2012
Y2 - 30 January 2012 through 2 February 2012
ER -