Stored Program Concept

Definition:

A fundamental computer architecture principle where both data and instructions are stored in the
same memory and treated identically by the CPU.

Key Points:

 Von Neumann Architecture (Princeton Architecture) follows this concept.

 Harvard Architecture (used in microcontrollers) separates instruction and data memory.

Example:

 When you run a program (e.g., ADD R1, R2), the instruction is fetched from memory just like
data.

Previous Year Question:

Q: What is the stored program concept? How does it differ from Harvard Architecture?
A:

 The stored program concept means instructions and data are stored in the same memory.

 Difference: Harvard Architecture uses separate memories for instructions and data (faster
but more complex).

CPI (Cycles Per Instruction)

Definition:

Average number of clock cycles needed to execute a single instruction.

Formula:

CPI=Total Clock Cycles/Number of Instructions

Example:

 A program executes 1000 instructions in 2500 clock cycles.

 CPI = 25001000=2.510002500=2.5

Previous Year Question:

Q: A program runs in 10,000 cycles and executes 5,000 instructions. What is the CPI?
A:

CPI=10,0005,000=2CPI=5,00010,000=2

3. MIPS (Million Instructions Per Second)

Definition:
Measures CPU performance in millions of instructions executed per second.

Formula:

MIPS=Instruction CountExecution Time×106=Clock Rate (Hz)CPI×106MIPS=Execution Time×106Instru

ction Count=CPI×106Clock Rate (Hz)

Example:

 A 2 GHz CPU with CPI = 1.5:

MIPS=2×1091.5×106=1333.33MIPS=1.5×1062×109=1333.33

Previous Year Question:

Q: A 1.5 GHz processor has a CPI of 2. Calculate MIPS.

A:

MIPS=1.5×1092×106=750MIPS=2×1061.5×109=750

4. Amdahl’s Law

Definition:

Predicts the maximum speedup achievable when improving a portion of a system.

Formula:

Speedup=1(1−P)+PSSpeedup=(1−P)+SP1

 PP = Fraction of program improved.

 SS = Speedup of the improved part.

Example:

 If 40% of a program is optimized to run 5x faster:

Speedup=1(1−0.4)+0.45=10.6+0.08=1.47xSpeedup=(1−0.4)+50.41=0.6+0.081=1.47x

Previous Year Question:

Q: If 30% of a program is made 10x faster, what is the overall speedup?

A:

Speedup=1(1−0.3)+0.310=10.7+0.03=1.37xSpeedup=(1−0.3)+100.31=0.7+0.031=1.37x

5. Expected Exam Questions & Answers

Q1: Compare CPI and MIPS.

A:
Metric Definition Use Case

CPI Cycles per instruction Measures efficiency of instruction execution

MIPS Millions of instructions per second Measures raw CPU performance

Q2: Why does Amdahl’s Law show diminishing returns?

A:

 Because unimproved portions (1−P1−P) dominate as SS increases.

 Example: Even if S=∞S=∞, max speedup = 11−P1−P1.

Q3: A CPU runs at 3 GHz, executes 6 billion instructions in 4 seconds. Find CPI.

A:

Instruction Count=6×109Instruction Count=6×109Clock Cycles=3×109×4=12×109Clock Cycles=3×109

×4=12×109CPI=12×1096×109=2CPI=6×10912×109=2

Summary Table for Quick Revision

Concept Formula Example

Stored Program Instructions + Data in same memory Von Neumann vs Harvard

Clock CyclesInstructionsInstructionsClock Cycle

CPI CPI = 2.5
s

MIPS Clock RateCPI×106CPI×106Clock Rate 750 MIPS

Amdahl’s Law 1(1−P)+PS(1−P)+SP1 Speedup = 1.37x

1. Forwarding (Operand Forwarding / Bypassing)

Definition:

A technique to reduce pipeline stalls caused by data hazards by directly passing results from one
pipeline stage to another without waiting for writeback.

Why Needed?

 Without forwarding, RAW (Read-After-Write) hazards cause pipeline bubbles (stalls).

Example:

ADD R1, R2, R3 ; R1 = R2 + R3

SUB R4, R1, R5 ; Needs R1 from previous instruction

 Without Forwarding: SUB must wait for ADD to write R1 to the register file.

 With Forwarding: The result of ADD is forwarded directly to SUB’s EX stage.

Types of Forwarding:

1. EX → EX Forwarding: For back-to-back ALU operations.

2. MEM → EX Forwarding: When a load instruction feeds an ALU operation.

Exam Question:

Q: What is forwarding? How does it resolve RAW hazards?

A:

 Forwarding bypasses the register file by sending data directly from one pipeline stage to
another.

 It avoids stalls by allowing dependent instructions to access results before they are written
back.

2. Branch Prediction

Definition:

A technique to minimize pipeline stalls caused by control hazards (branches) by predicting whether
a branch will be taken or not.

Types:

1. Static Branch Prediction

o Always predict "not taken" (simple but inefficient).

o Example: MIPS uses "delay slots" to handle branches.

2. Dynamic Branch Prediction

o Uses Branch History Table (BHT) to track past behavior.

o 2-bit Predictor: Improves accuracy by tracking strong/weak taken/not-taken states.

Example:

LOOP:

BEQ R1, R2, TARGET ; Branch if R1 == R2

ADD R3, R4, R5

 J LOOP

TARGET:

SUB R6, R7, R8

 Without Prediction: Pipeline stalls until BEQ resolves.

 With Prediction: CPU predicts "taken" and fetches TARGET speculatively.

Exam Question:

Q: Compare static and dynamic branch prediction.

A:

Feature Static Prediction Dynamic Prediction

Complexity Low High (needs BHT)

Accuracy Poor High (adapts)

Hardware Cost None Extra registers

3. Loop Unrolling

Definition:

A compiler optimization that reduces loop overhead by executing multiple loop iterations in a single
iteration.

Why Used?

 Reduces branch penalties (fewer loop condition checks).

 Improves instruction-level parallelism (ILP).

Example:

Original Loop (5 iterations):

for (int i = 0; i < 5; i++) {

a[i] = b[i] + c[i];

Unrolled Loop (2x unrolling):

for (int i = 0; i < 5; i+=2) {

a[i] = b[i] + c[i];

a[i+1] = b[i+1] + c[i+1];

}

 Benefits:

o Fewer branch instructions (from 5 checks → 3 checks).

o Better pipeline utilization.

Trade-offs:

✔ Faster execution (reduced branches).

❌ Increased code size (can cause cache misses).

Exam Question:

Q: What is loop unrolling? Give an example with 4x unrolling.

A:

 Loop unrolling reduces loop overhead by executing multiple iterations per cycle.

 4x Unrolling Example:

for (int i = 0; i < 16; i+=4) {

a[i] = b[i] + c[i];

a[i+1] = b[i+1] + c[i+1];

a[i+2] = b[i+2] + c[i+2];

a[i+3] = b[i+3] + c[i+3];

Summary Table for Quick Revision

Technique Purpose Key Mechanism

Forwarding Eliminate RAW hazards Bypasses register writeback

Branch Prediction Minimize control hazards Predicts taken/not-taken (static/dynamic)

Loop Unrolling Reduce branch penalties Executes multiple iterations at once

Expected Exam Problems

Q1: How does forwarding improve CPI in pipelining?

A:

 By eliminating stalls due to RAW hazards, forwarding recycles wasted cycles, improving CPI.
Q2: Why is a 2-bit predictor better than a 1-bit predictor?

A:

 A 2-bit predictor avoids mispredictions after a single anomaly (e.g., a rare branch exit).

Q3: When is loop unrolling NOT beneficial?

A:

 When the loop body is large (causes I-cache misses) or iteration count is unknown.

Final Tips for Exams

✔ Draw diagrams for forwarding paths (EX → EX, MEM → EX).

The differences between hardwired and micro-programmed control units:

Hardwired Control Unit Micro-programmed Control Unit

Implementation Fixed set of logic gates and Microcode stored in memory

circuits

Flexibility Less flexible, difficult to More flexible, easier to modify

modify

Instruction Set Supports limited instruction Supports complex instruction sets

sets

Complexity of Design Simple design, easy to Complex design, more difficult to

implement implement

Speed Fast operation Slower operation due to microcode

decoding

Debugging and Testing Difficult to debug and test Easier to debug and test

Size and Cost Smaller size, lower cost Larger size, higher cost

Maintenance and Difficult to upgrade and Easier to upgrade and maintain

Upgradability maintain