Chapter 8 CPU
CPU
Register File
CU
ALU
General Register Organization
Input
R1
R2
R3
R4
R5
R6
R7
LD SELA MUX MUX SELB
3x8 A B
Decoder
OPR
ALU
SELD
General Register Organization
OPR Operation R1
Input
00000 Transfer A R2
00001 Increment A R3
00010 Add A + B R4
00101 Subtract A − B R5
R6
00110 Decrement A R7
01000 AND A and B
01010 OR A and B LD SELA MUX MUX SELB
01100 XOR A and B 3x8 A B
01110 Complement A Decoder
10000 Shift right A OPR
ALU
11000 Shift left A SELD
Examples: Microoperation SELA SELB SELD OPR
R1 ← R2 − R3 010 011 001 00101
R4 ← SHL R4 100 000 100 11000
Stack Organization-Register Stack
• LIFO Current
Top of Stack
Last In First Out TOS 63
.
.
7
6
5
SP 4 0 1 2 3
3 0 0 5 5
FULL EMPTY 2 0 0 0 8
1 0 0 2 5
Stack Bottom 0
Stack
Stack Organization
• PUSH Current 1 6 9 0
SP ← SP + 1 Top of Stack
TOS 10
M[SP] ← DR 9
If (SP = 0) then (FULL ← 1) 8
7
EMPTY ← 0 6
5 1 6 9 0
SP 4 0 1 2 3
3 0 0 5 5
FULL EMPTY 2 0 0 0 8
1 0 0 2 5
Stack Bottom 0
Stack
Stack Organization
• POP Current
DR ← M[SP] Top of Stack
TOS 63
SP ← SP - 1 .
If (SP = 0) then (EMPTY ← 1) .
7
FULL ← 0 6
5 1 6 9 0
SP 4 0 1 2 3
3 0 0 5 5
FULL EMPTY 2 0 0 0 8
1 0 0 2 5
Stack Bottom 0
Stack
Stack Organization
• Memory Stack
– PUSH PC 0
1
SP ← SP + 1 2
M[SP] ← DR
– POP AR 100
DR ← M[SP] 101
SP ← SP - 1 102
200
SP 201
202
Reverse Polish Notation
• Infix Notation
A+B
• Prefix or Polish Notation
+AB
• Postfix or Reverse Polish Notation (RPN)
AB+
(2) (4) (3) (3) +
RPN (8) (3) (3) +
AB+CD ABCD+ (8) (9) +
17
Reverse Polish Notation
• Example
(A + B) [C (D + E) + F]
(A B +) (D E +) C F +
Postfix Expression Evaluation
1. Scan the expression from left to right.
2. When an operator is reached, perform the operation with the
two operands found on the left side of the operator.
3. Replace the two operands and the operator by the result
obtained from the operation.
(Example)
infix
3 * 4 + 5 * 6 = 42
postfix
34*56*+
12 5 6 * +
12 30 +
42
Reverse Polish Notation
• Stack Operation
(3) (4) (5) (6) +
PUSH 3
PUSH 4
MULT 6
PUSH 5
PUSH 6 4
5
30
MULT
ADD 3
12
42
CPU Organization
• Single Accumulator
– Result usually goes to the Accumulator
– Accumulator has to be saved to memory quite often
• General Register
– Registers hold operands thus reduce memory traffic
– Register bookkeeping
• Stack
– Operands and result are always in the stack
Instruction Formats
• Three-Address Instructions
– ADD R1, R2, R3 R1 ← R2 + R3
• Two-Address Instructions
– ADD R1, R2R1 ← R1 + R2
• One-Address Instructions
– ADD M AC ← AC + M[AR]
• Zero-Address Instructions
– ADD TOS ← TOS + (TOS – 1)
• RISC Instructions
– Lots of registers. Memory is restricted to Load & Store
Opcode Operand(s) or Address(es)
Instruction Formats
Example: Evaluate (A+B) (C+D)
• Three-Address
1. ADD R1, A, B ; R1 ← M[A] +
M[B]
2. ADD R2, C, D ; R2 ← M[C] +
M[D]
3. MUL X, R1, R2 ; M[X] ← R1
R2
Instruction Formats
Example: Evaluate (A+B) (C+D)
• Two-Address
1. MOV R1, A ; R1 ← M[A]
2. ADD R1, B ; R1 ← R1 +
M[B]
3. MOV R2, C ; R2 ← M[C]
4. ADD R2, D ; R2 ← R2 +
M[D]
5. MUL R1, R2 ; R1 ← R1
R2
6. MOV X, R1 ; M[X] ← R1
Instruction Formats
Example: Evaluate (A+B) (C+D)
• One-Address
1. LOAD A ; AC ← M[A]
2. ADD B ; AC ← AC +
M[B]
3. STORE T ; M[T] ← AC
4. LOAD C ; AC ← M[C]
5. ADD D ; AC ← AC +
M[D]
6. MUL T ; AC ← AC
M[T]
Instruction Formats
Example: Evaluate (A+B) (C+D)
• Zero-Address
1. PUSH A ; TOS ← A
2. PUSH B ; TOS ← B
3. ADD ; TOS ← (A +
B)
4. PUSH C ; TOS ← C
5. PUSH D ; TOS ← D
6. ADD ; TOS ← (C +
D)
7. MUL ; TOS ←
Instruction Formats
Example: Evaluate (A+B) (C+D)
• RISC
1. LOAD R1, A ; R1 ← M[A]
2. LOAD R2, B ; R2 ← M[B]
3. LOAD R3, C ; R3 ← M[C]
4. LOAD R4, D ; R4 ← M[D]
5. ADD R1, R1, R2 ; R1 ← R1 +
R2
6. ADD R3, R3, R4 ; R3 ← R3 +
R4
7. MUL R1, R1, R3 ; R1 ← R1
Addressing Modes
• Implied Opcode Mode ...
– AC is implied in “ADD M[AR]” in “One-Address”
instr.
– TOS is implied in “ADD” in “Zero-Address” instr.
• Immediate
– The use of a constant in “MOV R1, 5”, i.e. R1 ← 5
• Register
– Indicate which register holds the operand
Addressing Modes
• Register Indirect
– Indicate the register that holds the number of the
register that holds the operand
MOV R1, (R2) R1
• Autoincrement / Autodecrement R2 = 3
– Access & update in 1 instr.
R3 = 5
• Direct Address
– Use the given address to access a memory location
Addressing Modes
• Indirect Address
– Indicate the memory location that holds the address of
the memory location that holds the data
AR = 101
100
101 0 1 0 4
102
103
104 1 1 0 A
Addressing Modes
• Relative Address
– EA = PC + Relative Addr 0
1
PC = 2 2
100
AR = 100
101
102 1 1 0 A
Could be Positive or 103
Negative 104
(2’s Complement)
Addressing Modes
• Indexed
– EA = Index Register + Relative Addr
Useful with XR = 2
“Autoincrement” or
“Autodecrement”
+
100
AR = 100
101
Could be Positive or
Negative 102 1 1 0 A
(2’s Complement) 103
104
Addressing Modes
• Base Register
– EA = Base Register + Relative Addr
Could be Positive or AR = 2
Negative
(2’s Complement)
+
100 0 0 0 5
BR = 100
101 0 0 1 2
102 0 0 0 A
Usually points to 103 0 1 0 7
the beginning of an 104 0 0 5 9
array
Types of Instructions
• Data Transfer Instructions
Name Mnemonic
Data value is not
Load LD modified
Store ST
Move MOV
Exchange XCH
Input IN
Output OUT
Push PUSH
Pop POP
• Data Manipulation Instructions
• Program Control Instructions
Data Transfer Instructions
Mode Assembly Register Transfer
Direct address LD ADR AC ← M[ADR]
Indirect address LD @ADR AC ← M[M[ADR]]
Relative address LD $ADR AC ← M[PC+ADR]
Immediate operand LD #NBR AC ← NBR
Index addressing LD ADR(X) AC ← M[ADR+XR]
Register LD R1 AC ← R1
Register indirect LD (R1) AC ← M[R1]
Autoincrement LD (R1)+ AC ← M[R1], R1 ← R1+1
Data Manipulation Instructions
Name Mnemonic
• Arithmetic Increment INC
Decrement DEC
• Logical & Bit Manipulation Add ADD
Subtract SUB
• Shift Multiply
Divide
MUL
DIV
Add with carry ADDC
Subtract with borrow SUBB
Name Mnemonic Negate NEG
Clear CLR
Complement COM Name Mnemonic
AND AND Logical shift right SHR
OR OR Logical shift left SHL
Exclusive-OR XOR Arithmetic shift right SHRA
Clear carry CLRC Arithmetic shift left SHLA
Set carry SETC Rotate right ROR
Complement carry COMC Rotate left ROL
Enable interrupt EI Rotate right through carry RORC
Disable interrupt DI Rotate left through carry ROLC
Program Control Instructions
Name Mnemonic
Branch BR
Jump JMP
Skip SKP
Subtract A – B but don’t
Call CALL store the result
Return RET
Compare (Subtract) CMP
10110001
Test (AND) TST
00001000
Mask
00000000
Status Bits
Cn-1
A B
Cn ALU
F
V Z S C
Fn-1
Zero Check
Conditional Branch Instructions
Mnemonic Branch Condition Tested Condition
BZ Branch if zero Z=1
BNZ Branch if not zero Z=0
BC Branch if carry C=1
BNC Branch if no carry C=0
BP Branch if plus S=0
BM Branch if minus S=1
BV Branch if overflow V=1
BNV Branch if no overflow V=0
Conditional Branch Instructions
• Example:
– A: 1 1 1 1 0 0 0 0 A: 11110000
– B: 0 0 0 1 0 1 0 0 +(−B): 1 1 1 0 1 1 0 0
11011100
C=1 Z=0
S=1
V=0
Program Interrupts
• Save:
– PC Main Program
– Registers •
• rupt
e r
– Status Bits • Int
•
ISR
10 CMA
•
11 •
Load AC
12 STA [201]
•
•
Program Status •
•
Word RET
•
PSW
•
•
Types of Interrupts
• External Interrupts
– Keyboard, Mouse … etc
• Internal Interrupts
– Timers, Divide-By-Zero … etc
• Software Interrupts
Main Program
•
• ISR
• •
• •
10 INT •
11 • •
• RET
•
CISC
• Complex Instruction Set Computer
– Large number of instructions with a complicated ALU
– Some instructions perform specialized tasks and are
used infrequently
– Large variety of addressing modes
– Variable length instruction formats
– Instructions can manipulate operands in memory
RISC
• Reduced Instruction Set Computer
– Relatively few instructions, hence simple ALU
– Relatively few addressing modes
– Memory access limited to “load” and “store”
– All operations done within “registers” of the CPU
– Fixed-length and easily decoded instruction format
– Single-cycle instruction execution
– Hardwired control unit
Homework
Chapter 8
• 8-1
• 8-3
• 8-7
• 8-8
• 8-9
• 8-11
• 8-13
• 8-14
• 8-15
• 8-16
• 8-17
• 8-18
• 8-32
Homework
• Mano
8-1 A bus-organized CPU has 16 registers with 32 bits in
each, an ALU, and a destination decoder.
a. How many multiplexers are there in the A bus, and
what is the size of each multiplexer?
b. How many selection inputs are needed for MUX A
and MUX B?
c. How many inputs and outputs are there in the decoder?
d. How many inputs and outputs are there in the ALU
for data, including input and output carries?
e. Formulate a control word for the system assuming
that the ALU has 35 operations.
Homework
8-3 Specify the control word that must be applied to the
processor of Fig. 8-2 to implement the following
microoperations.
a. R1 ← R2 + R3
b. R4 ← R4
c. R5 ← R5 – 1
d. R6 ← shl R1
e. R7 ← input
Homework
8-7 Convert the following arithmetic expressions from infix to
reverse Polish notation.
a. A B + C D + E F
b. A B + A (B D + C E)
c. A + B [C D + E (F + G)]
A * [B + C (D + E)]
d. ─────────────
F (G + H)
Homework
8-5 Convert the following arithmetic expressions from reverse
Polish notation to infix notation.
a. A B C D E + − /
b. A B C D E / − +
c. A B C / D − E F / +
d. A B C D E F G + + +
8-9 Convert the following numerical arithmetic expression
into reverse Polish notation and show the stack operations
for evaluating the numerical result.
(3 + 4) [10 (2 + 6) + 8]
Homework
8-11 A computer has 32-bit instructions and 12-bit addresses.
If there are 250 two-address instructions, how many one-
address instructions can be formulated?
8-13 The memory unit of a computer has 256K words of 32
bits each. The computer has an instruction format with
four fields: an operation code field, a mode field to specify
one of seven addressing modes, a register address field to
specify one of 60 processor registers, and a memory
address. Specify the instruction format and the number of
bits in each field if the instruction is in one memory word.
Homework
8-14 A two-word instruction is stored in memory at an address
designated by the symbol W. The address field of the
instruction (stored at W + 1) is designated by the symbol
Y. The operand used during the execution of the
instruction is stored at an address symbolized by Z. An
index register contains the value X. State how Z is
calculated from the other addresses if the addressing
mode of the instruction is
a. direct
b. indirect
c. relative
d. indexed
Homework
8-15 A relative mode branch type of instruction is stored in
memory at an address equivalent to decimal 750. The
branch is made to an address equivalent to decimal 500.
a. What should be the value of the relative address field
of the instruction (in decimal)?
b. Determine the relative address value in binary using
12 bits. (Why must the number be in 2’s complement?)
c. Determine the binary value in PC after the fetch phase
and calculate the binary value of 500. Then show that
the binary value in PC plus the relative address
calculated in part (b) is equal to the binary value of
500.
Homework
8-16 How many times does the control unit refer to memory
when it fetches and executes an indirect addressing mode
instruction if the instruction is (a) a computational type
requiring an operand from memory; (b) a branch type.
8-17 What must the address field of an indexed addressing
mode instruction be to make it the same as a register
indirect mode instruction?
8-18 An instruction is stored at location 300 with its address
field at location 301. The address field has the value 400.
A processor register R1 contains the number 200.
Evaluate the effective address if the addressing mode of
the instruction is (a) direct; (b) immediate; (c) relative;
(d) register direct; (e) index with R1 as the index register.
Homework
8-32 The content of the top of a memory stack is 5320. The
content of the stack pointer SP is 3560. A two-word call
subroutine instruction is located in memory at address
1120 followed by the address field of 6720 at location
1121. What are the content of PC, SP, and the top of the
stack:
a. Before the call instruction is fetched from memory?
b. After the call instruction is executed?
c. After the return from subroutine?
