Optimal and efficient algorithms for multidomain clock skew scheduling

Li Li, Yinghai Lu, Hai Zhou

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

Clock skew scheduling is an effective technique to improve the performance of sequential circuits. However, with process variations, it becomes more difficult to implement a large number of clock delays in a precise manner. Multidomain clock skew scheduling (MDCSS) is one way to overcome this limitation. In this paper, we prove the NP-completeness of multidomain clock scheduling problem and design a practical optimal algorithm to solve it. Given the domain number, we bound the number of all possible skew assignments and develop an optimal algorithm with efficient pruning techniques as well as a very efficient heuristics based on the optimal framework. The experimental results on ISCAS89 sequential benchmarks show the optimality and efficiency of our method compared with the most recent approaches to MDCSS.

Original languageEnglish (US)
Article number6607242
Pages (from-to)1888-1897
Number of pages10
JournalIEEE Transactions on Very Large Scale Integration (VLSI) Systems
Volume22
Issue number9
DOIs
StatePublished - Sep 2014

Keywords

  • Algorithms
  • Clock skew scheduling
  • Optimization

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Optimal and efficient algorithms for multidomain clock skew scheduling'. Together they form a unique fingerprint.

Cite this