An efficient algorithm for multi-domain clock skew scheduling

Yanling Zhi, Wai Shing Luk, Hai Zhou, Changhao Yan*, Hengliang Zhu, Xuan Zeng

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

Conventional clock skew scheduling for sequential circuits can be formulated as a minimum cycle ratio (MCR) problem, and hence can be solved effectively by methods such as Howard's algorithm. However, its application is practically limited due to the difficulties in reliably implementing a large set of arbitrary dedicated clock delays for the flip-flops. Multi-domain clock skew scheduling was proposed to tackle this impracticality by constraining the total number of clock delays. Even though this problem can be formulated as a mixed integer linear programming (MILP), it is expensive to solve optimally in general. In this paper, we show that, under mild restrictions, the underlying domain assignment problem can be formulated as a special MILP that can be solved effectively using similar techniques for the MCR problem. In particular, we design a generalized Howard's algorithm for solving this problem efficiently. We also develop a critical-cycle-oriented refinement algorithm to further improve the results. The experimental results on ISCAS89 benchmarks show both the accuracy and efficiency of our algorithm. For example, only 4.3% of the tests have larger than 1% degradation (3% in the worst case), and all the tests finish in less than 0.7 seconds on a laptop with a 2.1GHz processor.

Original languageEnglish (US)
Title of host publicationProceedings - Design, Automation and Test in Europe Conference and Exhibition, DATE 2011
Pages1364-1369
Number of pages6
StatePublished - May 31 2011
Event14th Design, Automation and Test in Europe Conference and Exhibition, DATE 2011 - Grenoble, France
Duration: Mar 14 2011Mar 18 2011

Other

Other14th Design, Automation and Test in Europe Conference and Exhibition, DATE 2011
CountryFrance
CityGrenoble
Period3/14/113/18/11

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'An efficient algorithm for multi-domain clock skew scheduling'. Together they form a unique fingerprint.

Cite this