GATE COA Questions

Introduction

GATE (Graduate Aptitude Test in Engineering) regularly tests Computer Organization and Architecture concepts with numerical problems and conceptual questions. COA typically carries 10-15 marks in GATE CS/IT papers. This page covers the most frequently asked types of problems with detailed solutions, so you build both speed and accuracy for exam day.

Cache Memory Numerical Problems

Problem 1: Direct-Mapped Cache

Question: A computer has a 32-bit address space. The cache is direct-mapped with 256 lines, and each cache block is 64 bytes. Find the number of tag bits, index bits, and offset bits.

Solution:

• Block size = 64 bytes = 2⁶ → Offset bits = 6
• Number of cache lines = 256 = 2⁸ → Index bits = 8
• Tag bits = 32 - 8 - 6 = 18 bits

The address breakdown looks like:

Problem 2: Set-Associative Cache

Question: A 4-way set-associative cache has 64 sets, block size of 32 bytes, and the memory address is 24 bits. What is the tag size?

Solution:

• Block size = 32 = 2⁵ → Offset = 5 bits
• Number of sets = 64 = 2⁶ → Index = 6 bits
• Tag = 24 - 6 - 5 = 13 bits
• Total cache size = 4 × 64 × 32 = 8192 bytes = 8 KB

Problem 3: Average Memory Access Time

Question: A processor has L1 cache with hit time 1 ns and miss rate 5%. L2 cache has hit time 5 ns and miss rate 20%. Main memory access time is 100 ns. Calculate AMAT.

Solution:

Pipeline Problems

Problem 4: Pipeline Speedup

Question: A non-pipelined processor takes 20 ns per instruction. A 5-stage pipeline has each stage taking 5 ns with 1 ns overhead per register. What is the speedup for 100 instructions?

Solution:

• Non-pipelined time for 100 instructions = 100 × 20 = 2000 ns
• Pipeline clock cycle = max(stage delays) + overhead = 5 + 1 = 6 ns
• Pipeline time = (k + n - 1) × cycle = (5 + 100 - 1) × 6 = 104 × 6 = 624 ns
• Speedup = 2000/624 = 3.21

Note: Ideal speedup would be 5 (number of stages), but overhead and pipeline fill/drain reduce it.

Problem 5: Pipeline with Stalls

Question: In a 5-stage pipeline, 20% of instructions are loads followed by a dependent instruction (causing 1 stall), and 15% are branches (causing 2 stalls with no prediction). Find effective CPI.

Solution:

Problem 6: Pipeline Hazard Detection

Question: Identify data hazards in this instruction sequence:

Solution:

• RAW hazard between I1→I2: I2 reads R1 written by I1
• RAW hazard between I1→I3: I3 reads R1 written by I1
• RAW hazard between I2→I4: I4 reads R4 written by I2
• With forwarding: I1→I2 hazard resolved by EX-EX forwarding, I1→I3 by MEM-EX forwarding, I2→I4 by EX-EX forwarding. No stalls needed with full forwarding.

Amdahl's Law Problems

Problem 7: Speedup Calculation

Question: A program spends 40% time on floating-point operations. If we make floating-point 8× faster, what is the overall speedup? What if we make it infinitely fast?

Solution:

Key insight: Even making 40% of the program infinitely fast gives only 1.67× speedup. This is why Amdahl's Law matters — the sequential portion is the bottleneck.

Memory and Addressing Problems

Problem 8: Memory Chip Organization

Question: Design a 64KB memory using 16K × 4-bit memory chips. How many chips are needed? How many address lines?

Solution:

• Required: 64KB = 64K × 8 bits
• Each chip: 16K × 4 bits
• Chips for width: 8/4 = 2 chips in parallel (to get 8-bit word)
• Chips for depth: 64K/16K = 4 groups
• Total chips = 4 × 2 = 8 chips
• Address lines = log₂(64K) = 16 bits
• Chip select needs: log₂(4) = 2 bits (from upper address lines)

Problem 9: Virtual Memory

Question: A system has 32-bit virtual address, 24-bit physical address, and 4KB page size. Find: number of entries in page table, bits in each entry.

Solution:

• Page size = 4KB = 2¹² → Offset = 12 bits
• Virtual pages = 2³²/2¹² = 2²⁰ → Page table entries = 2²⁰ = 1M
• Physical frames = 2²⁴/2¹² = 2¹² → Frame number = 12 bits
• Each page table entry = Frame number + control bits = 12 + ~4 = 16 bits (typically)

DMA and I/O Problems

Problem 10: DMA Transfer

Question: A DMA controller transfers data from disk at 2 MB/s to memory. The disk has blocks of 512 bytes. The bus clock is 100 MHz and each bus transfer moves 4 bytes. How much bus bandwidth does DMA consume?

Solution:

• DMA transfer rate = 2 MB/s = 2 × 10⁶ bytes/s
• Bus transfers needed = 2 × 10⁶ / 4 = 500,000 transfers/s
• Bus clock = 100 MHz = 10⁸ cycles/s
• Bus bandwidth consumed = 500,000 / 10⁸ = 0.5%

The DMA steals very little bus bandwidth — that is why it is efficient.

CPU Performance Problems

Problem 11: CPI and MIPS

Question: A processor runs at 2 GHz. A program has: 40% ALU (CPI=1), 30% Load/Store (CPI=3), 20% Branch (CPI=2), 10% Multiply (CPI=4). Find average CPI and MIPS rating.

Solution:

Problem 12: Speedup with New Architecture

Question: Machine A has clock rate 4 GHz and CPI 1.5. Machine B has clock rate 3 GHz and CPI 1.0. Which is faster and by how much for a program with 10⁹ instructions?

Solution:

Machine B is faster. Speedup = 0.375 / 0.333 = 1.125× faster

Frequently Asked Conceptual Questions

Q: Why does increasing pipeline stages not always improve performance?

Deeper pipelines have more overhead (latch delays), more hazards (longer forwarding paths), and higher branch misprediction penalties. Beyond a certain depth, diminishing returns set in — this is why modern CPUs use 14-20 stages rather than 50+.

Q: What is the difference between spatial and temporal locality?

• Temporal locality: If you accessed address X, you will likely access X again soon (loops, variables)
• Spatial locality: If you accessed X, you will likely access X+1, X+2 soon (arrays, sequential code)

Q: Why does 2's complement not have two zeros?

In 2's complement, +0 = 0000...0 and negating it (invert + add 1) gives 0000...0 again (overflow discarded). The extra pattern 1000...0 represents -2ⁿ⁻¹ instead of -0.

Q: Can a pipelined processor have CPI less than 1?

Yes! Superscalar processors issue multiple instructions per cycle, achieving CPI < 1 (or equivalently IPC > 1). A 4-wide superscalar can theoretically achieve CPI = 0.25.

GATE Exam Strategy for COA

1. Practice numericals daily — Cache and pipeline problems are almost guaranteed every year
2. Draw timing diagrams for pipeline problems — visual approach reduces errors
3. Memorize key formulas — AMAT, Amdahl's Law, CPI calculation, pipeline speedup
4. Watch for unit consistency — ns vs μs vs ms mistakes are common under pressure
5. Previous year papers — GATE 2015-2024 COA questions show clear patterns
6. Common traps — miss rate vs hit rate confusion, forgetting pipeline register overhead, mixing up address bits