Cache Memory and Mapping Process

1. What is Cache Memory? (2 marks)

Cache memory is a small, high-speed memory placed between the CPU and main memory (RAM). Its purpose is to store frequently used instructions and data so that the CPU can access them faster, reducing the average time needed to access data from main memory.

Key characteristics:

• Faster than main memory but smaller in size
• Sits closest to the CPU in the memory hierarchy
• Transparent to the programmer (managed by hardware)
• Reduces the speed mismatch between CPU and main memory

2. The Mapping Process (3 marks)

: "The transformation of data from main memory to cache memory is referred to as a mapping process."

When the CPU needs data, it first checks the cache:

• Cache Hit: Data found in cache -- CPU reads directly (fast)
• Cache Miss: Data not in cache -- fetched from main memory and a copy is placed in cache

Since cache is much smaller than main memory, a mapping function is needed to determine where a block of main memory will be placed in cache.

The three practical mapping procedures are:

1. Direct Mapping
2. Associative Mapping
3. Set-Associative Mapping

3. Direct Mapping (2 marks)

: "Main memory locations can only be copied into one location in the cache. This is accomplished by dividing main memory into pages that correspond in size with the cache."

How it works:

• Main memory is divided into pages of the same size as the cache.
• Each block of main memory maps to exactly one fixed location in the cache.
• The memory address is divided into three fields:

| TAG | INDEX (Cache Line) | BLOCK OFFSET |

• Tag: Identifies which page of main memory the block came from
• Index: Specifies the cache line where the block must be stored
• Offset: Identifies the specific word within the block

Example:

If cache has 128 lines and main memory has 4096 blocks:

• Block 0, 128, 256, ... all map to cache line 0
• Block 1, 129, 257, ... all map to cache line 1

Advantage:

• Simple and inexpensive to implement

Disadvantage:

• Two blocks with the same index but different tags cannot reside in cache simultaneously, causing frequent replacements (cache thrashing)

4. Associative Mapping (2 marks)

In associative (fully associative) mapping, any block of main memory can be placed in any line of the cache. There is no fixed mapping.

How it works:

• The memory address is divided into only two fields:

| TAG | BLOCK OFFSET |

• The entire tag is stored with each cache entry.
• When the CPU requests data, all cache tags are searched simultaneously (using associative/content-addressable memory) to find a match.

Advantage:

• Flexible: Any memory block can go into any cache line
• Eliminates the thrashing problem of direct mapping
• Higher hit rate

Disadvantage:

• Expensive and complex hardware required for simultaneous tag comparison
• Replacement policy (LRU, FIFO) must be implemented

5. Set-Associative Mapping (1 mark)

: "Set-Associative mapping is an improvement over direct mapping organization. Each word of cache can store two or more words of memory under the same index address."

• It is a compromise between direct and associative mapping.
• Cache is divided into sets, each set containing a fixed number of lines (called the set size or k-way).
• A memory block maps to a specific set (like direct mapping) but can go into any line within that set (like associative mapping).

6. Differentiation: Direct Mapping vs. Associative Mapping (Table) (marks covered above)

Summary

Cache memory bridges the speed gap between the CPU and main memory. The mapping process determines how main memory blocks are placed into cache. Direct mapping is simple but suffers from conflicts since each block has only one possible cache location. Associative mapping is flexible and conflict-free but requires costly hardware. Set-associative mapping is the practical middle ground used in modern processors.

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

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$.

Binary Adder-Subtractor Circuit

Introduction

A binary adder-subtractor is a combinational circuit that can perform both addition and subtraction of binary numbers using a single circuit, controlled by a mode select input.

Working Principle

The circuit uses the concept of 2's complement subtraction:

A - B = A + (2's complement of B) = A + (1's complement of B) + 1

• When Mode M = 0 → Circuit performs Addition: A + B
• When Mode M = 1 → Circuit performs Subtraction: A - B (i.e., A + B' + 1)

The key component used is the XOR gate:

So when M = 1, each bit of B is complemented (1's complement), and M = 1 is also fed into the carry-in (C0) of the first Full Adder, which adds 1, completing the 2's complement.

Circuit Diagram (4-bit Adder-Subtractor)

        B3      A3    B2      A2    B1      A1    B0      A0
        |       |     |       |     |       |     |       |
       XOR      |    XOR      |    XOR      |    XOR      |
        |  M----+     |  M----+     |  M----+     |  M----+---> C0 (Carry In)
        |       |     |       |     |       |     |       |
       FA  <--C3     FA  <--C2     FA  <--C1     FA  <-- M
        |             |             |             |
        S3            S2            S1            S0

Diagram:

B3 A3    B2 A2    B1 A1    B0 A0
 |  |     |  |     |  |     |  |
 C3 FA   C2 FA   C1 FA   C0 FA  <-- C0 = M
  |        |        |        |
  S3       S2       S1       S0

Each stage consists of a Full Adder (FA) where:

• One input is Ai
• Other input is M ⊕ Bi (XOR of mode bit and Bi)
• Carry ripples from stage to stage
• Initial carry C0 = M

Operation Summary

Overflow Condition

While adding two n-bit binary numbers, the result may be a number with (n+1) bits -- this situation is called overflow.

In the adder-subtractor, overflow can be detected by checking if the final carry out is inconsistent with the sign bits of the operands.

Conclusion

The binary adder-subtractor efficiently combines addition and subtraction in one circuit using XOR gates and Full Adders, with the mode input M controlling the operation. This reduces hardware complexity significantly compared to having separate adder and subtractor circuits.

Sequencer and Microprogram Sequencer

Definition of Sequencer

A sequencer is a part of the control unit of the CPU. It generates the addresses used to step through the microprogram of a control store (control memory). In other words, it determines the sequence in which microinstructions are fetched and executed from the control memory.

Microprogram Sequencer

The purpose of a microprogram sequencer is to present an address to the control memory so that a microinstruction may be read and executed.

Block Diagram

         ┌──────────────────────────────────────┐
         │         MULTIPLEXER (MUX)            │
         │  Source 0 | Source 1 | Source 2 | Source 3 │
         └──────────────────┬───────────────────┘
                            │  Selected Address
                            ▼
                  ┌─────────────────┐
                  │  Control Address│
                  │  Register (CAR) │
                  └────────┬────────┘
                           │  Address
                           ▼
                  ┌─────────────────┐
                  │  Control Memory │
                  │ (Microprogram   │
                  │    Store)       │
                  └────────┬────────┘
                           │  Microinstruction
                           ▼
                  ┌─────────────────┐
                  │  Control Data   │
                  │  Register (CDR) │
                  └─────────────────┘

Working of Microprogram Sequencer

1. Multiplexer (MUX): The multiplexer selects an address from 4 sources and routes it into the Control Address Register (CAR). The selection depends on the sequencer control inputs.

2. Control Address Register (CAR): The output from CAR provides the address for the control memory. It holds the address of the next microinstruction to be executed.

3. Control Memory: Stores the microprogram (set of microinstructions). The microinstruction at the address given by CAR is read out.

4. Control Data Register (CDR): Holds the microinstruction fetched from control memory for execution.

Typical Sequencer Operations

The sequencer supports the following address sequencing operations:

With three inputs, the sequencer can provide up to eight address sequencing operations. Some commercial sequencers have three or four inputs plus a T (test/condition) input, providing a wider range of operations.

Address Mapping

When a machine instruction is fetched, its opcode bits are mapped to a starting address in the control memory. For example:

• A 0 is placed in the most significant bit of the address.
• The four opcode bits are transferred directly.
• The two least significant bits are cleared (set to 00).

This provides each computer instruction a microprogram routine with a capacity of four microinstructions. If more microinstructions are needed, additional memory locations can be used.

Summary

The microprogram sequencer acts as the brain of the control unit by continuously generating the correct sequence of addresses to step through microinstructions stored in control memory, enabling the CPU to execute each machine instruction correctly through its corresponding microprogram routine.

STEP 1 - EXTRACT

Given data:

• Expression: $X = (AB + C - D) / (E + FG)$
• Required representations: three-address, one-address (single), zero-address instructions.

No numeric values are involved; this is a symbolic instruction-set problem.

STEP 2 - SOLVE

1. Three-Address Instructions

Format: OP DEST, SRC1, SRC2

MUL R1, A, B       ; R1 = A * B
ADD R1, R1, C      ; R1 = A*B + C
SUB R1, R1, D      ; R1 = A*B + C - D
MUL R2, F, G       ; R2 = F * G
ADD R2, E, R2      ; R2 = E + F*G
DIV X,  R1, R2     ; X = (A*B + C - D) / (E + F*G)

Total: 6 instructions

2. One (Single) Address Instructions

Format uses the Accumulator (AC): OP M means $AC = AC ; \text{OP} ; M[M]$

LOAD  F        ; AC = F
MUL   G        ; AC = F*G
ADD   E        ; AC = E + F*G
STORE T        ; T = E + F*G
LOAD  A        ; AC = A
MUL   B        ; AC = A*B
ADD   C        ; AC = A*B + C
SUB   D        ; AC = A*B + C - D
DIV   T        ; AC = (A*B + C - D) / (E + F*G)
STORE X        ; X = result

Total: 10 instructions

Note: The denominator is computed first so that only one temporary (T) is needed and the numerator can remain in the accumulator for the final DIV. An alternative 12-instruction version computes both sub-expressions, stores both, then reloads, which works but uses two extra instructions. The 10-instruction form is the standard optimal solution.

3. Zero-Address Instructions (Stack-Based)

Operands are implicit on the stack. Uses PUSH / POP for memory access and arithmetic on top two elements.

Postfix (reverse Polish) of the expression: $$A,B,,C,+,D,-,E,F,G,,+,/$$

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

Total: 14 instructions

Summary Table

Key Observation: As the number of addresses per instruction decreases, the number of instructions needed increases.

For the one-address form the optimal solution needs 10 instructions; a version that stores and reloads both operands needs 12. Both are logically correct, and 10 is the minimal standard form.