Chapter 08 Register Transfer Specification And Design (NEW)
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (773.95 KB, 62 trang )
Principles Of
Digital Design
Chapter 8
Register Transfer
Specification And Design
Chapter preview
3
Boolean
algebra
3
Logic gates and
flip-flops
6
Finite-state
machine
Binary system
and data
representation
Sequential design
techniques
2
5
Combinational
components
Generalized
finite-state
machines
6
4
Logic design
techniques
Storage
components
8
7
8
Register-transfer
design
9
Processor
components
Copyright © 2004-2005 by Daniel D. Gajski
2
Slides by Xi Cheng, University of California, Irvine
Register-transfer design
z
Each standard or custom IC consists of one or more
datapaths and control units.
z
To synthesize such IC we introduce the model of a FSM
with a datapath (FSMD).
z
We demonstrate synthesis algorithms for FSMD model,
including component selection, resource sharing,
pipelining and scheduling.
Copyright © 2004-2005 by Daniel D. Gajski
3
Slides by Xi Cheng, University of California, Irvine
Example 7.1
Copyright © 2004-2005 by Daniel D. Gajski
4
Slides by Xi Cheng, University of California, Irvine
Design Model
Control
inputs
Control
unit
Datapath
inputs
Control
signals
Status
signals
Control
outputs
Nextstate
logic
D
Q
D
Q
Control unit
Copyright © 2004-2005 by Daniel D. Gajski
Datapath
inputs
Control
signals
Selector
Register
RF
Mem
.
.
.
.
.
.
D
Datapath
outputs
High-level block diagram
Control
inputs
.
.
.
Datapath
Bus 1
Bus 2
Q
State
register
Output
logic
*/÷
ALU
Bus 3
Status
signals
Register
Datapath
Control
outputs
outputs
Register-transfer-level block diagram
5
Datapath
Slides by Xi Cheng, University of California, Irvine
Ones-counter specification
Data
Mask
Temp
Ocount
Start = 0
Start = 1
Done=0; Data = Input
Done=0; Ocount = 0
Done=0; Mask = 1
Done=0; Temp = Data AND Mask
Data = 0
Done=0; Ocount = Ocount + Temp
Done=1; Data = Data >> 1
Data = 0
Done=1; Output =Ocount
Copyright © 2004-2005 by Daniel D. Gajski
6
Slides by Xi Cheng, University of California, Irvine
FSDM Definition
In Chapter 6 we defined an FSM as a quintuple < S, I, O, f, h >
where S is a set of states, I and O are the sets of input and output
S , and h : S × I
O
symbols: f : S × I
More precisely,
I = A1 × A2 ×…Ak
S = Q1 × Q2 ×…Qm
O = Y1 × Y2 ×…Yn
Where Ai, 1 ≤ i ≤ k , is an input signal, Qi, 1 ≤ i ≤ m is the flip-flop output
and Yi, 1 ≤ i ≤ n is an output signal.
To define a FSMD, we define a set of variables V = V1 × V2 ×…Vq
which defines the state of the datapath by defining the values of all
variables in each state.
=
=
{
U
U
=
{(
W
V
∈
)
∈
W
}
}
V∈ {≤ p = f ≥}
I =I ×I
C D
where IC = A1 × A2 ×…Ak as before and ID = B1 × B2 ×…Bp,
O =O ×O
C
D
Where OC = Y1 × Y2 ×…Yn as before and OD = Z1 × Z2 ×…Zr.
Copyright © 2004-2005 by Daniel D. Gajski
7
Slides by Xi Cheng, University of California, Irvine
FSDM Definition
With formal definition of expressions and relations over a set of variables
we can simplify function f : ( S ×V ) × I
S ×V by separating it into two
parts: fC and fD. The function fC defines the next state of the control unit
S
fC : S ×IC × STAT
while the function fD defines the values of datapath variables in the next
state
V
fD : S ×V × ID
fD :={fDi : V × ID
V : { Vj =ej | Vj
Also,
hC : S ×IC × STAT
V, ej Expr ( V × ID )}}
∈
∈
OC
and
hD : S ×V × ID
Copyright © 2004-2005 by Daniel D. Gajski
OD
8
Slides by Xi Cheng, University of California, Irvine
FSMD specification of Ones-counter
Next state Control Datapath
Present (Start. Data=0)
Output output
State
00 01 10 11 Done Outport Data
Datapath Variables
Ocount
Temp
Mask
s0
s1
s0 s0 s1 s1
0
Z
X
X
X
X
s2 s2 s2 s2
0
Z
Inport
X
X
X
s2
s3
s3 s3 s3 s3
0
Z
Data
0
X
X
s4 s4 s4 s4
0
Z
Data
Ocount
X
1
Ocount
Data AND
Mask
Mask
X
Mask
s4
s5 s5 s5 s5
0
Z
Data
s5
s6 s6 s6 s6
0
Z
Data Ocount+Temp
s6
s4 s7 s4 s7
0
Z
Data>>1
Ocount
X
Mask
s7
s0 s0 s0 s0
1
Ocount
Data
Ocount
X
X
State and output table
Next state Control Datapath
Present (Start. Data=0)
Output output Data Variables
State
00 01 10 11 Done Outport
Present
State
s0
Next state
condition
state
Start = 0
s0
[Start = 1
Control and Datapath actions
condition actions
]
Done = 0
s0
s1
s0 s0 s1 s1
0
Z
s2 s2 s2 s2
0
Z
Data = Inport
s1
s2
Data = Inport
s2
s3
s3 s3 s3 s3
0
Z
Ocount = 0
s2
s3
Ocount = 0
s4 s4 s4 s4
0
Z
Mask = 1
s3
s4
Mask = 1
s4
s5 s5 s5 s5
0
Z
Temp = Data AND Mask
s4
s5
Temp = Data AND Mask
s5
s6
Ocount = Ocount + Temp
s5
s6 s6 s6 s6
0
Z
Ocount = Ocount + Temp
s6
s4 s7 s4 s7
0
Z
Data = Data >> 1
s7
s0 s0 s0 s0
1
Ocount
Data
s6
s7
State and output table with variable assignments
Copyright © 2004-2005 by Daniel D. Gajski
0
[Data = 0
s1
s4
s7
s0
Data = Data >> 1
]
[
Done = 1
Data = Inport
]
State-action table
9
Slides by Xi Cheng, University of California, Irvine
Algorithmic-State-Machine
z
Graphic representation of FSMD model
z
Equivalent to state-action table
z
Similar to a flowchart used for program description
Copyright © 2004-2005 by Daniel D. Gajski
10
Slides by Xi Cheng, University of California, Irvine
ASM Symbols
Name
Definition
Example
State box
Decision
Box
Condition
Box
ASM
Block
Copyright © 2004-2005 by Daniel D. Gajski
11
Slides by Xi Cheng, University of California, Irvine
ASM rules
z
Rule 1: The chart must define a unique next state for each state
and set of conditions.
z
Rule 2: Every path defined by the network of condition boxes
must lead to another state.
ASM block
s1
s1
ASM block
0
0
1
cond1
0
1
cond2
1
cond1
0
1
cond2
s2
s3
s2
Undefined next state
Copyright © 2004-2005 by Daniel D. Gajski
s3
Undefined exit path
12
Slides by Xi Cheng, University of California, Irvine
ASM chart for Ones-counter
(a) State-based (Moore) chart
Copyright © 2004-2005 by Daniel D. Gajski
13
(b) Input-based (Mealy) chart
Slides by Xi Cheng, University of California, Irvine
State-action tables for Ones-counter
Next state
Present State
Q2 Q1 Q0
Name
State-based
table
000
s0
001
s1
Condition
Start = 0,
s0
Start = 1,
s1
Datapath actions
Operations
Done = 0
Data = Inport
010
s2
011
s3
100
s4
101
s5
s2
DataLSR=1,
s3
DataLSR=0,
s4
Ocount = 0
s4
Data
0,
s2
Data = 0,
s5
Ocount = Ocount + 1
Data = Data >> 1
Done = 1
s0
=
Output = Ocount
=
=
+
+
=
=
=
+
=
=
=
+
=
=
=
=
=
≠
+
≠
+
+
+
=
≠
≠
+
=
=
+
+
+
=
Copyright © 2004-2005 by Daniel D. Gajski
State condition
+
≠
≠
+
=
14
=
Slides by Xi Cheng, University of California, Irvine
State-action tables for Ones-counter
Next state
Present State
Name
Q1 Q0
00
s0
Input-based
01
table
s1
10
s2
11
Condition
State
Start = 0,
Start = 1,
s0
]
s1
[
[ Data
0,
s2
Data = 0,
s3
=
=
=
=
=
[
]
+
=
]
Ocount = 0
Ocount = Ocount + 1]
Data = 0,
Data = Data >> 1
[Done = 1
Output = Ocount
+
≠
Data = Inport
DataLSR=1,
=
]
+
+
≠
+
=
Copyright © 2004-2005 by Daniel D. Gajski
[
s0
=
=
=
Done = 0
s2
s3
=
Datapath actions
condition
Operations
≠
=
=
≠
=
≠
+
≠
=
=
=
15
=
Slides by Xi Cheng, University of California, Irvine
Logic schematics for Ones-counter
z
z
D2 = Q2(next) = s2DataLSB + S3 + S4(Data
0)’
= Q1Q’0Data’LSB + Q1Q0 + Q2Q’0(Data
D1 = Q1(next) = s1 + s2DataLSB + s4(Data
z
S1= s4 =Q2Q’0
0)’
z
S0 = s2 + s4 = Q1Q’0 + Q2Q’0
0)
z
E = s3 = Q1Q0
z
Load =s1 = Q’2Q’1Q0
z
Done = Output enable = s5 = Q2Q0
= Q’2Q’1Q’0 + Q1Q’0DataLSB + Q2Q’0(Data
z
D0 = Q0(next) = s0Start + s2DataLSB + s4(Data
= Q’2Q’1Q’0Start+Q1Q’0DataLSB+Q2Q’0(Dara
0)
0)’
0)’
State-based version
Copyright © 2004-2005 by Daniel D. Gajski
16
Slides by Xi Cheng, University of California, Irvine
Logic schematics for Ones-counter
z
z
z
z
z
z
z
D1 = Q1 ( next ) = s1+s2 = Q’1Q0 + Q1Q’0
D0 = Q0 ( next ) = s0Start + s2( Data 0 )’
= Q’1Q’0Start + Q1Q’0 ( Data 0 )
S1 =s2( Data 0 ) = Q1Q’0( Data 0 )
S0 = s1 + s2( Data 0 ) = Q’1Q0 + Q1Q’0( Data
E = s2DataLSB = Q1Q’0DataLSB
Load = s1 = Q’1Q0
Done = Output enable = s3= Q1Q0
0)
Input-based version
Copyright © 2004-2005 by Daniel D. Gajski
17
Slides by Xi Cheng, University of California, Irvine
Register-transfer synthesis
z Register sharing
Block diagram
s0
a = In 1
b = In 2
Start
s1
0
z Functional unit sharing
1
t1 = |a|
t2 = |b|
s2
x = max( t1 , t2 )
y = min ( t1 , t2 )
z Bus sharing
s3
t3 = x >> 3
t4 = y >>1
s4
t5 = x – t3
s5
t6 = t4 + t5
s6
t7 = max ( t6 , x )
s7
Done = 1
Out = t7
ASM Chart of Square-root approximation
Copyright © 2004-2005 by Daniel D. Gajski
18
Slides by Xi Cheng, University of California, Irvine
Resource usage in square-root
approximation
s1
Block diagram
s0
a = In 1
b = In 2
Start
s1
0
1
t1 = |a|
t2 = |b|
a
b
t1
t2
x
y
t3
t4
t5
t6
t7
X
X
No. of live
variables
2
s2
s3
s4
s5
s6
X
X
X
X
X
s7
X
X
X
X
X
X
X
X
2
2
3
3
2
1
Variable usage
s2
x = max( t1 , t2 )
y = min ( t1 , t2 )
s3
t3 = x >> 3
t4 = y >>1
s4
t5 = x – t3
s1
abs
s2
min
1
max
1
t6 = t4 + t5
s7
Done = 1
Out = t7
No. of
operations
1
s7
2
1
1
2
1
1
1
2
1
2
1
1
1
Operation usage
ASM Chart of Square-root approximation
Copyright © 2004-2005 by Daniel D. Gajski
s6
2
+
t7 = max ( t6 , x )
s5
1
-
s6
s4
2
>>
s5
s3
Max. no.
of units
19
Slides by Xi Cheng, University of California, Irvine
Simple library components
Sign bit
(a)
Absolute value unit
b
“0”
“0”
Subtractor
b
(version 1)
|b|
|b|
|b|
a
b
Subtractor
a
b
Subtractor
Sign bit
Sign bit
1
0
Selector
1
0
Selector
Min(a,b)
Max(a,b)
(c) Min unit
min/max
control
(e) Min/Max
unit
a
a
“0”
Shift
control
00 0
a>>1
>>1
>>3
1
0
Selector
a>>3
(f) 1-bit right shifter
Adder
a+b
(i) Adder
(g) 3-bit right shifter
a
b
Copyright © 2004-2005 by Daniel D. Gajski
1
0
Selector
min/max(a,b)
(d) Max unit
a
b
Subtractor
Sign bit
a
(version 2)
0
1
Selector
1
0
Selector
a
(b) Absolute value unit
Subtractor
Sign bit
0
b
Adder
add/sub a
control
0
a-b
a>>3/a>>1
(h) 1-bit/3-bit right shifter
b
Adder
a+b/a-b
(j) Subtractor
20
(k) Adder/Subtractor
Slides by Xi Cheng, University of California, Irvine
Connectivity requirements
Block diagram
a b t1 t2 x y t3 t4 t5 t6 t7
s0
a = In 1
b = In 2
Start
s1
abs1 1
0
1
t1 = |a|
t2 = |b|
s2
abs2
1
0
min
1 1 0
max
1 1 1 0
x = max( t1 , t2 )
y = min ( t1 , t2 )
>>3
t3 = x >> 3
t4 = y >>1
>>1
t5 = x – t3
-
s3
0
1
1 0
0
1
0
s4
s5
+
t6 = t4 + t5
1
1
0
1 1 0
s6
Connectivity table
t7 = max ( t6 , x )
s7
Done = 1
Out = t7
ASM Chart of Square-root approximation
Copyright © 2004-2005 by Daniel D. Gajski
21
Slides by Xi Cheng, University of California, Irvine
Register sharing (Variable merging)
z
Grouping of variables with nonoverlaping
lifetimes
z
Each group shares one register
z
Grouping reduces number of registers needed in
the design
z
Two algorithms:
Copyright © 2004-2005 by Daniel D. Gajski
left-edge
graph-partitioning
22
Slides by Xi Cheng, University of California, Irvine
Left-edge algorithm
Copyright © 2004-2005 by Daniel D. Gajski
23
Slides by Xi Cheng, University of California, Irvine
Register sharing by left-edge algorithm
s1 s2 s3 s4 s5 s6 s7
a
b
t1
t2
x
y
t3
t4
t5
t6
t7
X
X
R1 = {a, t1, x, t7}
R2 = {b, t2, y, t4, t6}
X
X
X
X
X
X
X
X
s0
a = In 1
b = In 2
R3 = {t2, t5 }
X
Start
Register assignments
X
s1
X
X
0
1
t1 = |a|
t2 = |b|
s2
X
x = max( t1 , t2 )
y = min ( t1 , t2 )
Sorted list of variables
s3
t3 = x >> 3
t4 = y >>1
s4
t5 = x – t3
s5
t6 = t4 + t5
s6
t7 = max ( t6 , x )
s7
Done = 1
Out = t7
ASM Chart
Datapath schematic
Copyright © 2004-2005 by Daniel D. Gajski
24
Slides by Xi Cheng, University of California, Irvine
Merging variables with common sources
and destination
a
si
x=a+b
c
b
Selector
d
Selector
+
sj
a,c
b,d
Selector
Selector
+
y=c+d
Partial ASM Chart
Copyright © 2004-2005 by Daniel D. Gajski
Selector
Selector
x
y
Datapath without register sharing
25
Selector
x,y
Datapath with register sharing
Slides by Xi Cheng, University of California, Irvine
