Transcript Color template - University of Utah

Computer-Aided Design of Digital VLSI
Circuits & Systems
Perspectives on Next-Generation
Logic Synthesis
Priyank Kalla
Dept. of Elec. & Comp. Engineering
University of Utah,SLC
Logic Synthesis in VLSI Realization
Objective:
Generate Optimal Designs
Specifications
Circuit Netlist
Sequential
Optimization
Optimized
Netlist
Tech. Mapping
Cell Library
Place & Route
Semi-Custom Design Styles
Semi-Custom
Array-based
Cell-based
Std. Cells
Macro cells
Hierarchical
Std. Cells
PLA
Memory
Gate-Arrays
MPGAs
FPGAs
Choice of Design Styles
Custom
Semi-custom Gate-array
Density
Very high
High
Medium
Performance
Very high
High
Medium
Design time
Very Long
High
Medium/low
Manufacturi
ng time
Medium
Medium
Short
Low volume
Very High
High
Low
Low
Low
High
Cost
High. Vol.
Cost
Design Representations
Transformation:
 Architectural
F1 = A*A – B*B
F2 = C*C – D*D
F = x F1 + x’ F2
 Behavioural
F1 = (A-B)(A+B)
F2 = (C-D)(C+D)
F = x F1 + x’ F2
Transformations
s1
s1
s4
s2
s0
s3
s2
s0
s3
Transformation Criteria
 Architectural
Resource Optimization
Latency/Throughput Optimization
Computation Scheduling, Resource Binding
Testability and Verifiability
 Behavioural
Logic Area
Gate Delay (timing performance)
Switching & Static Power Dissipation
Testability and Verifiability
Area
…
Minimization Versus Optimization
Delay…
 Minimization
versus Optimization Trade-offs
Minimize Logic Area, or Delay, or Power….
Optimize Area within bounded Delays
Optimize Delay within bounded Area
Physical Synthesis: Optimize Area w.r.t.
Reliability and Manufacturability
What is Logic Synthesis?
 Given:
Logic Functions or Finite-State Machines
Automatically generate designs (synthesis)
Minimize or Optimize Logic w.r.t. constraints
Optimally map logic onto realistic gates
 Problems
and Challenges
Memory: Size!
Size!
SIZE!
Time: Computationally intensive operations
What kind of representations to use?
How to optimize logic to target the technology?
When Technology was PLAs….
 Two-Level
Logic Minimization: K-map type
F = a’bc + ab’c + abc’ + abc
F = ab + ac + bc
Fewer inputs = fewer transistors
Reduced Area AND Reduced Delay
Algorithmic Techniques:
Quine-McCluskey, Espresso, Signature-cubes
Then came CMOS Technology….
 Salient
Features:
Very high noise margins
Design Scalability
Enabled Standard Cell-based Design
Abstract Electrical Properties: Area-Delay
Fanout-Drive Scalability: X’sistor Sizing
Low (zero) Static Power Dissipation
Enabled Standard-Cell Place & Route
Estimates: Close to ~10% of actual layout
Cheap, Reliable, Scalable, low turn-aournd time
Multi-Level Logic Synthesis
F
= ab + bc + ac
F = b(a + c) + ac
F = ab + c(b + a)
Problem: Area and Delay became dependent
Problem: How do you factorize?
Multi-Level Synthesis for CMOS
 Synthesis
Issues to consider
Objective: Minimize number of literals (area)
Delay: Depth of paths, fanouts, signal orders,
arrival and required times….
Area  Delay became dependent
Factorization:
Extract common subexpressions
Fanout problems
Routing Difficulties
Optimization (instead of minimization) became
the dominant issue
Don’t Cares came into Focus….
F
= a(b+c)
When a = 0, (b + c) = Don’t care
D.C. = a’(b + c)? Not really….
How to “generate” D.C. set to optimize logic?
Problem: How do you factorize to create a good
don’t care set ?
Problem: How to filter “bad” don’t care sets ?
Don’t Cares Computations…..
 How
to efficiently compute D.C.s and simplify ckt?
Input DC
Image computations
Controllability and observability DCs
Propagate DC set across the circuit
Image of the DC
Solution: Sequence of Optimizations
 Script-based
multi-level logic synthesis
Collapse the whole circuit into two-level logic
Apply K-map type two-level minimization
Perform Greedy Factorization
Compute Don’t Cares
Simplify with Don’t cares
Estimate area/delay, re-factorize if needed
Delay minimization: depth minimization, fanout
adjustment, transistor sizing, buffer insertion….
Sequential Optimization
 Behavioural
Transformations
s1
s1
s4
s2
s0
s3
 Behavioural
s2
s0
s3
Optimizations:
Code assignments: What is there effect on design?
S0 (00), s1(01), s2(10), s3(11)
S0(00), s1(10), s2(01), s3(11)
FPGA-based Logic Synthesis
 Look-up
Table based FPGAs
Look-up
Table
 Optimizations
Criteria:
a b c
f
0
0
0
0
1
1
1
1
0
0
0
1
0
1
0
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
Input-space Partitioning, Decomposition
Literal minimization does nothing here…..
Routing resources, congestion……
The coming of age of Synthesis….
 Power
of multi-level logic synthesis
Two-level minimization: solved!
Good factorization techniques found
Good Boolean Decomposition techniques
Good representations: ROBDDs…..
Don’t care theory well understood
Technological challenges well understood
(CMOS, FPGA, PLA, Memories….)
Some Problems Remain……
 Limitations
of conventional synthesis techniques
Sequential Optimizations not well understood
Perhaps the problem has become redundant?
Technology specific decomposition still needs
some work
Not much support for hierarchical synthesis
No support for across the boundary optimizations
Power optimization at logic-level: NO IDEA!!
Effect of factorization on Placement & routing
New Challenges in Logic Synthesis
 The
problems of the future…..
Static CMOS: area-delay will become
unacceptable
Layout is already becoming unsolvable
Static (leakage) power is increasing
Design granularity…. Large v/s small
Hierarchical synthesis will become a major issue
NOISE! Dynamic logic related….
New Technologies to Synthesize
 Dynamic
Logic
Problems: Domino logic is monotonic
Charge Sharing, leakage, noise….
Standard-cell based or macro-cell based?
 Pass
Transistor Logic (PTL)
All of the above problems
Signal degradation + restoration?
s
Need of the Hour: I think……
 Mixed
Pass Transistor & Static CMOS Logic
Area reduction due to PTL
Delay reduction due to PTL & CMOS buffers
Signal degradation + restoration can be solved
Challenges:
Factorize to reduce noise
What to map on PTL and what to map on CMOS?
s1
s2
CMOS
Gate
Large fanout
Need of the Future: I think……
 For
new technologies, “nano”-type
Area/Delay estimation Rethink
Sequential Optimization will bounce back!
Binary valued logic to Multi-values Logic
Power has to be handled at logic level
Memory no problem…. But computation time….
Logic optimization for manufacturability…..
Structured Logic Decomposition for estimatable
Placement and routing….
How about “Synthesis for verifiablity” ?