Transcript Behavioral Domain

Logic Synthesis:
Course Introduction
Shashi Kumar
Embedded System Group
Department of Electronics and Computer Engineering
Jönköping Univ.
Shashi Kumar
1
Outline
 Objectives and scope of the course
 Course Overview
 Laboratory Organization
 Literature
23rd Oct. 2000
Shashi Kumar
2
Course Objectives
 To learn techniques to synthesize digital circuits at
logic level.
Specifation of circuits at logic level
 Combinational Circuits
 Sequential circuits
Optimization of logic circuits
 Minimize cost( area)
 Delay/ Clock period
Technology Mapping or Library Binding
 Implement the logic circuit using a given set of library
components
 Implement the circuit using FPGAs
23rd Oct. 2000
Shashi Kumar
3
Course Scope
 You will:
Learn theory used to design logic synthesis tools
Use a Public Domain Logic Synthesis tool called SIS
(from Univ. Of California, Berkeley )
Do small digital circuit design in the laboratory and
optimize them using SIS.
 You will not learn in this course:
Lower level physical design
Higher level behavioral design
A hardware description language like VHDL
23rd Oct. 2000
Shashi Kumar
4
Course Pre-requisites
 Compulsory
Basic knowledge in digital circuit design
Discrete mathematic concepts
 Boolean Algebra
 Graph Theory
 Useful but not compulsory
Some programming experience
Familiarity with UNIX O.S.
23rd Oct. 2000
Shashi Kumar
5
Digital System Design Process
Design Idea
Behavioral Design
Hardware Description Language
RTL Design
Logic Design
Buses, Registers,
ALU’s
Net-list of gates and
flip-flops
Physical Design
Manufacturing
23rd Oct. 2000
Shashi Kumar
6
Y-Chart
Behavioral
Domain
Structural Domain
Processors, Mem, Buses
Registers, ALUs, MuXs,
.
Gates, Flip-Flops
Transistors
Flowcharts, Algorithms
Register Transfers
Boolean Expressions
Transistor Functions
Transistor Layout
Cells, Modules
Chips, ASICs
Boards, MCM
Physical
Domain
23rd Oct. 2000
Shashi Kumar
7
Design Processes
Structural Domain
Processors, Mem, Buses
Registers, ALUs, MuXs,
.
Gates, Flip-Flops
Transistors
Synthesis
Behavioral Domain
Flowcharts, Algorithms
Register Transfers
Boolean Expressions
Transistor Functions
Transistor Layout
Implementation
Cells, Modules
Chips, ASICs
Boards, MCM
Physical
Domain
23rd Oct. 2000
Shashi Kumar
8
Levels of Abstraction
Behavioral Domain
……
PC = PC + 1;
IR = Mem( PC);
…
A = A + B;
….
Structural Domain
A
B
Adder
Control
U= A*!B + C
V = !A*!C+!B
……
23rd Oct. 2000
&
+
Shashi Kumar
R
A
M
P
C
&
+
9
Synthesis
Synthesis involves the transformation of system
description from behavioral domain to structural
domain.
Architectural/Behavioral Synthesis
 Algorithmic Description  RTL Design
 RTL Design : Design using Registers, Adders, Multiplexors,
buses etc.
Logic Synthesis
 Boolean functions, Finite State Machine  Logic Design
 Logic Design: Design using gates and flip-flops
Physical Synthesis
 Switching functions  Transistor switches
23rd Oct. 2000
Shashi Kumar
10
Logic Synthesis
&
 Example
&
Sum = !A*!B*C+!A*B*!C+A*!B*!C+A*B*C
Cout = !A*B*C+A*!B*C+A*B*!C+A*B*C
+
Sum
&
&
S0,0
S1,1
”1”
J1 Q1
K1
J2 Q2
K2
S2,2
CLK
S3,3
23rd Oct. 2000
Shashi Kumar
11
Logic Optimization
Transform the description to an equivalent description so that the cost
of the new description is smaller than the original description.
Cout = !A*B*C+A*!B*C+A*B*!C+A*B*C
Cost: 4 3-input AND gates
and 1 4-input OR gate
Cost: 3 2-input AND gates
and 1 3-input OR gate
Cout = B*C+A*C+A*B
V = A*C+AD+A*E+B*C+B*D+B*E
Cost: 6 2-input AND gates
and 1 6-input OR gate
V = (A+B)*(C+D+E)
Cost: 1 2-input AND gates
and 2 3-input OR gate
23rd Oct. 2000
Shashi Kumar
12
Sequential Logic Synthesis
Synthesize the behavior of the system in terms of flip-flops
and gates.
Generic Implementation of an FSM
X: set of inputs;
X
Z: set of outputs;
N: Number of states
S(t+1) = F( S(t), X)
Z(t) = G( S(t), X(t))
Number of bits in SR   Log2 N
S(t+1)
F
S
R
S(t)
G
Z
Objectives
 Minimize size of SR
 Implement the functions F and G using minimum number of gates.
23rd Oct. 2000
Shashi Kumar
13
FSM Minimization
 Transform the given FSM to another equivalent
FSM which has lesser number of states.
Equivalent FSM with minimum number of states
Minimizes the size of the state register
The problem is very hard for large FSMs
 Hard Problem
Time required to find an equivalent FSM with
minimum number of states grows exponentially with
number of states.
Time = k1 * 2N; Time to minimize FSM with 40 states may take years!
23rd Oct. 2000
Shashi Kumar
14
State-Encoding
 State Encoding is the task of assigning binary
codes to the states of an FSM.
 Number of different possibilities of state encodings =
O(3N), for an FSM with N states.
 The hardware cost and speed depends on the codes given
to states
 Cost of hardware: cost of state register, cost of implementing
functions F and G.
 Delay depends on the implementation of function F and G
 It is important to select a good encoding for states.
 The task is very hard!
23rd Oct. 2000
Shashi Kumar
15
Technology Mapping or Library Binding
 Technology mapping step in logic synthesis takes an
optimized description of circuit and implements it using a
restricted set of components from a library.
 ASIC Design : using a technology dependent cell library
 FPGA: using the blocks of FPGAs
 PCB based implementation: components available in lab. or stock
 The task in technology mapping is to get an
implementation which meets the desired objectives.
 Minimum Cost
 Minimum Delay
 Meets cost and Delay constraints
23rd Oct. 2000
Shashi Kumar
16
Laboratory Objectives
 To Learn:
Representations of circuit at logic level
Learn a Computer Aided design tool for:





Two-Level Logic optimization
Multi-Level Logic Optimization
FSM Minimization
FSM Encoding
Technology Mapping
23rd Oct. 2000
Shashi Kumar
17
SIS Tool
 SIS is a Logic Synthesis tool developed at
University of California, Berkeley.
http://www-cad.eecs.berkeley.edu/Software/software.html
 SIS is installed in a unix machine in Högskolan
SIS accepts circuits in certain formats
 BLIF
 KISS
SIS consists of a set of commands and has a text
interface.
 You will use do all your laboratory exercises
23rd Oct. 2000
Shashi Kumar
18
Laboratory Exercises
 Exercise 1: Logic Optimization using SIS
Design and optimization of combinational circuit
 4-bit unsigned multiplier design
Design and optimization of sequential circuits
 Design of a pattern recognizer
Logic optimization of bench-mark circuits
 Exercise 2: Technology mapping using SIS
Use SIS to implement the combinational and the
sequential circuit designed in exercise 1 onto an FPGA
using SIS.
23rd Oct. 2000
Shashi Kumar
19
Text and Reference Books
1.
2.
3.
4.
Giovanni De Micheli, Synthesis and optimization of digital circuits,
McGraw-Hill International Editions, Electrical Engineering Series,
1994, ISBN 0-07-016333-2.
Stephen D. Brown, Robert J. Francis, Jonathan Rose, Zvonko G.
Vranesic, Field-Programmable Gate Arrays, Kluwer Academic
Publishers, 1992, ISBN 0-7923-9248-5.
Saeyang Yang, ” Logic Synthesis and Optimization Benchmarks user
guide Version 3.0”, Report, Microelectronic Center of North
Carolina, Box 12889, Research Triangle Park, NC 27709, USA.
Ellen M. Sentovich, et. Al. ,” SIS: A System for Sequential Circuit
Synthesis”, Lectronic Research Laboratory, Memo. Number
UCB/ERL M92/41, Department of Electrical Engineering and
Computer Science, May 1992.
23rd Oct. 2000
Shashi Kumar
20