1
Processor Data Path and Control
CIT 595
Spring 2007
7 - 2CIT 595
What Do We Know?
Already discovered:
• Gates (AND, OR..)
• Combinational logic circuits (decoders, mux)
• Memory (latches, flip-flops)
• Sequential logic circuits (state machines)
• Simple processors (programmable traffic sign)
What’s next?
• Apply all this to build a working processor
7 - 3CIT 595
Von Neumann Model
MEMORY
MAR MDR
INPUT
Keyboard
Mouse
Scanner
Disk
OUTPUT
Monitor
Printer
LED
Disk
PROCESSING UNIT
ALU TEMP
CONTROL UNIT
PC IR
7 - 4CIT 595
LC-3 Processor Von Nuemann Model
CONTROL
UNIT
2
7 - 5CIT 595
LC-3 Data Path
Filled arrow
= info to be processed.
Unfilled arrow
= control signal.
The data path of a
computer is all the
logic used to process
information
CONTROL
UNIT
7 - 6CIT 595
One More Device
Tri-state buffer
• NOT an inverter!
• Device with a special output that can take a third state (i.e.
besides 0 and 1)
Allows wires to be “shared”
• Alternative to mux
• Only one source may drive at a time!
• Usually used to control data over a bus
D Q
E
Z10
Z00
111
001
QDE
Z = “high impedance” state
7 - 7CIT 595
Data Path Components
Global bus
• Set of wires that carry 16-bit signals to many components
• Inputs to bus are controlled by triangle structure called tri-state
devices
Place signal on bus when enabled
Only one (16-bit) signal should be enabled at a time
Control unit decides which signal “drives” the bus
• Any number of components can read bus
Register only captures bus data if write-enabled by the control
unit
Memory and I/O
• Control signals and data registers for memory and I/O devices
• Memory: MAR, MDR (also control signal for read/write)
• Input (keyboard): KBSR, KBDR
• Output (text display): DSR, DDR
7 - 8CIT 595
LC-3 Data Path
Filled arrow = info to be processed. Unfilled arrow = control signal.
CONTROL
UNIT
3
7 - 9CIT 595
Data Path Components (cont.)
ALU
• Input: register file or sign-extended bits from IR (immediate field)
• Output: bus; used by…
Condition code registers
Register file
Memory and I/O registers
Register File
• Two read addresses, one write address (3 bits each)
• Input: 16 bits from bus
Result of ALU operation or memory (or I/O) read
• Outputs: two 16-bit
Used by ALU, PC, memory address
Data for store instructions passes through ALU
7 - 10CIT 595
Data Path Components (contd..)
PC and PCMUX
• Three inputs to PC, controlled by PCMUX
1. Current PC plus 1 (normal operation)
2. Adder output (BR, JMP, …)
3. Bus (TRAP)
MAR and MARMUX
• Some inputs to MAR, controlled by MARMUX
1. Zero-extended IR[7:0] (used for TRAP; more later)
2. Adder output (LD, ST, …)
7 - 11CIT 595
Data Path Components (cont..)
Condition Code Logic
• Looks at value (from ALU) on bus and generates N, Z, P signals
• N,Z,P Registers are set only when control unit enables them
Control Unit
• For each stage in instruction processing decides:
Who drives the bus?
Which registers are write enabled?
Which operation should ALU perform?
Lets Look at Instruction Processing next..
7 - 12CIT 595
Instructions
Fundamental unit of work
Constituents
• Opcode: operation to be performed
• Operands: data/locations to be used for operation
Encoded as a sequence of bits (just like data!)
• Sometimes have a fixed length (e.g., 16 or 32 bits)
• Atomic: operation is either executed completely, or not at all
4
7 - 13CIT 595
Instruction Processing
DECODE instructionDECODE instruction
EVALUATE ADDRESSEVALUATE ADDRESS
FETCH OPERANDSFETCH OPERANDS
EXECUTE operationEXECUTE operation
STORE resultSTORE result
FETCH instruction from mem.FETCH instruction from mem.
7 - 14CIT 595
Instruction Processing: FETCH
Idea
• Put next instruction in IR & increment PC
Steps
• Load contents of PC into MAR
• Increment PC
• Send “read” signal to memory
• Read contents of MDR, store in IR
EAEA
OPOP
EXEX
SS
FF
DD
7 - 15CIT 595
FETCH in LC-3
Load PC into MAR (inc PC)
Control
Data
CONTROL
UNIT
7 - 16CIT 595
FETCH in LC-3
Load PC into MAR
Read Memory
Control
Data
CONTROL
UNIT
5
7 - 17CIT 595
FETCH in LC-3
Load PC into MAR
Read Memory
Copy MDR into IR
Control
Data
CONTROL
UNIT
7 - 18CIT 595
Instruction Processing: DECODE
Identify opcode
• In LC-3, always first four bits of instruction
• 4-to-16 decoder asserts control line corresponding
to desired opcode
Identify operands from the remaining bits
• Depends on opcode
e.g., for LDR, last six bits give offset
e.g., for ADD, last three bits name source operand #2
EAEA
OPOP
EXEX
SS
FF
DD
7 - 19CIT 595
DECODE in LC-3
CONTROL
UNIT
Decoding usually
a part of the
Control Unit but
can be seperate
7 - 20CIT 595
Instruction Processing: EVALUATE ADDRESS
Compute address
• For loads and stores
• For control-flow instructions
Examples
• Add offset to base register (as in LDR)
• Add offset to PC (as in LD and BR) EAEA
OPOP
EXEX
SS
FF
DD
6
7 - 21CIT 595
EVALUATE ADDRESS in LC-3
Load/Store
CONTROL
UNIT
7 - 22CIT 595
Instruction Processing: FETCH OPERANDS
Get source operands for operation
Examples
• Read data from register file (ADD)
• Load data from memory (LDR)
EAEA
OPOP
EXEX
SS
FF
DD
7 - 23CIT 595
FETCH OPERANDS in LC-3
ADD
CONTROL
UNIT
7 - 24CIT 595
FETCH OPERANDS in LC-3
LDR
CONTROL
UNIT
7
7 - 25CIT 595
Instruction Processing: EXECUTE
Actually perform operation
Examples
• Send operands to ALU and assert ADD signal
• Do nothing (e.g., for loads and stores)
EAEA
OPOP
EXEX
SS
FF
DD
7 - 26CIT 595
EXECUTE in LC-3
ADD
CONTROL
UNIT
7 - 27CIT 595
Instruction Processing: STORE
Write results to destination
• Register or memory
Examples
• Result of ADD is placed in destination reg.
• Result of load instruction placed in destination reg.
• For store instruction, place data in memory
Set MDR
Assert WRITE signal to memory
EAEA
OPOP
EXEX
SS
FF
DD
7 - 28CIT 595
STORE in LC-3
ADD
CONTROL
UNIT
8
7 - 29CIT 595
STORE in LC-3
LDR
CONTROL
UNIT
7 - 30CIT 595
STORE in LC-3
STORE
Set MDR
CONTROL
UNIT
7 - 31CIT 595
STORE in LC-3
STORE
Set MDR
Assert “write”
CONTROL
UNIT
7 - 32CIT 595
Time to Complete One Instruction
• It takes fixed number of clock ticks (repetition of rising
or falling edge) to execute each instruction
The time interval between ticks is known as clock cycle
Thus instruction performance is measured in clock cycles
• Hence the clock sequences each phase of an
instruction by raising the right signals as the right time
• So what determines the time between ticks i.e. the
length of the clock cycle?
9
7 - 33CIT 595
Clocking Methodology
• Defines when signals can be read and when they can be written
• It is important to specify the timing of reads and writes because, if
a value is written at the same time it is read, the value of read could
be old, new or mix of both
• All values are stored on clock edge (edge-triggered) i.e. within a
defined interval of time (length of the clock cycle)
• In a processor, since only memory elements can store values this
means that
Any collection of combinational logic must have its inputs coming from
a set of memory elements and its outputs written into a set of memory
elements
7 - 34CIT 595
Clocking Methodology (contd..)
• The length of the clock cycle is determined as follows:
• The time necessary for the signals to reach memory
element 2 defines the length of the clock cycle
i.e. minimum clock cycle time must be at least as great as the
maximum propagation delay of the circuit
7 - 35CIT 595
How does the control unit work ?
Two approaches:
• Hardwired Control
• Microprogrammed Control
7 - 36CIT 595
Approach I: Hardwired Control
Hardwired Control
Directly connects the control lines
to actual machine instructions
The instructions are divided into
fields, and bits in the fields are
connected to input lines that drives
the various digital logic components
The control signals are some
combination of the instruction bit
plus other signals such as
interrupts, or condition codes from
previous instruction
10
7 - 37CIT 595
LC3 as Hardwired Control Implementation
The Control Signals (red colored lines) are outputs by some
combination of inputs from the instruction bit fields
Decoder
7 - 38CIT 595
ADD Instruction
101000001I[11:9]I[2:0]I[8:6]00001ADD
I[5]I[15:12]Instr
ControlOpcode
7 - 39CIT 595
Sequencing the Stages in Hardwired Implementation
• The combination Control Unit set all the control lines
needed by an instruction
• How do we ensure that we sequence through
Instruction cycle i.e. F->D->EA->OP->EX->S?
• We connect the clock to a synchronous counter and the
counter to the decoder
• The decoder output enabled is based on counter outputs (i.e.
which cycle you are in)
• The decoder output is then used as enable signal (gating) to
enable only certain control signals during a particular cycle
• Note: the diagram does not show sequencing logic to avoid
cluttering the diagram
7 - 40CIT 595
Sequencing Instruction Stages in Hardwired
Implementation (contd..)
Example:
• Suppose the max. number of cycles an instruction takes is 8
• Then we would have 3-bit counter whose outputs are fed into
3 x 8 decoder
• The output of the decoder, T0 to T7 are enable based on
count i.e.
T0 = 1 when count = 000 (cycle 0), all others are disabled
…
T7 = 1 when count = 111(cycle 7), all others are disabled
• The decoder output that is enabled used to define the
behavior in a particular cycle
• If < 8 clock cycles are required by another instr., then the
counter is reset back to 0 (so the next instruction can properly
function as well)
11
7 - 41CIT 595
Hardwire Control with Timing (Sequencing) Control
7 - 42CIT 595
JMP Instruction
0x1000100--I[8:6]-1100JMP
I[5]I[15:12]Instr
ControlOpcode
7 - 43CIT 595
LDR Instruction
100000101I[11:9]-I[8:6]-0110LDR
I[5]I[15:12]Instr
ControlOpcode
BaseR DR 7 - 44CIT 595
TRAP
010001xx1111---1111TRAP
I[5]I[15:12]Instr
ControlOpcode
12
7 - 45CIT 595
Implementation Diagram is not complete
What about AND? NOT? BR? What changes would you
make?
7 - 46CIT 595
Approach II: Microprogrammed Control
• In microprogrammed control, each machine instruction is in
turn implemented by a series of microinstructions
• Machine instructions are the input for a microprogram that
converts the 1s and 0s of an instruction into control signals
• The microinstructions are often stored in firmware or read
only memory, which is also called the control store
• Microprogram is also known as Microcode in some literature
• Microprogram Control is essentially a Finite State Machine
7 - 47CIT 595
Microprogrammed Control is a FSM
State Machine
Combinational
Logic Circuit
Storage
Elements
Inputs Outputs
State
Nextstate
Currentstate
PC,IR, etc.. Control signals
7 - 48CIT 595
LC3 Microprogrammed Control: State Diagram
Finite state machine
• Input: PC, IR, etc..
• Output: many control signals
Need to map abstract ops
to control signals
• E.g., MAR <- PC
⇒ GatePC and LD.MAR
• E.g., PC <- PC + 1
⇒ PCMUX=2 and LD.PC
If in state 1, then the microInstruction
for state 1 will
enocode information for GatePC,
LD.MAR, PCMUX, LD.PC and
next state as state 2
13
7 - 49CIT 595
LC3 Implemented using Microprogram Control
• The behavior of LC-3 during a given clock
cycle is completely described by the 49 bit
microinstruction
• 39 control signals to assert datapath
components
• 10 signals + 9 other to determine the
control signals for the next clock cycle
• Each phase of instruction cycle may
require more than one microinstruction
• Hence a microinstruction is retrieved
during each clock cycle
Microprogram Control
7 - 50CIT 595
LC3 Implemented using Microprogram Control (contd..)
• All possible processor behavior (state) is
stored into memory called Control Store
• i.e. each location stores one microinstruction
• There are 52 possible microinstructions
(states) that can describe LC3’s behavior
• Hence need a 6-bit address to lookup the
control store
• The microsequencer produces the 6 bit
address from combination of 10 bits of
Microinstruction + 9 bit additional info,
which will correspond to the next behavior
of the processor
Microprogram Control
7 - 51CIT 595
Big Picture: LC3 as Microprogrammed Control
7 - 52CIT 595
R
R R
R R
PC<–BaseR
20
To 18
PC<–BaseR
R7<–PC
[IR[11]]
1 0
12
4
PC<–PC+off11
21
To 18
To 18
To 18
To 18
To 18
To 8
(See Figure C.7)
RTI
MAR <–PC
PC<–PC+1
[INT]
MDR<–M
IR<–MDR
R
DR<–SR1+OP2*
set CC
DR<–SR1&OP2*
set CC
[BEN]
PC<–PC+off9
PC<–MDR
MAR<–PC+off9
MDR<–M[MAR ]
RR
MAR<–MDR
MAR<–PC+off9
MDR<–M[MAR]
MAR<–MDR
MAR<–B+off6
MAR<–PC+off9
MAR<–B+off6
MAR<–PC+off9
MDR<–SR
DR<–MDR
set CC
M[MAR]<–MDR
18
32
1
5
76
11
3
0
0
1
22
29
3126
23
24
25
27
To 18
To 18
To 18 To 18
To 18
0
R R
MDR<–M[MAR]
To 49
(See Figure C.7)
28
30
2
10
NOTES
16
MDR<–M[MAR]
R7<–PC
B+off6 : Base + SEXT[offset6]
PC+off9 : PC + SEXT{offset9]
PC+off11 : PC + SEXT[offset11]
*OP2 may be SR2 or SEXT[imm5]
DR<–NOT(SR)
set CC
9
NOT
14
DR<–PC+off9
set CC
LEA LD LDR LDI STI STR ST
JSR
ADD
AND
JMP
BR
1
RR
BEN<–IR[11] & N + IR[10] & Z + IR[9] & P
[IR[15:12]]
1101
To 13
33
35
MAR<–ZEXT[IR[7:0]]
15
TRAP
Appendix C of Patt
& Patel Fig C.2
14
7 - 53CIT 595
LC3 Microprogram: Control Signals for Current State
0IR[11:9]
0
(ADD)IR[8:6]IR[5]XX0011001001
0XXXX
0
(PC + 1)X10001001018
R.WDRALUKSR1SR2PCMARMAR
I
R
C
CREGPCMDRALUPCMARMX
MISCMUXLDGATE
CURR
STATE
The table above provides the control signal values (some of the 39
signals) for two states (18, 1)
State 18: Is performing part of the FETCH stage
State 1: Is performing stages OP-EX-STORE for ADD inst
Note:
• Assume all Register and Memory Read/Write signal are set 0 unless
in case of write (i.e. set to 1)
• Also there is no need of timing circuit like in hardwired control, as
each signal behavior is defined for every clock cycle
MEM
EN
0
0
7 - 54CIT 595
LC3 Microprogram: Next State
Depends on:
• 10 bits of current microinstruction
• J (6-bits): encodes the next state (mostly likely states of the
possible next states)
• COND (3-bits): field indicates special tests that must occur to
compute the true next state
0 – Unconditional (that next state is the encoded state)
1 – Memory Read
2 – Branch
3 – Addressing Mode (for JSR and JSRR instructions)
5 – Interrupt Test
• IRD (1-bit) : If set to IRD = 1, ignore J and COND. This only
happens in state 32 and as we want to use the bits from the IR
to select the next state
7 - 55CIT 595
LC3 Microprogram: Next State (contd..)
Depends on (contd..):
• INT: To indicate interrupt from another program or
device, Only tested if in state 18 (because that is before
the start of an instruction cycle)
• R: indicate the end of memory operation
• IR[15:11]: current opcode
• PSR[15]: processor executing in supervisor or user
mode
• BEN: indicates whether or not a branch should be
taken
7 - 56CIT 595
LC3 Next State Example
0-1510032
1800181
33,49053318
POSSIBLE
NEXT STATE
(depends
also on 9
other Bits)IRDCONDJ
CURR
STATE
• State 18: Most likely next state is 33 but need to
check for INT (COND = 5). If INT = 1, Next State = 49
• State 1: Next State is just 18 (this because you are
done finishing ADD instr and want to start a new instr.
Cycle)
• State 32: J and COND ignored as IRD = 1, 0 – 15
are your next possible states
15
7 - 57CIT 595
Generic Microprogram Control
This further logic
may not be needed
7 - 58CIT 595
LC3 Processor
Implemented as
Microprogram
Control
7 - 59CIT 595
Hardwired vs. Microprogrammed
Complexity
• There is an extra level of instruction interpretation in
microprogrammed control, which makes it slower than
hardwired control
Flexibility
• Instruction and Control Logic are tied together in
hardwired control, which makes it difficult to modify
• New instructions can be easily added by only making
changes to the microprogram in microprogrammed
control implementation