SmipRef: An efficient method for multi-domain clock skew scheduling

Yanling Zhi, Wai Shing Luk, Hai Zhou, Xuan Zeng*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

Conventional clock skew scheduling (CSS) for sequential circuits can be solved effectively using methods including the parametric shortest path algorithm and Howard's algorithm. Nevertheless, its application is practically limited due to the difficulties in reliably implementing a large set of arbitrary dedicated clock delays for flip-flops. Thus multi-domain clock skew scheduling (MDCSS) was proposed to tackle this by constraining the total number of clock delays. However, this new problem is hard to solve optimally in general. In this paper, we propose a novel method to efficiently solve it. Under mild restrictions, the problem is transformed into a special mixed integer linear programming problem, which can be solved optimally using similar techniques for the CSS problem. Then the solution quality is further improved by a critical-cycle-oriented refinement. As a result, our method obtains optimal solutions for 88 of the 93 tests on ISCAS89 benchmarks. The experimental results on large circuits in Opencores benchmarks also demonstrate its efficiency of at least one order faster than existing algorithms. To improve the runtime performance, we also devise a graph pruning algorithm that can be applied to methods for the MDCSS problem as a preprocessing step. Its application on our method shows a speedup of 2.66X on average.

Original languageEnglish (US)
Pages (from-to)392-403
Number of pages12
JournalIntegration, the VLSI Journal
Volume46
Issue number4
DOIs
StatePublished - Sep 2013

Keywords

  • Clock skew scheduling
  • Minimum cycle ratio
  • Multi-domain
  • Timing optimization

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Electrical and Electronic Engineering

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

Cite this