Pipelining, Instruction Pipeline, and Four-Segment Instruction Pipeline

1. What is Pipelining?

Pipelining is a technique used in computer architecture to improve the performance of a processor by overlapping the execution of multiple instructions. Instead of completing one instruction fully before starting the next, the processor divides instruction execution into a series of stages and processes different instructions simultaneously at different stages.

It is analogous to an assembly line in a factory: just as different workers perform different tasks on different products simultaneously, different pipeline stages work on different instructions at the same time.

Key Idea: Increase throughput (number of instructions completed per unit time) without necessarily reducing the time for a single instruction.

2. Instruction Pipeline

An instruction pipeline is a pipeline mechanism applied specifically to the execution of instructions in a CPU. The instruction execution process is divided into a sequence of steps (stages), and each stage is handled by a dedicated hardware unit. Multiple instructions can be in different stages of execution at the same time.

Benefits:

• Increases CPU throughput
• Better utilization of hardware resources
• Reduces idle time of functional units

Limitations:

• Pipeline hazards (data, control, structural)
• Overhead due to pipeline registers between stages
• Branch instructions can cause pipeline stalls

3. Four-Segment Instruction Pipeline

A common and fundamental model divides instruction execution into four stages (segments):

Stage-by-Stage Explanation

Stage 1: Instruction Fetch (IF)

• The Program Counter (PC) holds the address of the next instruction.
• The instruction is fetched from memory (or instruction cache) and loaded into the Instruction Register (IR).
• PC is incremented to point to the next instruction.

Stage 2: Instruction Decode (ID)

• The fetched instruction is decoded to determine the operation to be performed.
• Source operands are read from the register file.
• Control signals for subsequent stages are generated.

Stage 3: Execute (EX)

• The ALU performs the required operation (arithmetic, logical, address computation).
• For memory instructions: effective address is calculated.
• For branch instructions: branch condition is evaluated.

Stage 4: Write Back (WB)

• The result computed in the EX stage is written back to the destination register or memory location.
• This completes the instruction execution.

Timing Diagram of Four-Segment Pipeline

Assume each stage takes 1 clock cycle (t).

Instruction | Clock Cycle
            | 1    2    3    4    5    6    7
------------|--------------------------------
   I1       | IF   ID   EX   WB
   I2       |      IF   ID   EX   WB
   I3       |           IF   ID   EX   WB
   I4       |                IF   ID   EX   WB

Performance Analysis

Without Pipeline (Sequential Execution):

For n instructions, each taking k stages with each stage taking time t:

$$T_{sequential} = n \times k \times t$$

For 4 instructions, 4 stages: $$T_{sequential} = 4 \times 4 \times t = 16t$$

With Pipeline:

$$T_{pipeline} = (k + n - 1) \times t$$

For 4 instructions, 4 stages: $$T_{pipeline} = (4 + 4 - 1) \times t = 7t$$

Speedup:

$$S = \frac{T_{sequential}}{T_{pipeline}} = \frac{n \times k}{k + n - 1}$$

$$S = \frac{16t}{7t} \approx 2.28$$

For large n, speedup approaches k (the number of stages), which is the ideal speedup.

Diagram of Four-Segment Pipeline

         +------+    +------+    +------+    +------+
 Instr.  |  IF  | -> |  ID  | -> |  EX  | -> |  WB  |  -> Result
 Stream  | Fetch|    |Decode|    |Execut|    |Write |
         +------+    +------+    +------+    +------+
            S1          S2          S3          S4
         [Pipeline Registers between each stage]

Each stage is separated by pipeline registers (latches) that hold intermediate results and pass them to the next stage on each clock edge.

Summary

Pipelining is one of the most important performance enhancement techniques in modern processor design, forming the basis for more advanced techniques like superscalar and out-of-order execution.

Selective Set Logical Operation

Definition

Selective Set is a logical operation that uses the OR operation to selectively set (force to 1) specific bits of a register (operand A) based on a mask operand (operand B), while leaving the remaining bits unchanged.

• If a bit in the mask (B) = 1, the corresponding bit in the result is set to 1 (regardless of A).
• If a bit in the mask (B) = 0, the corresponding bit in the result remains unchanged (retains the value of A).

The operation is defined as:

$$A \leftarrow A \text{ OR } B$$

Key Principle

• Wherever B = 1, the bit is forced/set to 1.
• Wherever B = 0, the bit is left as it is.

Example

Let A = 1010 0110 and B (mask) = 0000 1111

  A  =  1010 0110
  B  =  0000 1111
        ---------
A OR B= 1010 1111

The lower 4 bits are all set to 1 by the mask.

Hardware Circuit of Selective Set Operation

The circuit uses OR gates for each bit position. Each OR gate takes one bit from register A and the corresponding bit from mask B as inputs.

Bit position:    n-1          ...         1           0
                  |                       |            |
         A[n-1] --+--\              A[1] -+--\   A[0] -+--\
                  |   OR --> R[n-1]       |   OR->R[1]  |   OR --> R[0]
         B[n-1] --+--/              B[1] -+--/   B[0] -+--/

Detailed Single-Bit Circuit (for one bit position):

        A[i] ----\
                  [OR Gate] -----> Result R[i]
        B[i] ----/

Full n-bit Circuit Diagram:

A[n-1] ---|        A[1] ---|        A[0] ---|
          | OR|-->R[n-1]   | OR|-->R[1]     | OR|-->R[0]
B[n-1] ---|        B[1] ---|        B[0] ---|

  (Each bit position has one OR gate)

+-------+     +-------+     +-------+     +-------+
| A[n-1]|     | A[2]  |     | A[1]  |     | A[0]  |
+---+---+     +---+---+     +---+---+     +---+---+
    |              |              |              |
   [OR]           [OR]           [OR]           [OR]
    |              |              |              |
+---+---+     +---+---+     +---+---+     +---+---+
| B[n-1]|     | B[2]  |     | B[1]  |     | B[0]  |
+-------+     +-------+     +-------+     +-------+
    |              |              |              |
  R[n-1]         R[2]           R[1]           R[0]

Summary

Virtual Memory

Definition

Virtual Memory is a memory management technique that allows a computer to execute programs that are larger than the available physical (main) memory by using a portion of the secondary storage (hard disk) as an extension of RAM.

It creates an illusion for the user/process that a very large memory space is available, even when the actual physical memory is limited.

Key Concepts

1. Virtual Address Space

• Each process is given its own virtual address space, which is independent of physical memory locations.
• The CPU generates virtual (logical) addresses, which are translated to physical addresses by the Memory Management Unit (MMU).

2. Paging and Demand Paging

• Virtual memory is commonly implemented using paging.
• In demand paging, pages are loaded into physical memory only when needed (on demand), not all at once.
• If a required page is not in physical memory, a page fault occurs, and the OS loads the page from disk.

3. Page Fault Handling

When a page fault occurs:

1. The OS detects the missing page.
2. It finds the page on the disk (swap space).
3. It loads the page into a free frame in physical memory.
4. Updates the page table.
5. Resumes the process.

4. Swapping

• When physical memory is full, the OS swaps out (removes) a page from memory to disk using a page replacement algorithm (e.g., FIFO, LRU, Optimal).

Advantages of Virtual Memory

Disadvantages

• Slower performance due to disk access (page faults are costly).
• Thrashing can occur if too many page faults happen frequently, causing the system to spend more time swapping than executing.

Summary

Virtual memory separates the logical memory seen by the user from the physical memory of the system, enabling efficient, safe, and flexible memory management in modern operating systems.