Chapter 4

Central Processing Unit

Topics
 Introduction
 General Register Organization
 Stack Organization
 Instruction Formats
 Addressing Modes
 Data Transfer and Manipulation
 Program Control
 Reduced Instruction Set Computer
 4-1 Introduction
 3 major parts of CPU : Fig. 4-1
 1) Register Set
 2) ALU: microoperation
 3) Control: supervise information transfer

 Design Examples of simple CPU

 Hardwired Control : previous chapter
 Micro programmed
 As designer and a programmer(user) what we understand about CPU
from a given instruction set?
 In this chapter :
 Describe the organization and architecture of the CPU with an emphasis on the
user’s view of the computer
 User who programs the computer in machine/assembly language must be aware of
» 1) Instruction Formats
» 2) Addressing Modes Next topics
» 3) Register Sets

 The last section presents the concept of Reduced Instruction Set Computer (RISC)
 4-2 General Register Organization
External Input
 Register
C lo c k In p u t
 Memory locations are needed for storing
pointers, counters, return address, temporary R1

results, and partial products during multiplication R2

R3
 Memory access is the most time-consuming R4
R5
operation in a computer R6

 More convenient and efficient way is to store R7

intermediate values in processor registers Load

( 7 lin e s )
 Bus organization for 7 CPU registers : Fig. 4-2 SELA MUX MUX SELB

 2 MUX : select one of 7 register or external data

3× 8 A bus B bus
input by SELA and SELB decoder

 BUS A and BUS B : form the inputs to a

common ALU SELD
OPR
A r it h m e tic lo g ic u n it
(A L U )
 ALU : OPR determine the arithmetic or logic
microoperation External Output
» The result of the microoperation is available for O u tp u t
external data output and also goes into the inputs ( a ) B lo c k d ia g r a m

of all the registers 3 3 3 5

SELA SELB SELD OPR
 3 X 8 Decoder : select the register (by SELD) (b ) C o n tro l w o rd
that receives the information from ALU
 Binary selector input : R1  R 2  R3
 1) MUX A selector (SELA) : to place the content of R2 into BUS A
 2) MUX B selector (SELB) : to place the content of R3 into BUS B
 3) ALU operation selector (OPR) : to provide the arithmetic addition R2 + R3
 4) Decoder selector (SELD) : to transfer the content of the output bus into R1

 Control Word
 14 bit control word (4 fields) : Fig. 8-2(b)
» SELA (3 bits) : select a source register for the A input of the ALU
» SELB (3 bits) : select a source register for the B input of the ALU Tab. 8-1
» SELD (3 bits) : select a destination register using the 3 X 8 decoder
» OPR (5 bits) : select one of the operations in the ALU Tab. 8-2
 Encoding of Register Selection Fields : Tab. 8-1
» SELA or SELB = 000 (Input) : MUX selects the external input data
» SELD = 000 (None) : no destination register is selected but the contents of the output
bus are available in the external output
 Encoding of ALU Operation (OPR) : Tab. 8-2
Control Word Control Memory Micr
oprogrammed Control
 Examples of Microoperations : Tab. 8-3
 TSFA (Transfer A) : R 7  R1, External Output  R 2, External Output  External Input
 XOR : R5  0 ( XOR R5  R5)
 4-3 Stack Organization
 Stack or LIFO(Last-In, First-Out)
 A storage device that stores information
» The item stored last is the first item retrieved = a stack of tray
 Stack Pointer (SP)
» The register that holds the address for the stack
» SP always points at the top item in the stack
 Two Operations of a stack : Insertion and Deletion of Items
» PUSH : Push-Down = Insertion A d d re s s

» POP : Pop-Up = Deletion

64
 Stack
» 1) Register Stack (Stack Depth) FULL EM TY
 a finite number of memory words or register(stand alone)
» 2) Memory Stack (Stack Depth)
 a portion of a large memory 4
SP C 3
 Register Stack : Fig. 8-3 B 2

 PUSH : SP  SP  1 : Increment SP A 1
Last Item 0
SP = 0, M [ SP ]  DR : Write to the stack
EMTY = 1, If ( SP  0) then ( FULL  1) : Check if stack is full
FULL = 0 DR
EMTY  0 : Mark not empty
» The first item is stored at address 1, and the last item is stored at address 0
 POP : DR  M [ SP ] : Read item from the top of stack * Memory Stack
PUSH = Address
SP  SP  1 : Decrement Stack Pointer * Register Stack
If ( SP  0) then ( EMTY  1) : Check if stack is empty PUSH = Address

FULL  0 : Mark not full A d d re s s

M e m o r y u n it
 Memory Stack : Fig. 8-4 PC
1000

 PUSH : SP  SP  1 P ro g ra m
( in s tr u c t io n s )
M [ SP ]  DR
SP = 4001 2000
» The first item is stored at address 4000 AR
D a ta
 POP : DR  M [ SP ] (o p e ra n d s )

SP  SP  1 * Error Condition
3000
PUSH when FULL = 1
S ta c k
 Stack Limits POP when EMTY = 1

 Check for stack overflow(full)/underflow(empty) 3997

SP 3998
» Checked by using two register
3999
 Upper Limit and Lower Limit Register 4000
» After PUSH Operation Start Here 4001
 SP compared with the upper limit register
» After POP Operation
 SP compared with the lower limit register DR
Stack Arithmetic
 RPN (Reverse Polish Notation)
 Common arithmetic expressions written in infix notation (A*B + C *D)
 The difficulties when evaluated by a computer
 A stack organization is very effective for evaluating arithmetic expressions
 A * B + C * D  AB * CD * + : Fig. 8-5
» ( 3 * 4 ) + ( 5 * 6 )  34 * 56 * +

6
4 5 5 30
3 3 12 12 12 12 42

3 4 * 5 6 * +

 Q represent the arithmetic expression in Reverse polish notation

» (A+B)*[C*(D+E) +(G+F)]
 4-4 Instruction Formats
 Fields in Instruction Formats
 1) Operation Code Field : specify the operation to be performed
 2) Address Field : designate a memory address or a processor register
 3) Mode Field : specify the operand or the effective address (Addressing Mode)
 The number of address fields in the instruction format of a computer depends on
the internal organization of its register

X = Operand Address
 3 types of CPU organizations
 1) Single AC Org. : ADD X AC  AC  M [ X ]1 address filed
 2) General Register Org. : ADD R1, R2, R3 R1  R 2  R 3 deepened on no of register
 3) Stack Org. : PUSH X TOS  M [ X ]no address field if the instruction is ADD/MUL
 The influence of the number of addresses on computer instruction
X = (A + B)*(C + D) with zero, one, two or three address instructions
- 4 arithmetic operations : ADD, SUB, MUL, DIV
- 1 transfer operation to and from memory and general register : MOV
- 2 transfer operation to and from memory and AC register : STORE, LOAD
- Operand memory addresses : A, B, C, D
- Result memory address : X
 1) Three-Address Instruction

ADD R1, A, B R1  M [ A]  M [ B ]
ADD R2, C, D R 2  M [C ]  M [ D ]
MUL X, R1, R2 M [ X ]  R1  R 2
» Each address fields specify either a processor register or a memory operand
  Short program to perform arithmetic operation.
» Require too many bit to specify 3 address


» Example Cyber 170 computer

 2) Two-Address Instruction:

MOV R1, A R1  M [ A]
ADD R1, B R1  R1  M [ B ]
MOV R2, C R 2  M [C ]
ADD R2, D R2  R2  M [ D]
MUL R1, R2 R1  R1  R 2
MOV X, R1 M [ X ]  R1
» The most common in commercial computers
» Each address fields specify either a processor register or a memory operand
 3) One-Address Instruction

LOAD A AC  M [ A]
ADD B AC  A[C ]  M [ B ]
STORE T M [T ]  AC
LOAD C AC  M [C ]
ADD D AC  AC  M [ D ]
MUL T AC  AC  M [T ]
STORE X M [ X ]  AC

» All operations are done between the AC register and memory operand
 4) Zero-Address Instruction

PUSH A TOS  A
PUSH B TOS  B
ADD TOS  ( A  B )
PUSH C TOS  C
PUSH D TOS  D
ADD TOS  (C  D )
MUL TOS  (C  D )  ( A  B )
POP X M [ X ]  TOS

» Stack-organized computer does not use an address field for the instructions ADD, and
MUL
» PUSH, and POP instructions need an address field to specify the operand
» Zero-Address : absence of address ( ADD, MUL )
 4-5 Addressing Modes
 What is the work of operation field and address field in the given instruction?
 The addressing mode identifies the way operand is choose
 Purpose of Addressing Mode
 1) To give programming versatility to the user

» pointers to memory, counters for loop control, indexing of data,

program relocation
 2) To reduce the number of bits in the addressing field of the instruction

 Instruction Cycle

 1) Fetch the instruction from memory and PC + 1

 2) Decode the instruction
 3) Execute the instruction
 Program Counter (PC)

 PC keeps track of the instructions in the program stored in memory

 PC holds the address of the instruction to be executed next
 PC is incremented each time an instruction is fetched from memory
Opcode Mode Address
 Immediate Mode
 Operand field contains the actual operand
 Useful for initializing registers to a constant value
 Example : LD #NBR

 The address field may indicate register or memory

 Register Mode
 Operands are in registers
 Register is selected from a register field in the instruction
» k-bit field can specify any one of 2 k registers
 Example : LD R1 AC  R1 Implied Mode
 Register Indirect Mode
 Selected register contains the address of the operand rather than the operand itself
  Address field of the instruction uses fewer bits to select register than a memory
address directly .
 Example : LD (R1)
AC Mode
 Autoincrement or Autodecrement M [R1]

 Similar to the register indirect mode except that

» the register is incremented after its value is used to access memory

» the register is decrement before its value is used to access memory

» Example : LD (R1)+
AC  M [ R1], R1  R1  1
 The value of address field may give the address of the operand or address which
helps to calculate the address of the operand
 What is effective address?
 Direct Addressing Mode
 Effective address is equal to the address field of the instruction (Operand)
 Address field specifies the actual branch address in a branch-type instruction
 Example : LD ADR AC  M [ ADR ]
ADR = Address part of Instruction
 Indirect Addressing Mode
 Address field of instruction gives the address where the effective address is
stored in memory
 Example : LD @ADR AC  M [ M [ ADR ]]

 Relative Addressing Mode

 PC is added to the address part of the instruction to obtain the effective address
 Example : LD $ADR AC  M [ PC  ADR ]
 Indexed Addressing Mode
 XR (Index register) is added to the address part of the instruction to obtain the
effective address
 Example : LD ADR(XR) AC  M [ ADR  XR ]

 Base Register Addressing Mode

 the content of a base register is added to the address part of the instruction to
obtain the effective address  program relocation
 Similar to the indexed addressing mode except that the register is now called a
base register instead of an index register
» index register (XR) : LD ADR(XR) AC  M [ ADR  XR ] ADR
 index register hold an index number that is relative to the address part of the instruction
» base register (BR) : LD ADR(BR) AC  M [ BR  ADR ] BR
 base register hold a base address
 the address field of the instruction gives a displacement relative to this base address
A d d re s s M e m o ry
 Numerical Example
PC = 200 200 L o a d to A C Mode
Addressing Mode Effective Address Content of AC
201 A d d re s s = 5 0 0
Immediate Address Mode 201 500
Direct Address Mode 500 800 R1 = 400 202 N e x t in s t r u c tio n
Indirect Address Mode 800 300
Register Mode 400
XR = 100
Register Indirect Mode 400 700
Relative Address Mode 702 325 399 450
Indexed Address Mode 600 900 AC 400 700
Autoincrement Mode 400 700

Autodecrement Mode 399 450 500 800

R1 = 400
600 900
500 + 202 (PC)
R1 = 400 (after) 702 325
500 + 100 (XR)
R1 = 400 -1 (prior)
800 300
 4-6 Data Transfer and Manipulation
 Most computer instructions can be classified into three categories:
 1) Data transfer, 2) Data manipulation, 3) Program control instructions

 Data Transfer Instruction: transfer from one location to other without

changing the content
 Typical Data Transfer Instruction : Tab. 8-5
» Load : transfer from memory to a processor register, usually an AC (memory read)
» Store : transfer from a processor register into memory (memory write)
» Move : transfer from one register to another register
» Exchange : swap information between two registers or a register and a memory word
» Input/Output : transfer data among processor registers and input/output device
» Push/Pop : transfer data between processor registers and a memory stack
 8 Addressing Mode for the LOAD Instruction : Tab. 8-6
» :Direct Address
» @ : Indirect Address
» $ : Address relative to PC
» # : Immediate Mode
» ( ) : Index Mode, Register Indirect, Autoincrement
 Data Manipulation Instruction
 1) Arithmetic, 2) Logical and bit manipulation, 3) Shift Instruction
 4-7 Program Control
 Program Control Instruction : for decision making and changing path.

 Branch and Jump instructions are used interchangeably to mean the same thing,
but some times use d/t addressing modes.

Branch  one address example BR at address ADR, what does it mean?

• Branch and Jump instruction may be conditional or unconditional

• Conditional :some condition should met to change the program counter and cause
branch.

Example Skip (SKP)

to perform conditional branch certain status bit is set as a result of operation.

 Status Bit Conditions :

 Condition Code Bit or Flag Bit

» The bits are set or cleared as a result of an operation performed in the ALU
 4-bit status register

 Bit C (carry) : set to 1 if the end carry C8 is 1

 Bit S (sign) : set to 1 if F7 is 1

 Bit Z (zero) : set to 1 if the output of the ALU contains all 0’s
 Bit V (overflow) : set to 1 if the exclusive-OR of the last two carries (C8 and C7) is
equal to 1
 Conditional Branch : some condition should met Tab. 8-11
Example : BZ  Branch if Zero tested condition , Z = 1
 Compare condition performs subtraction and two type  signed and unsigned
Unsigned (A – B)
BHI  Branch if higher tested condition  A > B
Signed (A – B)
BGT  Branch if greater than , tested condition  A > B
 Flag Example : A - B = A + ( 2’s Comp. Of B ) : A =11110000, B = 00010100

11110000
C = 1, S = 1, V = 0, Z = 0
+ 11101100 (2’s comp. of B)
 A > B ,1A11011100
≠ B ( BHI, BHE or BNE)
 Subroutine Call and Return: self-contained sequence of instruction

Have different names(jump or branch to subroutine, branch and save return address
 When subroutine is called, branch is executed by doing two things

1. Return address is store in temporary location

2. Control transfer to the beginning of subroutine

 CALL : SP  SP  1 : Decrement stack point

M [ SP ]  PC : Push content of PC onto the stack
PC  Effective Address
: Transfer control to the subroutine
PC  M [ SP ] : Pop stack and transfer to
 RETURN :
SP  SP  1 PC

 Program Interrupt : Increment stack pointer

 Program Interrupt: What is interrupt?

 In principle, interrupt program is similar to subroutine call except some
differences
 Interrupt Service Program Vs Subroutine Call (the difference)
» 1) An interrupt is initiated by an internal or external signal (except for
software interrupt)
A subroutine call is initiated from the execution of an instruction (CALL)
» 2) The address of the interrupt service program is determined by the
hardware
 The address of the subroutine call is determined from the address field

of an instruction

» 3) An interrupt procedure stores all the information necessary to define the

state of the CPU
 A subroutine call stores only the program counter (Return address)

 When interrupt is recognized, the state of the CPU is determined from:

1. The content of the program counter

2. The content of all processor registers
3. The content of certain status conditions
 Program Status Word (PSW)
 The collection of all status bit conditions in the CPU, which specify the
interrupt allow and at which mode the CPU is operating.
 Two CPU Operating Modes
» Supervisor (System) Mode : Privileged Instruction
 When the CPU is executing a program that is part of
the operating system
External Int.
In te rru p t
CPU operating mode is determined from special bits in the PSW Internal Int. D e te c t
Software Int.
» User Mode : User program
 When the CPU is executing an user program D e t e r m in e t h e
a d d re s s o f IS R
PC, CPU Register, Status Condition

 Types of Interrupts S to re In f o r m a tio n

 1) External Interrupts

» come from I/O device, from a timing device, from a circuit M a i n bmonitoring
o d y o f IS R

the power supply, or from any other external source

 2) Internal Interrupts or traps ( illegal or erroneous use of ins)
ins R e s t o r e In f o r m a t io n

» caused by register overflow, attempt to divide by zero,

In te rru p t
an invalid operation code, stack overflow, and protection violation R e tu rn
 3) Software Interrupts

» initiated by executing an instruction

» used by the programmer to initiate an interrupt procedure at any desired point

in the program
 4-8 Reduced Instruction Set Computer (RISC)
 Complex Instruction Set Computer (CISC)(VAX and IBM 370 computers)

 Major characteristics of a CISC architecture

» 1) A large number of instructions - typically from 100 to 250 instruction

» 2) Some instructions that perform specialized tasks and are used infrequently

» 3) A large variety of addressing modes - typically from 5 to 20 different modes

» 4) Variable-length instruction formats

» 5) Instructions that manipulate operands in memory (RISC in register)

 Reduced Instruction Set Computer (RISC) around 1980’s

 Major characteristics of a RISC architecture

» 1) Relatively few instructions

» 2) Relatively few addressing modes, why ?

» 3) Memory access limited to load and store instruction

» 4) All operations done within the registers of the CPU

» 5) Fixed-length, easily decoded instruction format

» 6) Single-cycle instruction execution

» 7) Hardwired rather than microprogrammed control

 Other characteristics of a RISC architecture
» 1) A relatively large number of registers in the processor unit
» 2) Use of overlapped register windows to speed-up procedure call and return
» 3) Efficient instruction pipeline
» 4) Compiler support for efficient translation of high-level language programs into
machine language programs
 Overlapped Register Windows
R15

 Where procedure call occurs? C o m m o n to D a n d A

Circular Window
R10
 Time consuming operations during procedure call R73
L o c a l to D

» Saving and restoring registers R64

R63
» Passing of parameters and results C o m m o n to C a n d D

» to solve this :Register bank, memory stack P ro c D

R58
R57
L o c a l to C
 Overlapped Register Windows R48
R47
» Provide the passing of parameters and avoid the need C o m m o n to B a n d C

for saving and restoring register values R42

R41
P ro c C

 Concept of overlapped register windows : Fig. 8-9 L o c a l to B

R32

 Total 74 registers : R0 - R73 R31

C o m m o n to A a n d B

» R0 - R9 : Global registers R26

R25
P ro c B
L o c a l to A
» R10 - R63 : 4 windows
R16
 Window A 10 Local registers R9
C o m m o n t o a ll
R15
C o m m o n to A a n d D
 Window B + P ro c e d u re s

 Window C 2 sets of 6 registers R0

G lo b a l
R10
P ro c A
(common to adjacent windows) r e g is t e rs
 Window D
 Example) Procedure A calls procedure B
» R26 - R31
 Store parameters for procedure B

 Store results of procedure B

» R16 - R25 : Local to procedure A

» R32 - R41 : Local to procedure B
 Window Size = L + 2C + G = 10 + ( 2 X 6 ) + 10 = 32 registers
 Register File (total register) = (L + C) x W + G = (10 + 6 ) X 4 + 10 = 74 registers
» , G : Global registers = 10
L : Local registers = 10
C : Common registers = 6
W : Number of windows = 4
 Berkeley RISC I
 RISC Architecture : 1980

» Berkeley RISC project : first project = Berkeley RISC I

» Stanford MIPS project
 Berkeley RISC I
» 32 bit integrated circuit CPU, 32 bit instruction format, 31 instruction
» 3 addressing modes : register, immediate, relative to PC
» 138 register and 8 windows each have 32 register.
 Instruction Set : for the three categories of instruction Tab. 8-12 their name?
 Instruction Format N.B Rd: destination register
 Register Mode : bit 13 = 0 Rs: source register
» S2 = register 31 24 23 19 18 14 13 12 5 4 0
» Example) ADD R22, R21, R23 O pcode Rd Rs 0 Not used S2
 ADD Rs, S2, Rd : Rd = Rs + S2 8 5 5 1 8 5

( a ) R e g is t e r m o d e : ( S 2 s p e c if ie s a r e g is t e r )
 Register Immediate Mode : bit 13 = 1
» S2 = sign extended 13 bit constant 31 24 23 19 18 14 13 12 0
Opcode Rd Rs 1 S2
» Example) LDL (R22)#150, R5
8 5 5 1 13
 LDL (Rs)S2, Rd : Rd = M[R22] + 150
( b ) R e g is t e r - im m e d ia t e m o d e : ( S 2 s p e c if ie s a n o p e r a n d )
 PC Relative Mode
31 24 23 19 18 0
» Y = 19 bit relative address
O pcode COND Y
» Example) JMPR COND, Y
8 5 19
 Jump to PC = PC + Y
» CWP (Current Window Pointer) ( c ) P C r e la t iv e m o d e :
 CALL, RET
 RISC Architecture Originator
Architecture Originator Licensees
Alpha DEC Mitsubishi, Samsung
MIPS MIPS Technologies NEC, Toshiba
PA-RISC Hewlett Packard Hitachi, Samsung
PowerPC Apple, IBM, Motorola Bul
Sparc Sun Fujitsu, Hyundai
i960 Intel Intel only (Embedded Controller)
Review Exercise
1. A stack is organized such that SP always points at the next empty
location on the stack. This means that Sp can be initialized to 4000 and
the first item in the stack is stored in location 4000. List the
microoperations for the push and pop operations.
2. Convert the following arithmetic expressions from reverse Polish
notation to infix notation.
 A B C D E*/— +

3. 3. 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