Pipelining: 4-Segment Instruction Cycle and Advantages

1. What is Pipelining?

Pipelining is a technique used in computer architecture to improve CPU performance by overlapping the execution of multiple instructions. Instead of waiting for one instruction to complete all its phases before starting the next, the CPU divides instruction execution into a series of stages (segments), and different instructions occupy different stages simultaneously.

It works like an assembly line in a factory: while one instruction is being executed, the next instruction is being decoded, and the one after that is being fetched, all at the same time.

Pipelining is easy in RISC architecture because instructions are simple and take a single cycle to execute.

2. Pipelining Using a 4-Segment Instruction Cycle

The instruction cycle is divided into 4 segments (stages):

2.1 Micro-operations at Each Stage

Stage S1: Fetch

T0: AR <- PC
T1: IR <- M[AR], PC <- PC + 1

Stage S2: Decode

T2: Decode IR(12-14), AR <- IR(0-11), I <- IR(15)
    Determine instruction type (memory-reference, register, or I/O)

Stage S3: Execute

T3: Execute the instruction based on decoded opcode
    (ALU operation, memory read/write, I/O operation)

Stage S4: Write Back

T4: Write result to destination register or memory location
    SC <- 0 (reset sequence counter for next instruction)

2.2 Pipeline Timing Diagram

Without pipelining (sequential execution), each instruction takes 4 clock cycles. With pipelining, instructions overlap:

Clock Cycle:   1    2    3    4    5    6    7
               |    |    |    |    |    |    |
Instruction 1: FI   DI   EI   WB
Instruction 2:      FI   DI   EI   WB
Instruction 3:           FI   DI   EI   WB
Instruction 4:                FI   DI   EI   WB

• Without pipeline: 4 instructions x 4 cycles = 16 clock cycles
• With pipeline: 4 + (4-1) = 7 clock cycles

2.3 General Formula for Pipeline Execution Time

For a k-segment pipeline executing n tasks with clock cycle time t_p:

$$\text{Total Time} = [k + (n-1)] \times t_p$$

For our 4-segment pipeline (k = 4):

$$\text{Total Time} = [4 + (n-1)] \times t_p$$

Example: Execute 6 instructions (n = 6) with k = 4 segments:

$$\text{Total Time} = [4 + (6-1)] \times t_p = 9 \times t_p$$

Without pipelining: $$\text{Total Time} = n \times k \times t_p = 6 \times 4 \times t_p = 24 \times t_p$$

Speedup = 24 / 9 = 2.67x

2.4 Instruction Queue (FIFO Execution)

The instruction pipeline execution works like a queue using average execution (FIFO technique). When an instruction first arrives, it is placed in the queue and executed in the system, and the result is passed on to the next instruction in the queue.

This means:

• Instructions enter the pipeline in order (FIFO)
• Each instruction moves through S1 -> S2 -> S3 -> S4 sequentially
• Multiple instructions are in different stages at the same time

3. Advantages of Pipelining

4. Summary

Pipelining is one of the most fundamental techniques in modern processor design. By dividing the instruction cycle into 4 segments (Fetch, Decode, Execute, Write Back) and overlapping their execution using a FIFO queue mechanism, the CPU achieves significantly higher performance without requiring faster hardware.

Instruction Format: Basic Computer

Definition

An instruction format is the layout or structure that defines how the bits of an instruction word are organized and interpreted by the processor. It specifies the fields within an instruction, such as the opcode, address, and mode bits, so that the control unit can correctly decode and execute each instruction.

In the basic computer, each instruction is 16 bits wide and there are three types of instruction formats.

Three Instruction Formats of Basic Computer

1. Memory Reference Instruction

This type of instruction references a memory location as its operand.

Format (16 bits):

• Bit 15 (I-bit): Addressing mode indicator
  • I = 0 → Direct addressing (operand is at the given address)
  • I = 1 → Indirect addressing (given address holds the address of the operand)
• Bits 12-14: 3-bit opcode (can represent up to 7 memory reference instructions, since opcode 111 is reserved)
• Bits 0-11: 12-bit address field (can address up to 4096 memory locations)

Examples:

2. Register Reference Instruction

This type of instruction performs operations on CPU registers (primarily the Accumulator) and does not reference memory.

Format (16 bits):

• Bits 12-14 = 111 and Bit 15 = 0 identifies this as a register reference instruction
• Bits 0-11: Each bit specifies a particular register operation (only one bit is set at a time)

Examples:

3. Input/Output (I/O) Reference Instruction

This type of instruction handles communication with input/output devices and does not reference memory.

Format (16 bits):

• Bits 12-14 = 111 and Bit 15 = 1 identifies this as an I/O reference instruction
• Bits 0-11: Each bit specifies a particular I/O operation

Examples:

Summary Table

Key Point: The basic computer distinguishes between the three instruction types during the decode phase (T2) by examining bit 15 and the opcode bits 12-14 of the Instruction Register (IR).

Common Bus System of Basic Computer

Introduction

The common bus system is used in a basic computer to facilitate efficient communication between registers and memory. Instead of connecting every register to every other register with individual wires (which increases hardware complexity), a single shared bus is used to transfer data between all components.

Requirements / Key Features

• The basic computer has eight registers, a memory unit, and a control unit
• Six registers and memory are connected to the bus
• The input register (INPR) and output register (OUTR) are 8-bit registers
• All seven registers, memory, INPR and OUTR are driven by a single-phase clock pulse
• The particular register whose load (LD) input is enabled receives the data from the bus during the next clock pulse
• Which register is selected is determined by selection lines (S1, S0, etc.)

Construction of Common Bus

A common bus can be constructed using either:

1. Multiplexers (MUX)
2. Three-state buffers

Using Multiplexers

Each bit position of the bus has one MUX. For n registers, the selection lines choose which register drives the bus.

Example: 4-register, 4-bit bus using 4x1 MUX:

Registers:   A      B      C      D
             |      |      |      |
           [MUX 0][MUX 1][MUX 2][MUX 3]
                      |
                 COMMON BUS
                      |
              (to all registers)

Selection Lines:
  S1  S0  |  Selected Register
  --------|-------------------
   0   0  |       A
   0   1  |       B
   1   0  |       C
   1   1  |       D

• The selection lines S1 and S0 are connected to the selection inputs of all MUXes
• All MUXes select the same register at the same time
• The selected register's data is placed on the bus

Diagram: Common Bus System for Basic Computer

        +-------+   +-------+   +-------+   +-------+
        |  AR   |   |  PC   |   |  DR   |   |  AC   |
        | (12b) |   | (12b) |   | (16b) |   | (16b) |
        +---+---+   +---+---+   +---+---+   +---+---+
            |           |           |           |
            +-----+-----+-----------+-----------+
                  |
         +--------+--------+
         |   COMMON BUS    |   (16-bit)
         +--------+--------+
                  |
            +-----+-----+
            |           |
        +---+---+   +---+---+
        |  IR   |   |  TR   |
        | (16b) |   | (16b) |
        +-------+   +-------+
                  |
             +----+----+
             | MEMORY  |
             |  UNIT   |
             +---------+

  Selection Lines (S2, S1, S0) --> determine which register
                                   drives the bus

How It Works

1. The selection lines determine which register is connected to the bus as the source
2. The data from the selected register is placed on the common bus
3. The register whose LD (load) input is enabled will receive the data from the bus at the next clock pulse
4. Only one register can send data on the bus at a time, but any register can receive

Advantages

Summary

The common bus system provides an efficient and organized way to transfer information among the registers and memory of the basic computer. By using multiplexers and selection lines, any one of the registers can be selected to place its data on the bus, while the destination register is enabled by its load input to receive the data on the next clock pulse.

Cache Mapping

Definition

Cache mapping refers to the technique or procedure by which the contents of main memory blocks are mapped (assigned) to cache memory locations. Since cache memory is much smaller than main memory, a mapping function is needed to determine which cache location a particular main memory block will occupy when it is brought into cache.

Direct Mapping

Concept

In direct mapping, each block of main memory can be placed in one and only one specific location in the cache. Main memory is divided into pages that correspond in size with the cache. Each memory address is divided into three fields:

Address Division

For a memory address of k bits:

| TAG  |  INDEX (Cache Line)  |  WORD (Offset)  |
|  t   |         d            |       w         |

• Number of cache lines = 2^d
• Number of words per block = 2^w
• Tag bits = k - d - w

The cache line number is determined by:

Cache Line = (Main Memory Block Number) mod (Number of Cache Lines)

Block Diagram of Direct Mapping

Main Memory Address
+--------+----------+--------+
|  TAG   |  INDEX   |  WORD  |
+--------+----------+--------+
     |         |         |
     |         |         |
     |    +----v----+    |
     |    |  Cache  |    |
     |    |  Index  |    |
     |    | (Select |    |
     |    |  Line)  |    |
     |    +----+----+    |
     |         |         |
     |    +----v-----------------------+
     |    | Cache Line                 |
     |    |  +-------++--------------+ |
     |    |  | Valid ||  TAG | DATA  | |
     |    |  +-------++--------------+ |
     |    +----+-----------+----------+
     |         |           |
  +--v--+   Compare      Block
  | TAG |----+           Data
  +-----+    |              |
             v              |
          +------+          |
          | Hit? |          |
          +--+---+          |
             |              |
         YES | NO           |
             |   (Fetch     |
             |    from      v
             |    Main   +------+
             |    Memory)|      |
             v           | WORD |
          +------+       | MUX  |
          | Data |<------+------+
          | Out  |
          +------+

Working Steps

1. The CPU generates a memory address which is split into Tag, Index, and Word fields.
2. The Index field is used to directly select a specific cache line.
3. The Tag stored in that cache line is compared with the Tag from the CPU address.
4. If the Valid bit = 1 and Tags match → Cache HIT: the required word is read from the cache using the Word field.
5. If the Tags do not match or Valid bit = 0 → Cache MISS: the block is fetched from main memory, loaded into the indicated cache line, and the tag is updated.

Example

Suppose main memory has 32 blocks and cache has 8 lines:

• Block 0 maps to Cache Line 0 (0 mod 8 = 0)
• Block 1 maps to Cache Line 1 (1 mod 8 = 1)
• Block 9 maps to Cache Line 1 (9 mod 8 = 1)
• Block 17 maps to Cache Line 1 (17 mod 8 = 1)

Note: Blocks 1, 9, and 17 all compete for the same cache line, which is the main disadvantage of direct mapping.

Advantages and Disadvantages

Short Notes: a) CISC b) Conditional Branch

a) CISC (Complex Instruction Set Computer)

CISC is a processor design philosophy where the CPU is capable of executing a large number of complex instructions, each of which can perform multiple low-level operations (such as memory access, arithmetic, and logic) in a single instruction.

Key Characteristics of CISC:

Key Points:

• CISC emphasizes doing more work per instruction, reducing the number of instructions per program.
• It uses microprogrammed control to implement complex instructions.
• Examples: Intel x86, Intel 8086, VAX processors.
• The compiler work is reduced since complex operations are handled directly by hardware.
• CISC processors typically have a large control memory to store microinstructions for each complex instruction.

b) Conditional Branch

Conditional branch is a type of branching mechanism in which the transfer of control to a new address depends on the status (condition) of one or more status bits (flags) at the time of execution.

Definition:

Conditional branching is obtained by using part of a micro-instruction to select a specific status bit in order to determine its condition. The branch logic provides decision-making capabilities in the control unit.

How It Works:

• A portion of the micro-instruction specifies which status bit to test (e.g., zero flag, carry flag, sign flag).
• If the condition is TRUE -- the branch is taken and the program jumps to the specified address.
• If the condition is FALSE -- execution continues sequentially (next instruction).

Block Diagram (Conceptual):

Control Memory
      |
      v
[Micro-instruction] --> [Branch Logic] <-- [Status Bits (flags)]
                               |
                    ---------------------
                    |                   |
              Condition TRUE      Condition FALSE
                    |                   |
             Branch Address      Next Sequential Address

Methods of Selecting Next Microinstruction Address:

The following methods are used:

1. Incrementing of the control address register (sequential execution).
2. Unconditional branch or conditional branch depending on status bit conditions.
3. A mapping process from instruction bits to a control memory address.
4. A facility for subroutine call and return.

Example:

• In a basic computer, instructions like ISZ (Increment and Skip if Zero) use conditional branching:
  • After incrementing, if DR = 0, then PC is incremented by 1 (branch/skip).
  • Otherwise, execution continues normally.

Difference: Conditional vs Unconditional Branch

Significance:

Conditional branching is essential for implementing loops, if-else decisions, and program flow control in both high-level programs and microprogram control units.