6-vlsicad-multilevel1

VLSI CAD: Logic to Layout Rob A. Rutenbar University of Illinois Lecture 6.1 Logic Synthesis: Multilevel Logic and the Boolean Network Model © 2013, R.A. Rutenbar Why Multi-level Logic? •  2-level forms are too restrictive: specific area vs. delay tradeoff •  Area = gates + literals (wires), i.e., things that take space on a chip •  Delay = maximum levels of logic gates required to compute function •  2-level is minimum gate delay possible, but usually worst on area DELAY Typical 2-level design = many gates, but only 2 levels of logic, so fastest possible Multi-level designs = fewer gates, but > 2 levels small, few gates+literals big, many gates+literals fastest, 2 levels slower, >2 levels AREA Slide 2 © 2013, R.A. Rutenbar Why Multilevel? •  Rarely see 2-level designs for really big things… •  We use 2-level logic mostly for pieces of bigger things •  Even smallish things routinely done as multi-level ~1000 gate “block” of logic 1 2 3 4 999 1000 ? This is just NOT going to be the preferred logic network structure... Slide 3 © 2013, R.A. Rutenbar Real Multilevel Example •  …this is a small design, done by commercial synthesis tool Levels of logic in network 1 2 3 4 5 6 7 8 9 10 11 Slide 4 © 2013, R.A. Rutenbar Boolean Logic Network Model •  Need more sophisticated model: Boolean Logic Network •  Idea: it’s a graph of connected blocks, like any logic diagram, but now individual component blocks can be 2-level Boolean functions in SOP form a b c x y Ordinary gate logic …now as a Boolean logic network, x, y are now Boolean functions primary inputs primary outputs internal vertices a b c x y x=ab y=b+c Slide 5 © 2013, R.A. Rutenbar Multilevel Logic: What to Optimize? •  This is simplistic but surprisingly useful: Total literal count •  Count every appearance of every variable on right hand side of “=“ in every node •  (Yes, delays matter too, but for this class, only focus on logic complexity) Slide 6 X = Yd + Z Y = b+c Q = aX Z = b•c Q a b c d #Literals = © 2013, R.A. Rutenbar Optimizing Multilevel Logic: Big Ideas •  Again: this is a data structure. What operators do we need? •  3 basic kinds of operators •  Simplify network nodes: no change in # of nodes, just simplify insides, SOP form •  à You already know this! This is 2-level synthesis, this is ESPRESSO! •  Remove network nodes: take “too small” nodes, substitute them back into fanouts •  à This is not too hard. This is mostly manipulating the graph, simple SOP edits. •  Add new network nodes: this is factoring. Take big nodes, split into smaller nodes. •  à This is a big deal. This is new. This is what we need to teach you… Slide 7 © 2013, R.A. Rutenbar Optimizing Boolean Logic Network •  Simplifying a node •  Just run ESPRESSO on 2-level form inside the node, to reduce # literals •  As structural changes happen across network, “insides” of nodes may present opportunity to simplify •  Removing a node •  Typical case is you have a “small” factor which doesn’t seem to be worth making it a separate node •  “Push” it back into its fanouts, make those nodes bigger, and hope you can use 2-level simplification on them Slide 8 X = a +ab +bc X = a + bc Z = ab Y = cdZ + stuff X = qZ + stuff Y = cdab + stuff X = qab + stuff © 2013, R.A. Rutenbar Optimizing Boolean Logic Network •  Adding new node(s): this is Factoring, this is new, and hard •  Look at existing nodes, identify common divisors, extract them, connect as fanins •  Tradeoff: more delay (another level of logic), but fewer literals (less gate area) Slide 9 Y = abd + cd X = ab + c + r Q = ab+c Y = Qd X = Q + r Z = abrs+crs Z = Qrs divisor 16 literals 10 literals VLSI CAD: Logic to Layout Rob A. Rutenbar University of Illinois Lecture 6.2 Logic Synthesis: Multilevel Logic: Algebraic Model for Factoring © 2013, R.A. Rutenbar Aside: Multilevel Synthesis Scripts •  Multilevel synthesis–like 2-level synthesis–is heuristic •  …but it’s also more complex. Write scripts of basic operators •  Do several passes of different optimizations over the Boolean logic network •  Do some “cleanup” steps to get rid of “too small” nodes (remove them) •  Look for “easy” factors, just sitting around as existing nodes, and try to use them •  Look for “hard” factors, do the work to extract them, try them, keep the good ones •  Do 2-level optimization of insides of each logic node in network (ESPRESSO) •  Lots of “art” in the engineering of these scripts •  For us, the one big thing you don’t know: How to factor… Slide 11 © 2013, R.A. Rutenbar Another New Model: Algebraic Model •  Factoring: How do we really do it? •  Develop another model for Boolean functions, cleverly designed to let us do this •  Tradeoff: lose some “expressivity” -- some aspects of Boolean behavior and some Boolean optimizations we just cannot do, but we gain practical factoring. •  New model: Algebraic model •  Surprise: Term “algebraic” comes from pretending that Boolean expressions behave like polynomials of real numbers, not like Boolean algebra •  Big new Boolean operator: Algebraic Division (or, also “Weak” Division) Slide 12 © 2013, R.A. Rutenbar Algebraic Model •  Idea: keep just those rules (axioms) that work for polynomials of reals AND Boolean algebra, dump the rest Real numbers a•b = b•a a+b = b+a a•(b•c) = (a•b)•c a+(b+c) = (a+b)+c a•(b+c) = a•b + a•c a•1 = a a•0 = 0 a+0 = a Boolean algebra a•b = b•a a+b = b+a a•(b•c) = (a•b)•c a+(b+c) = (a+b)+c a•(b+c) = a•b+a•c a•1 = a a•0 = 0 a+0 = a a+a’ = 1 a•a’ = 0 a•a = a a+a = a a+1 = 1 a+(b•c) = (a+b)•(a+c) SAME NOT ALLOWED x Slide 13 © 2013, R.A. Rutenbar Algebraic Model •  If we only get to use algebra rules from real numbers…. •  Consequence: A variable and its complement must be treated as totally unrelated •  Aside: this is one of the losses of “expressive power” for Booleans we just tolerate •  Idea •  Boolean functions manipulated as SOP expressions–like polynomials •  Each product term in such an expression is just a set of variables, e.g., abRy •  SOP expression itself is just a list of these products (cubes), e.g. ab + Rx = ab,Rx F = ab + a’x + b’y ab + Rx + Sy Let R = a’ Let S = b’ Slide 14 © 2013, R.A. Rutenbar Algebraic Division: Our Model for Factoring •  Given function D we want to factor as: divisor quotient remainder (if =0, then we say the divisor is ‘technically’ called a Factor) F = D•Q + R Example with REAL 15 = 7•2 + 1 7 = D = divisor 2 = Q = quotient 1 = R = remainder Example with BOOLEAN SOP F = ac + ad + bc + bd + e = (a+b)•(c+d) + e (a+b) = D = divisor (c+d) = Q = quotient e = R = remainder Slide 15 © 2013, R.A. Rutenbar Algebraic Division •  Example •  Reminder: Quotient is only called a “Factor” if remainder is 0 F = ac + ad + bc + bd + e want F = D • Q + R Divisors (D) Quotient (D) Remainder (R) Factor? ac+ad+bc+bd+e a+b c+d a b c d e 1 0 Yes (trivial) c+d e No a+b e No c+d bc+bd+e No c+d ac+ad+e No a+b ad+bd+e No a+b ac+bc+e No 1 ac+ad+bc+bd No Slide 16 VLSI CAD: Logic to Layout Rob A. Rutenbar University of Illinois Lecture 6.3 Logic Synthesis: Multilevel Logic: Algebraic Division © 2013, R.A. Rutenbar Algebraic Division: Very Nice Algorithm •  Inputs •  A Boolean expression F and a divisor (to divide by) D, represented as lists of cubes (and each cube a set of literals) •  Output •  Quotient Q = F/D = cubes in quotient, or 0 (empty) if none •  Remainder R = cubes in remainder, or 0 (empty) if D was a factor •  i.e., figures out Q, R so that F = D•Q+ R = D•(F/D) + R •  Strategy •  Cubewise walk thru cubes in divisor D, trying to divide each of them into F •  ...being careful to track which cubes do divide into F Slide 18 © 2013, R.A. Rutenbar Algebraic Division Algorithm AlgebraicDivision( F, D) { // divide D into F for ( each cube d in divisor D ) { let C = { cubes in F that contain this product term “d” }; if ( C is empty ) { return ( quotient = 0, remainder = F); } let C = cross out literals of cube “d” in each cube of C; if ( d is the first cube we have looked at in divisor D ) let Q = C; else Q = Q ∩ C; } R = F - ( Q • D ); return ( quotient = Q, remainder = R) } Example: Cube xyzw contains product term “yz” Example: Suppose C = xyz + yzw +pqyz and d = “yz”. Then crossing out all the “yz” parts yields x + w + pq Example: Suppose Q = xyz + yzw +pqyz and C = “ xyz”. Then Q ∩ C is just the cubes that are in both Q and C in this case: xyz Slide 19 © 2013, R.A. Rutenbar Algebraic Division: Example F/D: F = axc + axd + axe + bc + bd + de D = ax + b F cube D cube: ax C = … D cube: b C = … axc -- axd -- axe -- bc -- bd -- de -- -- Easiest way manually is to make this table: one row per cube in F, one column per cube in D, bottom row to evolve Quotient Q and, when done, remember to get remainder R Slide 20 AlgebraicDivision( F, D) { // divide D into F for ( each cube d in divisor D ) { let C = { cubes in F that contain this product term “d” }; if ( C is empty ) { return ( quotient = 0, remainder = F); } let C = cross out literals of cube “d” in each cube of C; if ( d is the first cube we have looked at in divisor D ) let Q = C; else Q = Q ∩ C; } R = F - ( Q • D ); return ( quotient = Q, remainder = R) } 1 3 axcàaxcàc axdàaxdàd axdàaxeàe bcàbcàc bdàbdàd Q = c+d+e 2 4 Q = (c+d) ∩ (c+d+e) = c+d R = (axc + axd + axe + bc + bd + de) – (c+d)•(ax+b) (axc + axd + axe + bc + bd + de) – (axc + axd + bc + bd) = (axe + de) = remainder Remainder R = F–Q•D: “—” means remove cubes in Q•D that appear same in F 5 © 2013, R.A. Rutenbar Algebraic Division: Warning •  Remember: No “Boolean” simplification, only “algebraic” •  So what? Well, suppose you have this •  You must transform it to something like this... •  Because must treat the true and complement forms of variable as different Slide 21 F = ab’c’ + ab + ac + bc G = ab + c’ want F / G Let X=b’, Y=c’ à F = aXY + ab + ac + bc G = ab + Y then can do F / G © 2013, R.A. Rutenbar One More Constraint: Redundant Cubes •  To do F/D, function F must have no redundant cubes •  Technical term is: “minimal with respect to single-cube containment” •  In words: no one cube is completely covered by other cubes in SOP cover F = a + ab + bc is redundant quotient D = a is the divisor Now: compute F / D, i.e., F / a use our algebraic division algorithm à  Problem: F / D = 1 + b, remainder = bc à  “1+b” is not operation in Algebraic model! Slide 22 ab c 00 01 11 10 0 1 1 1 1 1 1 © 2013, R.A. Rutenbar Multilevel Synthesis Models: Where are We? •  For Boolean F, D, can compute F = Q•D + R via algebraic model •  This is great—but it’s still not enough. Don’t know how to find these divisors. •  Real problem: n functions F1, F2, … Fn, find a set of good common divisors di •  What are we looking for? •  Case 1: divisors d that are just 1 cube (1 product term), e.g., d = ab •  Case 2: “bigger” multiple-cube divisors, e.g. d = ab + cd + e Slide 23 factor d1 = ab+c F1 = d1 + x F2 = (d1)x+q F3 = ab+q F1 = ab + c + x F2 = abx + cx + q F3 = ab + q VLSI CAD: Logic to Layout Rob A. Rutenbar University of Illinois Lecture 6.4 Logic Synthesis: Multilevel Logic: Role of Kernels and Co-Kernels in Factoring © 2013, R.A. Rutenbar Where To Look For Good Divisors? •  Surprisingly, the Algebraic Model has a beautiful answer •  One more reason we like it: Has some surprising and elegant “deep structure” •  Where to look for divisors of function F? In the kernels of F •  Denoted K(F). Pronounced like “Colonel.” Spelled with TWO e’s (remember!) •  K(F) is another set of two-level SOP forms which are the special, foundational structure of any function F, being interpreted in our algebraic model. •  How to find a kernel k∈K(F)? Algebraically divide F by one of its co-kernels, c. •  Wow – lots of new concepts and terms here. Let us go develop these ideas… Slide 25 © 2013, R.A. Rutenbar Kernels and Co-Kernels of Function F •  Kernel of a Boolean expression F is: •  A cube-free quotient k obtained by (algebraically) dividing F by a single cube c •  This single cube c also has a name: it is a co-kernel of function F Slide 26 divisor D quotient Q expression F remainder R F = D•Q + R c = 1 cube kernel k if cube-free expression F remainder R F = c•k + R © 2013, R.A. Rutenbar Kernels Are Cube-Free… •  Cube-free means...? •  You cannot factor out a single cube (product term) divisor that leaves no remainder •  Technically -- has no one cube (product) that is a factor of expression •  Do F / cube, look at result, if you can ‘cross out’ some cube in each term, not a kernel Expression F F=d•Q+R Cube-free? a a+b ab + ac abc + abd ab + acd + bd Slide 27 a(1)+0 No -- Yes a(b+c)+0 No ab(c+d)+0 No -- Yes © 2013, R.A. Rutenbar Some Kernel Examples •  Kernels of F denoted K(F). Suppose F = abc + abd + bcd •  So, any Boolean F can have many different kernels k∈K(F) Slide 28 Divisor cube d F= d•Q + R Is it a Kernel of f? 1 a b ab … etc (1)(abc+abd+bcd)+0 No, has cube = b as factor (a)(bc+bd)+bcd No, also has cube = b as factor (b)(ac+ad+cd)+0 Yes, a kernel; co-kernel = (b) (ab)(c+d)+bcd Yes, a kernel; co-kernel = (ab) © 2013, R.A. Rutenbar Kernels: Why Are They Important? •  …, if they are important, how do we actually compute them? •  Big result: Brayton & McMullen Theorem •  From: R. Brayton and C. McMullen, “The decomposition and factorization of Boolean expressions. In IEEE International Symposium on Circuits and Systems, pages 49–54, 1982. Slide 29 Expressions F, G have a common multiple-cube divisor d if and only if there are kernels k1∈K(F), k2 ∈K(G) such that d = k1 ∩ k2 (ie, SOP form with common cubes in it) and d is an expression with at least 2 cubes in it © 2013, R.A. Rutenbar Multiple-Cube Divisors and Kernels •  In words: •  The only place to look for multiple-cube divisors is in the intersection of kernels! •  Further: this intersection of kernels is the divisor, there are no others Slide 30 d = ab+c+… F = stuff G = stuff k1 k2 k3 k4 k6 k5 k7 Kernels of F Kernels of G Intersect? ≥2 cubes? k3 k5 Yes! d=… F = new G = new Multi-cube divisor extracted! © 2013, R.A. Rutenbar Brayton-McMullen: Informal Illustration •  Remember: kernel1, kernel2 are cube-free… F = cube1 • kernel1 + remainder1 G = cube2 • kernel2 + remainder2 Slide 31 F = cube1 • [X + Y + stuff1] + remainder1 G = cube2 • [X + Y + stuff2] + remainder2 F = cube1 • [X + Y] + [cube1•stuff1 + remainder1] G = cube2 • [X + Y] + [cube2•stuff2 + remainder2] d = X+Y F = cube1•d + … G = cube2•d + … kernel1 ∩ kernel2 = [X + Y] = a multicube divisor of F & G © 2013, R.A. Rutenbar Kernels: Real Example •  Consider this F, G F = ae + be + cde + ab G= ad + ae + bd + be + bc K(F) Kernel Co-kernel a+b+cd e b+e a a+e b ae+be+cde+ab 1 K(G) Kernel Co-kernel a+b d or e d+e a or b d+e+c b ad+ae+bd+be+bc 1 Intersecting these 2 kernels: (a+b+cd) ∩ (a+b) = So, this is workable multicube divisor we can consider for both F,G Slide 32 VLSI CAD: Logic to Layout Rob A. Rutenbar University of Illinois Lecture 6.5 Logic Synthesis: Multilevel Logic: Finding the Kernels © 2013, R.A. Rutenbar Kernels: Very Useful, But How To Find? •  Another recursive algorithm (are we surprised...?) •  There are 2 more useful properties of kernels we need to see first… •  Start with a function F and a kernel k1 in K(F) •  Then: a new, interesting question: what about K( k1) ?? •  k1 is a perfectly nice Boolean expression, so it has got its own kernels •  Do these k1’s kernels have anything interesting to say about K(F)...? Slide 34 F = cube1 • k1 + remainder1 © 2013, R.A. Rutenbar How K(k1) Relates to K(F)… •  We know this: F = cube1•k1 + remainder1 •  Suppose k2 is a kernel in K( k1 ), then we know •  k1 = cube2•k2 + remainder2 •  Substitute this expression for k1 in original expression for F •  F = cube1•[cube2•k2 + remainder2] + remainder1 •  Neat trick: cube1•cube2 is itself just another single cube, rewrite to emphasize: •  F = (cube1•cube2)•[ k2 ] + [ cube1•remainder2 + remainder1] •  Lovely result: k2 also a kernel of original F (with co-kernel cube1•cube2) Slide 35 © 2013, R.A. Rutenbar There is a Hierarchy of Kernels Inside F •  Terminology: k∈K(F) is: •  A level-0 kernel if it contains no kernels inside it except itself •  In words: Only cube you can pull out, get a cube-free quotient is ‘1’ •  A level-n kernel if it contains at least one level-(n-1) kernel, and no other level-n kernels except itself •  In words: a level-1 kernel only has level-0 kernels inside it. A level-2 kernel only has level-1 and level-0 kernels in it, etc… Slide 36 F = stuff Level-2 kernel Level-1 kernel Level-0 kernel Level-1 kernel Level-0 kernel Level-0 kernel © 2013, R.A. Rutenbar Kernel Hierarchy •  2nd useful result [Brayton et al] •  Co-kernels of a Boolean expression in SOP form correspond to intersections of 2 or more of the cubes in this constituent SOP form •  Note: Intersections here means specifically that we regard a cube as a set of literals, and look at common subsets of literals •  This is not like “AND” for products. This is simple common sub-expressions. •  Example Slide 37 ace + bce + de + g ace ∩ bce = ce à ce is a potential co-kernel ace ∩ bce ∩ de = e à e is a potential co-kernel © 2013, R.A. Rutenbar Kernel Hierarchy •  How do we use these 2 results? •  Find the kernels recursively. Whenever we find one: •  Call FindKernels( ) on it, to find (if any) lower level kernels are inside •  Use algebraic division to divide function by potential co-kernels, to drive recursion •  …but be smart: co-kernels are intersections of the cubes •  ...if there’s at least 2 cubes, then look at the intersection of those