Previous Year Questions

(i) Define Superscalar.

Superscalar is a processor architecture that uses multiple parallel execution units (integer ALUs, FP units, load/store units) to issue and execute more than one instruction per clock cycle. Unlike a simple pipelined processor that completes at most one instruction per cycle, a 4-issue superscalar can theoretically retire up to 4 instructions every cycle.

(ii) Define Cluster Computer.

A Cluster is a collection of commodity computers (called nodes) interconnected through a high-speed network (like Ethernet or InfiniBand) that work together as a unified computing resource. Each node has its own private memory and OS instance. They communicate via message passing (e.g., MPI). Clusters are the foundation of modern supercomputers and cloud data centres.

(iii) Define Dataflow Architecture.

Dataflow architecture is a non-von Neumann computing paradigm where an instruction is executed as soon as all of its required input operands (data tokens) are available — there is no centralized Program Counter. Execution order is entirely determined by data dependencies, which naturally exposes maximum parallelism. Data tokens flow along edges of a dataflow graph from producer instructions to consumer instructions.

(iv) Define Instruction Pipelining.

Instruction Pipelining is a processor implementation technique where the execution of each instruction is broken into distinct stages (IF → ID → EX → MEM → WB) and multiple instructions are overlapped in execution — each stage processes a different instruction simultaneously, much like an assembly line.

(v) What is the primary goal of exception handling?

To ensure graceful recovery and prevent system failure when unexpected events occur during instruction execution (e.g., arithmetic overflow, page fault, illegal opcode). The processor must save the precise architectural state, invoke the OS exception handler, and resume execution correctly after the event has been handled.

(vi) What policy in virtual memory decides which page to remove?

The Page Replacement policy (algorithms like LRU, FIFO, Optimal, Clock) decides which existing page to evict from physical memory when a new page needs to be loaded and all frames are occupied.

(vii) What is a superpipelined processor?

A superpipelined processor divides the execution pipeline into a much larger number of finer-grained stages than a conventional pipeline. This allows the clock frequency to increase proportionally (since each stage has less combinational logic delay). For example, while a standard pipeline might have 5 stages, a superpipelined design might have 12–20+ stages, enabling a much higher clock rate but increasing branch misprediction penalties.

(viii) What is synchronization in a centralized shared-memory architecture?

Synchronization is the coordination mechanism that ensures mutual exclusion when multiple processors access shared data. It prevents race conditions and ensures data consistency. Common synchronization primitives include:

• Locks/Mutexes — Only one processor holds the lock at a time.
• Barriers — All processors must reach the barrier before any can proceed.
• Atomic operations — Hardware instructions like Test-and-Set, Compare-and-Swap that execute indivisibly.

(ix) What is exception handling in computer architecture?

The hardware/software mechanism for responding to exceptions — anomalous or exceptional conditions (like arithmetic overflow, undefined opcode, page fault, or external interrupts) that arise during program execution. The processor interrupts the current instruction stream, saves the program counter and machine state, and transfers control to a predefined OS exception handler routine.

(x) What are memory replacement policies?

Algorithms used to decide which page in physical memory to evict when a page fault occurs and all frames are occupied. Key policies:

• LRU (Least Recently Used): Evicts the page that hasn't been accessed for the longest time.
• FIFO (First-In, First-Out): Evicts the oldest page (first to arrive). Suffers from Belady's anomaly.
• Optimal (Belady's): Evicts the page that won't be used for the longest time in the future (theoretical, not implementable).

(xi) What is a memory replacement policy?

An algorithm (like LRU, FIFO, or Clock) used to choose a specific page to be removed from main memory when a page fault occurs and no free frames exist. The goal is to minimize the total number of future page faults.

(xii) What is a VLIW processor?

Very Long Instruction Word (VLIW) is a processor architecture where each instruction word is very wide (e.g., 128–1024 bits) and contains multiple independent operations (e.g., an integer add, an FP multiply, a load, a branch) packed together by the compiler. The hardware does not need dynamic scheduling logic — it simply dispatches each operation to its designated functional unit. Examples: Intel Itanium (IA-64), TI C6000 DSPs.

Cache Memory is a small, very fast memory placed between the CPU and Main Memory. It stores copies of the most frequently accessed data and instructions from main memory, so that the CPU can access them in just 1–3 clock cycles instead of waiting 50–100+ cycles for main memory.

Key Differences from Main Memory:

• Technology: Cache uses SRAM (Static RAM — 6-transistor cells, no refresh needed). Main memory uses DRAM (Dynamic RAM — 1-transistor + 1-capacitor cells, requires periodic refresh).
• Speed: L1 cache access: ~1–4 ns. DRAM access: ~50–100 ns. Cache is roughly 10–50× faster.
• Size: L1: 32–64 KB; L2: 256 KB–1 MB; L3: 4–64 MB. Main Memory: 4–128 GB. Cache is orders of magnitude smaller.
• Cost: SRAM costs significantly more per bit (~$500/GB vs ~$5/GB for DRAM), which is why cache sizes remain small.
• Management: Cache is managed entirely by hardware (the cache controller), transparent to the programmer. Main memory is managed by the OS (virtual memory, page tables).
• Locality: Cache exploits temporal locality (recently used data is likely needed again) and spatial locality (nearby addresses are likely needed next) to achieve hit rates of 90–99%.

A superscalar processor aims to achieve IPC (Instructions Per Cycle) > 1 by issuing multiple instructions simultaneously. However, this introduces several critical design trade-offs:

• Hardware Complexity vs. Performance Gain: Superscalar processors need complex hardware for: (a) fetching multiple instructions per cycle, (b) decoding multiple instructions in parallel, (c) detecting dependencies between instructions, (d) dynamic instruction scheduling (reservation stations), and (e) register renaming (RAT — Register Alias Table). Each additional issue slot exponentially increases the hardware cost (area, power, verification complexity).
• ILP Availability vs. Issue Width: The actual speedup is limited by the Instruction-Level Parallelism (ILP) inherent in the program. If the code has many sequential dependencies, the extra execution units sit idle. Typical programs exhibit ILP of only 2–4, meaning a 6-wide superscalar often wastes half its resources.
• Instruction Window Size: A larger instruction window allows the hardware to look further ahead to find independent instructions. However, the associative comparison logic (for wakeup and select) scales as O(n²), making very large windows impractical. Modern designs use 200–300 entry reorder buffers.
• Branch Prediction Accuracy: With multiple instructions in flight, a branch misprediction wastes even more work. A 4-wide superscalar with a 15-stage pipeline can waste 60 instructions on a single misprediction. This demands highly accurate (>95%) dynamic branch predictors, adding further hardware complexity.
• Power Consumption: The speculation logic, multiple execution units, and large register files consume significant dynamic and static power, creating thermal challenges.

Data Hazards occur in pipelined processors when instructions that are close together in the instruction stream have data dependencies — one instruction needs a value that hasn't been produced yet by a preceding instruction.

Types of Data Hazards:

• RAW (Read After Write) — True Dependency: Instruction B reads a register that Instruction A writes. B must wait for A's result. Example: ADD R1, R2, R3 followed by SUB R4, R1, R5. The SUB needs R1's new value before ADD has written it back.
• WAW (Write After Write) — Output Dependency: Two instructions write to the same register. The second write must happen after the first. Only occurs in out-of-order or multi-cycle pipelines.
• WAR (Write After Read) — Anti-Dependency: Instruction B writes a register that Instruction A reads. B must not overwrite the value before A has read it. Only occurs in out-of-order execution or with register renaming issues.

Resolution Techniques:

• Data Forwarding (Bypassing): Special hardware datapaths route the ALU result from the EX/MEM or MEM/WB pipeline register directly to the ALU input of the dependent instruction, bypassing the register file. This eliminates stalls for most arithmetic RAW hazards.
• Pipeline Stalling (Interlocking): The hazard detection unit inserts "bubbles" (NOPs) into the pipeline to delay the dependent instruction until the data is available. Used when forwarding alone is insufficient (e.g., Load-Use hazard requires 1 mandatory stall cycle).
• Compiler Instruction Scheduling: The compiler reorders independent instructions to fill the "gap" between a data-producing instruction and its consumer, avoiding the stall entirely without any additional hardware.
• Register Renaming: Eliminates WAW and WAR hazards by dynamically assigning physical registers to architectural registers, ensuring each write targets a unique physical location.

A Cache Miss occurs when the CPU requests data (or an instruction) that is not currently present in the cache memory. The processor must then fetch the data from the slower main memory (or a lower-level cache like L2/L3), incurring a significant latency penalty called the miss penalty (typically 50–200 clock cycles).

The 3 C's Classification of Cache Misses:

• Compulsory Misses (Cold-Start Misses): The very first access to any block of data will always be a miss because the block has never been loaded into the cache. These are unavoidable — even an infinitely large cache would suffer compulsory misses. Mitigation: Prefetching (hardware or software) to load blocks before they are needed.
• Capacity Misses: Occur when the entire working set of the program is larger than the cache. Even with a fully-associative cache, blocks get evicted and later needed again. Mitigation: Increase cache size; optimize code for better data locality (e.g., loop tiling/blocking).
• Conflict Misses (Collision Misses): Occur in direct-mapped or set-associative caches when multiple blocks map to the same cache set, causing useful blocks to be evicted even when the cache has unused space in other sets. Mitigation: Increase associativity (e.g., move from 2-way to 8-way set-associative); use victim caches.

A fourth "C" is sometimes added: Coherence Misses — misses caused by cache invalidation due to writes from other processors in a multiprocessor system.

The Memory Management Unit (MMU) is a critical hardware component (usually integrated into the CPU) that acts as the bridge between the CPU's virtual address space and the physical memory hardware. Its roles include:

• Address Translation: The MMU translates every virtual (logical) address generated by the CPU into a physical address in main memory. It does this by looking up the virtual page number in the Page Table to find the corresponding physical frame number, then appending the page offset.
• TLB Management: The MMU maintains a Translation Lookaside Buffer (TLB) — a small, fast, fully-associative cache that stores recent virtual-to-physical address translations. A TLB hit avoids the slow page table lookup entirely. Typical TLB hit rate: 99%+.
• Page Fault Generation: If the page table entry indicates the requested page is not in physical memory (valid bit = 0), the MMU generates a page fault exception. The OS then handles loading the page from disk into a free frame.
• Memory Protection: The MMU checks access permission bits (read/write/execute) stored in each page table entry. If a process tries to write to a read-only page or execute a non-executable page, the MMU raises a protection fault.
• Support for Multi-level Page Tables: Modern MMUs support hierarchical page tables (2-level, 4-level as in x86-64) to reduce the memory overhead of storing page tables for large address spaces.

In a pipelined processor, a Hazard is a situation that prevents the next instruction in the instruction stream from executing during its designated clock cycle, forcing a pipeline stall (bubble). Hazards are the primary reason real pipelines never achieve the theoretical speedup of k (number of stages).

1. Structural Hazards (Resource Conflicts):

• Cause: The hardware cannot support all possible combinations of instructions executing simultaneously. Two instructions need the same physical hardware resource in the same clock cycle.
• Classic Example: A unified memory (single-port) for both instructions and data. When a Load instruction is in the MEM stage reading data, the IF stage cannot simultaneously fetch the next instruction because they share the same memory port.
• Another Example: A single ALU shared between the EX stage (for arithmetic) and the ID stage (for branch target calculation).
• Solutions:
  • Resource Duplication: Use a Harvard Architecture — separate Instruction Cache (I-Cache) and Data Cache (D-Cache). This is the standard modern solution.
  • Pipeline Stalling: If duplication is too expensive, the hardware stalls one of the conflicting instructions for one cycle.

2. Data Hazards (Data Dependencies):

• Cause: An instruction depends on the result of a previous instruction that is still in the pipeline.
• Types:
  • RAW (Read After Write) — True Dependency: Most common and dangerous. Instruction j tries to read a source register before instruction i has written to it. Example:
    ADD R1, R2, R3 (writes R1 in WB — cycle 5)
    SUB R4, R1, R5 (reads R1 in ID — cycle 3)
    SUB reads the OLD value of R1 — incorrect!
  • WAW (Write After Write) — Output Dependency: Two instructions write to the same register; the writes must occur in program order.
  • WAR (Write After Read) — Anti-Dependency: Instruction j writes a register that instruction i still needs to read.
• Solutions:
  • Forwarding (Bypassing): Hardware datapaths route results from the EX/MEM or MEM/WB pipeline registers directly back to the ALU inputs. Eliminates most RAW stalls.
  • Pipeline Stalling (Interlock): For Load-Use hazards (a Load followed immediately by a dependent instruction), forwarding alone cannot help because the data isn't available until the end of the MEM stage. The hardware inserts exactly 1 bubble.
  • Compiler Scheduling: The compiler reorders independent instructions to separate dependent pairs, filling the gap naturally.
  • Register Renaming: Eliminates WAW and WAR by mapping architectural registers to a larger set of physical registers.

3. Control Hazards (Branch Hazards):

• Cause: The pipeline has already fetched subsequent sequential instructions, but a branch instruction changes the Program Counter (PC) to a non-sequential target. The fetched instructions are wrong and must be flushed.
• Penalty: In a 5-stage pipeline where the branch is resolved in the ID stage, the penalty is 1 cycle (1 instruction flushed). In deeper pipelines (15–20 stages), the penalty can be 15+ cycles.
• Solutions:
  • Static Branch Prediction: Assume "branch not taken" (always fetch sequentially) or predict backward branches as taken (loops). Simple but limited accuracy (~60–70%).
  • Dynamic Branch Prediction: Use a Branch History Table (BHT) or Branch Target Buffer (BTB) to predict based on past behaviour. Two-bit saturating counters achieve ~85–90% accuracy. Tournament predictors (combining local and global history) achieve ~95%+.
  • Delayed Branching: The compiler fills the branch delay slot (the instruction immediately after the branch) with a useful, independent instruction that executes regardless of the branch outcome.
  • Early Branch Resolution: Move the branch comparison hardware into the ID stage to reduce the penalty from 2 cycles to 1 cycle.

The design goal is to minimize every stall component through the techniques above, bringing the Effective CPI as close to 1.0 (or below 1.0 in superscalar designs) as possible.

(a) Concept of Virtual Memory:

Virtual Memory is a memory management technique that creates an illusion to users and programs that the computer has a very large, contiguous, and private main memory — even if the actual physical RAM is much smaller.

• Core Idea: Each process is given its own virtual address space (e.g., 0 to 2⁶⁴ - 1 on a 64-bit system). The OS and hardware cooperate to map only the actively used portions of this virtual space to physical RAM. Inactive portions reside on the much larger (but slower) disk/SSD, called swap space or page file.
• Key Benefits:
  • Memory Isolation: Each process has its own address space and cannot corrupt another process's memory.
  • Larger Address Space: Programs can use more memory than physically available — the OS transparently swaps pages between RAM and disk.
  • Simplified Memory Allocation: Programs see a simple, contiguous address space. The physical allocation can be scattered across non-contiguous frames.
  • Efficient Sharing: Multiple processes can share the same physical page of code (e.g., shared libraries like libc) by mapping different virtual addresses to the same physical frame.
  • Protection: Page table entries contain protection bits (R/W/X) enforced by hardware.

(b) Implementation in Modern Systems:

Virtual memory is implemented using a combination of hardware (MMU, TLB) and OS software (page tables, page replacement algorithms).

Step 1 — Paging:

• The virtual address space is divided into fixed-size blocks called pages (typically 4 KB).
• Physical memory is divided into equal-sized blocks called frames.
• A virtual address is split into: [Virtual Page Number (VPN) | Page Offset].

Step 2 — Page Table:

• The OS maintains a Page Table for each process, stored in main memory.
• Each entry maps a VPN → Physical Frame Number (PFN) and contains: Valid bit, Dirty bit, Reference bit, Protection bits (R/W/X).
• Modern systems use multi-level page tables (e.g., x86-64 uses 4-level: PML4 → PDPT → PD → PT) to avoid storing entries for unmapped regions.

Step 3 — Translation Lookaside Buffer (TLB):

• Accessing the page table in memory for every address translation would double the memory access time. The TLB is a small, fast, fully-associative cache inside the MMU that caches recent VPN → PFN translations.
• TLB hit rate: typically 99%+. A TLB miss triggers a page table walk (hardware or software).

Step 4 — Page Fault Handling:

• If the page table entry's valid bit = 0, the page is on disk → Page Fault exception.
• The OS selects a victim page (using LRU, Clock, or similar algorithm), writes it to disk if dirty, loads the requested page from disk into the freed frame, updates the page table, and restarts the faulting instruction.

Cache Coherence is the problem of ensuring that all processors in a multiprocessor system see a consistent view of shared memory. When Processor A writes to a memory location cached by Processor B, B's cached copy becomes stale. If B reads the stale value, the program produces incorrect results.

Cache Coherence Miss Penalty:

• A coherence miss (sometimes called the "4th C" of cache misses) occurs when Processor B tries to read a block that was invalidated or updated by Processor A's write.
• The miss penalty is the additional latency incurred to either: (a) fetch the updated block from main memory, or (b) fetch it directly from Processor A's cache via a cache-to-cache transfer.
• This penalty can be very large: 100–500 cycles depending on the interconnect latency, far worse than a regular L2/L3 cache miss.

1. Snoopy Bus Protocols (for Bus-Based Multiprocessors):

• Mechanism: All caches are connected to a shared bus. Every cache controller snoops (monitors) the bus for memory transactions issued by other caches.
• Write-Invalidate Protocol: When a processor writes to a shared block, it broadcasts an invalidation signal on the bus. All other caches holding that block mark their copies as Invalid. On their next access, they must fetch the updated block.
• Write-Update (Write-Broadcast) Protocol: Instead of invalidating, the writing processor broadcasts the new data on the bus. All other caches update their copies immediately. Reduces later read misses but generates more bus traffic.

2. MESI Protocol (Detailed):

The most widely used snoopy protocol. Each cache line is in one of four states:

• Modified (M): The block is exclusively in this cache and has been written (dirty). Main memory copy is stale. This cache must write-back before any other cache can use it.
• Exclusive (E): The block is exclusively in this cache but is clean (matches main memory). Can be written silently (transitions to M) without bus traffic.
• Shared (S): The block may be in multiple caches. All copies and main memory are consistent. A write requires broadcasting an invalidation first.
• Invalid (I): The block is not valid. Any access triggers a cache miss.

How MESI reduces penalty: The Exclusive state allows a single-reader to write without bus traffic. The Modified state enables cache-to-cache transfers — when another processor requests a Modified block, the owning cache can supply the data directly (intervention), which is faster than going to main memory.

3. Directory-Based Protocols (for Scalable Multiprocessors):

• Problem with Snooping: Snoopy protocols require a shared bus, which becomes a bottleneck beyond ~8–16 processors because every transaction is broadcast to all caches.
• Solution: A directory (distributed or centralized) is maintained alongside main memory. For each memory block, the directory records: which caches have a copy, and whether the block is clean or dirty.
• Operation: When a processor wants to read or write a block, it sends a point-to-point message to the directory (home node). The directory then sends targeted invalidation/update messages only to the caches that actually hold the block — no broadcasting needed.
• Scalability: Communication is proportional to the number of sharers, not the total number of processors. Scales to hundreds or thousands of processors.

4. Additional Techniques to Reduce Coherence Penalty:

• Optimized Interconnects: Replace shared buses with high-bandwidth point-to-point links (e.g., Intel QPI, AMD Infinity Fabric) or crossbar switches to reduce communication latency.
• Relaxed Consistency Models: Allow certain memory operations to be reordered (e.g., Total Store Ordering, Release Consistency), reducing the number of coherence transactions.
• Cache-to-Cache Transfers: When a dirty block is needed, it is transferred directly from the owning cache rather than being written back to memory first and then fetched.
• Software Optimizations: Minimize false sharing (where unrelated variables in the same cache line are written by different processors) through padding and data structure alignment.

Both Superscalar and VLIW architectures aim to execute multiple operations per clock cycle, but they take fundamentally different approaches to achieving this goal.

Superscalar Architecture:

• Scheduling: Dynamic — the hardware is responsible for detecting independent instructions at runtime and dispatching them to available execution units. Uses Tomasulo's algorithm, reservation stations, and reorder buffers.
• Hardware Complexity: Very high. Requires: (a) complex fetch logic to fetch multiple instructions per cycle, (b) dependency detection hardware comparing every new instruction against all in-flight instructions, (c) register renaming (RAT) to eliminate false dependencies, (d) out-of-order execution engine, (e) reorder buffer for in-order retirement.
• Compiler Complexity: Relatively simple — the compiler doesn't need to schedule for parallelism; the hardware handles it.
• Binary Compatibility: Excellent. Old binaries run correctly (and faster) on newer superscalar processors because the hardware dynamically adapts to find parallelism. This is why x86 has thrived for decades.
• Performance: Very good at exploiting dynamic ILP. Can speculate past branches, handle variable-latency operations, and adapt to runtime conditions. Typical IPC: 2–4 for integer workloads.
• Power Consumption: High — the scheduling, speculation, and renaming logic consume significant power.
• Examples: Intel Core series, AMD Ryzen, ARM Cortex-A series.

VLIW Architecture:

• Scheduling: Static — the compiler is entirely responsible for analyzing the program, finding independent operations, and packing them into a single wide instruction word before execution.
• Hardware Complexity: Very low. The hardware simply reads the wide instruction word and dispatches each operation slot to its fixed functional unit. No dependency checking, no register renaming, no reorder buffer.
• Compiler Complexity: Very high. The compiler must perform aggressive instruction scheduling, software pipelining (modulo scheduling), speculative execution (predicated instructions), and trace scheduling to fill all slots. If the compiler can't find enough independent operations, it inserts NOPs, causing code bloat.
• Binary Compatibility: Poor. The instruction encoding is tightly coupled to the hardware's functional unit layout. Changing the number or type of functional units requires recompilation of all software. This is a major practical disadvantage.
• Performance: Excellent for regular, predictable workloads (DSP, media processing, scientific computing). Poor for irregular, branch-heavy code (general-purpose computing) where the compiler cannot statically predict behaviour.
• Power Consumption: Low — the simple hardware design allows higher clock speeds with less power.
• Examples: Intel Itanium (IA-64), TI TMS320C6000 DSPs, Transmeta Crusoe.

Summary Comparison Table:

Aspect	Superscalar	VLIW
Scheduling	Dynamic (hardware)	Static (compiler)
HW Complexity	Very High	Low
Compiler Complexity	Low	Very High
Binary Compat.	Excellent	Poor
Code Size	Normal	Large (NOP padding)
Power	High	Low
Best Suited For	General-purpose	DSP, Embedded, Scientific

Question: A system has a 64-bit virtual address space and a 4 KB page size. The page table is stored in main memory, which has a memory access time of 100 ns. The TLB has a hit rate of 90%, and a TLB miss takes 500 ns to service. What is the effective memory access time?

Step 1 — Identify Given Values:

• Virtual Address Space = 64 bits
• Page Size = 4 KB = 2¹² bytes → Page Offset = 12 bits
• Number of Virtual Pages = 2⁶⁴ / 2¹² = 2⁵² pages
• Main Memory Access Time (t_m) = 100 ns
• TLB Hit Rate (h) = 0.90 (90%)
• TLB Miss Penalty (t_miss) = 500 ns (includes page table walk + TLB update)
• TLB Access Time (t_tlb) ≈ 0 ns (negligible, assumed to overlap with cache access)

Step 2 — Understand the Two Scenarios:

• TLB Hit (90% of accesses): The translation is found in the TLB instantly. The CPU then accesses main memory to fetch the data.
  Time = t_tlb + t_m = 0 + 100 = 100 ns.
• TLB Miss (10% of accesses): The TLB doesn't have the translation. The hardware walks the page table in main memory (taking 500 ns), updates the TLB, and then accesses the actual data in main memory.
  Time = t_tlb + t_miss + t_m = 0 + 500 + 100 = 600 ns.

Step 3 — Calculate EMAT:

Substituting values:

EMAT = 0.90 × (0 + 100) + 0.10 × (0 + 500 + 100)

EMAT = 0.90 × 100 + 0.10 × 600

EMAT = 90 + 60

Step 4 — Analysis:

• Without a TLB, every access would require a page table walk (500 ns) + data access (100 ns) = 600 ns.
• With a TLB at 90% hit rate, the EMAT is only 150 ns — a 4× improvement over no TLB.
• If the TLB hit rate improved to 99%, EMAT = 0.99 × 100 + 0.01 × 600 = 99 + 6 = 105 ns — very close to ideal.
• Observation: Even a 64-bit address space with 2⁵² virtual pages requires an enormous page table (impractical as a flat table). This is why modern systems use multi-level page tables and inverted page tables to manage the size.