Yield-Driven Clock Skew Scheduling for Arbitrary Distributions of Critical Path Delays

Yanling ZHI  Wai-Shing LUK  Yi WANG  Changhao YAN  Xuan ZENG  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E95-A   No.12   pp.2172-2181
Publication Date: 2012/12/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E95.A.2172
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
Category: Physical Level Design
yield-driven,  clock skew scheduling,  generalized Howard algorithm,  generalized minimum balance algorithm,  

Full Text: PDF(1.2MB)>>
Buy this Article

Yield-driven clock skew scheduling was previously formulated as a minimum cost-to-time ratio cycle problem, by assuming that variational path delays are in Gaussian distributions. However in today's nanometer technology, process variations show growing impacts on this assumption, as variational delays with non-Gaussian distributions have been observed on these paths. In this paper, we propose a novel yield-driven clock skew scheduling method for arbitrary distributions of critical path delays. Firstly, a general problem formulation is proposed. By integrating the cumulative distribution function (CDF) of critical path delays, the formulation is able to handle path delays with any distributions. It also generalizes the previous formulations on yield-driven clock skew scheduling and indicates their statistical interpretations. Generalized Howard algorithm is derived for finding the critical cycles of the underlying timing constraint graphs. Moreover, an effective algorithm based on minimum balancing is proposed for the overall yield improvement. Experimental results on ISCAS89 benchmarks show that, compared with two representative existing methods, our method remarkably improves the yield by 10.25% on average (up to 14.66%).