Transcript Synthesis and Verification

ECE 667
Spring 2011
Synthesis and Verification
of Digital Circuits
Introduction to Logic Synthesis
ECE 667 - Synthesis & Verification
1
Synthesis Flow
HDL specification
Front-end
parsing
Logic synthesis
Cell library
Techn-independent
optimization
Technology
mapping
Manufacturing
ECE 667 - Synthesis & Verification
2
Synthesis Flow
a multi-stage process
Specification
Logic Extraction
module example(clk,
a, b, c, d, f, g, h)
input
clk, a, b, c, d, e, f;
Technology-Independent
aoutput g, h; reg g, h;
Optimization
b
a
Technology-Dependent
Mapping
h
always
@(posedge
clk)
begin
g1
e
0
G
g = a | b;
bif (d) beging0
if (c) h = a&~h;
f
g
else h = b;
h5
G
dcend else if (f) g = c; else a^b;
g
h3
if (c) h = 1; else h ^b;
bd
H
end e
fendmodule
h
h1
H
ae
c
clk
c
d
f
clk
Data Flow Graph (DFG)
a
b
c
d
e
f
Typical Synthesis Scenario
RTL to Network Transformation
- read HDL
- control/data flow analysis
Technology independent Optimizations
- basic logic restructuring
- crude measures for goals
Technology Mapping
- use logic gates from target
cell library
Technology Dependent Optimizations
- timing optimization
- physically driven optimizations
Test Preparation
ECE 667 - Synthesis & Verification
- improve testability
- test logic insertion
5
Local versus Global Transformations
• Local transformations optimize the function of one
node of the network
– smaller area
– better performance
– map to a particular set of cells (library)
• Global transformations restructure the entire network
– merging nodes
– spitting nodes
– removing/changing connections between nodes
• Node representation:
–
–
–
–
SOP, POS
BDD
Factored forms
keep size bounded to avoid blow-up of local transformations
ECE 667 - Synthesis & Verification
6
Logic Optimization methods
Logic Optimization
Two-level logic (PLA)
Exact (QM)
Multi-level logic
(standard cells)
Heuristic
(espresso)
Boolean
Structural
(SIS)
Functional
(AC, Kurtis)
algebraic
ECE 667 - Synthesis & Verification
Functional
(BDD-based)
Boolean
7
General Logic Structure
Combinational logic (CL)
Sequential elements
• Combinational optimization
– keep latches/registers at current positions, keep their function
– optimize combinational logic in between
• Sequential optimization
– change latch position/function (retiming)
ECE 667 - Synthesis & Verification
8
What is Logic Synthesis?


X
Y
D
Given: Finite-State Machine F(X,Y,Z,  , ) where:
X: Input alphabet
Y: Output alphabet
Z: Set of internal states
 : X x Z Z (next state function, Boolean)
 : X x Z Y (output function, Boolean)
Combinational logic
Sequential logic
Target: Circuit C(G, W) where:
• G: set of circuit components
{Boolean gates, flip-flops, etc}
• W: set of wires connecting G
ECE 667 - Synthesis & Verification
9
Basic Model of Sequential circuit: FSM
X=(x1,x2,…,xn)

S=(s1,s2,…,sn)

Y=(y1,y2,…,yn)
S’=(s’1,s’2,…,s’n)
M(X,Y,S,S0,,):
X: Inputs
Y: Outputs
S: Current State
S0: Initial State(s)
: X  S  S (next state function)
: X  S Y (output function)
D
Sequential synthesis:
find (multi-level) implementation of (X) and
(X) that minimize its cost (area, delay, power)
Delay elements:
• Clocked: synchronous
• single-phase clock, multiple-phase clocks
• Unclocked: asynchronous
ECE 667 - Synthesis & Verification
10
Optimization Criteria for Synthesis
The optimization criteria for logic optimization is to
minimize some function of:
•
•
•
•
•
•
Area occupied by the logic gates and interconnect
(approximated by literals = transistors in technology
independent optimization)
Critical path delay of the longest path through the logic
Degree of testability of the circuit, measured in terms of the
percentage of faults covered by a specified set of test vectors
for an approximate fault model (e.g. single or multiple stuckat faults)
Power consumed by the logic gates
Noise Immunity
Place-ability, Wire-ability
while simultaneously satisfying misc. constraints
ECE 667 - Synthesis & Verification
11
Two-Level (PLA) vs. Multi-Level
E.g. Standard Cell Layout
PLA
Multi-level Logic
• control logic
• constrained layout
• highly automatic
• technology independent
• multi-valued logic
• input, output, state encoding
Very predictable
•
•
•
•
•
ECE 667 - Synthesis & Verification
all logic
general (standard cells, macro cells, blocks)
automatic
partially technology independent
part of multi-level logic
Very hard to predict
12
Two-level Logic: the PLA
Product terms
x0 x1
x2
AND
plane
OR
plane
f0
x0
ECE 667 - Synthesis & Verification
x1
f1
x2
13
Two-Level Logic Minimization
Every logic function can be
expressed in sum-of-products
format (AND-OR)
minterm
Inverting format (NORNOR) more effective
ECE 667 - Synthesis & Verification
14
Programmable Logic Array
Pseudo-NMOS PLA
GND
GND
GND
V DD
GND
GND
GND
GND
V DD
X0
X0
X1
AND-plane
ECE 667 - Synthesis & Verification
X1
X2
X2
f0
f1
OR-plane
15
Transformation-based Synthesis
• All modern synthesis systems are build that way
– Series of transformations that change network representation
• work on uniform network representation
– “script” of “scenario” that can combine those transformations to a
overall greedy
• Transformations differ in:
– their scope
• local versus global restructuring
– the domain they optimize
• combinational versus sequential
• timing versus area
• technology independent versus technology dependent
– the underlying algorithms they use
• BDD based, SAT based, structure based, etc.
ECE 667 - Synthesis & Verification
16
Network Representation
Boolean network:
• directed acyclic graph (DAG)
• node logic function representation
fj(x,y)
• node variable yj: yj= fj(x,y)
• edge (i,j) if fj depends explicitly on yi
Inputs x = (x1, x2,…,xn )
Outputs z = (z1, z2,…,zp )
External don’t cares: d1(x), …, dp(x)
ECE 667 - Synthesis & Verification
17
Sum of Products (SOP)
Example:
abc’+a’bd+b’d’+b’e’f
(sum of cubes)
Advantages:
• easy to manipulate and minimize
• many algorithms available (e.g. AND, OR, TAUTOLOGY)
• two-level theory applies
Disadvantages:
• Not representative of logic complexity. For example:
f = ad+ae+bd+be+cd+ce
f’ = a’b’c’+d’e’
These differ in their implementation by an inverter.
• Not easy to estimate logic size and performance
• Difficult to estimate progress during logic manipulation
ECE 667 - Synthesis & Verification
18
Factored Forms
Example:
(ad+b’c)(c+d’(e+ac’))+(d+e)fg
Advantages
• good representative of logic complexity
f=ad+ae+bd+be+cd+ce f’=a’b’c’+d’e’  f=(a+b+c)(d+e)
• in many designs (e.g. complex gate CMOS) the implementation
of a function corresponds directly to its factored form
• good estimator of logic implementation complexity
• doesn’t blow up easily
Disadvantages
• not as many algorithms available for manipulation
• hence often just convert into SOP before manipulation
ECE 667 - Synthesis & Verification
19
Binary Decision Diagrams (BDDs)
• Like factored form, represents both function and
complement
• Like network of muxes, but restricted since
controlled by primary input variables
• not really a good estimator for
implementation complexity
• Given an ordering, reduced BDD is canonical,
hence a good replacement for truth tables
• For a good ordering, BDDs remain reasonably
small for complicated functions (e.g. not
multipliers)
• Manipulations are well defined and efficient
• True support (dependency) is displayed
ECE 667 - Synthesis & Verification
20
AND-INVERTER Graphs (AIG)
•
•
Base data structure uses two-input AND function for vertices and
INVERTER attributes at the edges (individual bit)
– use De’Morgan’s law to convert OR operation etc.
Hash table to identify and reuse structurally isomorphic circuits
f
f
g
g
Means complement
ECE 667 - Synthesis & Verification
21