Bài giảng Multi-level logic optimization(cont) - Nguyễn Phạm Anh Khoa

Nội dung text: Bài giảng Multi-level logic optimization(cont) - Nguyễn Phạm Anh Khoa

1. CONTENT |Boolean division |Don’t care based optimization MULTI-LEVEL LOGIC OPTIMIZATION(CONT) 1 Nguyễn Phạm Anh Khoa Trần Huy Vũ BOOLEAN DIVISION BOOLEAN DIVISION | Algebraic division: | Boolean division: f = h.g + r | Example: f = abd+cd + abe+ace, assumed g = ab + c | h and g can share: = d(ab + c) + abe + ace | A common literal x | More optimal: f = (ab + c)(ae + d) a + bc = (a + b).(a + c) | Why? | Literal x and x’ ab + a’c + bc = (a + b)(a’ + c) y Algebraic division: f = h.g + r y h and g are orthogonal
2. SATISFIABILITY DON’T CARE OBSERVABILITY DON’T CARES a a y1 y1 b b y2 y2 f f c c | Satisfiability Don’t Care Set: | Says: The output F can observe the input X (X can | SDC = ∑j(Yj.Fj’ + Yj’.Fj) be observed at output F) if changes of X make F | Optimize a node N: changed | Use Satisfiability Don’t Care Set of Nodes that fan- | Example: if c = 1 then y2 can be observed at F out to N if c = 0 then y2 cannot be observed at F DON’T-CARE GENERATION OBSERVABILITY DON’T CARES | Define Observability of node Yj: | ∂Fk / ∂Yj = F kYj XOR FkYj’ (Boolean difference) | ∂Fk / ∂Yj = 0 (or F kYj = FkYj’ ) : Yj cannot be observed at F | F kYj = FkYj’ : Observability Don’t Care condition for Yj | Observability Don’t Care Set of node Yj | ODC = Πall outputs(Fkyj = Fkyj’) = Πall output(∂Fk / ∂Yj )’ Y1 = x1.x2 Y3=0 Î Y2=1 Y2 = x1.x3 12 Y3 = x3 + x4
3. RANGE COMPUTATION RANGE COMPUTATION Characteristic function Transition relation Let f : BN Æ BM Let f : BN Æ BM F : BN x BM Æ B N N Let A B , ƞA: B Æ {0,1} which is defined as ƞA(x) = 1 if xЄA, else ƞA(x) = 0 F(x,y) = 1 (x,y) Є BN x BM and y= f(x) Smoothing function ⊕ F(x,y) = Π (yi fi(x)) 1 ≤ i ≤ M N Let f : B Æ B and x=(x1,x2, ,xn) Sxf = Sx1Sx2 Sxnf f(A) = {y: Ǝx(xЄA)  F(x,y) = 1} Sxif= fxi +fxi 17 f(A)(y) = Sx(F(x,y).A(x)) 18 RANGE COMPUTATION Example: y1 = x1.x2 y2 = x1 + x3 y3 = x3 + x4 F(x,y) = y1⊕ (x1.x2). y2⊕ (x1 + x3). y3⊕ (x3+x4) C4 = A(x) = x1 + x2 + x3 + x4 LC4 = f(A)(y) = Sx(F(x,y).A(x)) LC4 = y2.y3 + y1.y2.y3 19