Bài giảng Multilevel logic optimiz

Nội dung text: Bài giảng Multilevel logic optimiz

1. Multilevel logic optimization • Goals • Methodology Multilevel logic optimization • Algebraic optimization method Hà Thủy Tú – 10070502 Trần Thế Anh - 10070471 1 2 Goals Goals • F = AC + AD + BC + BD + E • Representation of the Boolean function • Optimal A C –Area A – Speed D F A B – Testability B C C F – Power dissipation D B D E E 3 4
2. Methodology Methodology • Substitution • Elimination rewrite F in terms of G and its original inputs Inverse operation of substitution F = A + BC (5 literals) F = GA + G’B (4 literals) G = A + B G = C + D ⇒ F = G(A + C) (4 literals) ⇒ F = AC + AD + BC’D’ (7 literals) G = A + B G = C + D “division” plays a key role in all of these (except elimination) 9 10 Example Algebraic optimization method Restructuring Problem: Given initial network, find best network. • Division Initial network: f1 = abcd+abce+ab’cd’+ab’c’d’+a’c+cdf+abc’d’e’+ab’c’df’ f2 = bdg+b’dfg+b’d’g+bd’eg – Logic division minimizing, – Algebraic division f = bcd+bcf+b’cd’+a’c+cd’e+abc’d’e’+ab’c’df’ 1 – Kernels and algebraic divisors f2 = bdg+dfg+b’d’g+d’eg factoring, – Computing kernels f1 = c(d(b+f)+d’(b’+e)+a’)+ac’(bd’e’+b’df’) • Algebraic method for logic operations f2 = g(d(b+f)+d’(b’+e)) – The basic of algebraic optimization method decompose, – Factoring f = c(x+a’)+ac’x’ 1 – Extraction and resubstitution f2 = gx x = d(b+f)+d’(b’+e) – Resubstitution with complement Two problems: • find good common subfunctions 11 12 • how to do division
3. Division Division • Logic division f = p·q + r q, r unique • Algebraic division X1 X2 X3 f p=X1’X2 q=X3 r p is orthogonal to q, p⊥q, if sup(p) ∩ sup(q) = ∅ 0001 1 (p = ab’+ c, then sup(p)={a,b,c}) 001 1 ex. p= a+b q=c+d, then p ⊥q 01011 1 011111 ∃ h, r : f = g·h + r where h ≠ 0 and g⊥h 100 => g is an algebraic divisor of f 101 1 p ⊥ q 110 Quotient h = f/g is unique 111 1 17 18 Division Division • Algebraic division • Algebraic division – Computing quotient – Computing quotient Given f, g are lists of cubes –example f ={b1, b2, , b|f| } f = abc + abd + de g={a1, a2, , a|g| } g = ab + e Define h ≡ {c | a · c ∈ f} , ∀ i=1,2, ,|g| i j i j h1={c ,d} , h2 ={d} h is all multipliers of the cube a producing b i i x h = f/g = h1 ∩ h2 = {d} Then h = f/g = h1 ∩ h2 ∩ ∩ h|g| f = (ab + e)d + abc 19 20
4. Division Division • Computing kernels • Computing kernels KERNELS(f) { – Example 1 c = largest cube (max number of literals) factor of f; f f = abcd + abce + abef K(f) = R = ? K=KERNEL1(0,f/cf); if (f is cube-free) return (f ∪K); return(K); 1. cf = ab } 2. f/cf = g = cd + ce + ef , R ={cd + ce + ef} KERNEL1(j,g) { 3. Lexical ordering: a, b, c, d, e, f R=g; 4. a,b ∉ {cd, ce, ef} , repeat step 3 N=Max index of variables in g; For (i=j+1;i≤N;i=i+1){ 5. g/c = d + e ∈ P(f) & cube-free l1=a, l2=b, if (li in 1 or no cubes of g) continue; R = {cd + ce + ef, d + e} c = largest cube dividing g/li evenly; 6. repeat step 3 if (for all k≤i, lk ∉c) R=R ∪KERNEL1(i,g/(li∩c)); } Result R = {cd + ce + ef, d + e, c + f} Return(R); } 25 26 Division Division • Computing kernels • Computing kernels – Example 2 – Example 3 f = adf + aef + bdf + bef + cdf + cef + g •A kernel may have K(f) = R = ? many co-kernels. •Co-kernel can be the trivial cube 1. f = (a+b+c)(d+e)f + g 27 28
5. Algebraic method - logic operations Algebraic method - logic operations • Extraction and resubstitution (1) • Factoring f=ac+ad+ae+ag+bc+bd+be+bf+ce+cf+df+dg Single-cube factors: 16 literals f=a(c+d+e+g) + b(c+d+e+f) + c(e+f) + d(f+g) Multiple-cube factors: 14 literals f=(c+d+e)(a+b) + f(b+c+d) + g(a+d) + ce 33 34 Algebraic method - logic operations Algebraic method - logic operations • Extraction and resubstitution (2) • Extraction and resubstitution (3) 35 36