CN105677932A - Statistical timing analysis method used for post-silicon adjustable register circuits - Google Patents

Abstract

The invention belongs to the technical field of integrated circuits, in particular to a statistical timing analysis method used for post-silicon adjustable register circuits.The method comprises following steps: compressing a principal component to obtain N independent random variables; generating sparse grid collocation points; calculating the minimum clock cycle of each collocation point; calculating the generalized polynomial chaos coefficient of the minimum clock cycle; and calculating the yield rate of post-silicon adjustable register circuits.The statistical timing analysis method used for post-silicon adjustable register circuits has following beneficial effects: the method is high in feasibility and helps greatly reduce program operation time while obtaining precision comparable to the conventional method; and the statistical timing analysis method can be used for solving the large-scale statistical timing analysis problem of post-silicon adjustable register circuits.

Description

Statistical timing analysis method for circuits with post-silicon tunable registers

technical field

The invention belongs to the technical field of integrated circuits, and relates to a statistical timing analysis method for a post-band silicon adjustable register circuit.

technical background

As IC feature sizes shrink below 100nm, process variation has become one of the major challenges to circuit timing performance. Post-silicon tunable clock tree is a powerful technique to fix timing violations caused by process variation [1,2]. In post-silicon tunable clock trees, post-silicon tunable registers are inserted into the clock tree during the design phase. The delay of the post silicon adjustable register can be adjusted by changing the control signal. A typical post-silicon adjustable register structure is shown in Figure 2 [1]. After the chip is produced, the time margin of the register state can be balanced by changing the delay of the post-silicon tunable register. This process is called post-silicon tuning. During post-silicon tuning, more time margin is allocated to critical paths to fix timing violations. Post-silicon tunable clock tree technology has been widely applied to clock networks in Intel processors [3-6], and this technology can significantly improve yield and performance. However, it also introduces additional costs such as area and power consumption.

Therefore, in the past decades, various methods have been proposed to optimize circuits with post-silicon tunable registers. These optimization methods focus on reducing the overall size of post-silicon tunable registers while ensuring yield. For example, a perturbation method based on post-silicon tunable clock tree synthesis is proposed in [2]. In this approach, a statistical timing analysis of the circuit with post-silicon tunable registers is invoked in each iteration. Then, the overall size of the post-silicon tunable registers can be optimized based on the results of the statistical timing analysis. In one such optimization process, a statistical timing analysis of the circuit with post-silicon tunable registers is performed more than 1000 times. Therefore, the efficiency of statistical timing analysis is critical for post-silicon tunable register optimization algorithms. In [2], a Monte Carlo-based linear programming method is used for statistical time series analysis. Due to the poor performance of this method, this optimization process takes more than 30 hours for some test cases in ISCAS89.

Several relatively efficient statistical timing analysis methods have been proposed in the past few years for statistical timing analysis of circuits with post-silicon tunable registers under process fluctuations [7-15]. These methods use first-order or second-order polynomials to approximate the statistical delay of combinational circuits between registers. However, statistical timing analysis of circuits with post-silicon tunable registers is different from traditional statistical timing analysis problems. For traditional statistical timing analysis, combinational circuits between registers are modeled as acyclic graphs. The traditional statistical timing analysis method finds the statistical polynomial approximation of the combinational circuit delay by traversing the acyclic graph. For statistical timing analysis of circuits with post-silicon tunable registers, post-silicon tunable registers in combinational circuits and clock trees are considered simultaneously to determine the timing yield of the circuit. Therefore, such a circuit can be modeled as a cyclic graph. Statistical timing analysis focuses on finding the statistical minimum average cycle (circuit statistical minimum clock period) from the cyclic graph. This problem is very similar to the statistical timing analysis of transparent latch circuits [16]. The difficulty of this problem is that the number of cycles in a cycle graph is exponentially related to the number of edges.

Due to the long running time of the direct model Carlo method, a fast statistical timing analysis method for circuits with post-silicon adjustable registers was recently proposed in [17]. To avoid exhaustive enumeration of all cycles, the vertices in the graph are reduced one by one until there is only one vertex in the graph. In order to maintain the balance of the subtracted graph, some extra edges are added to the graph. In [17] a heuristic is proposed to reduce the number of edges by removing the edge with the smallest weight. However, the efficiency and precision of this method is highly dependent on the circuit structure.

The prior art relevant to the present invention has following references:

[1] J.-L.Tsai, D.Baik, C.C.-P.Chen, and K.K. Saluja, “Ayield improvement methodology using pre-and post-silicon statistical clock scheduling,” in Proceeding of the 2004 IEEE/ACM International conference on Computer-aided design. IEEE Computer Society, 2004, pp.611–618

[2] J.-L.Tsai, L. Zhang, and C.C.-P. Chen, "Statistical timing analysis driven post-silicon-tunableclock-treesynthesis," in Computer-Aided Design, 2005. ICCAD-2005. IEEE/ACM International Conference on. IEEE, 2005 , pp. 575–581.

[3] S.Tam, S.Rusu, U.Nagarji Desai, R.Kim, J.Zhang, and I.Young, "Clock generation and distribution for the firstia-64 microprocessor," Solid-State Circuits, IEEE Journal of, vol.35, no.11, pp.1545 –1552, 2000.

[4] N.A.Kurd, J.Barkarullah, R.O.Dizon, T.D.Fletcher, and P.D.Madland, "Amultigigahertz clocking scheme for the pentium(r)4microprocessor," Solid-State Circuits, IEEE Journal of, vol.36, no.11, pp.1647–1653, 2001.

[5] S.Tam, R.D.Limaye, and U.N.Desai, "Clock generation and distribution for the 130-nmitanium2 processor with 6-mbon-diel3 cache," Solid-State Circuits, IEEE Journal of, vol.39, no.4, pp.636–642, 2004.

[6] P. Mahoney, E. Fetzer, B. Doyle, and S. Naffziger, "Clock distribution on adult-core, multi-thread editanium-family processor," in Solid-State Circuits Conference, 2005. Digest of Technical Papers. ISSCC. 2005 IEEE International. IEEE, 2005, pp. 292 –599.

[7] J. Singhand S. Sapatnekar, "Statistical timing analysis with correlated non-gaussian parameters using independent component analysis," in Proceeding of the 43rd annual Design Automation Conference. ACM, 2006, pp.155–160.

[8] H. Chang, V. Zolotov, S. Narayan, and C. Visweswariah, “Parameterized block-based statistical timing analysis with non-gaussian parameters, nonlinear delay functions,” in Proceeding of the 42 ^nd annual Design Automation Conference. ACM, 2005, pp.71–76.

[9] Z.Feng, P.Li, and Y.Zhan, “Fast second-order statistical static timing analysis using parameter dimension reduction,” inDesignAutomationConference, 2007.DAC’07.44thACM/IEEE.IEEE, 2007, pp.244–249.

[10] L. Zhang, W. Chen, Y. Hu, J. A. Gubner, and C. C.-P. Chen, “Correlation-preserved non-gaussian statistical timing analysis with quadratic timing model,” in Proceeding of the 42nd annual Design Automation Conference. ACM, 2005, pp.83–88.

[11] Y.Zhan, A.J.Strojwas, X.Li, L.T.Pileggi, D.Newmark, and M.Sharma, “Correlation-awarestatisticaltiminganalysiswithnon-gaussiandelaydistributions,” inDesignAutomationConference, 2005.Proceedings.42nd.IEEE, 2005, pp.77–82 .

[12] V. Khandelwaland A. Srivastava, "A general framework for accurate statistical timing analysis considering correlations," in Proceeding of the 42 n dannual Design Automation Conference. ACM, 2005, pp.89–94.

[13] C. Visweswariah, K. Ravindran, K. Kalafala, S.G. Walker, S. Narayan, D.K. Beece, J. Piaget, N. Venkateswaran, and J.G. Hemmett, “First-order incremental block-based statistical timing analysis,” Computer-Aided Design of Integrated Circuits and Systems , IEEE Transactions on, vol.25, no.10, pp.2170–2180, 2006.

[14] K.Kang, B.C.Paul, and K.Roy, "Statistical timing analysis using levelized covariance propagation," inDesign, Automation and Testin Europe, 2005. Proceedings. IEEE, 2005, pp.764–769.

[15] H. Chang and S. S. Sapatnekar, "Statistical timing analysis considering spatial correlations using asingle pert-like traversal," in Proceeding of the 2003 IEEE/ACM international conference on Computer-aided design. IEEE Computer Society, 2003, p.621.

[16] R. Chen and H. Zhou, "Statistical timing verification for transparently latched circuits," Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactionson, vol.25, no.9, pp.1847–1855, 2006.

[17] B.Li, N.Chen, and U.Schlichtmann, “Fast statistical timing analysis for circuits with post-silicontunable clockbuffers,” in Computer-Aided Design (ICCAD), 2011IEEE/ACM International Conference on. IEEE, 2011, pp.111–117.

[18] H. Zhu, X. Zeng, W. Cai, J. Xue, and D. Zhou, "Asparsegrid based spectral stochastic collocation method for variations-aware capacity extraction of interconnects under nanometer process technology," in DATE.IEEE, 2007, pp.1–6.

[19] H. Zhu, X. Zeng, X. Luo, and W. Cai, "Generalized stochastic collocation method for variation-aware capacity extraction of interconnects considering arbitrary random probability," IEICE transactions on electronics, vol.92, no.4, pp.508–516, 2009.

[20] R.A. Howard, Dynamic Programming and Markov Process. The MIT press, 1960.

[21] S. Bhardwaj, P. Ghanta, and S. Vrudhula, “A framework for statistical timing analysis using non-lineardelay and slew models,” in Proceeding of the 2006 IEEE/ACM international conference on Computer-aided design. ACM, 2006, pp.225–230.

[21] D. Xiu and G. E. Karniadakis, "Thewiener–askey polynomial chaos for stochastic differential equations," SIAM Journalon Scientific Computing, vol.24, no.2, pp.619–644, 2002.

[23] M. Gong, H. Zhou, J. Tao, and X. Zeng, “Binning optimization based on sta for transparently-latched circuits,” in Proceeding of the 2009 International Conference on Computer-Aided Design. ACM, 2009, pp.328–335.

Contents of the invention

The purpose of the present invention is to provide a brand-new statistical timing analysis method for post-band silicon adjustable register circuits based on random configuration. The method of the invention adopts the Howard algorithm to calculate the clock period of the circuit on less than 100 determined sparse grid configuration points. Then proceed from these obtained clock cycles to calculate the yield rate of the circuit according to the random configuration theory. Compared with the existing method, the present invention can significantly reduce the running time of the program and improve the efficiency of statistical timing analysis of the post-band silicon adjustable register circuit under the condition of obtaining the accuracy comparable to the existing method.

The statistical timing analysis method for the post-band silicon adjustable register circuit proposed by the present invention includes the following steps, and the flow chart is shown in FIG. 1 .

Step 1. Pivot component compression to obtain N independent random variables.

The present invention uses a generalized stochastic configuration approach to deal with process fluctuations [18,19]. For relevant process parameters, the present invention can first carry out a principal component analysis (PCA) or independent element analysis (ICA) to obtain a group of N random variables For circuits with post-silicon tunable registers, the logic path maximum and minimum delays from register FFi to FF _j are independent random variables The function. In this invention, we use Indicates the delay in case of process fluctuations. The statistical minimum clock period T _min is also a function of these independent random variables, and T _min can be approximated with a generalized polynomial chaos extension,

${\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; min</span>}}<span\; class="notranslate">\; (</span>\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; \&xi;</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&ap;</span>{\stackrel{<span\; class="notranslate">\; ~</span>}{\mathrm{<span\; class="notranslate">\; T</span>}}}_{\mathrm{<span\; class="notranslate">\; min</span>}}<span\; class="notranslate">\; (</span>\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; \&xi;</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; +</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; N</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}^{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; t</span>}}_{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; N</span>}}}{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; N</span>}}^{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; N</span>}}}<span\; class="notranslate">\; ,</span>$

Among them, M is the polynomial highest price, represents N-dimensional generalized polynomial chaos, and i ₁ +...+i _N is the order of generalized polynomial chaos. coefficient It can be obtained by making the clock period T _min equal to the corresponding polynomial chaos at a group of configuration points. is the exact value are approximate.

Step 2. Generate sparse grid configuration points.

Generate sparse grid configuration points P is the number of configuration points. The generalized polynomial chaos coefficients can be solved numerically with high precision by Gauss-Hermitian integration. The l-order precision Gauss-Hermitian integral of the generalized form of one-dimensional integral is shown in the following formula,

${<span\; class="notranslate">\; \&Integral;</span>}_{<span\; class="notranslate">\; -</span><span\; class="notranslate">\; \&infin;</span>}^{<span\; class="notranslate">\; +</span><span\; class="notranslate">\; \&infin;</span>}\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; \&xi;</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; \&rho;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; \&xi;</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; d\&xi;</span>}<span\; class="notranslate">\; \&ap;</span>{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; l</span>}}\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; \&xi;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{\mathrm{<span\; class="notranslate">\; l</span>}}<span\; class="notranslate">\; )</span>{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{\mathrm{<span\; class="notranslate">\; l</span>}}<span\; class="notranslate">\; ,</span>$

Among them, f(ξ) is the integrand, ρ(ξ)dξ is the Gaussian measure, is the configuration point that takes the i-th real root of the one-dimensional Hermitian polynomial of order l, are the corresponding weights [18,19].

In order to solve the multidimensional integral, literature [22] proposes the tensor product method to construct multidimensional configuration points. make ${\mathrm{\&Theta;}}_1^l=\{{\mathrm{\&xi;}}_1^l,...,{\mathrm{\&xi;}}_l^l\}$ represents a one-dimensional configuration point, $W_1^l=\{{\mathrm{\&xi;}}_1^l,...,{\mathrm{\&xi;}}_l^l\}$ represents the corresponding weight. Then the multi-dimensional configuration points and corresponding weights can be formalized as,

${\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; d</span>}}^{\mathrm{<span\; class="notranslate">\; l</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; \&Theta;</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}<span\; class="notranslate">\; \&CircleTimes;</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; \&CircleTimes;</span>{\mathrm{<span\; class="notranslate">\; \&Theta;</span>}}_{\mathrm{<span\; class="notranslate">\; l</span>}}^{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; d</span>}}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>$

${\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; d</span>}}^{\mathrm{<span\; class="notranslate">\; l</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}<span\; class="notranslate">\; \&CircleTimes;</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; \&CircleTimes;</span>{\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; l</span>}}^{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; d</span>}}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 3</span>}<span\; class="notranslate">\; )</span>$

Wherein, i _j =l, j=1, 2, . . . , d. The number of multi-dimensional Gauss-Hermitian integral configuration points is (l+1) ^d , which increases exponentially with the dimension size d. Therefore, it is necessary to reduce the number of configuration points in practical applications.

The present invention uses sparse grid technology [18,19] to reduce the number of multi-dimensional integral configuration points, so that Indicates the one-dimensional i _j valence precision Gaussian integral configuration point, is the corresponding weight, it can be calculated by the following steps:

2.1 Calculation of multi-dimensional configuration points

For a d-dimensional integral of k-order precision, a set of configuration points generated with a sparse grid is A linear combination of tensor products of , given by,

${\mathrm{<span\; class="notranslate">\; \&Theta;</span>}}_{\mathrm{<span\; class="notranslate">\; d</span>}}^{\mathrm{<span\; class="notranslate">\; l</span>}}<span\; class="notranslate">\; =</span>{{<span\; class="notranslate">\; \&cup;</span>}_{\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; \&le;</span><span\; class="notranslate">\; |</span>\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; l</span>}}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; l</span>}}\mathrm{<span\; class="notranslate">\; \&Theta;</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}<span\; class="notranslate">\; \&times;</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; \&times;</span>{\mathrm{<span\; class="notranslate">\; \&Theta;</span>}}_{\mathrm{<span\; class="notranslate">\; l</span>}}^{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; d</span>}}}<span\; class="notranslate">\; ,</span>$

in, $\left|\stackrel{\&Right\; Arrow;}{l}\right|=i_1+...+i_d.$

2.2 Calculate the corresponding weight of multi-dimensional configuration points

corresponding to configuration point The weights for are given by,

${\mathrm{<span\; class="notranslate">\; w</span>}}_{{\mathrm{<span\; class="notranslate">\; j</span>}}_{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; j</span>}}_{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; d</span>}}}}<span\; class="notranslate">\; =</span>{<span\; class="notranslate">\; (</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; |</span>\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; l</span>}}<span\; class="notranslate">\; |</span>}\left(\begin{array}{c}\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}\\ \mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; |</span>\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; l</span>}}<span\; class="notranslate">\; |</span>\end{array}\right)<span\; class="notranslate">\; (</span>{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; \&Theta;</span>}}}_{{\mathrm{<span\; class="notranslate">\; j</span>}}_{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}}^{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span>{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; \&Theta;</span>}}}_{{\mathrm{<span\; class="notranslate">\; j</span>}}_{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; d</span>}}}}^{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; d</span>}}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; )</span>}^{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; d</span>}}}$

It can be shown that the sparse grid is exact for all polynomials of order at most (2l+1) in the d-variable. The number of sparse grid configuration points can be calculated by the following formula:

${\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; sg</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; dim</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; \&Theta;</span>}}_{\mathrm{<span\; class="notranslate">\; d</span>}}^{\mathrm{<span\; class="notranslate">\; l</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ~</span>\frac{{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; l</span>}}}{\mathrm{<span\; class="notranslate">\; l</span>}\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; d</span>}}^{\mathrm{<span\; class="notranslate">\; l</span>}}<span\; class="notranslate">\; ~</span>{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; l</span>}}\mathrm{<span\; class="notranslate">\; dim</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; \&pi;</span>}}_{\mathrm{<span\; class="notranslate">\; d</span>}}^{\mathrm{<span\; class="notranslate">\; l</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; ></span><span\; class="notranslate">\; ></span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 6</span>}<span\; class="notranslate">\; )</span>$

in, Represents all d-dimensional generalized polynomial chaos of order at most l. Compared with the tensor product strategy, the sparse grid technique avoids the exponentially increasing computational cost related to the dimension size.

Step 3. Calculate the minimum clock period for each configuration point.

For each configuration point, the inventive method uses an efficient minimum ring ratio algorithm to calculate the minimum clock period. This process includes the following four sub-steps.

3.1 Construct a weighted constraint graph, including both circuit logic and circuit clock trees.

Construct a weighted constraint graph containing circuit logic and circuit clock tree information, and the weight of each edge is defined as follows:

${\mathrm{<span\; class="notranslate">\; \&omega;</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; =</span>\left\{\begin{array}{c}{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; init</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; .</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; E.</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}}<span\; class="notranslate">\; ,</span>\\ {\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; E.</span>}}_{\mathrm{<span\; class="notranslate">\; h</span>}}<span\; class="notranslate">\; ,</span>\\ {\mathrm{<span\; class="notranslate">\; R</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; E.</span>}}_{\mathrm{<span\; class="notranslate">\; pst</span>}}<span\; class="notranslate">\; ,</span>\\ \mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; E.</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; ,</span>\end{array}\right.<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 7</span>}<span\; class="notranslate">\; )</span>$

Among them, E _pst represents the set of clock tree edges with post-silicon tunable registers, R _ij represents the delay adjustment range of post-silicon tunable registers corresponding to the clock tree edge (i, j), E _t represents the set of normal clock tree edges, R _ij =R _ji . T _init is the initial value of the clock period, which must be large enough to ensure that there is no negative cycle in the weighted graph. The method of the present invention sets T _init to the maximum value of D _ij . The delay of the post silicon tunable register can be defined as a _ij =t _i -t _j . Then the constraint |a _ij |≤R _ij of the post-silicon tunable register can be formalized as:

$\left\{\begin{array}{c}{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; \&le;</span>{\mathrm{<span\; class="notranslate">\; R</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; ,</span>\\ {\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; \&le;</span>{\mathrm{<span\; class="notranslate">\; R</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; .</span>\end{array}\right.$

3.2 Calculate the corresponding δ of each side.

The δ _ij corresponding to each side can be calculated by the following formula:

${\mathrm{<span\; class="notranslate">\; \&delta;</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; =</span>\left\{\begin{array}{c}\mathrm{<span\; class="notranslate">\; 1,0</span>}<span\; class="notranslate">\; \&ForAll;</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; E.</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}}<span\; class="notranslate">\; ,</span>\\ \mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; E.</span>}}_{\mathrm{<span\; class="notranslate">\; h</span>}}<span\; class="notranslate">\; ,</span>\\ \mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; E.</span>}}_{\mathrm{<span\; class="notranslate">\; pst</span>}}<span\; class="notranslate">\; ,</span>\\ \mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; E.</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; .</span>\end{array}\right.<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 8</span>}<span\; class="notranslate">\; )</span>$

3.3 Apply Howard's algorithm to solve the minimum ring ratio problem.

The delay a _ij of each post-silicon adjustable register is constrained by its adjustable range R _ij , ie |a _ij |≤R _ij . Then the time constraint of the post-silicon tunable register circuit can be formalized as:

${\mathrm{<span\; class="notranslate">\; C</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; T</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\left\{\begin{array}{c}{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; T</span>}<span\; class="notranslate">\; \&le;</span><span\; class="notranslate">\; -</span>{\stackrel{<span\; class="notranslate">\; ~</span>}{\mathrm{<span\; class="notranslate">\; D.</span>}}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; E.</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}}<span\; class="notranslate">\; ,</span>\\ {\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; \&le;</span>{\stackrel{<span\; class="notranslate">\; ~</span>}{\mathrm{<span\; class="notranslate">\; d</span>}}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; E.</span>}}_{\mathrm{<span\; class="notranslate">\; h</span>}}<span\; class="notranslate">\; ,</span>\\ {\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{<span\; class="notranslate">\; \&ForAll;</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}{\mathrm{<span\; class="notranslate">\; a</span>}}_{\mathrm{<span\; class="notranslate">\; st</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; ,</span>\\ <span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; a</span>}}_{\mathrm{<span\; class="notranslate">\; st</span>}}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; \&le;</span>{\mathrm{<span\; class="notranslate">\; R</span>}}_{\mathrm{<span\; class="notranslate">\; st</span>}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>{\mathrm{<span\; class="notranslate">\; buf</span>}}_{\mathrm{<span\; class="notranslate">\; st</span>}}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; Buf</span>}<span\; class="notranslate">\; ,</span>\end{array}\right.<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 9</span>}<span\; class="notranslate">\; )</span>$

Among them, Buf represents the post-silicon adjustable register set in the clock tree, Pi _{represents the clock path from the root node of the clock tree to the register FF i ,} Represents the initial delay on the clock path P _i , a _st represents the delay of the post-silicon adjustable register buf _st , and R _st represents the adjustable range of the post-silicon adjustable register buf _st . Indicates the maximum and minimum delays from FF _i to FF _j . For simplicity, we assume

The method of the present invention adopts the minimum ring ratio algorithm to calculate the minimum clock period. In the present invention, the minimum ring ratio problem is solved using Howard's algorithm [20]. The optimization problem for computing the minimum clock period can be formulated as follows,

$\begin{array}{cc}\mathrm{<span\; class="notranslate">\; Maximize</span>}& \mathrm{<span\; class="notranslate">\; \&lambda;</span>}<span\; class="notranslate">\; ,</span>\\ \mathrm{<span\; class="notranslate">\; Subject\; to</span>}& {\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; \&le;</span>{\mathrm{<span\; class="notranslate">\; \&omega;</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; \&lambda;</span>}<span\; class="notranslate">\; \&CenterDot;</span>{\mathrm{<span\; class="notranslate">\; \&delta;</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; E.</span>}<span\; class="notranslate">\; ,</span>\\ \mathrm{<span\; class="notranslate">\; Variables</span>}& \mathrm{<span\; class="notranslate">\; \&lambda;</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; .</span>\end{array}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 10</span>}<span\; class="notranslate">\; )</span>$

The constraints in the above problem are equivalent to those in Equation (9). It can be seen that the setup time constraint and the hold time constraint have not changed after the transformation, the only difference is the post silicon tunable register constraint. The present invention assumes that the clock arrival time of each vertex in the clock tree is t _i . For each rising edge (i, j) in the clock tree, the delay of the back silicon adjustable register is a _ij =t _i -t _j . For each post silicon tunable register buf _ij , it has two corresponding edges (i, j) and (j, i) at E _pst . Therefore, the constraint |a _ij |≤R _ij , R _ij =R _ji , Equivalent to t _i -t _j ≤ R _ij , $\&ForAll;(i,j)\&Element;{\mathrm{E.}}_{\mathrm{pst}}.$

3.4 Calculate the minimum clock period.

After solving the above minimum ring ratio problem, the maximum value of λ can be obtained, denoted as λ*. Then the minimum clock period is T _min =T _init -λ*.

Step 4. Calculate the minimum clock period generalized polynomial chaos expansion coefficients.

unknown coefficient The Galerkin method [21] can be used to minimize and The error between is obtained, that is,

$<span\; class="notranslate">\; <</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; min</span>}}<span\; class="notranslate">\; (</span>\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; \&xi;</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>{\stackrel{<span\; class="notranslate">\; ~</span>}{\mathrm{<span\; class="notranslate">\; T</span>}}}_{\mathrm{<span\; class="notranslate">\; min</span>}}<span\; class="notranslate">\; (</span>\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; \&xi;</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; N</span>}}^{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; N</span>}}}<span\; class="notranslate">\; (</span>\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; \&xi;</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ></span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 11</span>}<span\; class="notranslate">\; )</span>$

For all (i ₁ +...+i _N )=0,1,...,M. Here <·, ·> represents the inner product [19,20]. By exploiting the orthogonality of polynomial chaos, unknown coefficients can be computed [18,19],

${\mathrm{<span\; class="notranslate">\; t</span>}}_{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; N</span>}}}<span\; class="notranslate">\; =</span>{<span\; class="notranslate">\; <</span>\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; min</span>}}<span\; class="notranslate">\; (</span>\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; \&xi;</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; N</span>}}^{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; N</span>}}}<span\; class="notranslate">\; (</span>\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; \&xi;</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ></span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 12</span>}<span\; class="notranslate">\; )</span>$

Equation (12) is a multidimensional integral, which can be approximated by numerical integration at configuration points, namely:

${\mathrm{<span\; class="notranslate">\; t</span>}}_{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; N</span>}}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; P</span>}}{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; min</span>}}<span\; class="notranslate">\; (</span>{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; \&xi;</span>}}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; )</span>{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; N</span>}}^{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; N</span>}}}}<span\; class="notranslate">\; (</span>{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; \&xi;</span>}}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 13</span>}<span\; class="notranslate">\; )</span>$

in, is the kth configuration point, is the configuration point The minimum clock cycle at , which has been calculated in step 3.

Step 5. Calculate the yield rate of the post-silicon tunable register circuit.

Statistical timing analysis of circuits with post-silicon tunable registers is defined as finding the yield y(T),

y(T)=Prob(T≤T ₀ ), (14)

Among them, Prob represents the probability function.

The minimum clock period to obtain statistics After the polynomial chaos expansion of The cumulative probability function of can also be calculated. The yield rate of the silicon tunable register circuit with the back can be based on Calculate the cumulative probability function of .

Through the above steps, the present invention can obtain the final result of the statistical timing analysis of the post-band silicon adjustable register circuit. The method for statistical timing analysis of the post-band silicon adjustable register circuit of the present invention has the following advantages:

1. The present invention applies the method of random configuration in the statistical timing analysis of the post-band silicon adjustable register circuit for the first time, by using the sparse grid technology to reduce the number of configuration points of the multidimensional integral, and avoiding the exponential growth calculation related to the size of the dimension cost.

2. This method is more efficient, can significantly reduce the program running time while obtaining the accuracy comparable to the existing method, and can be used to solve the statistical timing analysis problem of large-scale post-band silicon adjustable register circuits.

Description of drawings

Fig. 1 is a flow chart of the method of the present invention;

FIG. 2 is a schematic diagram of a typical post-silicon adjustable register structure;

Fig. 3 (a) is the schematic diagram of the timing circuit of the first embodiment of the present invention;

FIG. 3(b) is a schematic diagram of a timing constraint diagram of the first embodiment of the present invention;

Fig. 3(c) is a schematic diagram of a weighted constraint diagram according to the first embodiment of the present invention;

Fig. 3(d) is a schematic diagram of corresponding δ calculation in the first embodiment of the present invention.

detailed description

In order to make the above objects, features and advantages of the present invention more comprehensible, the present invention will be further described below through specific embodiments and accompanying drawings. It should be pointed out that the specific embodiments and accompanying drawings are only for illustration, and those of ordinary skill in the art can make various modifications and changes to the present invention within the scope of the present invention according to the description herein. These amendments and Modifications are also included within the scope of the present invention. In addition, the present invention refers to published documents, and these documents are used to describe the present invention more clearly, and their entire contents are incorporated herein by reference, which is equivalent to their entire contents having been repeatedly described herein.

Embodiment 1 is used to illustrate the main steps of the method of the present invention.

The implementation steps of the method for statistical timing analysis of the post-band silicon adjustable register circuit of the present invention are shown in FIG. 1 .

Figure 3(a) is an example of a sequential circuit with a logic path delay. Figure 3(b) is its corresponding timing constraints. Each vertex in Figure 3(b) represents a register in Figure 3(a). Each logical path in Figure 3(a) corresponds to two timing constraint edges in Figure 3(b). For example, the logical path delay from FF ₁ to FF ₂ in Figure 3(a) is 3. The maximum and minimum delays from FF ₁ to FF ₂ are both 3. Then, two corresponding timing constraint edges should be added in Fig. 3(b). Edge (1, 2) corresponds to the setup time constraint as:

t _i -t _j ≤ T-3.

Edge (1, 2) corresponds to the hold time constraint as:

t _i -t _j ≤3.

The circuit statistical timing analysis process is as follows:

Step 1. Pivot component compression to obtain N independent random variables.

Step 2. Generate sparse grid configuration points.

The configuration points are:

${\mathrm{<span\; class="notranslate">\; \&Theta;</span>}}_{\mathrm{<span\; class="notranslate">\; d</span>}}^{\mathrm{<span\; class="notranslate">\; l</span>}}<span\; class="notranslate">\; =</span>{<span\; class="notranslate">\; \&cup;</span>}_{\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; \&le;</span><span\; class="notranslate">\; |</span>\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; l</span>}}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; l</span>}}{\mathrm{<span\; class="notranslate">\; \&Theta;</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}<span\; class="notranslate">\; \&times;</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; \&times;</span>{\mathrm{<span\; class="notranslate">\; \&Theta;</span>}}_{\mathrm{<span\; class="notranslate">\; l</span>}}^{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; d</span>}}}<span\; class="notranslate">\; ,</span>$

in, $\left|\stackrel{\&Right\; Arrow;}{l}\right|=i_1+...+i_d.$ The corresponding weights are:

${\mathrm{<span\; class="notranslate">\; w</span>}}_{{\mathrm{<span\; class="notranslate">\; j</span>}}_{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; j</span>}}_{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; d</span>}}}}<span\; class="notranslate">\; =</span>{<span\; class="notranslate">\; (</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; |</span>\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; l</span>}}<span\; class="notranslate">\; |</span>}\left(\begin{array}{c}\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}\\ \mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; |</span>\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; l</span>}}<span\; class="notranslate">\; |</span>\end{array}\right)<span\; class="notranslate">\; (</span>{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; \&Theta;</span>}}}_{{\mathrm{<span\; class="notranslate">\; j</span>}}_{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}}^{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span>{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; \&Theta;</span>}}}_{{\mathrm{<span\; class="notranslate">\; j</span>}}_{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; d</span>}}}}^{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; d</span>}}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; .</span>}^{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; d</span>}}}$

Step 3. Calculate the minimum clock period of each configuration point, the steps are as follows:

Step 3.1: Construct a weighted constraint graph, including both circuit logic and circuit clock trees. Figure 3(c) shows the weighted constraint diagram, which also includes the circuit of Figure 3(a) and a clock tree. Solid lines represent logical paths, and dashed lines represent clock tree edges.

Step 3.2: Calculate the corresponding δ of each edge. The corresponding δ for the constraint graph shown in Fig. 3(c) is shown in Fig. 3(d).

Step 3.3: Apply Howard's algorithm to solve the minimum ring ratio problem. Solve the minimum ring ratio problem to obtain the optimal value λ*.

Step 3.4: Calculate the minimum clock period. After solving the above minimum ring ratio problem, we can get the maximum value of λ, denoted as λ*. Then the minimum clock period is T _min =T _init -λ*.

Step 4. Calculate the minimum clock period generalized polynomial chaos expansion coefficients.

${\mathrm{<span\; class="notranslate">\; t</span>}}_{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; N</span>}}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; P</span>}}{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; min</span>}}<span\; class="notranslate">\; (</span>{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; \&xi;</span>}}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; )</span>{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; N</span>}}^{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; N</span>}}}<span\; class="notranslate">\; (</span>{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; \&xi;</span>}}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>$

in, is the kth configuration point, is the configuration point The minimum clock cycle at , which has been calculated in step 3.

Step 5. Calculate the yield rate of the post-silicon tunable register circuit.

Statistical timing analysis of circuits with post-silicon tunable registers is defined as finding the yield y(T),

y(T)=Prob(T≤t ₀ ),

Among them, Prob represents the probability function.

Example 2 is used to show that the statistical timing analysis method proposed by the present invention can significantly reduce the program running time while obtaining comparable accuracy to the existing method.

In this embodiment, the settings similar to those in [17] are adopted. The results obtained by the Monte Carlo method with 10,000 sampling points are used as the comparison standard for judging the accuracy. The test circuit is from ISCAS89, and the basic unit gates in the test circuit are mapped to the SMIC 65nm unit library. In this embodiment, each register has a post-silicon adjustable register, and the adjustment range of each register is set to 0.3 times the longest path delay of the circuit. In the Monte Carlo method and the method of the present invention, 6 random variables (transistor length, transistor width, threshold voltage of NMOSFET and PMOSFET) are used to model process fluctuations. The standard deviation of these independent random variables was set at 10% of the nominal value. In this example, the quadratic delay model is used, and the SSTA method based on random configuration points is used to obtain the quadratic delay expression of the logic path [23]. In this SSTA engine, a deterministic STA engine is used to derive the latency of each configuration point's logical path. Finally, according to the stochastic allocation theory, the expression of the quadratic delay is deduced. The test cases and results are shown in Table 1. #Nodes and #Edges represent the number of vertices and edges in the timing constraint graph. Err (μ) represents the relative error of the average value of the minimum clock cycle, and Err (σ) represents the relative error of the standard deviation of the minimum clock cycle. Merge represents the method in [17]. Run time includes random configuration point generation, minimum clock cycle calculation and yield calculation.

The average relative error of the minimum clock cycle average value of the method of the present invention is 0.16%, which is obviously smaller than the method in the literature [17]. The average value of the relative error of the minimum clock cycle standard deviation of the method of the present invention is 0.48%, slightly higher than the method in the literature [17], but still sufficiently accurate. Therefore, the accuracy of the method of the present invention can be compared with the method in the literature [17].

It can be seen from Table 1 that for small-scale circuits, the running time of the method of the present invention is equivalent to or longer than that of the literature [17]. However, for large-scale circuits, the method of the present invention can achieve a speedup ratio of more than 10 times. The method in the literature [17] is highly dependent on the circuit structure, for example, the scale of the test circuit s1423 is much smaller than that of s13207, but the running time of s1423 is longer than that of s13207. The size of the S15850 is about 4 times that of the s13207, but the running time of the S15850 is 36 times that of the s13207. In contrast, the method of the present invention has an approximately linear relationship with the number of timing constraint edges. The running time of the method of the invention is predictable and has little correlation with the circuit structure, which is a very good characteristic in practical application.

Table 1 The inventive method and existing method comparative result

Claims (5)

1. A statistical timing analysis method for a post-strip silicon adjustable register circuit is characterized by comprising the following steps: the method comprises the following steps:

step 1, compressing principal components to obtain N independent random variables;

step 2, generating sparse grid configuration points;

step 3, calculating the minimum clock period of each configuration point;

step 4, calculating a generalized polynomial chaotic expansion coefficient with a minimum clock period;

and 5, calculating the yield of the silicon adjustable register circuit with the band.

2. The statistical timing analysis method for a post-silicon tunable register circuit according to claim 1, wherein the generating of sparse grid configuration points in step 2 comprises the following two substeps:

step 2.1: calculating a multi-dimensional configuration point;

step 2.2: and calculating the corresponding weight of the multi-dimensional configuration point.

3. The statistical timing analysis method for a post-silicon tunable register circuit according to claim 1, wherein the step 3 of calculating the minimum clock period for each configuration point comprises the following 4 sub-steps:

step 3.1: constructing a weighted constraint graph, and simultaneously containing circuit logic and a circuit clock tree, wherein each edge is defined as follows:

${\mathrm{\&omega;}}_{\mathrm{ij}}=\left\{\begin{array}{cc}{T}_{\mathrm{init}}-D_{\mathrm{ij}},& \&ForAll;(i,j)\&Element;E_s,\\ d_{\mathrm{ij}},& \&ForAll;(j,i)\&Element;E_h,\\ R_{\mathrm{ij}},& \&ForAll;(i,j)\&Element;E_{\mathrm{pst}},\\ 0,& \&ForAll;(i,j)\&Element;E_t.\end{array}\right.$

step 3.2: the correspondence of each edge is calculated,

${\mathrm{\&delta;}}_{\mathrm{ij}}=\left\{\begin{array}{cc}1,& \&ForAll;(i,j)\&Element;E_s,\\ 0,& \&ForAll;(j,i)\&Element;E_h,\\ 0,& \&ForAll;(i,j)\&Element;E_{\mathrm{pst}},\\ 0,& \&ForAll;(i,j)\&Element;E_t.\end{array}\right.$

step 3.3: and solving the problem of the minimum ring ratio by applying Howard algorithm.

Step 3.4: the minimum clock period is calculated.

4. The statistical timing analysis method for the post-silicon tunable register circuit according to claim 1, wherein the minimum clock period generalized polynomial chaotic expansion coefficient is calculated in step 4, and is obtained by the following calculation:

$t_{i_1,...,i_N}={\mathrm{\&Sigma;}}_{k=1}^p{w}_k{T}_{\min }\left({\stackrel{\&RightArrow;}{\mathrm{\&xi;}}}_k\right)H_N^{i_1,...,i_N}\left({\stackrel{\&RightArrow;}{\mathrm{\&xi;}}}_k\right),$

wherein,is the point of the k-th configuration,is a point of deploymentAt the minimum clock period of the clock signal,representing an N-dimensional generalized polynomial chaos.

5. The statistical timing analysis method for the post-band silicon tunable register circuit according to claim 1, wherein the step 5 of calculating the yield of the post-band silicon tunable register circuit comprises: at the time of obtaining statistical minimum clock periodAfter the polynomial chaotic expansion of (a),is calculated based on the cumulative probability function of the post-strip silicon tunable register circuitThe cumulative probability function of (2) is calculated.