A revisit to the primal-dual based clock skew scheduling algorithm

Min Ni*, Seda Ogrenci Memik

*Corresponding author for this work

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

5 Scopus citations

Abstract

Clock skew scheduling is a useful sequential circuit optimization method. The run time efficiency of this problem becomes crucial if it must be repeated iteratively in a higher level optimization. The widely recognized Burns' algorithm proposed to solve this problem suffers from high runtime complexity, which makes it unsuitable to be deployed in iterative optimization loops. This algorithm is based on the general concept of primal-dual optimization. In this paper, we demonstrate that a more efficient approach to the clock skew scheduling problem can be developed by designing a new algorithm using the same primal-dual optimization concept. The basic idea of the algorithm is to avoid creating new admissible graph and recalculating θ values for each iteration of the primal-dual optimization. The asymptotic runtime efficiency of our algorithm is of O(|V||E| + |V|2log|V|), which is improved from O(|V|2|E|) thanks to the heap data structure used in our proposed algorithm. The experimental results show that our algorithm is on average 95 times faster than Burns' implementation. In best case, we can observe as much as 189 times speedup.

Original languageEnglish (US)
Title of host publicationProceedings of the 11th International Symposium on Quality Electronic Design, ISQED 2010
Pages755-764
Number of pages10
DOIs
StatePublished - May 28 2010
Event11th International Symposium on Quality Electronic Design, ISQED 2010 - San Jose, CA, United States
Duration: Mar 22 2010Mar 24 2010

Other

Other11th International Symposium on Quality Electronic Design, ISQED 2010
CountryUnited States
CitySan Jose, CA
Period3/22/103/24/10

Keywords

  • Clock skew scheduling
  • Optimization
  • Primal-dual
  • Sequential circuit

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'A revisit to the primal-dual based clock skew scheduling algorithm'. Together they form a unique fingerprint.

Cite this