GSEIS - LME
Logic Synthesis in IC
Design and Associated Tools
Introduction
Wang Jiang Chau
Grupo de Projeto de Sistemas
Eletrônicos e Software Aplicado
Laboratório de Microeletrônica – LME
Depto. Sistemas Eletrônicos
Universidade de São Paulo
Escola Politécnica da Universidade de São Paulo
GSEIS - LME
Escola Politécnica da Universidade de São Paulo
GSEIS - LME
Example: 405 PBD Platform
High-Speed DMA
Controller
PPC405x3 CPU
- 200MHz (WC process 85 °C Tj,2.3V)
- 166MHz (WC process 125 °C Tj,2.3V)
- 16KB instruction cache,8KB data cache
PLB version 3 (64 bit @100MHz)
External peripheral bus
- 8-,16-,or
32-bit byte-addressable
- Byte parity on data bus
- 28-bit address bus
- up to 8 banks of ROM,
EPROM, SRAM,Flash &
slave peripheral I/O
- External master suppor
t
- Four Int. & Ext. channels
- Scatter/gather capability
- Master on HD serial int.
GPIO
EBC
DCR bus
UIC
GPIO
405 CPU
HSDMA
PLB
Arb
PC100 SDRAM
- 100MHz memory bus
- 32-bit data bus,
- 13-bit address bus
- 8-bit ECC support
- Four banks
- Multiplexed I/O functions
OPB
Arb
UART1
UART0
PLB 64bit
Two NS
16550-compatible
UARTs
IIC
HSMC
MISC
PM
MadMal8
PLB-OPB
Bridge
GPT
DCR bus
Reset
CLKG
OPB 32bit
PLL
System clock generation
- Single standard PLL
- Sleep control for most cores
- Wake from sleep capability for CPU
Escola Politécnica da Universidade de São Paulo
EMAC3
I 2 C interface with
integrated 5V-tolerant
bus transceivers
Ethernet 10/100Mbps
- (full-duplex) MAC
- Dedicated Memory Access
Layer (MadMAL) controller
with 50 MHz private bus
General purpose timers
OPB version 1.9,
32 bits @ 50MHz
GSEIS - LME
Three key embedded system
technologies
 Technology

A manner of accomplishing a task, especially using
technical processes, methods, or knowledge
 Three key technologies for embedded systems



Processor technology
IC technology
Design technology
Escola Politécnica da Universidade de São Paulo
GSEIS - LME
Processor technology
 The architecture of the computation engine
used to implement a system’s desired
functionality.
 Processor does not have to be programmable.
Controller
Datapath
Controller
Datapath
Controller
Datapath
Control
logic and
State register
Control logic
and State
register
Registers
Control
logic
index
Register
file
Custom
ALU
State
register
IR
PC
General
ALU
IR
Data
memory
total = 0
for i =1 to …
General-purpose (“software”)
Escola Politécnica da Universidade de São Paulo
+
PC
Data
memory
Program
memory
Assembly code
for:
total
Data
memory
Program memory
Assembly code
for:
total = 0
for i =1 to …
Application-specific
Single-purpose (“hardware”)
GSEIS - LME
Processor technology
 Processors vary in their customization for the
problem at hand.
Desired
functionality
General-purpose
processor
total = 0
for i = 1 to N loop
total += M[i]
end loop
Application-specific
processor
Escola Politécnica da Universidade de São Paulo
Single-purpose
processor
GSEIS - LME
IC technology- 1
 Three types of IC technologies



Full-custom/VLSI
Semi-custom ASIC (gate array and standard cell)
PLD (Programmable Logic Device)
Escola Politécnica da Universidade de São Paulo
GSEIS - LME
IC technology- 1
 Semi-custom design styles and implementation
semicustom
Cell-based (all masks)
Standard cells
Hierarchical cells
Macro cells
•Memory
•PLA
•Gate matrix, …
Escola Politécnica da Universidade de São Paulo
Array-based
Pre-diffused
•Gate arrays
•Sea of gates
•Compacted arrays
Pre-wired
•Anti-fuse based
•Memory-based
GSEIS - LME
Design Technology
 The manner in which we convert our concept of
desired system functionality into an implementation.
Specification
Estimative
Technology
Library
Modeling
Stimuli
Project
Representation
Validation
Synthesis
Implementation
Escola Politécnica da Universidade de São Paulo
[Lavagno, L, Netherlands, 1999]
GSEIS - LME
Moore’s law
 The most important trend in embedded systems.

Predicted in 1965 by Intel co-founder Gordon Moore
10,000
1,000
Logic transistors per 100
chip
10
(in millions)
1
Note:
logarithmic scale
0.1
0.01
0.001
IC transistor capacity has doubled roughly
every 18 months for the past several decades
Escola Politécnica da Universidade de São Paulo
GSEIS - LME
Design productivity gap
 While designer productivity has grown at an
impressive rate over the past decades, the rate of
improvement has not kept pace with chip capacity.
Logic transistors
per chip
(in millions)
10,000
100,000
1,000
10,000
100
10
1000
Gap
IC capacity
1
10
0.1
0.01
0.001
Escola Politécnica da Universidade de São Paulo
100
1
productivity
0.1
0.01
Productivity
(K) Trans./Staff-Mo.
GSEIS - LME
Design productivity gap
 1981 leading edge chip required 100 designer months

10,000 transistors / 100 transistors/month
 2002 leading edge chip requires 30,000 designer
months.

150,000,000 / 5000 transistors/month
 Designer cost increase from $1M to $300M.
Logic transistors
per chip
(in millions)
10,000
100,000
1,000
10,000
100
10
1000
Gap
IC capacity
1
10
0.1
0.01
0.001
Escola Politécnica da Universidade de São Paulo
100
1
productivity
0.1
0.01
Productivity
(K) Trans./Staff-Mo.
GSEIS - LME
The modeling of the design flow- 1
The Y- Diagram
Escola Politécnica da Universidade de São Paulo
GSEIS - LME
The modeling of the design flow- 2
Behavioral Domain
Systems
Algorithms
Register Transfers
Logic
Transfer function
Structural Domain
Communicating processes
Processors
ALU’s, RAM, etc.
Gates, flip-flops, etc.
Transistors
Transistor level
Cell layout
Module Layout
Floorplans
Physical Partitions
Physical Domain
Escola Politécnica da Universidade de São Paulo
GSEIS - LME
The modeling of the design flow- 3
Behavioral Domain
Executable
Specification
Algorithm
Transition
Graph
FSM
Structural
Domain
Physical
Domain
Systems Level
Processes
Channels
Architectural and
Algorithmic Level
HW Blocks
(w/ SW)
Controller and Data
path
Boolean Logic
Logic Cells
Transfer Equations
Transistors
Level
RT Level
Logic Gates Level
Layout
ASIC
Escola Politécnica da Universidade de São Paulo
Transistors Level
Final Implementation
Levels and
Domains
GSEIS - LME
System Level
Structural
Behavioral
Models of Computation
(MoCs)
Algoritms (and languages) for:
Finite State Machine or HCFSM
–very abstract (no
implementation details)
–No notion of Hw or Sw
–efficient to get a compact
execution model as first
design draft
Escola Politécnica da Universidade de São Paulo
Petri-nets
Concurrent Process (channels and
processes)
Data-flow, etc.
GSEIS - LME
Algorithmic Level
Structural
Behavioral (related to HW)
SW
CCD preprocessor
A2D
JPEG codec
Microcontroller
DMA controller
Memory controller
UART
Escola Politécnica da Universidade de São Paulo
0: int x, y;
1: while (1) {
2: while (!go_i);
3: x = x_i;
4: y = y_i;
5: while (x != y) {
6:
if (x < y)
7:
y = y - x;
else
8:
x = x - y;
}
9: d_o = x;
}
GSEIS - LME
Register Transfer Level
Structural
Behavioral
int x, y;
2:
!go_i
x = go_i
x_i
y = y_i
3:
begin
wait until clock'event and clock='1';
5:
If reset='1' then
x<y
x>y
7: y = y -x 8: x = x - y
9:
RegWrite_D1 := '0';
RegWrite_D2 := '0';
d_o = x
RegWrite_D3 := '0';
x_i
Video_Write_D := '0';
y_i
RegWrite_D <= '0';
Datapath
x_sel
n-bit 2x1
Else
n-bit 2x1
y_sel
Regwrite_D3 := RegWrite_D2;
x_ld
0: x
0: y
RegWrite_D2 := RegWrite_D1;
y_ld
RegWrite_D1 := RegWrite;
!=
5: x!=y
x_neq_y
<
6: x<y
subtractor
8: x-y
x_lt_y
subtractor
7: y-x
9: d
d_ld
d_o
Escola Politécnica da Universidade de São Paulo
....
GSEIS - LME
Gate Level
Behavioral
Structural
SC_MODULE(nand2)
{
sc_in<bool> A, B;
sc_out<bool> F;
void do_nand2()
{
F.write( !(A.read() &&
B.read()) );
}
SC_CTOR(nand2)
{
SC_METHOD(do_nand2);
sensitive << A << B:
}
};
Controller implementation model
go_i
x_sel
Combinational logic
y_sel
x_ld
y_ld
x_neq_y
x_lt_y
d_ld
Q3
Q2
Q1
Q0
State register
I3
I2
I1
4ns
3ns
I0
Escola Politécnica da Universidade de São Paulo
5ns
GSEIS - LME
Transistor Level
Behavioral
Structural
VDD
VDD
C
A
B
D
F
A
D
B
C
(c) complete gate
Escola Politécnica da Universidade de São Paulo
GSEIS - LME
The synthesis flow
Exec. Spec.
HW/SW
Codesign
Algorithm
1995- 20..
HW Blocks
High Level
Synthesis
19902000
Grf Tr
FSM
Asynchron. Logic
Synthesis
Bool. Log.
1990-2000
Ctrl & Dtpth
1985-95
Synchron. Logic
Synthesis
Lóg. Cel.
1975-85
Layout
Synthesis
Transf . Func.
The behavioral
and structural
sequencing
Transist.
Layout
Implementation
ASIC
Escola Politécnica da Universidade de São Paulo
Logic Synthesis
GSEIS - LME
Optimization Trade-Off in Combinational
Circuits
Escola Politécnica da Universidade de São Paulo
GSEIS - LME
Optimization Trade-Off in Sequential
Circuits
Escola Politécnica da Universidade de São Paulo
GSEIS - LME
The simulation flow
Program
Execution
(untimed)
Exec. Spec
HW Behavioral
Simulation
(untimed/timed)
Algorithm
HW/SW
Codesign
2000
Functional
Verification
HW Blocks
from untimed to
timed
High Level
Synthesis
1995
1990
RTL Simulation
(Cycle
Accurate)
Map Checking
1985
Logical Simulation
(Discrete Time
Accurate)
Grf Tr
FSM
Asynchron. Logic
Synthesis
Bool. Log.
Ctrl & Dtpth
Synchron. Logic
Synthesis
Log. Cel.
Layout
Synthesis
1980
Circuit Simulation
(Continuous Time)
Transf. Func.
Transist.
Layout
Implementation
ASIC
Escola Politécnica da Universidade de São Paulo
GSEIS - LME
Synthesis: Application of Optimization
Technology
System Synthesis
Algorithmic Synthesis
(High-level synthesis)
Logic Synthesis
Layout Synthesis
Escola Politécnica da Universidade de São Paulo
processor allocation
HW/SW partitioning
process/task scheduling
pipelining
scheduling
resource allocation
state machine optimization
multi-level logic minimization
technology mapping
clock tree design
optimal placement
global/detailed routing
GSEIS - LME
Logic Synthesis Definition- 1
 Wide Interpretation:
Automatic conversion of a hardware
description language (HDL) model into a
gate-level netlist, which meets a set of
design criteria (area, speed, testability,
design rules, etc.)
Escola Politécnica da Universidade de São Paulo
GSEIS - LME
Logic Synthesis Definition- 2
 Narrow Interpretation:
 Translation:
transform logic-level HDL into Boolean equations and latches
 Logic optimization:
reduce the area and/or delay of the equations by modifying the
equations and latches
 Technology mapping:
implement the equations and latches by choosing gates from a
fixed library of primitive elements
Logic synthesis is a set of techniques to assist a logic designer in producing
a high quality logic design quickly and efficiently
Escola Politécnica da Universidade de São Paulo
GSEIS - LME
Logic Synthesis?
Finite-State Machine F(X,Y,Z, ,  ) with:
X: Input alphabet
Y: Output alphabet
Z: Set of internal states
 : X x Z Z (next state function)
 : X x Z Y (output function)
Circuit C(G, W) with:
G: set of circuit components (cells, gates,
flip-flops, etc)
W: set of wires connecting components of G
Escola Politécnica da Universidade de São Paulo
GSEIS - LME
Sequential Logic Synthesis
State
Minimization


X
D
Finite-State Machine F(X,Y,Z, ,  ) with:
Y
State
Assignment
Circuit composed of :
Combinational logic for  and 
Set of registers (flip-flops) D
Escola Politécnica da Universidade de São Paulo
GSEIS - LME
Combinational Logic Synthesis


X
Y
Combinational logic for  and
D
Cells, gates and flip-flops
Escola Politécnica da Universidade de São Paulo

GSEIS - LME
Steps of Combinational Logic
Synthesis
x
y
z,Y = f (x, y)
Combinational
Logic
Two-level
minimization
z
Y
Removing the
Registers
Multi-level
optimization
z
x
x
Y
y
Removing the
Registers
Escola Politécnica da Universidade de São Paulo
Y
y
Technology
mapping
Removing the
Registers
GSEIS - LME
Objective Function for Synthesis
 Minimize area

in terms of literal count, cell count, register count,
etc.
 Maximize performance

in terms of maximal clock frequency of synchronous
systems, throughput for asynchronous systems
 Minimize power

in terms of switching activity in individual gates,
deactivated circuit blocks, etc.
Escola Politécnica da Universidade de São Paulo
GSEIS - LME
Constraints on Synthesis
 By implementation style:
 two-level implementation (PLA)
 multi-level logic
 FPGAs
 By performance requirements
 minimal clock speed requirement
 minimal latency, throughput
 By cell library
 set of cells in standard cell library
 fan-out constraints
 cell generators
Escola Politécnica da Universidade de São Paulo
GSEIS - LME
Logic Synthesis Advantages
 Design capture at the register transfer level (RTL) and
logic level using HDLs:


Technology independent design description
Easy reuse of old designs
 Designer focus is at the architectural level, not the gate
level


Automates tedious gate-level design phase
Allows designer to explore architectural changes quickly
 Logic optimization to implement the design at the gatelevel


Optimizes design for a specific ASIC technology and library
Optimization is essential to produce competitive designs
Escola Politécnica da Universidade de São Paulo
GSEIS - LME
Instability of Logic Synthesis
Change in area and performance (15 testcases and 20 libraries)
6
4
performance (% )
2
0
-2
-4
-6
-40
-30
-20
-10
area (%)
Escola Politécnica da Universidade de São Paulo
0
10
20
30