Chapter Five

Central Processing Unit (CPU)

Overview of CPU
✓ CPU is the heart and brain of the computer
✓ It interprets and executes machine level instructions
✓ Controls data transfer from/to Main Memory (MM) and CPU
✓ Detects any errors

General Register Organization

A set of flip-flops forms a register. A register is a unique high-speed storage area in the CPU. They
include combinational circuits that implement data processing. The information is always defined in
a register before processing. The registers speed up the implementation of programs. Registers
implement two important functions in the CPU operation are as follows

−It can support a temporary storage location for data. This supports the directly implementing
programs to have fast access to the data if required.

-It can save the status of the CPU and data about the directly implementing program.

Example − Address of the next program instruction, signals get from the external devices and error
messages, and including different data is saved in the registers. If a CPU includes some registers,
therefore a common bus can link these registers. A general organization of seven CPU registers is
displayed in the figure.

1
The CPU bus system is managed by the control unit. The control unit explicit the data flow
through the ALU by choosing the function of the ALU and components of the system.

Consider R1 ← R2 + R3, the following are the functions implemented within the CPU −

MUX A Selector (SELA) − It can place R2 into bus A.

MUX B Selector (SELB) − It can place R3 into bus B.

ALU Operation Selector (OPR) − It can select the arithmetic addition (ADD).

Decoder Destination Selector (SELD) − It can transfers the result into R1.

The multiplexers of 3-state gates are performed with the buses. The state of 14 binary
selection inputs determines the control word. The 14-bit control word defines a micro-
operation.

2
 Stack Organization
The CPU of most computers comprises of a stack or last-in-first-out (LIFO) list wherein
information is stored in such a manner that the item stored last is the first to be retrieved.
The operation of a stack can be compared to a stack of trays. The last tray placed on top of the
stack is the first to be taken off.

The stack in digital computers is essentially a memory unit with an address register that can
count only (after an initial value is loaded into it). A Stack Pointer (SP) is the register where the
address for the stack is held because its value always points at the top item in the stack. The
physical registers of a stack are always available for reading or writing unlike a stack of trays
where the tray itself may be taken out or inserted because it is the content of the word that is
inserted or deleted.

A stack has only two operations i.e. the insertion and deletion of items. The operation insertion is
called push (or push-down) because it can be thought of as the result of pushing a new item on
top. The deletion operation is called pop (or pop-up) because it can be thought of as the result of
removing one item so that the stack pops up. In actual, nothing is exactly pushed or popped in a
computer stack. These operations are simulated by incrementing or decrementing the stack pointer
register.
Register Stack
There are two ways to place a stack. Either it can be placed in a portion of a large memory or
it can be organized as a collection of a finite number of memory words or registers. The
organization of a 64-word register stack is exhibited in figure 5.3.

F i g u r e 5 . 3 : 64-word register stack

A binary number whose value is equal to the address of the word that is currently on top of the
stack is contained by the stack pointer register. Three items are placed in the stack - A, B and C
3
in that order. Item C is on top of the stack so that the content of SP is now 3. To remove the top
item, the stack is popped by reading the memory word at address 3 and decrementing the content
of SP. Item B is now on top of the stack since SP holds address 2. To insert a new item, the stack
is pushed by incrementing SP and writing a word in the next-higher location in the stack. Note that
item C has been read out but not physically removed. This does not matter because when the
stack is pushed, a new item is written in its place.

In a 64-word stack, the stack pointer contains 6 bits because 26 = 64. Since SP has only six bits, it
cannot exceed a number greater than 63 (111111 in binary). When 63 is incremented by l, the
result is 0 since 111111 + 1 = 1000000 in binary, but SP can accommodate only the six least
significant bits. Similarly, when 000000 is decremented by 1, the result is 111111. The 1-bit register
FULL is set to 1 when the stack is full, and the one-bit register EMTY is set to 1 when the stack is
empty of items. DR is the data register that holds the binary data to be written into or read out of the
stack.

Initially, SP is cleared to 0, EMTY is set to 1, and FULL is cleared to 0, so that SP points to the
word at address 0 and the stack is marked empty and not full. If the stack is not full (if FULL = 0),
a new item is inserted with a push operation. The push operation is implemented with the following
sequence of micro-operations:

SP ← SP + 1 Increment stack pointer

M[SP] ← DR Write item on top of the stack

If (SP= 0) then (FULL ← l) Check if stack is full

The stack pointer is incremented so that it points to the address of the next-higher word. The
word from DR is inserted into the top of the stack by the memory write operation. The
M[SP] denotes the memory word specified by the address presently available in SP whereas
the SP holds the address the top of the stack. The storage of the first item is done at address 1
whereas as the last item is store at address 0. If SP reaches 0, the stack is full of items, so
FULL is set to 1. This condition is reached if the top item prior to the last push was in location
63 and after incrementing SP, the last item is stored in location 0. Once an item is stored in
location 0, there are no more empty registers in the stack. If an item is written in the stack,
obviously the stack cannot be empty, so EMTY is cleared to 0.

A new item is deleted from the stack if the stack is not empty (if EMTY <> 0). The pop operation

4
consists of the following sequence of micro-operations:
DR ← M[SP] Read item from the top of stack
SP ← SP – 1 Decrement stack pointer
If (SP == 0) then (FULL ← 1) Check if stack is empty
EMTY ← 0 Mark the stack not full

DR. reads the top item from the stack. Then the stack pointer is decremented. If its
value attains zero, the stack is empty, so EMTY is set to 1. This condition is reached if the
item read was in location 1. Once this item is read out, SP is decremented and it attain
reaches the value 0, which is the initial value of SP. Note that if a pop operation reads the
item from location 0 and then SP is decremented, SP changes to 111111, which is
equivalent to decimal 63. In this configuration, the word in address 0 receives the last item
in the stack. Note also that an erroneous operation will result if the stack is pushed when
FULL = 1 or popped when EMPTY = 1.

Memory Stack

As shown in Fig. 5.3, stack can exist as a stand-alone unit or can be executed in a
random-access memory attached to a CPU. The implementation of a stack in the CPU is
done by assigning a portion of memory. A portion of memory is assigned to a stack
operation and a processor register is used as a stack pointer to execute stack in the CPU.
Figure 5.4 shows a portion of computer memory partitioned into three segments - program,
data, and stack. The address of the next instruction in the program is located by the program
counter PC while an array of data is pointed by address register AR. The top of the stack is
located by the stack pointer SP. The three registers are connected to a common address bus,
which connects the three registers and either one can provide an address for memory. PC
is used during the fetch phase to read an instruction. AR is used during the execute phase to
read an operand. SP is used to push or pop items into or from the stack.

5
Figure 5.4: Computer memory with program, data, and slack segments.

Fig 5.4 displays the initial value of SP at 4001 and the growing of stack with
decreasing addresses. Thus the first item stored in the stack is at address 4000, the
second item is stored at address 3999, and the last address that can be used for the
stack is 3000. No checks are provided for checking stack limits.

We assume that the items in the stack communicate with a data register DR. A
new item is inserted with the push operation as follows:

SP ← SP – 1

M[SP] ← DR

The stack pointer is decremented so that it points at the address of the next word.
A memory write operation inserts the word form DR into the top of the stack. A
new item is deleted with a pop operation as follows:

DR ← M[SP]

SP ← SP + 1

The top item is read from the stack into DR. The stack pointer is then incremented
to point at the next item in the stack.

Most computers are not equipped with hardware to check for stack overflow (full
stack) or underflow (empty stack). The stack limits can be checked by using two
processor registers: one to hold the upper limit (3000 in this case), and the other to

6
hold the lower limit (40001 in this case). After a push operation, SP is compared
with the upper-limit register and after a pop operation, SP is compared with the
lower-limit register.
Reverse Polish Notation
Reverse Polish Notation is a way of expressing arithmetic expressions that avoids
the use of brackets to define priorities for evaluation of operators. In ordinary
notation, one might write (3 + 5) * (7 - 2) and the brackets tell us that we have to add
3 to 5, then subtract 2 from 7, and multiply the two results together. In RPN, the
numbers and operators are listed one after another, and an operator always acts on
the most recent numbers in the list. The numbers can be thought of as forming a
stack, like a pile of plates. The most recent number goes on the top of the stack.
An operator takes the appropriate number of arguments from the top of the stack
and replaces them by the result of the operation.

In this notation the above expression would be 3 5 + 7 2 - *

Reading from left to right, this is interpreted as follows:

• Push 3 onto the stack.

• Push 5 onto the stack. The stack now contains (3, 5).

• Apply the + operation: take the top two numbers off the stack, add
them together, and put the result back on the stack. The stack now contains
just the number 8.

• Push 7 onto the stack.

• Push 2 onto the stack. It now contains (8, 7, 2).

• Apply the - operation: take the top two numbers off the stack, subtract the
top one from the one below, and put the result back on the stack. The
stack now contains (8, 5).
• Apply the * operation: take the top two numbers off the stack, multiply
them together, and put the result back on the stack. The stack now contains
just the number 40.

Polish Notation was devised by the Polish philosopher and mathematician

Jan Lucasiewicz (1878-1956) for use in symbolic logic. In his notation, the
7
operators preceded their arguments, so that the expression above would be written as

*+35-72

The 'reversed' form has however been found more convenient from a
computational point of view.
Instruction Formats
• It is the function of the control unit within the CPU to interpret each
instruction code

• The bits of the instruction are divided into groups called fields

• The most common fields are:

✓ Operation code
✓ Address field – memory address or a processor register
✓ Mode field – specifies the way the operand or effective
address is determined
• A register address is a binary number of k bits that defines one of 2k registers
in the CPU. The instructions may have several different lengths containing
varying number of addresses
• The number of address fields in the instruction format of a computer
depends on the internal organization of its registers

• Most computers fall into one of the three following organizations:

o Single accumulator organization

o General register organization

o Stack organization

• Single accumulator org. uses one address field

ADD X : AC ← AC + M[X]

• The general register org. uses three address fields

ADD R1, R2, R3: R1 ← R2 + R3

• Can use two rather than three fields if the destination is assumed to be one
of the source registers
• Stack org. would require one address field for PUSH/POP operations and
none for operation-type instructions
8
 PUSH X

ADD

Some computers combine features from more than one organizational structure

Example: X = (A+B) * (C + D)
5.2.1 Three-address instructions:

ADD R1, A, B R1 ← M[A] + M[B]

ADD R2, C, D R2 ← M[C] + M[D]

MUL X, R1, R2 M[X] ← R1 * R2

5.2.2 Two-address instructions:

MOV R1, A R1 ← M[A]

ADD R1, B R1 ← R1 + M[B]

MOV R2, C R2 ← M[C]

ADD R2, D R2 ← R2 + D

MUL R1, R2 R1 ← R1 * R2

MOV X, R1 M[X] ← R1
5.2.3 One-address instructions:

LOAD A AC ← M[A]

ADD B AC ← AC + 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
5.2.4 Zero-address instructions:

PUSH A TOS ← A

PUSH B TOS ←B

9
 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

Data Transfer and Manipulation
• There is a basic set of operations that most computers include in
their instruction set
• The opcode and/or symbolic code may differ for the same instruction
among different computers
• There are three main categories of computer instructions:
o Data transfer
o Data manipulation
o Program control

• Data transf er instructions: transfer data from one location to another without
changing the binary information content

Load LD Input IN
Store ST Output OUT
Move MOV Push PUSH
Exchange XCH Pop POP

• Some assembly language conventions modify the mnemonic

symbol to differentiate between addressing modes
LDI – load immediate
• Some use a special character to designate the mode

10
Data manipulation instructions: perform arithmetic, logic, and/or shift operation

• Arithmetic instructions:
Increment INC Divide DIV
Decrement DEC Add w/carry ADDC
Add ADD Sub. w/borrow SUBB
Subtract SUB Negate (2’s comp) NEG
Multiply MUL

• Some computers have different instructions depending upon the data type
ADDI Add two binary integer numbers
ADDF Add two floating point numbers
ADDD Add two decimal numbers in BCD

• Logical and bit manipulation instructions:

Clear CLR Clear carry CLRC
Complement COM Set carry SETC
AND AND Comp. carry COMC
OR OR Enable inter. EI
Exclusive-OR XOR Disable inter. DI

• Clear selected bits – AND instruction

• Set selected bits – OR instruction
• Complement selected bits – XOR instruction

• Shift instructions:
Logical shift right SHR Rotate right ROR
Logical shift left SHL Rotate left ROL
Arithmetic shift right SHRA ROR thru carry RORC
Arithmetic shift left SHLA ROL thru carry ROLC

11
 OP REG TYPE RL COUNT

Program Control
• Program control instructions: provide decision-making capabilities and change
the program path
• Typically, the program counter is incremented during the fetch phase to the
location of the next instruction
• A program control type of instruction may change the address value in the
program counter and cause the flow of control to be altered
• This provides control over the flow of program execution and a capability for
branching to different program segments

Branch BR Return RET

Jump JMP Compare CMP
Skip SKP Test TST
Call CALL

• TST and CMP cause branches based upon four status bits: C, S, Z, and V

CISC & RISC CHARACTERISTICS

An important aspect of computer architecture is the design of the
instruction set for the processor

The instruction set determines the way that machine language

programs are constructed

• Many computers have instructions sets of about 100 - 250

instructions
• These computers employ a variety of data types and a
large number of addressing modes – complex instruction set
computer (CISC)
• A RISC uses fewer instructions with simple constructs so they
can be executed much faster within the CPU without having to
use memory as often

The essential goal of a CISC architecture is to attempt to provide

a single machine instruction for each statement that is written in a
high-level language

12
The major characteristics of CISC architecture are:

• Large number of instructions

• Some instructions that perform specialized
tasks and are used infrequently
• Large variety of addressing modes
• Variable length instruction formats
• Instructions that manipulate operands in memory

The goal of RISC architecture is to reduce execution time by

simplifying the instructions set.

RISC Characteristics

The essential goal of RISC architecture involves an attempt to reduce

execution time by simplifying the instruction set of the computer.
The major characteristics of a RISC processor are:

• Relatively few instructions.

• Relatively few addressing modes.
• Memory access limited to load and store instructions.
• All operations done within the registers of the CPU.
• Fixed length easily decoded instruction format.
• Single-cycle instruction execution.
• Hardwired rather than microprogrammed control.

13
14