Input-output organisation and pipelining notes — Unit 5

The CPU must communicate with external devices (Keyboard, Monitor, Hard Drive). However, the CPU operates in nanoseconds, while mechanical I/O devices operate in milliseconds. A direct connection would force the CPU to freeze while waiting for a slow device.

To resolve this speed mismatch, devices connect to the system bus via I/O Interfaces or Controllers (e.g., USB Controller).

⇒1.1 I/O Interface Registers

An interface contains Data Registers (to buffer data), Command Registers (to receive CPU orders), and Status Registers (flags indicating if the device is busy, ready, or in error).

There are three ways the CPU manages data transfer with I/O devices.

⇒2.1 Programmed I/O (Polling)

The CPU executes a program that takes direct, manual control of the I/O operation.

• 1. CPU issues a read command to the I/O interface.
• 2. The CPU enters a tight loop, constantly reading the Status Register to check if data is ready. (This is called Polling).
• 3. Once the Ready flag is 1, the CPU reads the data into its accumulator, stores it in memory, and loops back for the next byte.

Flaw: Terrible inefficiency. The CPU spends 99% of its time trapped in the polling loop, doing absolutely no useful computation, just waiting for a slow keyboard to send a keypress.

Solves the polling problem. The CPU issues a command to the I/O interface and then goes away to execute other useful programs.

⇒3.1 The Interrupt Mechanism

• When the I/O device finally has data ready, it sends a hardware electrical signal over a dedicated Interrupt Request (IRQ) line.
• The CPU finishes its current instruction, saves its state (Pushes PC to Stack), and jumps to a special subroutine called the Interrupt Service Routine (ISR).
• The ISR handles the data transfer.
• An `IRET` (Interrupt Return) instruction restores the PC, and the CPU resumes its original program exactly where it left off.

Benefit: The CPU never wastes time waiting. It is only involved exactly when data is ready.

What if multiple devices send an interrupt at the exact same time? The system needs a way to decide which device to service first. This is called a Priority Interrupt system.

⇒4.1 Daisy-Chaining (Hardware Priority)

All devices share a single interrupt line to the CPU. The CPU responds with an Interrupt Acknowledge (INTACK) signal.

The INTACK wire passes sequentially through device 1, then device 2, then device 3. If device 1 requested the interrupt, it blocks the signal and identifies itself on the data bus. If it didn't request it, it passes the signal down the chain.
Priority is strictly determined by physical distance to the CPU.

⇒4.2 Parallel Priority (Hardware Priority)

Each device has its own interrupt wire. These wires feed into a Priority Encoder chip. The encoder outputs the address of the highest-priority active line to the CPU.

Interrupts are fine for keyboards, but terrible for hard drives. If a hard drive interrupts the CPU to transfer 10 Megabytes of data byte-by-byte, the CPU is overwhelmed.

DMA is a technique where a specialized hardware chip (the DMA Controller) takes control of the system bus and transfers blocks of data directly between the I/O device and Main Memory, completely bypassing the CPU.

⇒5.1 The DMA Process

• 1. CPU initializes the DMA Controller with a starting memory address, a word count, and a Read/Write command.
• 2. CPU continues executing other code that doesn't require the system bus.
• 3. DMA requests the bus from the CPU (Bus Request). CPU grants it (Bus Grant).
• 4. DMA transfers the entire block of data directly to memory.
• 5. When finished, the DMA sends a single interrupt to the CPU.

When the DMA controller takes over the bus, the CPU is blocked from using memory. The DMA can transfer data in different ways to minimize CPU disruption.

⇒6.1 Burst Mode

The DMA takes control of the bus and refuses to give it back until the entire block of data (e.g., 4KB) is transferred. The CPU is completely halted during this time. Fast for I/O, but stalls the CPU.

⇒6.2 Cycle Stealing Mode

The DMA requests the bus, transfers a single byte/word, and immediately gives the bus back to the CPU. It repeatedly "steals" a single cycle whenever the CPU isn't using the bus. Slower transfer, but allows the CPU to continue executing instructions almost unhindered.

Pipelining is the most crucial architectural innovation for CPU speed. It is based on the concept of an assembly line in a factory.

⇒7.1 Non-Pipelined Execution

A standard instruction takes e.g., 4 cycles to finish: Fetch(F), Decode(D), Execute(E), Write-back(W).
In a non-pipelined CPU, Instruction 2 cannot even begin Fetching until Instruction 1 has completely finished Write-back.
Total time for 3 instructions = 12 cycles.

⇒7.2 Pipelined Execution

The hardware is divided into independent stages separated by buffer registers.
While Instruction 1 is being Decoded, the Fetch hardware is idle. So, we let it fetch Instruction 2 simultaneously!

Cycle 1: F1
Cycle 2: D1, F2
Cycle 3: E1, D2, F3
Cycle 4: W1, E2, D3, F4

After the pipeline fills up, one complete instruction finishes every single clock cycle, effectively a 4x speedup.

To evaluate pipeline efficiency mathematically:

Let $k$ = number of stages in the pipeline.
Let $n$ = number of tasks (instructions) to execute.

• Time for Non-Pipelined: $T_{np} = n \times k$ cycles.
• Time for Pipelined: $T_p = (k + n - 1)$ cycles. (It takes $k$ cycles to fill the pipe, then 1 cycle for each remaining $n-1$ instructions).

⇒8.1 Speedup Ratio (S)

$S = \frac{T_{np}}{T_p} = \frac{n \times k}{k + n - 1}$

As the number of instructions $n$ approaches infinity, the denominator simplifies to $n$. Therefore, Maximum Speedup $S_{max} = k$.
A 5-stage pipeline can ideally provide a 5x speedup.

In theory, pipelining is perfect. In reality, instructions interfere with each other, causing the pipeline to stall (insert a 'bubble'). These interferences are called Hazards.

There are three types of hazards:

• 1. Structural Hazards (Resource Conflicts)
• 2. Data Hazards (Data Dependencies)
• 3. Control Hazards (Branch Penalties)

A structural hazard occurs when two different stages of the pipeline try to use the exact same hardware resource at the same time.

⇒10.1 The Memory Conflict

Assume the CPU has only one main memory.
Instruction 1 is in the Write-back stage (trying to write data to memory).
Instruction 4 is in the Fetch stage (trying to read an instruction from memory).

Memory can only handle one request per cycle. The pipeline must stall Instruction 4 for one cycle.

⇒10.2 Hardware Solution

Harvard Architecture: Physically split the Cache into two separate units: an Instruction Cache and a Data Cache. The Fetch unit talks to the I-Cache, and the Write-back unit talks to the D-Cache, completely eliminating the structural hazard.

A data hazard occurs when an instruction depends on the result of a previous instruction that has not yet finished moving through the pipeline.

⇒11.1 RAW (Read After Write)

I1: `ADD R1, R2, R3` (Computes R2+R3 and writes to R1)
I2: `SUB R4, R1, R5` (Needs to read R1)

I2 enters the Decode stage (reads registers) while I1 is in the Execute stage. I1 hasn't reached the Write-back stage yet, so I2 reads the OLD, incorrect value of R1. The pipeline must stall I2 until I1 writes back.

⇒11.2 Hardware Solution: Operand Forwarding

Also called Bypassing. As soon as the ALU finishes adding R2 and R3 in I1, the result is forwarded via special wires directly into the ALU input for I2, without waiting for the Write-back stage. This eliminates most data stalls.

The most devastating hazard to pipeline performance. Occurs when a branch instruction alters the Program Counter.

⇒12.1 The Branch Penalty

Consider a `JUMP TARGET` instruction. The pipeline fetches it. While it's decoding it, it blindly fetches the next linear instruction (PC+1). While the jump executes, it fetches PC+2.

When the jump executes, the CPU realizes the PC is changing to TARGET. The instructions fetched from PC+1 and PC+2 are wrong. They must be flushed (thrown away) from the pipeline.

A branch instruction can cost 3 to 4 wasted clock cycles, crippling performance.

Since ~20% of all code instructions are branches, CPU designers go to extreme lengths to minimize branch penalties.

⇒13.1 Branch Prediction

Hardware guesses whether a conditional branch will be taken or not before the condition is evaluated.
Static: Always guess "Not Taken" (just keep fetching linearly) or "Always Taken" (for loops).
Dynamic: Hardware tracks the history of each branch. If a loop branched 99 times, it guesses it will branch the 100th time. If the guess is right, 0 penalty. If wrong, flush pipeline.

⇒13.2 Delayed Branch

A software trick used in RISC. The compiler rearranges the code, placing a useful instruction (that needs to execute anyway) directly after the branch instruction. The CPU guarantees that the instruction following a branch will always execute, so the pipeline doesn't have to flush it.

Unit 5 details the architectural tricks used to maximize CPU throughput.

⇒14.1 University Exam Checklist

• Explain the difference between Programmed I/O and Interrupt-driven I/O.
• Describe Daisy Chaining priority interrupt hardware.
• Explain the function of the DMA controller. Contrast Burst Mode with Cycle Stealing.
• Calculate the speedup of a 6-stage pipeline executing 100 instructions compared to a non-pipelined system.
• Define Structural, Data, and Control hazards.
• Explain Operand Forwarding (Bypassing) as a solution to Data hazards.
• What is a Branch Penalty? Explain how Branch Prediction attempts to solve it.