Multi-parameter clock skew scheduling

Xingbao Zhou, Wai Shing Luk*, Hai Zhou, Fan Yang, Changhao Yan, Xuan Zeng

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

Clock skew scheduling is a powerful technique for circuit optimization. Conventionally it can be formulated as a minimum cost-to-time ratio cycle (MCR) problem, which can be solved efficiently by a set of specialized network optimization algorithms. However, those algorithms can only handle one single parameter at a time, for example, the clock period, the timing slack or the yield. This inflexibility limits the applicability of the scheduling technique because in a real design one may need to consider multiple parameters simultaneously. In this paper, we introduce a multi-parameter extension to the MCR problem. Furthermore, a convex nonlinear extension is also considered. In particular, we generalize Lawler's algorithm, which is based on the bisection strategy. When there is more than one parameter, the bisection strategy is naturally replaced by the ellipsoid method. More importantly, the ellipsoid method does not require the knowledge of all constraints explicitly in prior. Instead, for each iteration, only a constraint that is violated by the current solution is required. This constraint turns out to be a negative cycle in our formulation, which can be detected efficiently. As a result, our proposed method could gain up to 12 x run-time speedup for linear problems compared with a general linear programming solver and more than 700 x run-time speedup for nonlinear problems compared with a general convex programming solver based on our experimental results.

Original languageEnglish (US)
Pages (from-to)129-137
Number of pages9
JournalIntegration, the VLSI Journal
Volume48
Issue number1
DOIs
StatePublished - Jan 1 2015

Keywords

  • Clock skew scheduling
  • Ellipsoid method
  • Multi-parameter

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Multi-parameter clock skew scheduling'. Together they form a unique fingerprint.

Cite this