VLSI Combinational Circuit Design - Dr. Le Dung

is
Dr. Le Dung Hanoi University of Science and Technology
Netlist of gates (from library) 
which minimizes total cost.
Phases of synthesis (1/3)
1. Independent transformations (optimization):
Dr. Le Dung Hanoi University of Science and Technology
10/31/2012
9
Phases of synthesis (1/3)
Dr. Le Dung Hanoi University of Science and Technology
1. Independent transformations (optimization):
Phases of synthesis (1/3)
Dr. Le Dung Hanoi University of Science and Technology
1. Independent transformations (optimization):
10/31/2012
10
Phases of synthesis (1/3)
Dr. Le Dung Hanoi University of Science and Technology
1. Independent transformations (optimization):
Phases of synthesis (1/3)
Dr. Le Dung Hanoi University of Science and Technology
1. Independent transformations (optimization):
10/31/2012
11
Phases of synthesis (1/3)
d
a
c
b
e
f
g
h
Dr. Le Dung Hanoi University of Science and Technology
1. Independent transformations (optimization):
Original netlist
Phases of synthesis (2/3)
• Decomposition using base functions:
– Decompose to a network NAND2/NOT
d
a
c
b
e
fg
h
Dr. Le Dung Hanoi University of Science and Technology
Original netlist
10/31/2012
12
Phases of synthesis (2/3)
d
a
c
b
e
fg
h
• Decomposition using base functions:
– Decompose to a network NAND2/NOT
Dr. Le Dung Hanoi University of Science and Technology
Phases of synthesis (2/3)
d
a
c
b
e
fg
h
• Decomposition using base functions:
– Decompose to a network NAND2/NOT
Dr. Le Dung Hanoi University of Science and Technology
10/31/2012
13
Phases of synthesis (2/3)
d
a
c
b
e
fg
h
• Decomposition using base functions:
– Decompose to a network NAND2/NOT
Dr. Le Dung Hanoi University of Science and Technology
Phases of synthesis (2/3)
d
a
c
b
e
fg
h
• Decomposition using base functions:
– Decompose to a network NAND2/NOT
Dr. Le Dung Hanoi University of Science and Technology
10/31/2012
14
Phases of synthesis (2/3)
d
a
c
b
e
fg
h
• Decomposition using base functions:
– Decompose to a network NAND2/NOT
Dr. Le Dung Hanoi University of Science and Technology
Phases of synthesis (2/3)
d
a
c
b
e
fg
h
• Decomposition using base functions:
– Decompose to a network NAND2/NOT
Dr. Le Dung Hanoi University of Science and Technology
10/31/2012
15
Phases of synthesis (2/3)
d
a
c
b
e
fg
h
• Decomposition using base functions:
– Decompose to a network NAND2/NOT
Dr. Le Dung Hanoi University of Science and Technology
Phases of synthesis (2/3)
d
a
c
b
e
fg
h
• Decomposition using base functions:
– Decompose to a network NAND2/NOT
Dr. Le Dung Hanoi University of Science and Technology
10/31/2012
16
Phases of synthesis (2/3)
d
a
c
b
e
fg
h
• Decomposition using base functions:
– Decompose to a network NAND2/NOT
Dr. Le Dung Hanoi University of Science and Technology
Phases of synthesis (2/3)
d
a
c
b
e
fg
h
• Decomposition using base functions:
– Decompose to a network NAND2/NOT
Dr. Le Dung Hanoi University of Science and Technology
10/31/2012
17
Phases of synthesis (2/3)
d
a
c
b
e
fg
h
• Decomposition using base functions:
– Decompose to a network NAND2/NOT
Dr. Le Dung Hanoi University of Science and Technology
Phases of synthesis (2/3)
d
a
c
b
e
fg
h
• Decomposition using base functions:
– Decompose to a network NAND2/NOT
Dr. Le Dung Hanoi University of Science and Technology
Subject Graph
10/31/2012
18
What is technology mapping ? 
• Technology mapping is the problem of optimising a 
network for area or delay, using only library cells.
Mapping
library
rule
Dr. Le Dung Hanoi University of Science and Technology
Netlist of gates (from library) 
which minimizes total cost.
Original netlist
Phases of synthesis (3/3)
d
a
c
b
e
fg
h
• Technology mapping:
Greedy algorithm Æ Greedy search
Dr. Le Dung Hanoi University of Science and Technology
Subject Graph
10/31/2012
19
Phases of synthesis (3/3)
d
a
c
b
e
fg
h
• Technology mapping:
– Greedy search
Dr. Le Dung Hanoi University of Science and Technology
Subject Graph
Phases of synthesis (3/3)
d
a
c
b
e
fg
h
• Technology mapping:
‐ Greedy search
Dr. Le Dung Hanoi University of Science and Technology
Subject Graph
10/31/2012
20
• Technology mapping:
– Using principle of optimality
Phases of synthesis (3/3)
d
a
c
b
e
fg
h
15
Dr. Le Dung Hanoi University of Science and Technology
Subject Graph
Phases of synthesis (3/3)
d
a
c
b
e
fg
h
15 9 
• Technology mapping:
– Using principle of optimality
Dr. Le Dung Hanoi University of Science and Technology
Subject Graph
10/31/2012
21
Phases of synthesis (3/3)
d
a
c
b
e
fg
h
• Technology mapping:
– Using principle of optimality
Dr. Le Dung Hanoi University of Science and Technology
Subject Graph
Sea of gates
Cell I/O buffer
Fixed transistor 
layer
Customized 
metal layer for 
connecting gate
Dr. Le Dung Hanoi University of Science and Technology
Gate array based design
+ A gate array or uncommitted logic array (ULA) circuit is prefabricated
with a number of unconnected logic gates (cells).
+ CMOS transistors with fixed length and width are placed at regular
predefined positions and manufactured on a wafer, usually called a
master slice (Æ sea of gates).
+ Creation of a circuit with a specified function is accomplished by
adding a final surface layer or layers of metal interconnects to the chips
on the master slice late in the manufacturing process, joining these
elements to allow the function of the chip to be customized as desired
Æ reducing the designing time
Æ reducing the mask costs
+ Disadvantages
- slow clock speed
- wasted chip area
10/31/2012
22
Dr. Le Dung Hanoi University of Science and Technology
Gate array based design flow
Design entry
Placement
Routing
Simulation
Timing simulation
Fabrication (metal 1 mask) Testing
Library of cellsTechnology mapping
Dr. Le Dung Hanoi University of Science and Technology
Programmable Device Based Design
Based on programmable devices:
The interconnection layers are personalized by electronic means for a 
specific application. This work usually can be done by end-users.
F0 = A’B’+ AC’
F1 = B + AC’
F2 = A’B’+ BC’
F3 = AC + B
10/31/2012
23
Dr. Le Dung Hanoi University of Science and Technology
Programmable Elements
+ Fuse
+ Antifuse
+ Switch
+ Volatile
+ Non-volatile
+ One Time Programmable
+ Reprogrammable (Memory-based)
Dr. Le Dung Hanoi University of Science and Technology
Programmable Devices
• Simple Programmable Logic Device: 
+ Programmable read only memory (PROM)
+ Field Programmable logic array (FPLA or PLA)
+ Programmable array logic (PAL)
+ Generic array logic (GAL)
• Complex programmable logic device (CPLD)
• Field programmable gate array (FPGA)
• Field programmable interconnect (FPIC)
10/31/2012
24
Dr. Le Dung Hanoi University of Science and Technology
Basic SPLD organization 
AND
arra
y
OR
arra
y
Output
options
Product 
terms
Sum 
terms
Feedback terms
Inputs Outputs
Dr. Le Dung Hanoi University of Science and Technology
Fuse‐based programmable AND – OR Array  
10/31/2012
25
Dr. Le Dung Hanoi University of Science and Technology
Output Polarity Options 
Dr. Le Dung Hanoi University of Science and Technology
Bidirectional Pins and Feedback line 
10/31/2012
26
Dr. Le Dung Hanoi University of Science and Technology
PLD Design Process 
Dr. Le Dung Hanoi University of Science and Technology
Combinational Circuit is implemented on SPLD 
10/31/2012
27
Dr. Le Dung Hanoi University of Science and Technology
PROM = Read‐Only‐Memory
Dr. Le Dung Hanoi University of Science and Technology
PROM = PLD with fixed AND array
10/31/2012
28
Dr. Le Dung Hanoi University of Science and Technology
Full‐adder on PROM 
Dr. Le Dung Hanoi University of Science and Technology
PAL
10/31/2012
29
Dr. Le Dung Hanoi University of Science and Technology
Combinational Circuit is implemented PAL
Dr. Le Dung Hanoi University of Science and Technology
FPLA
Programmable
OR array
Programmable
AND array
10/31/2012
30
Dr. Le Dung Hanoi University of Science and Technology
Combinational Circuit is implemented on FPLA (1)
Minimize each function separately
Æ 8 product terms
F1 = bd + b’c + ab’
F2 = c + a’bd
F3 = bc + ab’c’+ abd
Multiple‐Output Optimization
Æ 5 product terms
F1 = abd + a’bd + ab’c’+ b’c
F2 = a’bd + b’c + bc
F3 = abd + ab’c’+ bc
Dr. Le Dung Hanoi University of Science and Technology
Combinational Circuit is implemented on FPLA (2)
F1 = abd + a’bd + ab’c’+ b’c
F2 = a’bd + b’c + bc
F3 = abd + ab’c’+ bc
10/31/2012
31
Dr. Le Dung Hanoi University of Science and Technology
Exercise
Implement the two
functions with PLA
PLA
Dr. Le Dung Hanoi University of Science and Technology
Generic Array Logic architecture
Output logic macrocell (OLMC)
10/31/2012
32
Dr. Le Dung Hanoi University of Science and Technology
CPLD architecture
AND-OR
Plane
O I/O
Switch matrix
I/O O
AND-OR
Plane
AND-OR
Plane
O I/O I/O
AND-OR
Plane
O
Dr. Le Dung Hanoi University of Science and Technology
FPGA architecture (1)
10/31/2012
33
Dr. Le Dung Hanoi University of Science and Technology
FPGA architecture (2)
Dr. Le Dung Hanoi University of Science and Technology
FPGA architecture (3)
Switch Matrix and interconnection
Long lines : 
- Across whole chip
- High fan-out, low skew
- Suitable for global signals (CLK) and buses
- 2 tri-states per CLB for busses
10/31/2012
34
Dr. Le Dung Hanoi University of Science and Technology
FPGA architecture (4)
Configurable Logic Block (CLB)
5 logic inputs
Data input (DI)
Clock (K)
Clock enable (EC)
Direct reset (RD)
2 outputs (X,Y)
Dr. Le Dung Hanoi University of Science and Technology
FPGA architecture (5)
I/O Block (IOB)
10/31/2012
35
Dr. Le Dung Hanoi University of Science and Technology
FPGA development toolkit