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

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

doi:10.1587/transfun.E95.A.2172

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

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

Full Text Views

0

Share
Cite this

Summary :

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%).

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E95-A No.12 pp.2172-2181

Publication Date: 2012/12/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E95.A.2172

Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)

Category: Physical Level Design

Cite this

Copy

Yanling ZHI, Wai-Shing LUK, Yi WANG, Changhao YAN, Xuan ZENG, "Yield-Driven Clock Skew Scheduling for Arbitrary Distributions of Critical Path Delays" in IEICE TRANSACTIONS on Fundamentals, vol. E95-A, no. 12, pp. 2172-2181, December 2012, doi: 10.1587/transfun.E95.A.2172.
Abstract: 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%).
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/transfun.E95.A.2172/_p

Copy

@ARTICLE{e95-a_12_2172,
author={Yanling ZHI, Wai-Shing LUK, Yi WANG, Changhao YAN, Xuan ZENG, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Yield-Driven Clock Skew Scheduling for Arbitrary Distributions of Critical Path Delays},
year={2012},
volume={E95-A},
number={12},
pages={2172-2181},
abstract={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%).},
keywords={},
doi={10.1587/transfun.E95.A.2172},
ISSN={1745-1337},
month={December},}

Copy

TY - JOUR
TI - Yield-Driven Clock Skew Scheduling for Arbitrary Distributions of Critical Path Delays
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2172
EP - 2181
AU - Yanling ZHI
AU - Wai-Shing LUK
AU - Yi WANG
AU - Changhao YAN
AU - Xuan ZENG
PY - 2012
DO - 10.1587/transfun.E95.A.2172
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E95-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2012
AB - 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%).
ER -