Accumulator Based Computer Organization

In computer architecture, the organization of the CPU (Central Processing Unit) depends on how
operands are stored and how arithmetic/logic operations are performed. One classic and simple
approach is the Accumulator-based organization, which was widely used in early computers and
microcontrollers.

An Accumulator is a special-purpose register within the CPU that holds one of the operands and the
result of arithmetic or logic operations. In this organization, most instructions implicitly use the
accumulator for one operand. Because the accumulator is the default location, many instructions only
need to specify a single explicit address.

Let’s say, we want to compute: Z = (A + B) – C

The sequence of operations are as follows:
1. Load A ; Load number A into accumulator
2. ADD B ; Add number B to accumulator
3. SUB C ; Subtract number C from accumulator
4. Store Z ; Store accumulator content in location Z

So, the accumulator acts as:

Temporary storage for intermediate results.
Primary working register of the CPU.

A simplified block diagram:

Accumulator (ACC) − main register for computation.

Program Counter (PC) − holds the address of the next instruction.
Instruction Register (IR) − holds the current instruction.
Arithmetic Logic Unit (ALU) − performs arithmetic/logic operations, one input from ACC.
Memory Address Register (MAR) and Memory Data Register (MDR) (not shown in Fig.) − interface with
memory.
Control Unit (CU) − decodes and executes instructions.

Advantages:
• Simplicity of design
• Fewer bits per instruction
• Faster execution for small programs
• Cost-effectiveness – useful in simple embedded systems

Disadvantages:
• Limited flexibility − only one accumulator; cannot hold multiple intermediate results
simultaneously
• Frequent memory access − for every new operand, data must be fetched from memory,
increasing access time
• Difficult optimization − limited opportunity for instruction-level parallelism.
• Not scalable − inefficient for large programs and complex computations

General Registers Based Computer Organization

A general-purpose register-based computer organization uses a set of high-speed general-purpose

registers (GPRs) within the CPU to store data, instead of relying on a single accumulator. This
organization speeds up program execution by reducing the need to access main memory, as most
operations can be performed directly on the data in the registers.

Instructions in this architecture typically use two or three address fields, which can specify a GPR or a
memory location.
Registers from R0 to R7 − the general-purpose registers
Program Counter (PC) − holds the address of the next instruction.
Instruction Register (IR) − holds the current instruction.
Arithmetic Logic Unit (ALU) − performs arithmetic/logic operations, one input from ACC.
Memory Address Register (MAR) and Memory Data Register (MDR) (not shown in Fig.) − interface with
memory.
Control Unit (CU) − decodes and executes instructions.

Let’s say, we want to compute: Z = (A + B) – C

The sequence of operations are as follows:
1. LOAD R1, A ; Load number A into R1 register
2. LOAD R2, B ; Load number B into R2 register
3. ADD R3, R1, R2 ; Add R1 & R2, and store the sum in R3
4. LOAD R1, C ; Load number C into R1
5. SUB R3, R3, R1 ; Subtract R1 from R3

Advantages:
• High speed − operands in registers, faster ALU operations
• Reduced memory access − fewer load/store cycles.
• Efficient use of CPU time − multiple registers support overlapping of operations (pipelining).
• Flexibility − any register can be used for arithmetic, logic, or address calculations.

Disadvantages:
• More complex control logic − decoder and data paths are larger.
• Larger instruction size − extra bits needed to specify register addresses.
• Hardware cost − more registers increase area and power.
• Context switching overhead − saving/restoring many registers during interrupts or task
switches.

Stack-Based Computer Organization

Stack-based computer organization uses a Last-In, First-Out (LIFO) structure called a stack for memory
management, data storage, and arithmetic operations. It is managed by a stack pointer (SP) that points
to the top element. The two primary operations are PUSH (adding an item to the top) and POP
(removing the top item).

In a stack-based computer, all arithmetic, logic, and data-handling operations are performed using a
stack rather than named registers or accumulators. Operands for any operation are implicitly taken
from the top elements of the stack. Results are pushed back onto the stack.

Hence, instructions do not need to specify operands explicitly, making instruction format very compact.
The instruction mode used here is “implicit” or “implied”.

Block diagram of stack-based computer:

Program Counter (PC) − points to next instruction.
Instruction Register (IR) – holds current instruction.
Stack Pointer (SP) – points to the top of the stack (TOS).
Stack Memory – stores operands and intermediate results.
ALU – performs operations on data from top of stack.
Control Unit – decodes instructions and generates control signals.

Example: Z = (A + B) × C
The sequence of operations are as follows:
1. PUSH A ; load number A to top of stack
2. PUSH B ; load number B to top of stack
3. ADD ; top of stack now contains A+B
4. PUSH C ; load number C to top of stack
5. MUL ; multiply the top two contents of stack
6. POP Z ; copy the product from stack to Z

Advantages
• Compact instructions − operands implicit; smaller program size.
• Simpler instruction decoding − no need to parse operand fields.
• Less data path hardware − no multiple registers required.
• Useful for high-level language execution − supports recursion and procedure calls easily.

Disadvantages:
• Difficult random access − operands accessible only in LIFO order.
• More data movement − frequent PUSH and POP operations cause stack overhead.
• Lower performance − compared to register machines, due to stack access latency.
• Limited parallelism − instructions highly sequential (each depends on top of stack).
 Addressing Modes in Computers

Addressing modes in computer architecture are techniques that determine how the CPU finds the
operand (the data) for an instruction, offering different ways to calculate the effective memory address.
Addressing modes provide flexibility in referring to operands.

Inherent / Implied / Implicit Addressing Mode

In this mode, the operand is implied by the operation itself. The instruction does not explicitly mention
any operand because the operation inherently knows where to act. Used in Single-operand instructions,
especially in accumulator- and stack-based processors.

Examples:
CLA ; Clear the accumulator
CMA ; Complement the accumulator
ADD ; Add the top two contents of stack

Immediate Addressing Mode

The operand (data) is given within the instruction itself; not stored in memory. The execution of the
instruction is faster because memory fetch is not required. The disadvantage is that the value of the data
is fixed and cannot be changed dynamically.

Examples:
MOV R1, #25 ; Move the immediate data 25 to register R1.
ADD R2, #36 ; Add 36 to the content of R2 register.
SUB R3, #10 ; Subtract 10 from the R3 register.

Register Addressing Mode

The operand is located in a CPU register. The instruction specifies the name of the register that holds
the operand. Advantage: very fast execution; Disadvantage: limited number of registers in CPU.

Examples:
MOV R1, R2 ; Copy the contents of register R2 into R1.
ADD R3, R1, R2 ; Add the contents of R1 & R2 and copy the sum to R3.
SUB R3, R1, R2 ; Subtract the content of R2 from R1 and copy the result into R3.

Direct / Absolute Addressing Mode

The instruction contains the absolute memory address where the operand is located. The advantage is
that we can directly specify the address in the instruction. The disadvantage is that the range of
addresses is limited.
Examples:
MOV A, 2050H ; Move data from memory location 2050H into register A.
ADD R1, 3000H ; Add the data which is present in location 3000H to R1 register.
INC 4000H ; Increment the content of location 4000H by one.

Register Indirect Addressing Mode

The register holds the address of the memory location where the operand is located. That is, the CPU
accesses memory indirectly through the register. Advantage: Allows access to a range of memory using
a small instruction. Disadvantage: One extra memory access is needed to fetch the operand.

Examples:
MOV AX, [SI] ; Move data from memory location pointed to by the register SI into AX register.
If SI = 2050H, then operand = contents of memory[2050H].
MOV [DI], AX ; Move the date from AX register to memory pointed by DI register
If DI = 2050H, then AX is stored in the memory with address 2050H.

Indexed / Displacement Addressing Mode

The address of the operand is obtained by adding a constant which is specified in the instruction to the
content of a register. That is, Effective Address (EA) = Base Address (in register) + [Link].
Advantage: Excellent for accessing array elements. Disadvantage: Slightly more complex address
calculation

Examples:
MOV AX, [BX + 05H] ; Copy the operand from memory whose address is (BX + 5) to AX register
MOV R2, 1000[R2] ; Copy the operand from memory whose address is R2+1000 to R2 register.

Auto Increment Addressing Mode

After accessing the operand through a register-indirect method, the register’s value is automatically
incremented to point to the next operand. Advantage: Ideal for accessing sequential memory (like
arrays). Disadvantage: Only useful for sequential access, not random access.

Example:
MOV R2, R1+ ; Move data from memory pointed by R1 to R2, then increment R1.

Auto Decrement Addressing Mode

The content of register is decremented first, and then the operand is accessed from memory through
register-indirect method. Advantage: Useful for stack operations (LIFO) and sequential memory.
Disadvantage: Not suitable for forward memory traversal or random access.

Example:
MOV R2, R1- ; Decrement R1, then move data from memory [R1] to R2.
Relative Addressing Mode

The effective address is obtained by adding a constant specified in the instruction to the program
counter (PC). This is used during branch or jump operations. Advantage: Enables position-
independent code; that is, physical address does not matter. Disadvantage: Limited range (127 bytes
forward or 128 bytes backward).

Example:
JMP 100 ; Jump to the instruction which is 100 bytes ahead of the current PC value.
JMP -100 ; Jump to the instruction which is 100 bytes behind the current PC value.

Instruction Formats based on Number of Addresses/Operands

Every instruction in a computer’s instruction set tells the CPU what operation to perform and where to
find the operands. Depending on how many operand addresses an instruction explicitly specifies,
instruction formats are categorized into four major types:

Zero-address, One-address, Two-address, and Three-address instructions.

Each corresponds to a different CPU organization (stack, accumulator, or general register based).

Zero Address Instructions

It is used primarily in stack-based organizations. The operands are implicitly available on the top of the
stack. No need to mention operand addresses explicitly. Result is also pushed back onto the stack.
Advantages: Very compact instructions; Simpler decoding.
Disadvantages: Many PUSH/POP instructions are required; Random access is not possible (only LIFO).

Example: Z = A+B×C
PUSH A ; Copy the content of A to top-of-stack (TOS)
PUSH B ; Copy the content of B to TOS
ADD ; Add the top two contents of stack and store the sum back in TOS
PUSH C ; Copy the content of C to TOS
MUL ; Multiply the top two contents of the stack and store product in TOS
POP Z ; Copy the product from TOS to Z

One Address Instructions

It is used in accumulator-based architecture. One operand is implicitly in the accumulator (AC), whereas
the other operand’s address is explicitly specified in the instruction.
Advantage: Short instruction (opcode + one address); simpler hardware design
Disadvantage: Frequent memory access for every new operand; not efficient for executing complex
expressions.

Example: Z = A+B×C
 LOAD B ; ACC ← B
MUL C ; ACC ← ACC × C
ADD A ; ACC ← ACC + A
STORE Z ; D ← ACC

Two Address Instructions

This is used commonly in general purpose register architectures. Each instruction specifies two
addresses: Source operand (in register or memory) and Destination operand (in register or memory).
Advantages: Reduced memory traffic – results are kept in registers; Moderate instruction size (opcode
+ two addresses)
Disadvantages: Longer instructions (two address fields); One operand is overwritten by the result; May
require multiple instructions to complete a complex expression.

Example: Z = A+B×C
MOV R1, B ; R1 ← B
MUL R1, C ; R1 ← R1 × C
ADD R1, A ; R1 ← R1 + A
MOV Z, R1 ; Z ← R1

Three Address Instructions

It is used in general purpose register architectures. Each instruction explicitly specifies two source
operands, and one destination operand.
Advantages: High flexibility – all operands are present in registers; No overwriting of registers; Ideal for
pipelining; Minimum memory access.
Disadvantages: Longer instruction length – opcode + three addresses; More complex hardware.

Example: Z = A+B×C
MUL R1, B, C ; R1 ← B × C
ADD Z, A, R1 ; Z ← A + R1

Exercises:

Write codes to execute the following instructions using 0, 1, 2 and 3 address instructions:
(i) Z = (A+B) × (C+D)
(ii) Z = (A×B) + (B×C)
(iii) Z = A×B − C
 Multiplication in Computers

1. Sequential Multiplier

In small systems (such as a calculator) where high-speed operation is not necessary, two unsigned
numbers can be multiplied using an iterative approach called Sequential Multiplier.

Example: Multiplicand = M = 5 = 0101 Multiplier = Q = 12 = 1100

A Q
Initial values 0000 1100
Iteration #1
Q(0) = 0. Hence no addition
Right Shift AQ 0000 0110
Iteration #2
Q(0) = 0. Hence no addition
Right Shift AQ 0000 0011
Iteration #3
Q(0) = 1. Hence A  A + M 0101 0011
Right Shift AQ 0010 1001
Iteration #4
Q(0) = 1. Hence A  A + M 0111 1001
Right Shift AQ 0011 1100
 Product = AQ = 0011 1100 = 60. (5 ×12 = 60)

For signed numbers, the following changes need to be done:

If sign-bit (MSB) of M is 1, then compute the complement of M, else leave M as it is.
If sign-bit of Q is 1, then compute the complement of Q, else leave Q as it is.
Multiply n–1 bits of M and Q to obtain the product.
Compute S = (sign-bit of M) ⊕ (sign-bit of Q) XOR operation
If S = 1, then compute the complement of the product, else leave as it is.

2. Booth’s Multiplier

This algorithm makes use of the string property, that is, it inspects two bits of the multiplier at a time
and decides which action to perform, either addition or subtraction. This method can be used for both
signed and unsigned multiplications.
Example: Multiplicand = M = −4 = 1100 Multiplier = Q = +7 = 0111

A Q
Initial values 0000 01110 Bit pair = 10 → subtraction
Iteration #1
AA–M 0100 01110
Right Shift AQ 0010 00111 Bit pair = 11 → no add/sub
Iteration #2
Right Shift AQ 0001 00011 Bit pair = 11 → no add/sub
Iteration #3
Right Shift AQ 0000 10001 Bit pair = 01 → addition
Iteration #4
AA+M 1100 10001
Right Shift AQ 1110 01000 Product = 1110 0100

Note: Here, while shifting, the sign bit is retained the same (this is called arithmetic right shift).
Final product = 1110 0100 = −27 + 26 + 25 + 22 = −28

Exercises:

Use Booth’s algorithm to multiply:

(i) +14 (multiplicand) by −8 (multiplier), where each number is represented using 6 bits
(ii) -10 (multiplicand) and +6 (multiplier), where each number is represented using 6 bits.
(iii) -23 (multiplicand) by -11 (multiplier), where each number is represented using 6 bits

Hint: +14 = 001110 -14 = 110010

+8 = 001000 -8 = 111000
+10 = 001010 -10 = 110110
+23 = 010111 -23 = 101001
 Memory Unit of a Computer System

The memory unit of a computer is a fundamental component responsible for storing data,
instructions, and intermediate results that are used during processing. It provides the necessary
space for a computer to hold programs and data both temporarily and permanently. The memory system
plays a crucial role in determining the speed, performance, and efficiency of the entire computing
system.

Classification of Computer Memory

Broadly, computer memory is classified into three main categories:

1. Internal Memory
2. Main Memory
3. Secondary Memory
Each serves a distinct function within the memory hierarchy.

1. Internal Memory

Internal memory refers to the small, high-speed memory components located inside the CPU or
directly accessible by it. It provides the fastest access time and holds data or instructions currently
being executed.

Types of Internal Memory

1. CPU Registers
o Smallest and fastest memory units.
o Hold temporary data, instructions, and addresses during execution.
o Examples: Accumulator, Instruction Register (IR), Program Counter (PC), and general-
purpose registers.
o Access time: in nanoseconds.

2. Cache Memory
o Acts as a buffer between CPU and main memory.
o Stores copies of frequently accessed data/instructions to reduce average access time.
o Typically organized into L1, L2, and L3 levels:
▪ L1 Cache: Inside CPU core, smallest (e.g., 64 KB), fastest.
▪ L2 Cache: On-chip but shared by cores, larger (e.g., 512 KB – 2 MB).
▪ L3 Cache: Shared by multiple cores, slower but larger (e.g., 4–20 MB).

Characteristics
• Very high speed.
• Limited storage capacity.
• Volatile (data lost when power is off).
• Essential for CPU performance optimization.
2. Main Memory

Main memory is the primary working memory of the computer system where data and programs in
active use are stored temporarily. It provides a bridge between the CPU and secondary storage.

Types of Main Memory

1. RAM (Random Access Memory)

o Volatile memory — data is lost when power is switched off.
o Read/write operations are possible.
o Directly addressable by the CPU.
o Two types:
▪ Static RAM (SRAM):
▪ Uses flip-flops to store bits.
▪ Faster, costlier, and used in cache memory.
▪ Dynamic RAM (DRAM):
▪ Uses capacitors and transistors.
▪ Slower, cheaper, and denser — used in main memory modules.

2. ROM (Read-Only Memory)

o Non-volatile — retains data even without power.
o Data is permanently written during manufacturing or programming.
o Stores firmware or system programs (e.g., BIOS).
o Types:
▪ PROM (Programmable ROM): Can be programmed once.
▪ EPROM (Erasable PROM): Can be erased using UV light and reprogrammed.
▪ EEPROM (Electrically Erasable PROM): Can be erased and rewritten electrically.
▪ Flash Memory: A type of EEPROM used in USB drives and SSDs.

Functions of Main Memory

• Stores the operating system.
• Holds application programs currently in execution.
• Contains data required for ongoing processing.

Characteristics
• Moderate speed compared to internal memory.
• Limited capacity (typically GBs in modern systems).
• Directly accessible by the CPU.
• Volatile in nature (for RAM).

3. Secondary Memory

Secondary memory (or external memory) provides permanent data storage for programs and files
that are not actively in use. It is non-volatile and used to store large volumes of data cost-effectively.

Examples of Secondary Memory

1. Magnetic Storage Devices:

 o Hard Disk Drives (HDDs)
o Magnetic Tapes (used for backups and archiving)
2. Optical Storage Devices:
o CDs (Compact Discs)
o DVDs (Digital Versatile Discs)
o Blu-ray Discs
3. Solid-State Devices:
o SSDs (Solid-State Drives)
o USB Flash Drives
o Memory Cards
4. Cloud and Network Storage:
o Online data storage and backup systems (e.g., Google Drive, OneDrive).

Characteristics
• Non-volatile — retains data permanently.
• Slower than main memory but much larger in capacity (TBs or PBs).
• Data must be loaded into main memory for CPU access.
• Cost per bit is much lower than primary memory.

Functions
• Long-term storage of programs, data, and backups.
• Stores files, multimedia, databases, and system images.
• Supports data archiving and retrieval.

Cache Memory
(Pronounced as Cashay)

The cache memory is a small, high-speed memory unit located between the CPU and main memory
(RAM). It stores frequently accessed instructions and data, thereby reducing the average time to
access data from the main memory.

Because CPU speed is much higher than that of main memory, a speed mismatch exists. Cache memory
acts as a buffer to minimize this mismatch and improve system performance.

Need for Cache Memory

• The CPU operates at nanosecond speeds, while RAM operates at tens or hundreds of
nanoseconds.
• If the CPU must always wait for data from RAM, its processing speed reduces drastically.
• Cache memory stores copies of frequently used data and instructions, allowing the CPU to
access them much faster.
• The goal is to reduce the average memory access time (AMAT).
Basic Working Principle

1. When the CPU needs to read data:

o It first checks if the data is present in the cache memory.
o If found, it’s a cache hit.
o If not found, it’s a cache miss, and the data is fetched from the main memory.
2. The fetched data from the main memory is then copied into the cache for future use.
3. The cache controller automatically handles these operations, keeping track of what data is stored
where.

Cache Hit
A cache hit occurs when the CPU finds the required data in the cache memory.
• Access time is very small (a few nanoseconds).
• The CPU proceeds without accessing the main memory.

Cache Miss
A cache miss occurs when the required data is not present in the cache.
• The data is fetched from main memory, which takes longer.
• The cache is then updated with the fetched data for future use.

Hit Ratio
The hit ratio is the fraction of memory accesses found in the cache.
It measures cache performance.

Number of cache hits

Hit Ratio (h) =
Total number of memory accesses

• Typical hit ratios are between 90% to 99% in modern systems.

Miss Ratio
Miss Ratio (m) = 1 − Hit Ratio

It indicates how often the CPU must access main memory.

Access Time

The average memory access time (AMAT) or effective access time (EAT) is given by:

EAT = (Hit ratio × Cache access time) + (Miss ratio × Main memory access time after a cache miss)

𝐸𝐴𝑇 = 𝑇𝑒𝑓𝑓 = ℎ 𝑡𝑐 + (1 − ℎ)(𝑡𝑐 + 𝑡𝑚 )

This equation shows how the cache improves the effective speed of memory operations.

Efficiency of cache memory system is:

𝑡
Λ = 𝑐⁄𝑇
𝑒𝑓𝑓
Examples:

1. Calculate the average memory access time and efficiency of a cache memory system if access time for
cache memory is 160 ns, access time for main memory is 960 ns and cache hit ratio is 0.9.

Solution:
Average access time = 𝑇𝑒𝑓𝑓 = ℎ 𝑡𝑐 + (1 − ℎ)(𝑡𝑐 + 𝑡𝑚 )
= 0.9 × 160 + (1 − 0.9)(160 + 960) ns
= 256 ns
𝑡𝑐
Efficiency = Λ = ⁄𝑇 = 160/256 = 0.625 = 62.5%
𝑒𝑓𝑓

2. A cache memory system has 95% hit ratio, an access time of 100 ns for a cache hit and an access time
of 800 ns for a cache miss. Compute the effective access time and efficiency.

Solution:
Here consider tc = 100 ns and tc + tm = 800 ns
Teff = 0.95×100 + (1−0.95)×800 = 135 ns
Efficiency = 100 / 135 = 0.74 = 74%

Cache Mapping Techniques

Since cache memory is smaller than main memory, an efficient mapping technique is required to decide
where to store a particular block of main memory in the cache. There are three major mapping
techniques:

A. Direct Mapping
B. Fully Associative Mapping
C. Set-Associative Mapping

Levels of Cache

Modern CPUs use multi-level caching to optimize speed and capacity trade-offs:
Level Location Size Speed Function
L1 Small
Inside CPU core Fastest Immediate access
Cache (32–128 KB)
Medium
L2 On CPU chip (shared or per-
(256 KB–2 High speed Backup for L1
Cache core)
MB)
L3 Large Slower than Reduces main memory
Shared among cores
Cache (4–20 MB) L2 access
L4 Improves system-level
Optional (on motherboard) Very large Slower
Cache caching

Conclusion

Cache memory plays a crucial role in bridging the speed gap between the CPU and main memory.
By intelligently storing and managing frequently accessed data, it achieves:

• Reduced memory access time,

• Improved CPU utilization, and
• Enhanced overall system performance.

Data Transfer Between CPU and I/O Devices

In a computer system, the CPU (Central Processing Unit) performs computations, while I/O
(Input/Output) devices handle data exchange with the external world − such as keyboards, printers,
disk drives, and network cards.

Since I/O devices are typically slower than the CPU and memory, an efficient mechanism is required
to synchronize data transfer between them.

The communication between CPU and I/O devices is managed through the I/O interface (or controller),
which acts as a link between high-speed CPU/memory and low-speed peripherals.

I/O Interface Functions:

• Converts signals between CPU and peripheral formats.
• Provides control and status registers for synchronization.
• Handles data buffering to manage speed differences.
• Generates interrupts or DMA requests as needed.
Methods of Data Transfer

There are three main techniques for data transfer between CPU and I/O devices:

1. Programmed I/O
2. Interrupt-driven I/O
3. Direct Memory Access (DMA)

Each technique differs in how CPU involvement and control are handled.

1. Programmed I/O

In Programmed I/O (PIO), the CPU directly controls all data transfer operations between memory
and the I/O device by executing a program or set of instructions.

The CPU continuously polls (checks) the I/O device status register to determine whether it’s ready to
send or receive data.

Working Principle

1. CPU issues a command to the I/O device (e.g., READ or WRITE).

2. CPU keeps checking the status flag of the I/O device until it becomes “ready.”
3. When the device is ready, CPU transfers one word/byte of data between the device and its
register.
4. CPU repeats the process for each word, until the entire data transfer is complete.

This technique is simple but inefficient, as the CPU remains busy waiting for the I/O device.

Types of Programmed I/O

There are two ways to address I/O devices in programmed I/O systems:
(a) Isolated (or Direct) I/O and (b) Memory-mapped I/O

(a) Isolated or Direct I/O

• Uses separate address space for memory and I/O devices.

• CPU uses special I/O instructions (e.g., IN and OUT in Intel x86) to access devices.

Example:

IN AL, 60H ; Read from I/O port 60H into AL register

OUT 61H, AL ; Write AL register to I/O port 61H

Features:

• Separate control signals for memory (MEMR/MEMW) and I/O (IOR/IOW).

• Limited address space for I/O (usually 256 or 65,536 ports).
Advantages:

• Clear distinction between memory and I/O space.

• Simple hardware implementation.

Disadvantages:

• Additional instructions required (IN, OUT).

• I/O operations cannot use memory-based instructions.

(b) Memory-Mapped I/O

• I/O devices are assigned specific memory addresses in the same address space as normal
memory.
• The CPU can use standard data transfer instructions (like MOV, LD/ST) for I/O operations.
• No separate I/O instructions are needed.

Example:

MOV AL, [3000H] ; Read from I/O device mapped at 3000H

MOV [4000H], AL ; Write to I/O device mapped at 4000H

Features:

• Memory and I/O share the same address and control signals.
• I/O registers are treated like memory locations.

Advantages:

• Allows powerful addressing modes for I/O.

• Simplifies programming.
• Efficient for systems with many devices.

Disadvantages:

• Reduces available memory address space.

• May require more complex decoding circuitry.

2. Interrupt-Driven I/O

In Interrupt I/O, the CPU does not continuously poll the I/O device. Instead, the device notifies the
CPU via an interrupt signal when it is ready for data transfer.

This allows the CPU to perform other tasks while the I/O device completes its operation.

Working Principle
 1. CPU initiates an I/O operation and continues executing other instructions.
2. When the I/O device is ready, it sends an interrupt signal to the CPU.
3. The CPU pauses the current program and saves its state.
4. CPU “jumps” to a special routine called the Interrupt Service Routine (ISR) to handle the I/O
operation.
5. After the ISR is executed, the CPU resumes the interrupted task.

Advantages

• CPU time is efficiently utilized.

• No need for continuous polling.
• Fast response to device requests.

Disadvantages

• Slight overhead in saving and restoring CPU context.

• Requires interrupt-handling hardware and software.

Examples:

Printers, Disk controllers and Serial ports

3. Direct Memory Access (DMA)

Direct Memory Access (DMA) allows peripherals to transfer data directly to or from main memory
without involving the CPU for each byte or word transfer.

A dedicated hardware unit called the DMA Controller (DMAC) manages the process.

Need for DMA

• In large data transfers (e.g., disk or network), CPU-controlled I/O (Programmed or Interrupt) is
inefficient.
• DMA allows bulk data transfer at high speed without burdening the CPU.

Working Principle

1. CPU initializes the DMA controller with:

o Source address (memory location or I/O port)
o Destination address
o Number of bytes to transfer
o Direction of transfer (read/write)
2. DMA controller takes control of the system bus from the CPU (bus arbitration).
3. Data is transferred directly between I/O device and memory.
4. On completion, DMA controller sends an interrupt signal to the CPU indicating the end of
transfer.
DMA Transfer Modes

Mode Description
DMA transfers an entire block of data in one continuous sequence. CPU is idle
Burst Mode
during the transfer.
Cycle Stealing DMA transfers one word per cycle, “stealing” bus cycles from the CPU
Mode intermittently.
Transparent
DMA transfers data only when CPU is not using the bus. (CPU has highest priority.)
Mode

Advantages of DMA

• High-speed data transfer.

• CPU is free to perform other tasks.
• Efficient for large data blocks (e.g., disk, graphics, audio).

Disadvantages
• Complex hardware (requires DMAC).
• CPU and DMA may contend for memory access.

Comparison of different I/O Techniques

Feature Programmed I/O Interrupt I/O DMA

CPU Control Fully involved Partially involved Minimal
Data Transfer By CPU instructions By ISR By DMA controller
Efficiency Low Moderate High
Hardware Complexity Low Medium High
Suitable For Simple devices Moderate-speed devices High-speed devices
CPU Waiting Time High Low Very low
Example Keyboard Printer Hard Disk, GPU
 Pipelined and Non-Pipelined Processors

In a computer system, the CPU executes instructions that follow a sequence of steps such as fetching,
decoding, and executing.

The processor organization that determines how these steps are carried out for one or more
instructions gives rise to two major execution models:

1. Non-pipelined Processor – executes one instruction at a time, sequentially.

2. Pipelined Processor – allows overlapping execution of multiple instructions, like an assembly
line.

Non-Pipelined Processor

A non-pipelined processor executes only one instruction at a time.

Each instruction must complete all stages (fetch, decode, execute, etc.) before the next one begins.

Operation

If an instruction requires k stages (say, 5 stages), and each stage takes 1 clock cycle,
then the total time per instruction = k clock cycles.

Example

Let each instruction need 5 stages:

• IF (Instruction Fetch)
• ID (Instruction Decode)
• EX (Execute)
• MEM (Memory Access)
• WB (Write Back)

For a non-pipelined processor:

Instruction 1: IF → ID → EX → MEM → WB
Instruction 2: starts only after Instruction 1 completes

Total cycles required to execute n instructions:

𝑇𝑛𝑜𝑛−𝑝𝑖𝑝𝑒 = 𝑛 × 𝑘

For example, if n = 5 and k = 5, then the CPU requires 25 clock cycles to complete.

Characteristics

• Simple control logic.

• No overlapping; low throughput.
 • Easier to design and debug.
• Inefficient CPU utilization — many resources remain idle during part of the cycle.

Pipelined Processor

A pipelined processor divides instruction execution into multiple stages and allows overlapping of
different stages from successive instructions.

Just like an assembly line, while one instruction is being executed, the next instruction is decoded, and
another is fetched — simultaneously.

What is a Pipeline?

A pipeline in a processor is a sequence of processing stages where:

• Each stage performs a specific sub-task.

• All stages operate in parallel on different instructions.
• Intermediate results flow from one stage to the next.

Each stage typically takes one clock cycle. After the pipeline is filled, one instruction completes every
clock cycle.

a) 3-Stage Pipeline

Common in simple microcontrollers and early processors.

Stage Name Function

1 Instruction Fetch (IF) Fetch instruction from memory
2 Instruction Decode (ID) Decode instruction, fetch operands
3 Execute (EX) Perform operation and store result

After pipeline filling, one instruction completes every cycle.

5-Stage Pipeline

Typical in RISC architectures (e.g., MIPS, ARM).

Stage Name Function

1 IF – Instruction Fetch Fetch instruction from memory
2 ID – Instruction Decode / Register Fetch Decode opcode, read operands
3 EX – Execute / Address Calculation Perform ALU operation or compute address
4 MEM – Memory Access Read/write from/to data memory
5 WB – Write Back Write result back to register file
This structure forms the classic 5-stage instruction pipeline.

Timing of Pipelined Execution

Let each stage take 1 clock cycle (k = 5).

Cycle Stage 1 Stage 2 Stage 3 Stage 4 Stage 5

1 IF₁ – – – –
2 IF₂ ID₁ – – –
3 IF₃ ID₂ EX₁ – –
4 IF₄ ID₃ EX₂ MEM₁ –
5 IF₅ ID₄ EX₃ MEM₂ WB₁
6 – ID₅ EX₄ MEM₃ WB₂
7 – – EX₅ MEM₄ WB₃
8 – – – MEM₅ WB₄
9 – – – – WB₅

Thus, the first instruction finishes after 5 cycles (pipeline filling), and each subsequent instruction
finishes every 1 cycle thereafter.

Performance Analysis:

Let: k = number of pipeline stages; n = number of instructions

Then:

Non-pipelined total time:

𝑇𝑛𝑜𝑛 = 𝑛 × 𝑘

Pipelined total time:

𝑇𝑝𝑖𝑝𝑒 = 𝑘 + (𝑛 − 1)

Speedup (ideal):
𝑇𝑛𝑜𝑛 𝑛×𝑘
𝑆= =
𝑇𝑝𝑖𝑝𝑒 𝑘 + (𝑛 − 1)

As n → ∞ (many instructions),
𝑆𝑚𝑎𝑥 ≈ 𝑘

→ meaning a k-stage pipeline can ideally be k times faster than a non-pipelined processor.
Example:

For 5 instructions, 5-stage pipeline:

𝑇𝑛𝑜𝑛 = 25 cycles, 𝑇𝑝𝑖𝑝𝑒 = 5 + (5 − 1) = 9 cycles

So the effective speedup ≈ 25 / 9 ≈ 2.78

Advantages of Pipelining

• Increased throughput: Several instructions completed per unit time.

• Better resource utilization: All functional units kept busy.
• Improved CPU performance without increasing clock speed.

Disadvantages

• Increased hardware complexity.

• Hazards can reduce efficiency.
• Unequal stage delays may cause pipeline imbalance.
• Additional circuitry required for hazard detection and forwarding.

Summary

Feature Non-Pipelined Processor Pipelined Processor

Instruction Execution Sequential Overlapped
CPU Utilization Low High
Throughput 1 / k instructions per cycle ≈ 1 instruction per cycle
Latency per Instruction k cycles k cycles
Hardware Complexity Simple Complex
Speedup 1× Up to k× (ideal)
Example 8085 (simple microprocessor) MIPS, ARM, Pentium, RISC-V

Real-World Pipeline Structures

Architecture Pipeline Depth Notes

Intel 8086 2-stage Fetch, Execute
MIPS R2000 5-stage Classic RISC pipeline
Intel Pentium 4 ~20 stages Deep pipeline for high clock speed
ARM Cortex-A Series 8–14 stages Superscalar, multi-issue pipelines

Deep pipelines enable high clock rates but increase branch penalties and power consumption.
 Pipeline Hazards (Limitations)

A pipeline hazard is any situation that prevents the next instruction in the instruction stream from
executing during its designated clock cycle.

Hazards cause pipeline stalls (bubbles), reducing overall speedup and efficiency.

There are three main categories of hazards:

1. Structural Hazards
2. Data Hazards
3. Control Hazards

1. Structural Hazards

Structural hazards occur when two or more pipeline stages need the same hardware resource at
the same time.

Since most CPU pipelines share resources like memory or registers, conflicts can occur, preventing one
instruction from proceeding.

Example 1: Memory Conflict

In a 5-stage pipeline (IF–ID–EX–MEM–WB):

• The IF stage (Instruction Fetch) needs to access Instruction Memory.

• The MEM stage (Memory Access) needs to access Data Memory.

If instruction and data share the same memory, both stages cannot access it simultaneously.

Solutions:

• Use separate instruction and data memories (Harvard Architecture).

• Introduce memory interleaving.
• Insert a pipeline stall (bubble) until the resource becomes available.

Example 2: Register File Access Conflict

If register file allows only one access per cycle, and two instructions need simultaneous read/write,
structural hazard arises.

Solutions:

• Use multiport register files.

• Schedule instructions to avoid simultaneous access.
2. Data Hazards

Data hazards occur when an instruction depends on the result of a previous instruction that has
not yet completed its passage through the pipeline.
They arise because instructions are overlapped − the result of one instruction may not be ready when
another instruction needs it.

Types of Data Hazards

There are three types based on the read/write dependencies between instructions:

Type Dependency Example Description

RAW Read After Write True dependency Instruction needs data produced by previous instruction
WAR Write After Read Anti-dependency Instruction writes before previous instruction has read
Output Two instructions write to same destination in wrong
WAW Write After Write
dependency order

RAW (Read After Write) Hazard

Example:

I1: ADD R1, R2, R3 ; R1 = R2 + R3

I2: SUB R4, R1, R5 ; R4 = R1 - R5

Here:
• I2 needs the value of R1 produced by I1.
• But I1 writes to R1 only in WB stage, while I2 reads R1 in ID stage — too early!

Solutions:

1. Data Forwarding (Bypassing):

o Forward the result directly from EX/MEM stage of I1 to EX stage of I2.
2. Pipeline Stall:
o Delay I2 until I1 completes its WB stage (inserting NOPs or bubbles).

WAR (Write After Read) Hazard

Occurs when an instruction writes a register before a previous instruction has read it.
This can happen in out-of-order pipelines (not in simple in-order 5-stage pipelines).

Example:

I1: SUB R4, R1, R2 ; Reads R1

I2: ADD R1, R3, R5 ; Writes R1

If I2 writes to R1 before I1 reads it, the correct value of R1 is lost.

Solutions:

• Maintain in-order execution for register reads/writes.

• Use register renaming (assign a new physical register for each write).

WAW (Write After Write) Hazard

Occurs when two instructions write to the same register, and the writes occur out of order.

Example:

I1: MUL R2, R3, R4 ; Writes R2

I2: ADD R2, R5, R6 ; Writes R2

If I2 finishes before I1, R2 ends up with the wrong value.

Solutions:

• In-order completion of instructions.

• Register renaming (used in superscalar/out-of-order processors).

3. Control Hazards

Control hazards (also called branch hazards) occur when the pipeline makes wrong decisions on
branch predictions or cannot determine the next instruction address in time.

They arise due to branch or jump instructions that alter the normal sequential flow.

Example:

I1: JEQ R1, R2, LABEL ; jump if equal (jump if zero flag is set)
I2: ADD R3, R4, R5
I3: SUB R6, R7, R8
LABEL: MUL R9, R10, R11

If the branch (I1) is taken, instructions I2 and I3 (already fetched) are invalid.
If not taken, execution continues sequentially.

Since the branch outcome is known only after the EX-stage, the pipeline may have already fetched the
wrong instructions.

Solutions

Pipeline Stall (Flushing)

• Stop fetching new instructions until branch decision is known.

 • Flush wrong-path instructions from pipeline if branch is taken.

Branch Prediction

• Static prediction: Assume branch is not taken (default), or always taken.

• Dynamic prediction: Use branch history table (BHT) or two-bit saturating counters to guess
future branches based on past behavior.

If prediction is correct → no stall;

if wrong → flush pipeline and reload correct path.

Delayed Branching
• Compiler schedules a useful instruction (independent of branch) into the branch delay slot.

Summary

Type Cause Example Typical Solution

IF & MEM both access
Structural Resource conflict Separate memories or stalls
memory
ADD → SUB using same
Data (RAW) Data dependency Forwarding or stalls
register
Data (WAR, Out-of-order
Writes/read conflicts Register renaming
WAW) access
Branch prediction, delay slot,
Control Branch or jump BEQ instruction
flush

Conclusion

• Pipeline hazards limit ideal speedup.

• Structural, data, and control hazards require careful hardware and compiler techniques.
• Modern CPUs use forwarding, prediction, renaming, and speculative execution to minimize
hazard penalties.
• Despite hazards, pipelining remains the most effective method to enhance processor
throughput.
 Bus Arbitration in Computer Systems

In a computer system, the system bus is a shared communication pathway that connects the CPU, main
memory, and I/O devices.

It carries address, data, and control signals for transferring information among these components.

However, since multiple devices may request control of the bus simultaneously, a mechanism is
required to
decide which device gains access to the bus at a given time.

This mechanism is called Bus Arbitration.

What is Bus Arbitration?

Bus arbitration is the process of selecting one bus master (e.g., CPU, DMA controller, or I/O device)
from multiple bus requesters, so that only one can control and use the shared system bus at any
moment.

The device that currently has control is called the bus master, while others must wait.

Why is Bus Arbitration Required?

a) To Avoid Bus Contention

• Multiple masters (CPU, DMA, I/O controllers) may simultaneously request the bus.
• Without arbitration, simultaneous access attempts could cause data corruption or electrical
conflicts.

b) To Ensure Fair and Efficient Sharing

• Arbitration ensures fairness and predictable timing, especially in systems with real-time
constraints.

c) To Control Access Priority

• Some devices (e.g., DMA controller) may require higher priority than others (e.g., printer
controller).
• Arbitration allows priority-based or time-based control of bus usage.

d) To Optimize Bus Bandwidth Utilization

• Proper arbitration minimizes idle bus time and improves overall system throughput.

Basic Bus Arbitration Mechanism

The arbitration process generally involves the following steps:

1. Bus Request (BR):

 Each device that needs the bus sends a request signal to the arbiter.
2. Bus Arbitration Decision:
The arbiter decides which requester will get the bus based on a chosen protocol (priority,
time, lottery, etc.).
3. Bus Grant (BG):
The arbiter sends a grant signal to the selected master.
4. Bus Use:
The selected master transfers data across the bus.
5. Bus Release:
After completion, the master releases the bus and other devices may compete again.

Types of Bus Arbitration Schemes

A. Centralized Arbitration

• A single bus arbiter (hardware or CPU logic) controls the entire arbitration process.
• All devices send their requests to this central arbiter.

Features

• Simple and fast for small systems.

• Arbiter decides who gets access — using priority logic or rotating schemes.

Example Methods

1. Static Priority-based Protocol

2. Dynamic Priority / Rotating Priority
3. Time Division Multiple Access (TDMA)
4. Lottery-based Protocol

1. Static Priority-Based Protocol

Each device is assigned a fixed priority level.

When multiple devices request the bus simultaneously, the arbiter grants it to the highest-priority
device.

Example:

CPU – Highest priority; DMAC – medium priority; I/O – lowest priority

Advantages
• Simple and fast.
• Deterministic behavior — important for real-time systems.

Disadvantages

• Starvation: Low-priority devices may be perpetually denied access.

 • Poor fairness.

2. Dynamic Priority or Rotating Priority Scheme

• The priority order changes dynamically after each bus grant.

• The device that just used the bus is moved to the lowest priority position.

Advantage

• Ensures fairness among all devices.

Disadvantage

• Slightly more complex control logic.

3. TDMA-Based (Time Division Multiple Access) Protocol

• Bus access is divided into time slots, and each device is pre-assigned a time slot to use the
bus.
• Each master is allowed to use the bus only during its allocated time slot, whether or not it has
data to transfer.

Advantages

• Predictable and periodic access.

• Ideal for real-time systems with strict timing needs.

Disadvantages

• Wasted bandwidth if a device has no data in its slot.

• Inflexible to dynamic workloads.

Bandwidth Allocation

• The bus bandwidth (data transfer capacity per unit time) is shared among devices according
to their assigned time slots. For instance, a high-speed device can be given more frequent
slots.

4. Lottery-Based (Probabilistic) Protocol

• Each bus master is given a number of “lottery tickets” proportional to its required share of
bandwidth.
• When multiple requests occur, the arbiter randomly picks a ticket — the corresponding master
wins bus control.

Example:
Device Tickets Probability of Winning
CPU 4 4/10
DMA 3 3/10
I/O 3 3/10

Advantages

• Flexible and supports probabilistic fairness.

• Adjustable bandwidth allocation by changing ticket counts dynamically.

Disadvantages

• Non-deterministic — not suitable for strict real-time systems.

• Slightly slower decision making.

Summary

Term Description
Process of deciding which master controls the shared bus at a
Bus Arbitration
time.
Centralized Arbitration Single arbiter manages all bus requests.
Distributed Arbitration All devices coordinate among themselves to decide access.
Static Priority Protocol Fixed priority; simple but may cause starvation.
TDMA Protocol Pre-allocated time slots; ensures deterministic access.
Lottery-Based Protocol Randomized selection using weighted tickets; ensures fairness.
Bandwidth Allocation Distribution of available bus capacity among devices.