Transcript 04a-logic synthesis

Multi-Level Optimization
 1. Reduce number of literals
 fewer literals means less transistors (less space)
 fewer inputs implies faster gates (less switches in series)
 fan-ins (# of gate inputs) are limited in some technologies
 2. Reduce number of gates
 number of gates (or gate packages) influences manufacturing costs
 3. Reduce number of levels of gates
 fewer levels of gates implies reduced signal propagation delays
 minimum delay configuration typically requires more gates
(wider less deep circuits)
 Explore tradeoffs between increased circuit delay and reduced gate
count
 automated tools to optimize logic and explore possibilities
CSE 567 - Autumn 1998 - Combinational Logic - 1
Optimization Approaches
 Exploit common subexpressions (less gates)
 Minimize number of literals rather than terms
 Trade more levels of logic for reduced fan-in (may also be faster)
 No systematic minimization procedure exists as in the two-level case
A
B
C
D
X = AC'D + BC'D + ACD' + BCD'
(12 literals and 4 wires, max fan-in = 4)
X = (A+B)C'D + (A+B)CD'
(8 literals and 6 wires, max fan-in = 2)
X = (A+B)(C xor D)
(4 literals and 2 wires, max fan-in = 2)
CSE 567 - Autumn 1998 - Combinational Logic - 2
Network Operations
 Operations on factored forms
 elimination
 decomposition
 extraction
 simplification
 substitution
manipulate network via a collection
of transformations
there exists no algorithm that
guarantees an "optimal" multi-level
network will be obtained
outputs
inputs
each node is an arbitrarily complex gate
CSE 567 - Autumn 1998 - Combinational Logic - 3
Factoring Boolean Expressions
 Division with Boolean functions
F = DQ + R
D = divisor
Q = quotient
R = remainder
 Example:
X = ac + ad + bc + bd + e
Y=a+b
X/Y = c + d
X = Y (c + d) + e
divisor
interesting divisors
are called kernels
and cubes
remainder
quotient
CSE 567 - Autumn 1998 - Combinational Logic - 4
Algebraic vs. Boolean Division
 Algebraic division – use rules of algebra (see previous example)
 Boolean division – use rules of Boolean algebra
F = ad + bcd + e
G=a+b
G does not divide F under algebraic rules
F/G = (a + c) d
(very large number of these)
G does divide F under Boolean rules
F = GQ + R = [G (a + c) d] + e
(a + b) (a + c) d + e
(aa + ac + ab + bc) d + e
(a + bc) d + e
ad + bcd + e
the key here is the
absorption theorem of
Boolean algebra
CSE 567 - Autumn 1998 - Combinational Logic - 5
Kernels and Cubes
 Kernel: cube-free factor of an expression (no cube can factor it
evenly)
kernels:
non-kernels:
a + b, a + cd
a, abc, a(c + d)
 Co-kernel: quotient resulting from dividing the expression by the kernel
e.g., F = a c + b c + b’ d’
kernels: a + b
co-kernels: c
G = (a + b + c) (d + e) f + gkernels: a + b + c; d + e
co-kernels: de, df; af, bf, cf
CSE 567 - Autumn 1998 - Combinational Logic - 6
Why Kernels?
 Multi-cube algebraic divisors (only other divisors are cubes)
 Can be partitioned into a hierarchy (efficient extraction algorithms)
 level-0 kernel: cannot be divided evenly by a kernel
 level-n kernel: can be divided evenly only by level-(n-1) kernels and
itself
F = (a (b + c) + d) (eg’ + g (f + e’)) + (b + c) (h + i)
level-0 (among others):
level-1 (among others):
level-2:
b+c
a (b + c) + d
F
F = j (a (b + c) + d) (eg’ + g (f + e’)) + (b + c) (h + i)
F is level-3 because it contains a level-2 kernel:
(a (b + c) + d) (eg' + g (f + e'))
CSE 567 - Autumn 1998 - Combinational Logic - 7
Tabular Method for Finding Kernels
 Use a cube-literal matrix
 Rectangles represent a cube
 The co-rectangle represents a kernel
 e.g. g = abe + acd + bcd
 cube = cd
 kernel = a+b
CSE 567 - Autumn 1998 - Combinational Logic - 8
Common-Cube Extraction
 Find the cubes common two several expressions
 Useful for extracting the cubes (factoring)
 e.g. F = abc + abd +eg
G = abfg
H = bd + ef
CSE 567 - Autumn 1998 - Combinational Logic - 9
Finding Kernel Intersectons
 First find the kernels and co-kernels (cubes)
 e.g. F = af + bf + ag + cg + ade + bde + cde
G = af + bf + ace + bce
H = ade + cde
 (Number these cubes in order of appearance)
CSE 567 - Autumn 1998 - Combinational Logic - 10
Finding Kernel Intersections
 The cokernel-cube matrix
 A column for each cube
 A row for each cube in each function
 Numbers indicate which cubes in the corresponding kernel
 Rectangles in this matrix correspond to common kernels
CSE 567 - Autumn 1998 - Combinational Logic - 11
Example to Illustrate Transformations
 Unoptimized logic network
a
v = a’d + bd + c’d + ae’
w
b
p = ce + de
r = p + a’
s = r + b’
x
c
t = ac + ad + bc + bd + e
y
d
q=a+b
u = q’c + qc’ + qc
e
CSE 567 - Autumn 1998 - Combinational Logic - 12
z
Example to Illustrate Transformations
(cont’d)
 Optimized network
a
j = a’ + b + c’
v = jd + ae’
w
b
x
s = ke + a’ + b’
c
k=c+d
t = kq + e
y
q=a+b
u=q+c
z
d
e
CSE 567 - Autumn 1998 - Combinational Logic - 13
Elimination
 Removing a node (too simple a function, better to absorb into other gates)
a
v = a’d + bd + c’d + ae’
w
b
p = ce + de
s = p + a’ + b’
x
c
t = ac + ad + bc + bd + e
y
d
q=a+b
u = q’c + qc’ + qc
e
CSE 567 - Autumn 1998 - Combinational Logic - 14
z
Decomposition
 Break a complex node into simpler ones (too complex for a single gate,
create opportunities for sharing sub-expressions)
a
j = a’ + b + c’
v = jd + ae’
w
b
p = ce + de
r = p + a’
s = r + b’
x
c
t = ac + ad + bc + bd + e
y
d
q=a+b
u = q’c + qc’ + qc
e
CSE 567 - Autumn 1998 - Combinational Logic - 15
z
Extraction
 Finding common sub-expressions and pulling them out into their own node
(most important and complex function in multi-level optimization)
a
v = a’d + bd + c’d + ae’
w
b
p = ke
r = p + a’
s = r + b’
x
c
k=c+d
t = ka + kb + e
y
u = q’c + qc’ + qc
z
d
q=a+b
e
CSE 567 - Autumn 1998 - Combinational Logic - 16
Simplification
 Two-level minimization applied to a node (exploit structural don't cares)
a
v = a’d + bd + c’d + ae’
w
b
p = ce + de
r = p + a’
s = r + b’
x
c
t = ac + ad + bc + bd + e
y
d
q=a+b
u=q+c
e
CSE 567 - Autumn 1998 - Combinational Logic - 17
z
Substitution
 Reuse existing nodes to make others simpler (closely linked to
extraction and decomposition)
a
v = a’d + bd + c’d + ae’
w
b
p = ke
r = p + a’
s = r + b’
x
c
k=c+d
t = kq + e
y
d
q=a+b
e
u = q’c + qc’ + qc
CSE 567 - Autumn 1998 - Combinational Logic - 18
z
Multi-Level Logic Don’t Cares
 Don't cares come from two sources in multi-level circuits
 From specification (external explicit don't cares)
 in terms of circuit inputs and outputs
 From structure of circuit graph (internal implicit don't cares)
 a combination of input and internal values cannot occur or
 an internal node output is irrelevant for some input combinations
depending on how it is used by its fanout
a
b
x
a =1, b = 1, x =1 can never occur
 Both are critical in arriving at minimal circuits
 Must be maintained throughout all graph operations
CSE 567 - Autumn 1998 - Combinational Logic - 19
Restructuring Multi-Level Logic for Speed
 Decrease fanout of nodes
 more destinations for a signal implies slower transmission
 elimination
 Decrease fanin of nodes
 gate speed proportional to square of number of inputs (1st order)
 decomposition, simplification
 Move late input closer to outputs
 make path to output shorter, pre-compute other logic
 Shannon decomposition (f = a fa + a’ fa’)
A
A
A is a late arriving input
that is moved closer to the output
by restructuring the logic
(i.e., changing DAG structure)
CSE 567 - Autumn 1998 - Combinational Logic - 20
Summary of Multi-Level Optimization
 Minimization procedures
 heuristic application of the operations we just listed
 no guarantee of finding an optimal realization
 does quite well in a practical amount of time (with algebraic
division)
 Everything up to this point has been technology independent
 just considering literal count or depth of circuit
 not the types of elements available to actually implement the
circuit
 Technology mapping
 process of converting circuit graph into one where each node is
directly implementable with an available gate or function block
CSE 567 - Autumn 1998 - Combinational Logic - 21
Technology Mapping
 Process of transforming logic network so that all nodes can be directly
implemented with an available component directed toward area or
speed optimization
 Requires library of available gates
 permutations of inputs (e.g., a•b + c – a and b can be switched)
 area and delay for each library gate
 Example:
NAND2
area: 4
delay: 2
NAND4
area: 8
delay: 8
AOI21
area: 6
delay: 5
XOR2
area: 16
delay: 6
CSE 567 - Autumn 1998 - Combinational Logic - 22
Canonical Representation for Library
Cells
 Represent function in terms of 2-input NAND gates
 Not a unique representation
 library must represent all non-isomorphic possibilities
 Example:
 F = (ABCD)'
has two representations
CSE 567 - Autumn 1998 - Combinational Logic - 23
Technology Mapping by Tree Matching
 Dynamic programming algorithm
 taken from code generation – Aho and Johnson's TWIG
 DAG is viewed as a forest of trees (two options)
 1. partition into trees (break graph at fanout nodes)
 2. duplicate logic in common sub-trees
 Consider adding inverter pairs along any arc of original DAG
node in graph
cell in library




CSE 567 - Autumn 1998 - Combinational Logic - 24