Transcript Logic Synthesis 4 - CS Course Webpages

Logic Synthesis 4
Outline
– Multi-Level Logic Synthesis
– Multi-Level Logic Minimization
Goal
– Understand multi-level logic
synthesis algorithms
Multi-Level Logic Synthesis
• Multilevel Logic Interactive Synthesis System - MIS
– perform logic optimization by factoring equations
– similar to SOCRATES weak division
• Goals
– global and local area minimization
– reduce delay to below specification
• Target Technology
– complex CMOS gates - PMOS pullup and NMOS pulldown
networks
Strategy
• Global optimization
– use algebraic factorization to identify common subexpressions
– avoid exponential search
• Local optimization
– identify two-level subcircuits
– compute local DCs imposed by surrounding circuit
– minimize subcircuits using ESPRESSO-type approach
Global Optimization Approach
• Read in and clean up network
– constant propagation, double-inverter elimination, ...
– ESPRESSO minimization of each equation
• Global area optimization
– find common factors in equations
– factor equations using “best” factors
» generates new equations for common factors
– check whether equations themselves are common factors
» substitute if they are
– assign phase to each equation to minimize inverters
» invert equation or not
– repeat several times
– area is estimated by number of literals in equations
– “best” factors are those that most reduce literal count
Local Optimization Approach
• Local area optimization
– regard each equation as a complex gate
– optimize single gate or gates sharing literals
– decompose gate - break big gate into smaller ones
» factor equation, generate new equations for factors
– check whether equations themselves are common factors
» substitute if they are
– for each equation compute DC-set from surrounding
equations and apply ESPRESSO to equation
– repeat several times
Timing Optimization
• Reduce delay to meet specification
with minimum area increase
• Algorithm
– compute longest delay path
– compute slack time at each node
» time node has to spare vs. longest path
» critical path is set of nodes with <=0 slack
– reduce delay on node
» refactor gate to simplify transistors
» factor complex gate into simpler gates
» combine several gates into complex gate
– repeat until specification met
Factoring Reduces Area
• Example
– sum of products form:
x = abeg’ + abfg + abe’g + aceg’ + ace’g + deg’ + dfg + de’g
+ bh + bi + ch + ci
– factored form:
x = (a(b + c) + d)(eg’ + g(f + e’)) + (b + c)(h + i)
• Area
– SOP form has 41 literals, 148 transistors in CMOS
– factored form has 13 literals, 76 transistors in CMOS
– using straightforward implementation
Algebraic and Boolean Division
• Product
– support - literals used in equation
– product - equations f, g, product fg, make nonredundant by
containment
» containment - remove cubes covered by others
» example: ab + a = a
– algebraic (normal) product if f and g have disjoint support
» no common literals
» example: (a + b)(c + d) = ac + ad + bc + bd
– boolean product - common literals, apply DeMorgan’s laws
» example: (a + b)(a + c) = aa + ab + ac + bc = a + bc
Algebraic and Boolean Division
• Quotient
– quotient of f/g is largest set q of cubes s.t. f = qg + r
» q - quotient
» r - remainder
– algebraic quotient - qg is algebraic product
– boolean quotient - qg is boolean product
– if f/g is not empty, g is divisor of f
• Example
f = ad + bcd + e
g = a + bc
h=a+b
f/g = d (g is algebraic divisor of f)
f/h = (a + c)d (h is boolean divisor of f)
Kernels
• Equation is cube-free if no cube divides it evenly
– ab + c is cube-free
– ab + ac, abc are not cube-free
• Primary divisors of f are:
D(f) = {f/C | C is a cube }
• Kernels of f are:
K(f) = { g | g  D(f) and g is cube-free }
• Kernels are cube-free primary divisors
• For kernel k = f/C, C is co-kernel of k
Kernels
• Example
x = adf + aef + bdf + bef + cdf + cef + g = (a + b + c)(d + e)f + g
– kernel a + b + c, co-kernels df and ef
– kernel d + e, co-kernels af, bf, cf
– divisor (d + e)f, not kernel since not cube-free
– kernel x, co-kernel 1
• Common divisors
– f and g have common multi-cube divisor d iff d is
intersection of kf and kg for kf  K(f) and kg  K(g)
– finding common divisors - find kernels of each equation,
look for non-trivial intersections
Kernel Generation and Intersection
• Normally find level-0 kernels
– kernels that do not contain kernels
» level-1 kernel contains only level-2 kernels, etc.
– finding all kernels can be too costly
– multiple iterations of level-0 kernel factoring is equivalent
to factoring using all kernels
• Kernel intersection
–
–
–
–
avoid many empty intersections
find unique cubes of set of kernels
generate new cube of these cubes for each kernel
find co-kernels of this set of cubes
» these are unique intersections of kernels
Examples
• Kernel levels
x = (a(b + c) + d)(eg’ + g(f + e’)) + (b + c)(h + i)
– level-0: b + c
– level-1: a(b + c) + d
– level-2: x
• Kernel intersection
K = { k1, k2, k3 }, k1 = abc + de + fg, k2 = abc + de + fh, k3 = abc + fh + gh
intersections: abc = k1  k2  k3 , abc + de = k1  k2 , abc + fh = k2  k3
distinct cubes: t1 = abc, t2 = de, t3 = fg, t4 = fh, t5 = gh
new function: IF(K) = t1t2t3 + t1t2t4 + t1t4t5
Co-kernels(IF(K)) = { t1, t1t2, t1t4 }
Cube subset of K: I(K) = { t1, t1 + t2, t1 + t4 } = { abc, abc + de, abc + fh}
Conclusions
• Many algorithm details not discussed
– see book for more details
– challenge is to develop good script to apply operators
– best script varies with circuit type
» try backtracking and modifying script as it runs
• Circuit quality as good as hand design
– if correct script is applied
• Execution time is fairly fast
– to achieve good results