PadhaikoAll subjects

Central Processing Unit (CPU)

Computer Organization and Architecture (ENCT 303)

Open in the Padhaiko app

2.1 Processor bus organization

The Central Processing Unit (CPU) fetches instructions from memory, decodes them, and executes operations on data using internal registers, an Arithmetic Logic Unit (ALU), and a control unit. To move data rapidly among multiple registers and the ALU without building dedicated point-to-point wires between every pair of registers, the CPU uses an internal processor bus organization.

There are three classical internal bus architectures:

Internal Processor Bus Organizations
OrganizationStructureAdvantageLimitation
Single-Bus OrganizationAll registers, ALU inputs/outputs, and memory interface connect to one shared internal busSimplest wiring and lowest hardware costOnly one data transfer per clock cycle; requires temporary buffer registers (, ) at ALU inputs/outputs
Two-Bus OrganizationTwo independent internal buses (e.g., Bus A and Bus B) feed the two ALU inputs simultaneouslyBoth ALU operands can be supplied in one cycleHigher multiplexer/bus routing complexity than single-bus
Three-Bus OrganizationTwo source buses (-bus, -bus) feed the ALU, and a third result bus (-bus) writes back to a destination registerComplete register-to-register ALU operation () finishes in a single clock cycleGreatest chip area and interconnect cost

In a single-bus CPU, executing takes multiple micro-steps: first place onto the bus and latch it into temporary register , then place onto the bus while the ALU adds and the bus value into result register , and finally transfer onto the bus into . In a three-bus CPU, drives Bus A, drives Bus B, the ALU computes , and Bus C latches the result directly into in one clock cycle.

2.2 Processor register organization: Control word, examples of microoperations

A general-purpose register organization connects a bank of CPU registers (say through ) to two multiplexers (MUX A and MUX B), which feed the two inputs of the ALU. The ALU output connects to a destination decoder (SELD) that enables the write-clock of the chosen destination register, and also routes to an external output bus.

Definition

Control Word

A control word is a binary bit pattern applied to the selection inputs of the multiplexers, destination decoder, and ALU function selector to specify one complete register-transfer microoperation in a single clock cycle.

For a typical 7-register CPU (–, with code 000 selecting external Input for MUX A/MUX B and None for SELD):

Thus, a 14-bit control word is formatted as:

Sample Microoperations and Symbolic Control Words
MicrooperationSELASELBSELDOPR14-Bit Control Word
R2 (010)R3 (011)R1 (001)SUB (00101)010 011 001 00101
R4 (100)R5 (101)R4 (100)OR (01010)100 101 100 01010
R6 (110)000R6 (110)INC (00001)110 000 110 00001
Input (000)000R7 (111)TSFA (00000)000 000 111 00000

2.3 Stack organization: Register stack, memory stack, reverse polish notation, evaluation of arithmetic expressions

A stack is a Last-In, First-Out (LIFO) storage structure where elements are inserted (PUSH) and removed (POP) from one end called the Top of Stack (TOS). A Stack Pointer (SP) register tracks the address of the top element.

AspectRegister StackMemory Stack
Storage MediumFixed set of high-speed CPU hardware registers (e.g., 64 words)A dedicated region of main memory (RAM)
CapacityVery small, fixed size; requires FULL and EMTY status flagsLarge, flexible capacity limited only by allocated RAM
SP Width & DirectionSmall counter (e.g., 6-bit SP for 64 words); typically increments on PUSH (SP <- SP + 1) and wraps to 0 when fullFull memory address width; typically grows downward from high to low addresses (PUSH: SP <- SP - 1; M[SP] <- DR)
SpeedExtremely fast (internal register access)Slower (requires a memory read/write cycle per push or pop)

In a 64-word register stack (addresses to ), initialization sets SP = 0, EMTY = 1, FULL = 0.

In a memory stack growing downward (e.g., stack segment from address 4000 down to 3000, initial SP = 4001):

Reverse Polish Notation (RPN) and Expression Evaluation

Standard algebraic notation is infix (), which requires parentheses and operator-precedence rules. Reverse Polish Notation (RPN)—also called postfix notation—places each operator immediately after its operands (), eliminating parentheses and enabling direct evaluation using a hardware stack:

  1. Scan the RPN expression from left to right.
  2. When an operand is encountered, PUSH its value onto the stack.
  3. When a binary operator is encountered, POP the top two operands ( then ), compute , and PUSH the result back onto the stack.
  4. At the end of the expression, the final result sits alone at the top of the stack.

2.4 Instruction formats: CPU organization, zero and more address instruction formats

The format of an instruction is heavily dictated by the CPU organization—specifically how operands are implicitly or explicitly referenced:

  1. Single Accumulator Organization: All operations use an implied Accumulator (AC) register, requiring only one explicit address field (e.g., ADD X means ).
  2. General Register Organization: Multiple CPU registers hold operands and intermediate results, allowing two- or three-address instructions (e.g., ADD R1, R2, R3).
  3. Stack Organization: Operands sit on top of a hardware stack, so arithmetic instructions require zero explicit addresses (e.g., ADD pops two items, adds them, and pushes the sum).
Zero-, One-, Two-, and Three-Address Instruction Formats
FormatExplicit AddressesExample (X = (A + B) * (C + D))Code Size vs. Instruction Length
Three-AddressADD R1, A, B
ADD R2, C, D
MUL X, R1, R2
Fewest instructions; longest instruction word
Two-AddressMOV R1, A
ADD R1, B
MOV R2, C
ADD R2, D
MUL R1, R2
MOV X, R1
Moderate instruction count and word length
One-Address (AC implied)LOAD A
ADD B
STORE T
LOAD C
ADD D
MUL T
STORE X
Shorter instructions; needs temporary memory stores
Zero-Address (Stack implied)PUSH A, PUSH B, ADD, PUSH C, PUSH D, ADD, MUL, POP XShortest arithmetic instructions; requires PUSH/POP

2.5 Addressing modes: Types, examples, strengths and weaknesses

An addressing mode specifies the rule for interpreting or modifying the address field of an instruction to obtain the Effective Address (EA) of the operand.

Definition

Effective Address (EA)

The Effective Address (EA) is the final memory address (or register) where the actual operand resides after applying the instruction's addressing mode calculation.

Common CPU Addressing Modes
ModeEffective Address / Operand RuleExampleStrengthsWeaknesses
Implied (Implicit)Operand is fixed by opcodeCMA (complement AC), CLCZero address bits needed; compactLimited to fixed registers
ImmediateOperand is inside instruction itselfMVI A, 25HFast; zero memory fetch for operandOperand magnitude limited by field size; read-only constant
RegisterOperand is in specified CPU register ADD R1 ()Very fast; short register fieldLimited number of CPU registers
Register Indirect (register holds memory pointer)ADD (R1) ()Short address field accesses full memory; great for pointers/loopsNeeds extra cycle to load pointer into first
Autoincrement / AutodecrementLike register indirect, plus MOV A, (R1)+Ideal for stepping through arrays and stacks in one instructionHardware must update register automatically
Direct (Absolute) (address field gives memory location)LDA 2050HSimple; single memory read for operandLimited address range; prevents easy code relocation
Indirect Memory (address field points to pointer)ADD @2050HSupports full address space pointersSlow: requires two memory accesses per operand
PC-RelativeJMP +12Compact short offset; position-independent codeLimited jump/data span around PC
IndexedLOAD 1000(XR)Ideal for accessing array elements (base + index)Dedicated index register required
Base-RegisterLOAD 20(BR)Enables dynamic program relocation in memoryMust initialize base register before execution

2.6 Instruction set

A computer's instruction set is the complete collection of machine operations its CPU can execute, typically grouped into three functional classes.

2.6.1 Data transfer instruction

Data transfer instructions move data unchanged from a source to a destination (between memory and processor registers, between two registers, or between CPU and I/O ports). Common mnemonics include LOAD (LD), STORE (ST), MOVE (MOV), EXCHANGE (XCH), PUSH, POP, IN, and OUT. On most architectures, data transfer instructions do not alter arithmetic status flags.

2.6.2 Data manipulation instruction: Arithmetic, logical and shift operations

Data manipulation instructions process data inside the ALU and update status flags:

  1. Arithmetic Instructions: INC, DEC, ADD, SUB, MUL, DIV, ADDC (add with carry), SUBB (subtract with borrow), NEG (two's complement).
  2. Logical & Bit-Manipulation Instructions: CLR (clear), COM (1's complement), AND (mask/clear bits), OR (set bits), XOR (toggle/compare bits), CLR C / SET C (bit flags).
  3. Shift & Rotate Instructions:
    • Logical Shift (SHL, SHR): Shifts bits left or right, shifting 0 into the vacated bit; last shifted-out bit goes to Carry (C).
    • Arithmetic Shift (SHLA, SHRA): Preserves the sign bit on right shift (SHRA copies the MSB into itself) so signed division by keeps the correct sign.
    • Rotate / Circular Shift (ROL, ROR, ROLC, RORC): Bits shifted out one end wrap around to the other end (directly or through the Carry flag).

2.6.3 Program control instruction

Program control instructions alter the sequential flow of control by modifying the Program Counter (PC):

2.7 Status bit conditions

During ALU operations, the processor records properties of the result in status bits (condition code flags) stored inside the Program Status Word (PSW) or Status Register. For an -bit result or :

Standard CPU Status Flags (PSW)
FlagNameCondition Setting Flag Primary Use
CCarryCarry-out from MSB () in addition, or borrow in subtractionUnsigned overflow detection and multi-word arithmetic
ZZeroEvery bit of the ALU result is ()Equality checks (CMP), loop counters reaching zero
S / NSign / NegativeMost significant bit of result is ()Detecting negative two's complement results
V / OOverflowSigned overflow occurs: (carry into MSB differs from carry out of MSB)Detecting signed arithmetic out of range ()
PParityEven (or odd, architecture-dependent) count of 1s in resultError checking in communication/byte ops

2.8 Interrupt: Definition, types, processing and ISR

Definition

Program Interrupt and ISR

An interrupt is a hardware or software signal that temporarily suspends the CPU's current instruction sequence so the processor can immediately respond to an urgent event. The routine executed to handle the event is called an Interrupt Service Routine (ISR) or interrupt handler.

Types of Interrupts

  1. External (Hardware) Interrupts: Originate outside the CPU from I/O devices (keyboard keypress, disk completion), timers, or power-fail sensors.
    • Maskable (INTR): Can be ignored or delayed by clearing the Interrupt Enable (IE) flag.
    • Non-Maskable (NMI): Cannot be disabled by software; reserved for critical events (power failure, memory parity error).
  2. Internal (Traps / Exceptions): Generated synchronously inside the CPU by an abnormal condition during instruction execution—such as division by zero, invalid opcode, arithmetic overflow, or memory protection fault.
  3. Software Interrupts: Triggered deliberately by executing a special instruction (e.g., INT 21H, SYSCALL, SWI) to request operating system services.

Interrupt Processing Cycle and ISR Execution

When an enabled interrupt request arrives, the CPU completes the current instruction before responding:

  1. Acknowledge & Disable Further Interrupts: The hardware clears the interrupt-enable flip-flop (preventing nested interruption unless explicitly re-enabled by the ISR).
  2. Save Context: The CPU pushes the current Program Counter (PC) (the return address) and Program Status Word (PSW) onto the system stack.
  3. Determine ISR Address (Vectoring): Either the interrupting device supplies a vector number (vectored interrupt), or the CPU jumps to a fixed address and polls status flags (non-vectored).
  4. Execute ISR: The ISR saves any working registers it modifies, services the device or error condition, restores those registers, and concludes with a Return from Interrupt (IRET / RETI) instruction.
  5. Restore Context: IRET pops PSW and PC from the stack, resuming the interrupted program seamlessly at the exact point it left off.

Worked Out Examples

Example 1

1 (6 marks)

Convert the infix arithmetic expression into Reverse Polish Notation (RPN), evaluate it using a stack trace for , , , , , and write the equivalent zero-address instruction sequence.

Converting infix to RPN (postfix): Respecting parentheses and precedence (/ before -):

  • Inner subexpression
  • Quotient
  • Second factor
  • Product

Evaluating the RPN expression on a stack:

Stack Trace for RPN Evaluation
Token ScannedActionStack Contents (Bottom Top)
3Push 3[3]
5Push 5[3, 5]
+Pop 5, 3; push 3 + 5 = 8[8]
10Push 10[8, 10]
8Push 8[8, 10, 8]
2Push 2[8, 10, 8, 2]
/Pop 2, 8; push 8 / 2 = 4[8, 10, 4]
-Pop 4, 10; push 10 - 4 = 6[8, 6]
*Pop 6, 8; push 8 * 6 = 48[48]

Writing the zero-address machine program:

Zero-Address Stack ProgramText
PUSH A
PUSH B
ADD
PUSH C
PUSH D
PUSH E
DIV
SUB
MUL
POP X
Answer:

The RPN form is , the stack evaluation yields , and the zero-address program uses PUSH, ADD, DIV, SUB, MUL, and POP X.

Example 2

2 (6 marks)

A two-word instruction is stored in memory at location 399 with its address field at location 400. The address field holds the value 400. A processor register R1 contains the number 200. Evaluate the Effective Address (EA) and the loaded value for LOAD under each of the following addressing modes:

  1. Direct addressing
  2. Immediate addressing
  3. Relative (PC-relative) addressing
  4. Register indirect addressing (R1)
  5. Indexed addressing with R1 as index register

Assume relevant memory words hold: , , , .

Determining the updated Program Counter: Because the instruction occupies two words at addresses 399 and 400, after fetching the entire instruction the Program Counter points to the next sequential instruction:

Computing Effective Address and Operand for each mode:

  • Direct Addressing: ; Operand .
  • Immediate Addressing: The operand is stored directly in the second word of the instruction (location 400), so and Operand .
  • PC-Relative Addressing: ; Operand .
  • Register Indirect Addressing (R1): ; Operand .
  • Indexed Addressing (R1): ; Operand .
Answer:
  1. Direct: , Operand ; 2. Immediate: , Operand ; 3. Relative: , Operand ; 4. Register Indirect: , Operand ; 5. Indexed: , Operand .
Example 3

3 (5 marks)

Two 8-bit two's complement numbers () and () are added in an 8-bit ALU. Determine the 8-bit binary sum and the resulting values of the Carry (C), Zero (Z), Sign (S), and Overflow (V) status flags. Explain why V is set even though C = 0.

Performing 8-bit binary addition bit-by-bit: Adding from LSB (bit 0) to MSB (bit 7):

Tracking carries into the MSB () and out of the MSB ():

  • At bit 6: , producing a carry into bit 7: .
  • At bit 7: , producing carry-out .

Evaluating the status flags:

  • Carry (C): (no unsigned carry-out beyond 8 bits; unsigned ).
  • Zero (Z): because the 8-bit result 10110100 is non-zero.
  • Sign (S): , making the 8-bit signed result appear negative ().
  • Overflow (V): .

Interpreting the signed overflow: The true sum exceeds the maximum positive 8-bit two's complement integer (). Thus signed overflow occurs (V = 1) even though the unsigned sum fits in 8 bits (C = 0).

Answer:

8-bit sum , with flags , , , . Overflow is set because two positive numbers summed beyond , causing .

Exercises

Exercise — Central Processing Unit (CPU)

Question 1

Compare single-bus, two-bus, and three-bus internal CPU organizations. Trace the microoperations needed to compute on a single-bus CPU versus a three-bus CPU.

Comparing internal bus organizations:

  • Single-bus: One shared internal data bus connects all registers and the ALU; requires temporary registers (ALU input latch) and (ALU output latch), taking multiple clock cycles per ALU operation.
  • Two-bus: Two internal buses simultaneously supply both ALU inputs; the result still returns on one of the buses or via a latch.
  • Three-bus: Two source buses feed the two ALU inputs while a dedicated third bus writes the ALU output directly to the destination register in one clock cycle.

Tracing :

  • Single-bus (3 cycles):
    1. (place on bus, latch into )
    2. (place on bus, ALU adds and bus, latch into )
    3. (place on bus, latch into )
  • Three-bus (1 cycle): , , ALU computes , result .
Answer:

Single-bus uses minimal wiring with temporary registers (3 cycles for ), two-bus supplies both ALU inputs in parallel, and three-bus completes in a single clock cycle.

Question 2

A CPU register organization has 7 general registers (–, encoded 001–111) and uses a 14-bit control word [SELA(3) | SELB(3) | SELD(3) | OPR(5)], where OPR codes are ADD = 00010, SUB = 00101, AND = 01000, INC = 00001, and TSFA = 00000. Write the 14-bit binary control words for:

Encoding each microoperation field-by-field:

  1. : SELA = 010 (), SELB = 110 (), SELD = 001 (), OPR = 00010 (ADD). Control word: 010 110 001 00010 (01011000100010).
  2. : SELA = 101 (), SELB = 011 (), SELD = 101 (), OPR = 01000 (AND). Control word: 101 011 101 01000 (10101110101000).
  3. : SELA = 100 (), SELB = 000 (unused), SELD = 100 (), OPR = 00001 (INC). Control word: 100 000 100 00001 (10000010000001).
Answer:
  1. 010 110 001 00010; 2. 101 011 101 01000; 3. 100 000 100 00001.
Question 3

Write a program to evaluate using:

  1. Two-address instructions
  2. Zero-address (stack) instructions

Then evaluate the stack RPN expression for .

Two-address instruction sequence (using registers R1, R2):

Two-Address ProgramText
MOV R1, B
MUL R1, C
ADD R1, A
MOV R2, D
SUB R2, E
MUL R1, R2
MOV Y, R1

Zero-address instruction sequence and RPN evaluation: The postfix form of is :

Zero-Address ProgramText
PUSH A
PUSH B
PUSH C
MUL
ADD
PUSH D
PUSH E
SUB
MUL
POP Y

Evaluating with :

  • Push 12, 4, 2 MUL pops 2, 4 and pushes 8 (stack [12, 8]).
  • ADD pops 8, 12 and pushes 20 (stack [20]).
  • Push 15, 6 SUB pops 6, 15 and pushes 9 (stack [20, 9]).
  • MUL pops 9, 20 and pushes 180. POP Y stores .
Answer:

Two-address and zero-address programs compute for the given values.

Question 4

An 8-bit CPU subtracts () from ( in signed two's complement) using two's complement addition . Find the 8-bit result and the C, Z, S, and V status flags. Does signed overflow occur?

Computing :

  • , so ().
  • Adding and :
    • Sum bits: 0011 1100 ( as signed 8-bit).
    • Carry into MSB: (bit 6: , no carry into bit 7).
    • Carry out of MSB: (bit 7: ).

Determining the status flags:

  • C = 1 (; no unsigned borrow because ).
  • Z = 0 (result 00111100 is non-zero).
  • S = 0 (MSB is 0).
  • V = C_8 XOR C_7 = 1 XOR 0 = 1.

In signed arithmetic, , which falls outside the 8-bit signed range , so signed overflow (V = 1) occurs.

Answer:

The 8-bit result is , with , , , and . Yes, signed overflow occurs because cannot be represented in 8-bit two's complement.

Question 5

Define an interrupt and distinguish among external interrupts, internal traps (exceptions), and software interrupts. Trace the sequence of hardware and software actions from the moment an interrupt is acknowledged until the interrupted program resumes.

Defining and classifying interrupts: An interrupt is a signal that suspends normal sequential program execution so the CPU can execute an Interrupt Service Routine (ISR):

  • External Interrupts: Asynchronous signals from external hardware (I/O controllers, timers), split into maskable (INTR, controlled by interrupt-enable flag) and non-maskable (NMI, always serviced).
  • Internal Interrupts (Traps/Exceptions): Synchronous CPU-generated events caused by the executing instruction itself (divide by zero, illegal opcode, page fault).
  • Software Interrupts: Explicit instructions (e.g., INT, SYSCALL) used by programs to invoke OS kernel services.

Tracing interrupt processing and return:

  1. CPU finishes executing the current instruction and samples pending interrupts (if IE = 1 or NMI).
  2. Hardware disables further maskable interrupts and saves PC and PSW onto the stack.
  3. CPU obtains the ISR address (via interrupt vector or fixed location) and loads it into PC.
  4. The ISR saves working registers, services the interrupting device/condition, and restores those registers.
  5. IRET restores PSW and PC from the stack, resuming the interrupted program transparently.
Answer:

Interrupts are categorized as external (hardware INTR/NMI), internal (synchronous exceptions/traps), and software (INT/SYSCALL). Upon acknowledgement after the current instruction, the CPU saves PC and PSW, vectors to the ISR to handle the event, and restores PSW and PC via IRET to resume the original program.

← IntroductionControl Unit →