College Performance Data
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Copyright By PowCoder代写 加微信 powcoder
DEPARTMENT OR UNIT NAME.
DELETE FROM MASTER SLIDE IF
Department of Electrical & Computer Engineering
Digital Logic And Computing Systems
Chapter 07 – Control Path
EEL3701C Fall 2022
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Register-Transfer Level (RTL)
Transistors
Logic Circuits
Micro Architecture
(Register-Transfer Level)
Instruction set Architecture
Complex circuit components are
made from simple elements
Information is represented,
processed, transported, and
stored as words in registers.
Information flow from register to
register through combinational
→ Register-Transfer
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
❑ Basic Structure
❑ Controller Implementation
❑ Microprograming
❑ RTL Design Flow
❑ Design Example
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
❑ Complex digital systems usually consist of two parts
◼ A data path (ALU) performs computation on data
◼ A control path (control unit, controller) manages the system
o Data path and control path are connected through status and
control signals
o Data path and control path consists of sequential and
combinational components
Basic Structure: Data Path+Controller
Data Path Controller
Control Signals
Status Signals
lData Path
Controller
Controller
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Controller Implementation
❑ Controllers are modelled using automata theory
◼ Input variables X: k control inputs and n status signals
◼ Output variables Y: l control outputs and m control signals
◼ State variables S: control states.
◼ State transition function d (x,s)
◼ Output function m (s) (usually modelled after Moore)
Controller
Control Signals
Status Signals
Controller
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Controller Implementation
❑ Implementation Options
◼ “Hard-wired control“
o Automata design discussed in chapter 6, i.e. d (x,s) and m (s) are
realized as combinational logic
o Advantage: Fast
o Drawback: Not Flexible
◼ “Micro-programmable control“
o d (x,s) and m (s) are stored in memory
o Automata behavior can be changed through memory override
o Advantage: Flexible
o Drawback: Slow
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Microprogramming
Programmable
Control Memory
Microsequencer
State Register
Microinstruction
Instruction
❑ Basic Idea
◼ Current state and outputs are defined using microinstructions
◼ The microinstructions are stored in a microprogram memory (Control
Memory, CM)
◼ A microsequencer computes the address of the next microinstruction
using the inputs and the current state
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Microprogramming
❑ Important Questions
◼ How do we compute the next address?
◼ Which values do we store in microprogram memory?
◼ How do we generate output signals?
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Microprogramming
Programmable
Control Memory
Microsequencer
State Register
x1 … xn y1 … ym
si,1 … si,n yi,1 … yi,m
si,1 … si,n yi,1 … yi,m
❑ Option 1: CM stores the complete state transition table
◼ A row in the table corresponds to a microinstruction (i.e. next state
and outputs)
◼ The microsequencer selects the next state based on the input one of
the next states as address for the CM
◼ Advantage: most flexible, d (x,s) and m (s) (re)programmable
◼ Drawback: CM can be very large and very slow
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Microprogramming
Microprogrammed Controller
State Transition Table
01 S1 S200
00 S1 S110
00 S0 S011
0 1 y1 y0
0 1 1 0 0 1
0 0 1 1 1 0
0 1 0 1 0 0
0 0 0 0 0 0
. . . . . .
0 0 1 1 1 00 0
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
❑ In general, the number of possible next states is very small
◼ In particular, processor instructions are executed sequentially
→ the next instruction address is the current address + 1
◼ Possible structure of the microinstructions
Computing the Next Address
y1 y2 …….. ymBADRCOND
Control Signals
Target Address: address of the next
microinstruction, if COND is ‘1’.
Otherwise increment address
(Address+1)
Condition: select one of the
inputs (external conditions)
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Computing the Next Address
Option 2: CM store COND, BADR and output signals
o The microsequencer consists of 2 components
1. Microprogram Counter: computes addresses for the CM
▪ The microprogram counter is incremented with positive clock edge
▪ LDBADR (load branch address) = 1: the address of the next microinstruction is
loaded in the microprogram counter
▪ LDSADR (load start address) = 1: the start address SADR is loaded in the
microprogram counter
▪ Microprogram memory in processors store microprograms
2. MUX, uses COND as selector for the inputs
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Microprogramming
CMMicroprogram
CM Data Register
y1 y2 ……….. ymCOND BADR
n-way, 1-bit
condition select
branch address
conditions
start address
add T0, 0, 0
addi T1, 0, 10
bge T0, T1, BCH # IF (T0 >= T1) GOTO BCH
addi T0, T0, 1 #i++
BCH: add T0, T1, T0
bge T0, T1 (False)
bge T0, T1 (TRUE)
add T0, 0, 0
addi T1, 0, 10
bge T0, T1, BCH # IF (T0 >= T1) GOTO BCH
addi T0, T0, 1 #i++
BCH: add T0, T1, T0
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Generating Output Signals
Control Signals
“Control fields”
❑ Horizontal microprogramming
◼ 1 bit is used for each output signal (a control field) in CMDR
→ “horizontal” microprogramming
◼ Advantage: maximal parallelism in data path
o All control signals can be set independently
◼ Drawback: wide microinstruction → large control memory (CM)
o Combination of output signals are sometime possible
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Generating Output Signals
Control Lines
Single control field
❑ Vertical microprogramming
◼ Only one control field (with bit) is stored
o The value in the field corresponds to the binary coding of the
signal that must be set
→ “vertical” microprogramming
◼ Advantage: small control memory (CM)
◼ Drawback: only one signal can be set at a time; Slow; No parallelism
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Generating Output Signals
Control Lines
Control fields
❑ Diagonal microprogramming
◼ Control signals that can/must not be simultaneously active are
grouped in a control field and binary coded
→ “diagonal” or “zoned” microprogramming
◼ The number of fields defines the level of parallelism
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Microprogramming
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
❑ Systematic mapping of (sequential) algorithms in a digital circuit
RTL Design Flow
Data Path Controller
Control Signals
Status Signals
Multiplication Algorithm:
1. Load operand registers X,Y
2. C← 0, P← 0
3. repeat n-times:
if Y(0)=1 then
shift (C,P,Y) right
4. Result is in (P,Y)
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
RTL Design Flow
❑ Possible Approach
◼ Data Path
o Identify the components of the circuits (Objects)
o Define the connections among the various units
o Define operations : for each method 1 control signal
o Define conditions: for each status signal 1 status signal
◼ Controller
o Define 1 state for each sequential step
o For each state: define next state and control signals
o Implement controller “hardwired” or microprogrammed
◼ In practice, we use computer aided design (CAD) tools (HDL)
o Modelling in textual and graphical language
o Model simulation
o (Semi) automatic design
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Design Example I – gcd(a,b)
To simplify, operand, inputs, and result output
not included in the diagram
❑ Greatest Common Divisor – gcd(a,b)
◼ A circuit to compute the gcd of two 8-bit unsigned integer A and B
◼ Interface signals: START, DONE, CLK, RST
◼ Behavior:
o Processing begins when START=1
o Computation completed when DONE=1
Data Path Controller
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
gcd(a,b) – Algorithm
Idea for the gcd(a,b) – algorithm:
gcd(a,b) = a, if a = b
= gcd(a-b, b), if a > b
= gcd(a, b-a), if a < b done = FALSE; elseif (b>a)
else done = TRUE;
until done;
What components are needed for the data path ?
o Register for a and b
o Comparator: to compute a>b, a
else done = TRUE;
until done;
Register A
Subtractor
Comparator
Register B
SELL SELR0 01 1
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
gcd(a,b) – Timing
Assumption:
o A=6, B=4
o Use of positive edge-triggered D-FF
After setting control signals, the controller always waits 1 clock
cycle for the correct status signals to be available
S0 S1 S2 S1 S3 S1 S4 S0 S0
6 6 6 2 2 2 2 2 2A
4 4 4 4 4 2 2 2 2B
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Design Example II – SeqAdd(a,b)
❑ Design of an 8-bit sequential adder for unsigned integer numbers: C=A+B
◼ Interface signals: IBUS, OBUS, START, DONE, CLK, RST
◼ Behavior:
o START=1 start of the addition. A and B are placed on the input bus, IBUS, sequentially,
after each clock cycle.
o Operation completed: DONE=1, result is placed on the output bus, OBUS
Sequential
Data Path Controller
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
SeqAdd(a,b) – Algorithm, Data Path
Algorithms
1. Wait until START=1
2. A ← IBUS, Cin ← 0
3. B ← IBUS
4. for i=0..7:
5. A(0) ← sum(A(0),B(0),Cin),
Cin ← carry(A(0),B(0),Cin)
6. rotate A and B left
7. Result is in A and on OBUS
i (2 : 0)sum
A (7 : 0) B (7 : 0)
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
SeqAdd(a,b) – Data Path-Components
Components Control Signals/Status Signals
Register A: 8-bit Register
parallel load A(7:0) ALD
load A(0) A0LD
rotate left A(7:0) RT
MUX: 2-times, 1-bit Multiplexer ASRC
Register B: 8-bit Register
parallel load B(7:0) BLD
rotate right B(7:0) RT
+: Full Adder
Cin: 1-bit Register
load Cin CLD
MUX: 2-times, 1-bit Multiplexer CSRC
i: Loop counter (3-bit Register, mod-8 counter)
set i(2:0) to 0 iSET
increment i(2:0) CNTUP
loop counter = 7 iEQ7
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
SeqAdd(a,b) – Control/Status Signals
i (2 : 0)iEQ7 sum
A (7 : 0) B (7 : 0)
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
SeqAdd(a,b) – Controller
Interface Definition:
Data Path Controller
DONEOBUS 8
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
SeqAdd(a,b) – Controller State Transition:
– only outputs that are set to 1 are shown in the diagram
– Optimization:
A0LD=CSRC=CNTUP=ASRC
CLD=ASRC+ALD
→ The number of control signals can be reduced to 4
START TRUE
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
SeqAdd(a,b) – Timing
State S0 S1 S2S0 S3 S4 S3 S4 S3 S4 S3 S4 S3 S4 S3 S4
S3 S4 S3 S4
ASRC, A0LD, CSRC, CNTUP
i 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7
START TRUE
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
SeqAdd(a,b) – Controller
Transition Table
S0 = ”000”, S1 = “001”, S2 = “010”, S3 = “011”, S4 = “100”, S5 = “101”
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
SeqAdd(a,b) – Microprogrammed Control
CMMicroprogram Counter
ALD ASRC BLD RT DONECOND BADR
4-times, 1-bit
Condition Selector Branch Address
000 01 000 0 0 0 0 0
001 00 xxx 1 0 0 0 0
010 00 xxx 0 0 1 0 0
011 00 xxx 0 1 0 0 0
100 10 011 0 0 0 1 0
101 11 000 0 0 0 0 1
SADR ”
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com