Patent ID: 7562324

Claim:
A method of designing a digital synchronous VLSI system established from a quadratic equation for Clock Skew scheduling and optimization comprising following steps: (a) constructing a circuit model for the quadratic equation using a digital computer, utilizing the feature of circuit linear dependence and a minimum spanning tree that works with a Depth First Search algorithm to deduce the clock skew matrix; C 1 = R 1 , s 1 , R 3 , s 4 , R 2 , s 3 , R 1 C 2 = R 2 , s 4 , R 3 , s 2 , R 4 , R 3 , R 2 → B = [ 1 0 - 1 1 0 0 1 0 - 1 1 ] = [ I C ] wherein s=clock skew, R=Register, C=Circuit loop I = [ 1 0 0 1 ] C = [ - 1 1 0 0 - 1 1 ] (b) executing “least square error” to optimize the produced clock skew matrix produced in 1 (a); min ⁢ ⁢ ɛ = ∑ k = 1 p ⁢ ⁢ ( s k - g k ) 2 → min ⁢ ⁢ ɛ ~ = s t ⁢ ⁢ s - 2 ⁢ g t ⁢ ⁢ s Introducing the Lagrange Multipliers by utilizing the method of quadratic programming, and deduce the Lagrange function Λ(s, λ) Λ( s ,λ)={tilde over (ε)}+λ t Bs=s t s− 2 g i s+λ t Bs {tilde over (ε)} is a stationary point (fixed point) in the Lagrange function (s, λ), so 0 is given from a first-order partial differentiation, namely ∇(s, λ)=0 → s t ⁢ ⁢ s - 2 ⁢ g t ⁢ ⁢ s + λ 2 ⁢ ⁢ Bs = 0 = Bs → | 2 ⁢ s + B t ⁢ ⁢ λ = 2 ⁢ g Bs = 0 Presenting in a manner of matrix → [ 2 ⁢ I p B t 0 BB t ] ⁡ [ s λ ] = 2 ⁡ [ g Bg ] → λ = 2 ⁢ M - 1 ⁢ ⁢ Bg s = - 1 2 ⁢ ⁢ B t ⁢ ⁢ λ + g wherein M = BB t = [ I C ] ⁡ [ I C ] = I + CC B t =transpose matrix of B s and g presented as S=[S c S b ] and g=[g c g h ], the deduction expression is λ = 2 ⁢ M - 1 ⁢ ⁢ Bg ⁢ → s b = - 1 2 ⁢ ⁢ C t ⁢ ⁢ λ + g b s c = - 1 2 ⁢ ⁢ λ + g c Wherein g=optimal clock skew, s=calculated clock skew, λ is the Lagrange Multipliers. And S c =[S 1 S 2 . . . S p−r+1 ] t is chord clock skew, S b =[S p−r+2 . . . S p ] t is main clock skew; (c) calculating the Lagrange Multipliers with the use of high precision and calculating speed Conjugate Gradients Algorithm; Output a set of calculated results when the Residual Error is small enough to reach a stop condition of iteration; (d) wherein the value of x computed by Conjugate Gradients Algorithm approaches the correct value of x; (e) wherein the result of clock skew produced in (c) is the optimum clock skew amount for circuit working; and (f) testing by ISCAS'89 benchmark.