SPECO : stochastic perturbation based clock tree optimization considering temperature uncertainty.

Abstract

Modern computing system applications or workloads can bring significant non-uniform temperature

gradient on-chip, and hence can cause significant temperature uncertainty during clock-tree synthesis.

Existing designs of clock-trees have to assume a given time-invariant worst-case temperature map but

cannot deal with a set of temperature maps under a set of workloads. For robust clock-tree synthesis

considering temperature uncertainty, this paper presents a new problem formulation: Stochastic

PErturbation based Clock Optimization (SPECO). In SPECO algorithm, one nominal clock-tree is presynthesized

with determined merging points. The impact from the stochastic temperature variation is

modeled by perturbation (or small physical displacement) of merging points to offset the induced

skews. Because the implementation cost is reduced but the design complexity is increased, the

determination of optimal positions of perturbed merging points requires a computationally efficient

algorithm.

In this paper, one Non-Monte-Carlo (NMC) method is deployed to generate skew and skew variance

by one-time analysis when a set of stochastic temperature maps is already provided. Moreover, one

principal temperature–map analysis is developed to reduce the design complexity by clustering

correlated merging points based on the subspace of the correlation matrix. As a result, the new

merging points can be efficiently determined level by level with both skew and its variance reduced.

The experimental results show that our SPECO algorithm can effectively reduce the clock-skew and its

variance under a number of workloads with minimized wire-length overhead and computational cost.