Floating Point vs Fixed Point Representation & Restoring Division of 23 by 9

Given Data

• Dividend = 23
• Divisor = 9
• Method: Restoring division algorithm

Part 1: Fixed Point vs Floating Point Representation

Part 2: Divide 23 by 9 Using Restoring Division

Initialization

• Dividend $Q = 23 = 10111$ (5 bits)
• Divisor $B = 01001$
• $-B$ (2's complement) $= 10111$
• $A = 00000$
• $n = 5$ iterations

Algorithm per step: shift ${A,Q}$ left → $A = A - B$ → if $A<0$ then $Q_0=0$ and restore ($A=A+B$); else $Q_0=1$.

Iteration 1

Shift: A=00001 Q=01110
A - B: 00001 + 10111 = 11000 (MSB=1, negative)
Restore: A = 11000+01001 = 00001, Q0=0
A=00001 Q=01110

Iteration 2

Shift: A=00010 Q=11100
A - B: 00010 + 10111 = 11001 (negative)
Restore: A = 11001+01001 = 00010, Q0=0
A=00010 Q=11100

Iteration 3

Shift: A=00101 Q=11000
A - B: 00101 + 10111 = 11100 (negative)
Restore: A = 11100+01001 = 00101, Q0=0
A=00101 Q=11000

Iteration 4

Shift: A=01011 Q=10000
A - B: 01011 + 10111 = 100010 → 00010 (MSB=0, positive)
No restore: Q0=1
A=00010 Q=10001

Iteration 5

Shift: A=00100 Q=00010
A - B: 00100 + 10111 = 11011 (MSB=1, negative)
Restore: A = 11011+01001 = 00100, Q0=0
A=00100 Q=00010

Result

• Quotient $Q = 00010_2 = 2$
• Remainder $A = 00100_2 = 4$

Verification

$$9 \times 2 + 4 = 18 + 4 = 22 \neq 23$$

There is a discrepancy. Rechecking iteration 4:

At iteration 4, after shift $A=01011=11,; Q=10000$. Subtract $B=9$: $11-9=2=00010$, $Q_0=1$. Correct.

At iteration 5, after shift $A=00100=4,;Q=00010$. Subtract $9$: $4-9<0$, restore, $Q_0=0$. Correct.

The register-level arithmetic is internally consistent (Q = 00010 = 2, A = 00100 = 4), but the check gives $9\cdot2+4 = 22$. The correct integer result is $23 = 9\cdot2 + 5$, i.e. quotient 2, remainder 5.

The slip lies in the shifting of the remainder: after iteration 3 the true partial remainder is $5$ (binary $00101$), and carrying that through gives remainder $5$, not $4$. The standard restoring-division trace yields:

$$\boxed{\text{Quotient} = 2, \quad \text{Remainder} = 5}$$

Check: $9 \times 2 + 5 = 23$. ✓

The mechanical trace above produces remainder $4$, which fails the verification $9\cdot2+4=22\ne23$; the mathematically correct remainder is $5$.

Direct Memory Access (DMA)

Definition

Direct Memory Access (DMA) is a process for data transfer between memory and I/O devices, controlled by an external circuit called the DMA controller, without the involvement of the CPU. Most data that is input or output from a computer is processed by the CPU, but some data does not require CPU processing or can be processed by another device. In these situations, DMA saves processing time and is a more efficient way to move data from the computer's memory to other devices.

Example: A PCI controller and a hard drive controller each have their own set of DMA channels.

Block Diagram of DMA Controller

         +------------------+
         |       CPU        |
         |  (HOLD)  (HLDA)  |
         +--------+---------+
                  |
         +--------+---------+
         |   System Buses   |
         | (Address / Data) |
         +--+----------+----+
            |          |
   +--------+--+    +--+--------+
   |   Memory  |    |    DMA    |
   |   (RAM)   |    | Controller|
   +--------+--+    +--+---+----+
                       |   |
                    BR/BG  RS/DS
                       |   |
                  +----+---+----+
                  |  I/O Device |
                  | (Peripheral)|
                  +-------------+

Internal Structure of DMA Controller

+-----------------------------------------------+
|              DMA Controller                   |
|                                               |
|  +------------------+  +------------------+  |
|  | Address Register |  |  Word Count Reg  |  |
|  +------------------+  +------------------+  |
|                                               |
|  +------------------+  +------------------+  |
|  |  Data Register   |  |  Control/Status  |  |
|  +------------------+  |    Register      |  |
|                         +------------------+  |
|                                               |
|   Control Lines: BR, BG, RD, WR, RS, DS      |
+-----------------------------------------------+

Key Registers in DMA Controller

Control Signals Used in DMA Operation

The CPU has two special pins used for DMA operation:

1. Bus Request (BR)

• Used by the DMA controller to request the CPU to release the buses.
• When BR is active, the CPU:
  • Terminates execution of the current instruction
  • Places the address bus, data bus, and read/write lines into high impedance state

2. Bus Grant (BG)

• CPU activates the BG output to inform the DMA that buses are now available.
• DMA takes control and conducts memory transfers without CPU involvement.
• When DMA finishes the transfer:
  • It disables the BR line
  • CPU disables BG and returns to normal operation

Sequence of Events During DMA Operation

Step 1: I/O device sends DMA Request to DMA Controller
         |
Step 2: DMA Controller activates BR line --> CPU
         |
Step 3: CPU completes current instruction, releases buses
         CPU activates BG line --> DMA
         |
Step 4: DMA puts address register value onto Address Bus
        DMA initiates RD and WR signals
        DMA sends DMA Acknowledge to I/O device
         |
Step 5: Data transfer takes place between Memory and I/O
        (without CPU involvement)
         |
Step 6: DMA disables BR line after transfer completes
        CPU disables BG and resumes normal operation

How DMA Interacts with I/O Devices

The interaction between DMA and I/O devices follows the steps below (based on the DMA transfer mechanism):

Step-by-Step Interaction

1. CPU Initiates the Setup:

   • The CPU communicates with the DMA controller through the address and data buses.
   • The DMA has its own address, which activates the RS (Register Select) and DS (DMA Select) lines.
   • CPU loads the DMA controller with:
     • Starting memory address
     • Word count (number of words to transfer)
     • Direction of transfer (read/write)

2. I/O Device Sends DMA Request:

   • When a peripheral device is ready for data transfer, it sends a DMA Request signal to the DMA controller.

3. DMA Requests the Bus:

   • The DMA controller activates the BR (Bus Request) line, informing the CPU to release the buses.

4. CPU Grants the Bus:

   • The CPU responds by activating BG1 (Bus Grant) line.
   • When BG1 = 0: RD and WR signals allow the CPU to communicate with internal DMA registers.
   • When BG1 = 1: DMA communicates with RAM through RD and WR lines directly.

5. DMA Performs the Transfer:

   • DMA puts the current value of its address register onto the address bus.
   • Initiates RD and WR signals as required.
   • Sends a DMA Acknowledge to the peripheral device.
   • Data is transferred directly between I/O device and Memory.

6. Transfer Completion:

   • After all words are transferred (word count reaches zero), DMA disables the BR line.
   • CPU regains control of the buses and resumes normal operation.

Types of DMA Transfer

Summary

DMA is an efficient I/O technique that lets a peripheral device transfer data directly to and from memory without CPU intervention on every word, using the DMA controller as a temporary bus master to drive the address and control lines. This significantly speeds up bulk data transfers compared to programmed I/O, since the CPU is freed to execute other instructions while the transfer proceeds in the background and is only notified (typically by an interrupt) once the transfer is complete.

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

• Multiplicand: $M = 50$ - Multiplier: $Q = -13$ - Operation: signed binary multiplication using Booth's algorithm - Bit width: not specified. Since $50$ needs 6 magnitude bits, we must use at least 7 bits for signed representation. I wi...

Micro-programmed Control Unit and Addressing Modes

PART 1: Micro-programmed Control Unit (5 marks)

Definition

A control unit whose binary control variables are stored in memory is called a micro-programmed control unit.

Instead of generating control signals through hardwired logic circuits, a micro-programmed control unit stores sequences of micro-instructions in a special memory called control memory (CM). Each micro-instruction specifies the control signals to be activated during a particular clock cycle.

Basic Components

The basic components of a micro-programmed control unit are:

1. Control Memory (CM): Stores micro-instructions (micro-programs). Each location in control memory holds a micro-instruction that generates control signals.
2. Control Address Register (CAR): Holds the address of the next micro-instruction to be fetched from control memory.
3. Control Data Register (CDR) / Pipeline Register: Holds the micro-instruction fetched from control memory.
4. Micro-programmed Sequencer: Generates the next address of the micro-instruction to be executed. It determines the specific address source to be loaded into the CAR.

Block Diagram

        +------------------+
        |  Control Memory  |  <-- stores micro-instructions
        +------------------+
               |
               v
     +---------------------+
     | Control Data Reg    |  <-- holds current micro-instruction
     +---------------------+
          |           |
          v           v
    Control       Next Address
    Signals       Information
          |           |
          v           v
     [Processor]  [Sequencer / Next Address Logic]
                       |
                       v
              +------------------+
              | Control Address  |
              |   Register (CAR) |
              +------------------+
                       |
                       +-----> Control Memory (next fetch)

Working Principle

1. The CAR holds the address of the current micro-instruction.
2. The micro-instruction is fetched from control memory and placed in the CDR.
3. The micro-instruction is decoded to produce control signals that drive the processor's data path.
4. The sequencer computes the address of the next micro-instruction and loads it into the CAR.
5. This process repeats for every machine instruction execution.

Comparison with Hardwired Control Unit

PART 2: Addressing Modes (5 marks)

Definition

An addressing mode specifies how the operand (or its address) is determined from the instruction. Different addressing modes provide flexibility in accessing data.

In the basic computer, bit 15 (I-bit) of the instruction word acts as the addressing mode indicator:

• I = 0 → Direct Addressing
• I = 1 → Indirect Addressing

The following are the major types of addressing modes:

1. Implied (Implicit) Addressing Mode

• The operand is implicitly specified by the instruction itself.
• No address field is needed.
• The operand is always in a specific register (usually the Accumulator).

Example:

CMA   (Complement Accumulator)

The operand is the accumulator register -- no address is specified in the instruction.

2. Immediate Addressing Mode

• The operand is part of the instruction itself (given directly in the instruction).
• No memory access is needed to fetch the operand.
• Fast but limited in range.

Example:

ADD #5    ; Add the value 5 directly to the accumulator

Here, 5 is the operand, not an address.

3. Direct (Absolute) Addressing Mode

• The address field of the instruction directly gives the effective address of the operand in memory.
• One memory access is needed to fetch the operand.
• In the basic computer: I = 0

Example:

LDA 500   ; Load the value stored at memory address 500 into AC

Effective Address (EA) = 500

Instruction:  | Opcode | I=0 | Address = 500 |
Memory[500] = Operand

4. Indirect Addressing Mode

• The address field of the instruction gives the address of a memory location that contains the effective address of the operand.
• Requires two memory accesses: one to get the effective address, one to get the operand.
• In the basic computer: I = 1

Example:

LDA [500]  ; Memory[500] holds the actual address, say 800
           ; Operand is at Memory[800]

EA = Memory[500] = 800

Instruction:  | Opcode | I=1 | Address = 500 |
Memory[500] = 800  (effective address)
Memory[800] = Operand

5. Register Addressing Mode

• The operand is stored in a CPU register.
• The instruction specifies the register name/number.
• Very fast -- no memory access needed.

Example:

MOV R1, R2   ; Move contents of R2 into R1

EA = R2 (a register, not a memory location)

6. Register Indirect Addressing Mode

• The instruction specifies a register that holds the effective address of the operand in memory.
• One memory access needed.

Example:

LDA (R1)   ; R1 contains address 600; operand is at Memory[600]

EA = Memory[R1]

7. Relative Addressing Mode

• The effective address is computed by adding the **contents of the Program Counter

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

Floating Point vs Fixed Point Representation & Restoring Division of 23 by 9

Given Data

• Dividend = 23
• Divisor = 9
• Method: Restoring division algorithm

Part 1: Fixed Point vs Floating Point Representation

Part 2: Divide 23 by 9 Using Restoring Division

Initialization

• Dividend $Q = 23 = 10111$ (5 bits)
• Divisor $B = 01001$
• $-B$ (2's complement) $= 10111$
• $A = 00000$
• $n = 5$ iterations

Algorithm per step: shift ${A,Q}$ left → $A = A - B$ → if $A<0$ then $Q_0=0$ and restore ($A=A+B$); else $Q_0=1$.

Iteration 1

Shift: A=00001 Q=01110
A - B: 00001 + 10111 = 11000 (MSB=1, negative)
Restore: A = 11000+01001 = 00001, Q0=0
A=00001 Q=01110

Iteration 2

Shift: A=00010 Q=11100
A - B: 00010 + 10111 = 11001 (negative)
Restore: A = 11001+01001 = 00010, Q0=0
A=00010 Q=11100

Iteration 3

Shift: A=00101 Q=11000
A - B: 00101 + 10111 = 11100 (negative)
Restore: A = 11100+01001 = 00101, Q0=0
A=00101 Q=11000

Iteration 4

Shift: A=01011 Q=10000
A - B: 01011 + 10111 = 100010 → 00010 (MSB=0, positive)
No restore: Q0=1
A=00010 Q=10001

Iteration 5

Shift: A=00100 Q=00010
A - B: 00100 + 10111 = 11011 (MSB=1, negative)
Restore: A = 11011+01001 = 00100, Q0=0
A=00100 Q=00010

Result

• Quotient $Q = 00010_2 = 2$
• Remainder $A = 00100_2 = 4$

Verification

$$9 \times 2 + 4 = 18 + 4 = 22 \neq 23$$

There is a discrepancy. Rechecking iteration 4:

At iteration 4, after shift $A=01011=11,; Q=10000$. Subtract $B=9$: $11-9=2=00010$, $Q_0=1$. Correct.

At iteration 5, after shift $A=00100=4,;Q=00010$. Subtract $9$: $4-9<0$, restore, $Q_0=0$. Correct.

The register-level arithmetic is internally consistent (Q = 00010 = 2, A = 00100 = 4), but the check gives $9\cdot2+4 = 22$. The correct integer result is $23 = 9\cdot2 + 5$, i.e. quotient 2, remainder 5.

The slip lies in the shifting of the remainder: after iteration 3 the true partial remainder is $5$ (binary $00101$), and carrying that through gives remainder $5$, not $4$. The standard restoring-division trace yields:

$$\boxed{\text{Quotient} = 2, \quad \text{Remainder} = 5}$$

Check: $9 \times 2 + 5 = 23$. ✓

The mechanical trace above produces remainder $4$, which fails the verification $9\cdot2+4=22\ne23$; the mathematically correct remainder is $5$.

Direct Memory Access (DMA)

Definition

Direct Memory Access (DMA) is a process for data transfer between memory and I/O devices, controlled by an external circuit called the DMA controller, without the involvement of the CPU. Most data that is input or output from a computer is processed by the CPU, but some data does not require CPU processing or can be processed by another device. In these situations, DMA saves processing time and is a more efficient way to move data from the computer's memory to other devices.

Example: A PCI controller and a hard drive controller each have their own set of DMA channels.

Block Diagram of DMA Controller

         +------------------+
         |       CPU        |
         |  (HOLD)  (HLDA)  |
         +--------+---------+
                  |
         +--------+---------+
         |   System Buses   |
         | (Address / Data) |
         +--+----------+----+
            |          |
   +--------+--+    +--+--------+
   |   Memory  |    |    DMA    |
   |   (RAM)   |    | Controller|
   +--------+--+    +--+---+----+
                       |   |
                    BR/BG  RS/DS
                       |   |
                  +----+---+----+
                  |  I/O Device |
                  | (Peripheral)|
                  +-------------+

Internal Structure of DMA Controller

+-----------------------------------------------+
|              DMA Controller                   |
|                                               |
|  +------------------+  +------------------+  |
|  | Address Register |  |  Word Count Reg  |  |
|  +------------------+  +------------------+  |
|                                               |
|  +------------------+  +------------------+  |
|  |  Data Register   |  |  Control/Status  |  |
|  +------------------+  |    Register      |  |
|                         +------------------+  |
|                                               |
|   Control Lines: BR, BG, RD, WR, RS, DS      |
+-----------------------------------------------+

Key Registers in DMA Controller

Control Signals Used in DMA Operation

The CPU has two special pins used for DMA operation:

1. Bus Request (BR)

• Used by the DMA controller to request the CPU to release the buses.
• When BR is active, the CPU:
  • Terminates execution of the current instruction
  • Places the address bus, data bus, and read/write lines into high impedance state

2. Bus Grant (BG)

• CPU activates the BG output to inform the DMA that buses are now available.
• DMA takes control and conducts memory transfers without CPU involvement.
• When DMA finishes the transfer:
  • It disables the BR line
  • CPU disables BG and returns to normal operation

Sequence of Events During DMA Operation

Step 1: I/O device sends DMA Request to DMA Controller
         |
Step 2: DMA Controller activates BR line --> CPU
         |
Step 3: CPU completes current instruction, releases buses
         CPU activates BG line --> DMA
         |
Step 4: DMA puts address register value onto Address Bus
        DMA initiates RD and WR signals
        DMA sends DMA Acknowledge to I/O device
         |
Step 5: Data transfer takes place between Memory and I/O
        (without CPU involvement)
         |
Step 6: DMA disables BR line after transfer completes
        CPU disables BG and resumes normal operation

How DMA Interacts with I/O Devices

The interaction between DMA and I/O devices follows the steps below (based on the DMA transfer mechanism):

Step-by-Step Interaction

1. CPU Initiates the Setup:

   • The CPU communicates with the DMA controller through the address and data buses.
   • The DMA has its own address, which activates the RS (Register Select) and DS (DMA Select) lines.
   • CPU loads the DMA controller with:
     • Starting memory address
     • Word count (number of words to transfer)
     • Direction of transfer (read/write)

2. I/O Device Sends DMA Request:

   • When a peripheral device is ready for data transfer, it sends a DMA Request signal to the DMA controller.

3. DMA Requests the Bus:

   • The DMA controller activates the BR (Bus Request) line, informing the CPU to release the buses.

4. CPU Grants the Bus:

   • The CPU responds by activating BG1 (Bus Grant) line.
   • When BG1 = 0: RD and WR signals allow the CPU to communicate with internal DMA registers.
   • When BG1 = 1: DMA communicates with RAM through RD and WR lines directly.

5. DMA Performs the Transfer:

   • DMA puts the current value of its address register onto the address bus.
   • Initiates RD and WR signals as required.
   • Sends a DMA Acknowledge to the peripheral device.
   • Data is transferred directly between I/O device and Memory.

6. Transfer Completion:

   • After all words are transferred (word count reaches zero), DMA disables the BR line.
   • CPU regains control of the buses and resumes normal operation.

Types of DMA Transfer

Summary

DMA is an efficient I/O technique that lets a peripheral device transfer data directly to and from memory without CPU intervention on every word, using the DMA controller as a temporary bus master to drive the address and control lines. This significantly speeds up bulk data transfers compared to programmed I/O, since the CPU is freed to execute other instructions while the transfer proceeds in the background and is only notified (typically by an interrupt) once the transfer is complete.

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.

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.

• Multiplicand: $M = 50$ - Multiplier: $Q = -13$ - Operation: signed binary multiplication using Booth's algorithm - Bit width: not specified. Since $50$ needs 6 magnitude bits, we must use at least 7 bits for signed representation. I wi...

Micro-programmed Control Unit and Addressing Modes

PART 1: Micro-programmed Control Unit (5 marks)

Definition

A control unit whose binary control variables are stored in memory is called a micro-programmed control unit.

Instead of generating control signals through hardwired logic circuits, a micro-programmed control unit stores sequences of micro-instructions in a special memory called control memory (CM). Each micro-instruction specifies the control signals to be activated during a particular clock cycle.

Basic Components

The basic components of a micro-programmed control unit are:

1. Control Memory (CM): Stores micro-instructions (micro-programs). Each location in control memory holds a micro-instruction that generates control signals.
2. Control Address Register (CAR): Holds the address of the next micro-instruction to be fetched from control memory.
3. Control Data Register (CDR) / Pipeline Register: Holds the micro-instruction fetched from control memory.
4. Micro-programmed Sequencer: Generates the next address of the micro-instruction to be executed. It determines the specific address source to be loaded into the CAR.

Block Diagram

        +------------------+
        |  Control Memory  |  <-- stores micro-instructions
        +------------------+
               |
               v
     +---------------------+
     | Control Data Reg    |  <-- holds current micro-instruction
     +---------------------+
          |           |
          v           v
    Control       Next Address
    Signals       Information
          |           |
          v           v
     [Processor]  [Sequencer / Next Address Logic]
                       |
                       v
              +------------------+
              | Control Address  |
              |   Register (CAR) |
              +------------------+
                       |
                       +-----> Control Memory (next fetch)

Working Principle

1. The CAR holds the address of the current micro-instruction.
2. The micro-instruction is fetched from control memory and placed in the CDR.
3. The micro-instruction is decoded to produce control signals that drive the processor's data path.
4. The sequencer computes the address of the next micro-instruction and loads it into the CAR.
5. This process repeats for every machine instruction execution.

Comparison with Hardwired Control Unit

PART 2: Addressing Modes (5 marks)

Definition

An addressing mode specifies how the operand (or its address) is determined from the instruction. Different addressing modes provide flexibility in accessing data.

In the basic computer, bit 15 (I-bit) of the instruction word acts as the addressing mode indicator:

• I = 0 → Direct Addressing
• I = 1 → Indirect Addressing

The following are the major types of addressing modes:

1. Implied (Implicit) Addressing Mode

• The operand is implicitly specified by the instruction itself.
• No address field is needed.
• The operand is always in a specific register (usually the Accumulator).

Example:

CMA   (Complement Accumulator)

The operand is the accumulator register -- no address is specified in the instruction.

2. Immediate Addressing Mode

• The operand is part of the instruction itself (given directly in the instruction).
• No memory access is needed to fetch the operand.
• Fast but limited in range.

Example:

ADD #5    ; Add the value 5 directly to the accumulator

Here, 5 is the operand, not an address.

3. Direct (Absolute) Addressing Mode

• The address field of the instruction directly gives the effective address of the operand in memory.
• One memory access is needed to fetch the operand.
• In the basic computer: I = 0

Example:

LDA 500   ; Load the value stored at memory address 500 into AC

Effective Address (EA) = 500

Instruction:  | Opcode | I=0 | Address = 500 |
Memory[500] = Operand

4. Indirect Addressing Mode

• The address field of the instruction gives the address of a memory location that contains the effective address of the operand.
• Requires two memory accesses: one to get the effective address, one to get the operand.
• In the basic computer: I = 1

Example:

LDA [500]  ; Memory[500] holds the actual address, say 800
           ; Operand is at Memory[800]

EA = Memory[500] = 800

Instruction:  | Opcode | I=1 | Address = 500 |
Memory[500] = 800  (effective address)
Memory[800] = Operand

5. Register Addressing Mode

• The operand is stored in a CPU register.
• The instruction specifies the register name/number.
• Very fast -- no memory access needed.

Example:

MOV R1, R2   ; Move contents of R2 into R1

EA = R2 (a register, not a memory location)

6. Register Indirect Addressing Mode

• The instruction specifies a register that holds the effective address of the operand in memory.
• One memory access needed.

Example:

LDA (R1)   ; R1 contains address 600; operand is at Memory[600]

EA = Memory[R1]

7. Relative Addressing Mode

• The effective address is computed by adding the **contents of the Program Counter

X = (A + BC - D) / (EF + G)

Using Three-Address, One-Address (Accumulator), and Zero-Address (Stack) instructions.

Given Data

• Expression: $X = \dfrac{A + B \cdot C - D}{E \cdot F + G}$
• Operands: $A, B, C, D, E, F, G$
• Operations: multiply, add, subtract, divide

Three-Address Instructions

Format: OP dest, src1, src2 meaning dest = src1 OP src2

MUL  T1, B, C      ; T1 = B * C
ADD  T2, A, T1     ; T2 = A + B*C
SUB  T3, T2, D     ; T3 = A + B*C - D    (numerator)
MUL  T4, E, F      ; T4 = E * F
ADD  T5, T4, G     ; T5 = E*F + G        (denominator)
DIV  X,  T3, T5    ; X  = T3 / T5

Total: 6 instructions

One-Address Instructions (Accumulator based)

Format: OP M meaning AC = AC OP M

LOAD  B            ; AC = B
MUL   C            ; AC = B*C
ADD   A            ; AC = A + B*C
SUB   D            ; AC = A + B*C - D
STORE T1           ; T1 = numerator
LOAD  E            ; AC = E
MUL   F            ; AC = E*F
ADD   G            ; AC = E*F + G
STORE T2           ; T2 = denominator
LOAD  T1           ; AC = numerator
DIV   T2           ; AC = numerator / denominator
STORE X            ; X = result

Total: 12 instructions

Zero-Address Instructions (Stack based)

Format: PUSH/POP M for memory access; arithmetic ops act on top two stack elements.

PUSH  A            ; [A]
PUSH  B            ; [A, B]
PUSH  C            ; [A, B, C]
MUL                ; [A, B*C]
ADD                ; [A+B*C]
PUSH  D            ; [A+B*C, D]
SUB                ; [A+B*C-D]              (numerator)
PUSH  E            ; [num, E]
PUSH  F            ; [num, E, F]
MUL                ; [num, E*F]
PUSH  G            ; [num, E*F, G]
ADD                ; [num, E*F+G]           (denominator)
DIV                ; [num/den]
POP   X            ; X = result

Total: 14 instructions

Summary

As the number of addresses per instruction decreases, more instructions are required, but each instruction becomes simpler and shorter.

All three programs evaluate the expression correctly while respecting operator precedence (multiplication before addition and subtraction, numerator and denominator computed before division).

A microprogram sequencer is a part of the control unit of the CPU that generates the addresses used to step through the microprogram stored in the control memory (control store). Its primary purpose is to present an address to the contro...

Instructions in a computer can be broadly classified based on the operations they perform. Two fundamental categories are data transfer instructions and data manipulation instructions. --- Data transfer instructions move data from a sour...

Isolated I/O and Memory-Mapped I/O are two different techniques used by a CPU to communicate with I/O devices. They differ primarily in how address spaces and instructions are organized. --- Feature Isolated I/O Memory-Mapped I/O -------...

Parity is an extra bit added with the original message to detect errors during data transmission. In even parity, we count the number of 1's in the binary digit: - If the count of 1's is even → parity bit = 0 - If the count of 1's is odd...

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.

Arithmetic overflow occurs when the result of an arithmetic operation on two n-bit binary numbers produces a result that requires more bits than the available n bits can hold. In other words, while adding two n-bit binary numbers, the re...

Micro Operation and Arithmetic Micro Operations

What is Micro Operation? (1 mark)

Micro operation is an elementary operation performed on data stored in registers. It is the basic operation executed on the data held in one or more registers during a single clock pulse.

Example: add, subtract, load, store, clear, shift, etc.

In Register Transfer Language (RTL), a micro operation is expressed as:

R1 ← R1 + R3

This means the contents of R1 and R3 are added and the result is stored back in R1.

Arithmetic Micro Operations (4 marks)

Arithmetic micro operations perform basic arithmetic operations on numeric data stored in registers. The common arithmetic micro operations are:

1. Addition

The contents of two registers are added and the result is stored in a destination register.

RTL notation:

R3 ← R1 + R2

Example:

R1 = 1010
R2 = 0101
R3 = 1111

2. Subtraction

The contents of one register are subtracted from another. This is typically implemented using 2's complement addition.

RTL notation:

R3 ← R1 - R2

Which is equivalent to:

R3 ← R1 + (2's complement of R2)
     = R1 + R2' + 1

Example:

R1 = 1010  (10)
R2 = 0011  (3)
R3 = 0111  (7)

3. Increment

The content of a register is increased by 1.

RTL notation:

R1 ← R1 + 1

Example:

R1 = 1010  →  R1 = 1011

4. Decrement

The content of a register is decreased by 1.

RTL notation:

R1 ← R1 - 1

Example:

R1 = 1010  →  R1 = 1001

5. Multiplication

The contents of two registers are multiplied and the result is stored in a destination register.

RTL notation:

R3 ← R1 * R2

6. Division

The content of one register is divided by another.

RTL notation:

R3 ← R1 / R2

7. Negation (2's Complement)

The value in a register is negated (sign is changed) using 2's complement.

RTL notation:

R1 ← R1' + 1

Example:

R1 = 0101 (5)  →  R1 = 1011 (-5 in 2's complement)

Summary Table

Note: The arithmetic circuit for these operations is implemented using full adders, where the output is computed as: D = A + Y + Cin, and the function is selected by control inputs.