ADVANCED COMPUTER ARCHITECTURE — MAKAUT EXAM NOTES Units 1–4 | 5-Mark & 15-Mark Q&A

■
ADVANCED COMPUTER
ARCHITECTURE
Complete Exam Notes — MAKAUT

Units 1–4 | 5-Mark & 15-Mark Model Answers

★★ = Very Important Questions for This Year's Exam ★★

Pipelining · Cache · ILP · Multiprocessor · Non-Von Neumann

How to use these notes: Questions marked ★★ VERY IMPORTANT (gold banner) are the most frequently
asked in MAKAUT exams and highly likely this year. Read all concept boxes first, then study model answers. For
5-mark answers: definition + 3-4 points. For 15-mark: use all sections + diagrams/tables.

Unit Coverage

Unit 1 Pipelining — hazards, exception handling, optimization (9L)

Unit 2 Hierarchical Memory — Cache, Virtual Memory, Replacement (8L)

Unit 3 ILP — Superscalar, VLIW, Vector Processors (6L)

Unit 4 Multiprocessor + Non-Von Neumann Architectures (12L)

★★ = Very Important This Year Page 1

ADVANCED COMPUTER ARCHITECTURE — MAKAUT EXAM NOTES Units 1–4 | 5-Mark & 15-Mark Q&A

UNIT 1 Pipelining & Computer Architecture Basics

Computer Arch Review · Quantitative Design · Pipeline Concepts · Hazards · Exception Handling · Optimization

■ Core Concepts — Unit 1

Pipeline: A technique where multiple instructions are overlapped in execution. Like an assembly line — while
instruction 1 is in stage 2, instruction 2 enters stage 1. 5 classic stages: IF (Instruction Fetch) → ID (Instruction
Decode) → EX (Execute) → MEM (Memory Access) → WB (Write Back).

Term Definition

Speedup Speedup = Time_unpipelined / Time_pipelined. Ideal: equal to number of stages.

CPI Cycles Per Instruction. Ideal pipelined CPI = 1. Hazards increase CPI.

Throughput Instructions completed per unit time. Pipeline maximises throughput.

Latency Time for one instruction to complete. Pipeline may increase latency.

MIPS Million Instructions Per Second. Performance metric.

AMAT Average Memory Access Time = Hit time + Miss rate × Miss penalty.

Pipeline Hazards — Summary

Hazard Type Explanation & Solution

Data Hazard Instruction needs data not yet produced by previous instruction. Solved by:
Forwarding/Bypassing, Stalls (NOPs), Compiler reordering.

Control Hazard Branch instruction causes wrong instructions to be fetched. Solved by: Branch prediction,
Delayed branching, Flush pipeline.

Structural Hazard Two instructions need the same hardware resource at same time. Solved by: Resource
duplication, Pipeline stalls.

RAW Hazard Read After Write — most common data hazard. Instruction reads before previous writes.

WAR Hazard Write After Read — anti-dependence. Instruction writes before previous reads.

WAW Hazard Write After Write — output dependence. Two writes to same register.

Exception Handling in Pipelines

Exception: Unexpected event during execution (divide by zero, page fault, illegal instruction).
Problem: In a pipeline, multiple instructions are in different stages — which one caused the exception?
Solutions: (1) Precise exceptions — pipeline is drained, state saved exactly at exception point. (2) Imprecise
exceptions — faster but harder to handle. (3) Hardware saves PC of faulting instruction; OS handler is invoked;
pipeline flushed.

★★ = Very Important This Year Page 2

ADVANCED COMPUTER ARCHITECTURE — MAKAUT EXAM NOTES Units 1–4 | 5-Mark & 15-Mark Q&A

Pipeline Optimization Techniques

• Loop Unrolling: Compiler replicates loop body to expose more ILP, reduce loop overhead.
• Instruction Scheduling: Compiler reorders instructions to avoid data hazards without changing results.
• Branch Prediction: Static (always taken/not taken) or Dynamic (history-based — 2-bit predictor).
• Delayed Branching: Execute instruction after branch regardless of outcome (branch delay slot).
• Register Renaming: Eliminate WAR/WAW hazards by using different physical registers.
• Forwarding/Bypassing: Route result directly from ALU output to ALU input — eliminates RAW stalls.

■ 5-MARK QUESTIONS — UNIT 1

5 Marks ★★ VERY IMPORTANT

Q. What is pipelining? What are its advantages and disadvantages?

Definition: Pipelining is an implementation technique where multiple instructions are overlapped in execution,
similar to an assembly line.
Pipeline Stages (Classic 5-stage):
• IF — Instruction Fetch
• ID — Instruction Decode / Register Read
• EX — Execute / ALU operation
• MEM — Memory Access
• WB — Write Back

Advantages:
• Increases instruction throughput (instructions per second).
• Better utilisation of hardware resources.
• Ideal CPI = 1 (one instruction completes per cycle).
• Speedup proportional to number of pipeline stages.

Disadvantages:
• Hazards (data, control, structural) reduce performance.
• Complex control logic required.
• Does not reduce latency of a single instruction.
• All stages must complete in same time (slowest stage limits speed).
■ Exam Tip: Definition + 5 stages + advantages + disadvantages = 5/5.

5 Marks ★★ VERY IMPORTANT

Q. Explain Data Hazards in pipeline with types and solutions.

Data Hazard: Occurs when an instruction depends on the result of a previous instruction still in the pipeline.

Type Description & Solution

RAW (Read After Write) Most common. Instr 2 reads register before Instr 1 writes it. Solution: Forwarding.

★★ = Very Important This Year Page 3

ADVANCED COMPUTER ARCHITECTURE — MAKAUT EXAM NOTES Units 1–4 | 5-Mark & 15-Mark Q&A

WAR (Write After Read) Instr 2 writes before Instr 1 reads. Anti-dependence. Solution: Register renaming.

WAW (Write After Write) Both instructions write same register. Output dep. Solution: Stall or renaming.

Solutions:
• Forwarding/Bypassing: Route result directly from ALU output to next instruction input — no stall needed.
• Pipeline Stall (NOP): Insert bubble (do-nothing cycle) until data is available.
• Compiler Reordering: Rearrange instructions so independent instructions fill the gap.
■ Exam Tip: Table of 3 types + solutions = full marks. Always give an example.

5 Marks ★★ VERY IMPORTANT

Q. What is Control Hazard? How is it handled?

Control Hazard: Arises due to branch instructions. When a branch is fetched, the pipeline doesn't know the next
instruction's address until branch is resolved (EX stage), causing wrong instructions to be fetched.

Solutions:
• Pipeline Flush: Cancel (squash) incorrectly fetched instructions when branch is resolved. Simple but wasteful.
• Delayed Branching: Always execute the instruction after the branch (delay slot). Compiler fills slot with useful
work.
• Static Branch Prediction: Always predict branch NOT taken (or always taken). Simple.
• Dynamic Branch Prediction: Use history of past branches. 2-bit saturating counter — changes prediction only
after 2 consecutive mispredictions. Accuracy: 85–95%.
• Branch Target Buffer (BTB): Cache of branch addresses and predicted targets. Reduces penalty.
■ Exam Tip: 4+ solutions with brief explanation = full marks.

5 Marks

Q. Explain Structural Hazard with example.

Structural Hazard: Occurs when two or more instructions need the same hardware resource at the same time and
the hardware cannot support all combinations of instructions in simultaneous overlapped execution.

Classic Example:
• Both a LOAD instruction (stage MEM) and an instruction fetch (stage IF) need to access memory simultaneously
— but there is only one memory unit.
• Solution: Use separate Instruction Memory (I-cache) and Data Memory (D-cache) — eliminates this hazard.

Other Examples:
• Single write port in register file → two instructions both need to write back simultaneously.
• Single functional unit for floating point — two FP operations can't proceed together.
Solutions: Resource duplication (add more units), Pipeline stalls, Scheduling.
■ Exam Tip: Definition + classic example + solution = 5/5.

5 Marks ★★ VERY IMPORTANT

Q. What are Quantitative Techniques in computer design? Explain any two principles.

★★ = Very Important This Year Page 4

ADVANCED COMPUTER ARCHITECTURE — MAKAUT EXAM NOTES Units 1–4 | 5-Mark & 15-Mark Q&A

Quantitative Techniques (from Hennessy & Patterson) provide measurable ways to evaluate and improve
computer performance.

Key Principles:
• Amdahl's Law: Speedup from improving one part is limited by how much that part is used. Speedup = 1 / [(1-f)
+ f/S] where f = fraction enhanced, S = speedup of enhancement.
• Make the Common Case Fast: Optimise the operations that happen most frequently. Even a small
improvement in common case gives big overall gain.
• CPU Performance Equation: CPU Time = Instruction Count × CPI × Clock Cycle Time.
• Principle of Locality: Programs reuse recently accessed data/code (temporal) and access nearby addresses
(spatial) — basis of caches.
• MFLOPS, MIPS: Metrics for reporting performance (though MIPS can be misleading).
■ Exam Tip: Name 4-5 principles with formulas. Amdahl's Law is always asked.

■ 15-MARK QUESTIONS — UNIT 1

15 Marks ★★ VERY IMPORTANT

Q. Explain all types of pipeline hazards in detail with solutions and techniques for pipeline
optimization.

SECTION A — DATA HAZARDS

Data hazards occur when an instruction depends on the result of a prior instruction still in the pipeline.

Type Explanation

RAW Read After Write — true dependence. Instr j reads register written by instr i. Most common and dangerous.

WAR Write After Read — anti-dependence. Instr j writes before instr i reads. Solved by register renaming.

WAW Write After Write — output dependence. Both write same register. Solved by renaming or stall.

Solutions for Data Hazards:

• Forwarding/Bypassing: Pass EX stage result directly to EX input of next instruction — eliminates most RAW
stalls without waiting for WB.
• Load-Use Hazard: LOAD followed immediately by instruction using loaded value — requires 1-cycle stall even
with forwarding.
• Compiler Scheduling: Insert independent instructions between dependent ones.

SECTION B — CONTROL HAZARDS

Occur due to branch instructions. Pipeline fetches wrong instructions while branch outcome is unknown.
• Branch Penalty: Number of cycles wasted = stages between IF and branch resolution.
• Static Prediction: Always predict not-taken. Simple. Effective for loops (~60% accuracy).
• Dynamic Prediction (2-bit): 2-bit saturating counter. States: Strongly Taken → Weakly Taken → Weakly
Not-Taken → Strongly Not-Taken. Accuracy: 85–95%.
• Branch Target Buffer (BTB): Small cache storing branch instruction PC → predicted target PC. Accessed
during IF.
• Delayed Branch: Compiler fills branch delay slot with useful instruction.

★★ = Very Important This Year Page 5

ADVANCED COMPUTER ARCHITECTURE — MAKAUT EXAM NOTES Units 1–4 | 5-Mark & 15-Mark Q&A

SECTION C — STRUCTURAL HAZARDS

Two instructions need same hardware simultaneously.
• Unified memory → Harvard architecture (separate I-cache, D-cache) solves IF/MEM conflict.
• Register file write port conflict → add multiple write ports or stall.
• Single FP unit → add pipeline FP unit or multiple FP units.

SECTION D — PIPELINE OPTIMIZATION TECHNIQUES

Technique Explanation

Loop Unrolling Replicate loop body N times. Exposes more ILP; reduces loop overhead branches.

Instruction Scheduling Reorder instructions (no semantic change) to fill delay slots and avoid hazards.

Register Renaming Map logical registers to physical registers. Eliminates WAR and WAW hazards.

Speculative Execution Execute instructions before knowing if they're needed (branch speculation).

Branch Prediction Predict branch direction early. Reduces control hazard penalty significantly.

Superscalar Issue Issue multiple instructions per cycle — further hides pipeline latencies.

SECTION E — EXCEPTION HANDLING

• Exception types: Interrupts (external), Traps (intentional — syscall), Faults (recoverable — page fault), Aborts
(unrecoverable).
• Precise Exception: All instructions before faulting instruction are completed; none after are committed. Harder to
implement but required by most OSes.
• Handler: Hardware saves PC and status; jumps to OS exception handler routine; handler fixes issue; resumes.
■ Exam Tip: 5 sections × 3 marks each = 15. Use tables, bold headings. Mention examples in each section.

★★ = Very Important This Year Page 6

ADVANCED COMPUTER ARCHITECTURE — MAKAUT EXAM NOTES Units 1–4 | 5-Mark & 15-Mark Q&A

UNIT 2 Hierarchical Memory Technology

Cache Organization · Miss Reduction · Virtual Memory · Mapping · Replacement Policies

■ Core Concepts — Unit 2

Memory Hierarchy: Registers → L1 Cache → L2 Cache → L3 Cache → Main Memory (RAM) → Disk.
Goal: Give the illusion of large, fast, cheap memory.
Locality Principle: (1) Temporal — recently used data likely used again soon. (2) Spatial — if address X
accessed, nearby addresses likely accessed next.
Inclusion: Data in L1 is also in L2 and RAM. Coherence: All copies of data must be consistent.

Concept Explanation

Direct Mapped Each memory block maps to exactly ONE cache line. Fast but high conflict misses.

Fully Associative Block can go to ANY cache line. Lowest conflict misses but complex/expensive.

Set Associative N-way: Each block maps to one SET, can go to any of N lines in that set. Best balance.

AMAT Formula AMAT = Hit Time + Miss Rate × Miss Penalty

3 C's of Misses Compulsory (first access), Capacity (cache too small), Conflict (mapping collision).

Write Through Write to cache AND memory simultaneously. Simple, no dirty bit needed.

Write Back Write only to cache; write to memory when block is evicted. Faster but needs dirty bit.

Virtual Memory Concepts

Virtual Memory: Allows programs to use more memory than physically available by using disk as extension of
RAM.
Page: Fixed-size block of virtual address space. Frame: Corresponding physical memory block.
Page Table: Maps virtual page number (VPN) → physical frame number (PFN).
TLB (Translation Lookaside Buffer): Fast cache for page table entries. Avoids full page table lookup on every
access.

Concept Explanation

Page Fault Required page not in RAM → OS loads it from disk. Very expensive (~millions of cycles).

TLB Hit Virtual→physical translation found in TLB. Fast (1-2 cycles).

TLB Miss Not in TLB → page table walk. Hardware or OS handles it.

Segmentation Divide memory into variable-size segments (code, data, stack). Each has base+limit.

LRU Least Recently Used — replace page not accessed for longest time. Best practical policy.

FIFO First In First Out — replace oldest loaded page. Simple, suffers Belady's anomaly.

★★ = Very Important This Year Page 7

ADVANCED COMPUTER ARCHITECTURE — MAKAUT EXAM NOTES Units 1–4 | 5-Mark & 15-Mark Q&A

Optimal Replace page not needed for longest future time. Theoretical best; impossible in practice.

Clock Algorithm Approximate LRU using reference bit. Efficient and practical.

■ 5-MARK QUESTIONS — UNIT 2

5 Marks ★★ VERY IMPORTANT

Q. Explain cache memory organization. Compare Direct Mapped, Fully Associative, and Set
Associative.

Cache Memory is a small, fast memory between CPU and main memory that stores frequently used
data/instructions.

Type Properties

Direct Mapped 1-way. Block i → cache line (i mod cache_size). Fast, simple. High conflict misses.

Fully Associative Any block → any line. Most flexible. Lowest misses but needs complex comparator
hardware.

2-way Set Assoc. 2 lines per set. Balance of speed and miss rate. Industry standard (L1, L2 caches).

N-way Set Assoc. N lines per set. As N increases → approaches fully associative. L3 often 8 or 16-way.

AMAT: AMAT = Hit Time + Miss Rate × Miss Penalty

Address Breakdown: Tag bits | Index bits | Block Offset bits
■ Exam Tip: Table comparison + AMAT formula + address breakdown = full 5 marks.

5 Marks ★★ VERY IMPORTANT

Q. Explain techniques for reducing cache misses.

3 C's of Cache Misses:

• Compulsory: First-ever access to a block. Unavoidable. Reduced by prefetching.
• Capacity: Cache too small to hold working set. Reduced by larger cache.
• Conflict: Too many blocks mapping to same set. Reduced by higher associativity.

Techniques to Reduce Misses:

• Larger Block Size: Exploits spatial locality. But too large → increases miss penalty and conflict misses.
• Higher Associativity: 2-way→4-way→8-way reduces conflict misses. But increases hit time.
• Larger Cache: Reduces capacity misses. But increases access time and cost.
• Hardware Prefetching: Fetch next block before it's requested (stride prediction).
• Software Prefetching: Compiler inserts PREFETCH instructions ahead of actual use.
• Victim Cache: Small fully-associative cache between L1 and L2 to hold recently evicted blocks.
• Write Buffer: Reduces stalls on write-through misses.
■ Exam Tip: 3 C's + 5 techniques = full marks.

5 Marks ★★ VERY IMPORTANT

★★ = Very Important This Year Page 8

ADVANCED COMPUTER ARCHITECTURE — MAKAUT EXAM NOTES Units 1–4 | 5-Mark & 15-Mark Q&A

Q. Explain Virtual Memory with page table and TLB.

Virtual Memory allows processes to use more address space than physical RAM. The OS manages mapping
virtual addresses to physical addresses.

Address Translation:
• CPU generates Virtual Address = VPN (Virtual Page Number) + Page Offset.
• TLB checked first: if hit → physical address immediately.
• TLB miss → page table walk to get PFN.
• If page not in RAM → Page Fault → OS loads from disk (swap space).

TLB (Translation Lookaside Buffer):

• Small, fully-associative hardware cache (~64–1024 entries).
• Stores recent VPN→PFN translations.
• TLB hit time: 1–2 cycles. Miss: 10–100s of cycles.

Mapping Techniques:
• Single-level Page Table: Simple but large for 64-bit address spaces.
• Multi-level Page Table: Hierarchical — only allocate tables for used virtual address space.
• Inverted Page Table: One entry per physical frame — efficient for large address spaces.
■ Exam Tip: Virtual address breakdown + TLB operation + mapping types = full marks.

5 Marks ★★ VERY IMPORTANT

Q. Compare page replacement policies: FIFO, LRU, Optimal.

Policy Comparison

Optimal (OPT) Replace page not needed for longest time in future. Theoretical — needs future knowledge. Best
possible miss rate.

FIFO Replace page that was loaded first. Easy to implement. Suffers Belady's Anomaly (more frames →
more faults!).

LRU Replace page not accessed for longest time. Best practical policy. Approximates OPT. Complex
hardware.

Clock (NRU) Approximate LRU. Reference bit set on access; clock hand sweeps, clears bits, replaces first 0-bit
page.

LFU Least Frequently Used. Replace page with lowest access count. Suffers with old popular pages.

Example: Reference string: 1 2 3 4 1 2 5 1 2 3 4 5, 3 frames:

• FIFO: 9 page faults | LRU: 8 page faults | OPT: 6 page faults.
■ Exam Tip: Table + example reference string = 5/5. Belady's anomaly always asked.

■ 15-MARK QUESTION — UNIT 2

15 Marks ★★ VERY IMPORTANT

★★ = Very Important This Year Page 9

ADVANCED COMPUTER ARCHITECTURE — MAKAUT EXAM NOTES Units 1–4 | 5-Mark & 15-Mark Q&A

Q. Explain hierarchical memory technology covering cache organization, virtual memory, and
memory replacement policies.

SECTION A — MEMORY HIERARCHY

• Goal: Combine speed of fast memory with capacity of large memory at low cost.
• Hierarchy (fastest to slowest): Registers → L1 Cache → L2 Cache → L3 Cache → RAM → SSD → HDD.
• Locality: Temporal (reuse same data) + Spatial (access nearby addresses).
• Inclusion Property: Content of L1 ⊆ L2 ⊆ RAM.
• Coherence: All cached copies of same data must remain consistent.

SECTION B — CACHE MEMORY

Organization Details

Direct Mapped Block maps to one line. Address = Tag + Index + Offset. Fastest, most conflict misses.

Set Associative N-way: maps to one set, any of N lines. 2-way and 4-way most common.

Fully Associative Maps anywhere. Needs content addressable memory (CAM). Lowest misses.

Write Through Write cache + memory together. Simple; write buffer used to reduce stall.

Write Back Write only to cache; use dirty bit; write to memory on eviction. Faster.

AMAT = Hit TimeL1 + Miss RateL1 × (Hit TimeL2 + Miss RateL2 × Miss PenaltyRAM)

Techniques to Reduce Misses:

• Increase block size → exploits spatial locality.
• Increase associativity → reduces conflict misses.
• Prefetching → hardware or compiler fetches data before needed.
• Victim cache → small buffer holds recently evicted blocks.

SECTION C — VIRTUAL MEMORY

• OS manages memory in pages (typically 4KB).
• Page Table maps VPN → PFN. Stored in main memory.
• TLB caches recent translations for speed.
• Page Fault: OS loads missing page from disk; LRU policy decides which page to evict.
• Protection: Each page table entry has valid bit, read/write/execute bits, dirty bit, reference bit.

Address Mapping:
• Virtual Address = [VPN | Page Offset].
• Physical Address = [PFN | Page Offset] (offset unchanged).
• Multi-level page tables used for large 64-bit address spaces.

SECTION D — REPLACEMENT POLICIES

Policy Details

OPT Replace page not needed furthest in future. Impossible in practice. Used as benchmark.

★★ = Very Important This Year Page 10

ADVANCED COMPUTER ARCHITECTURE — MAKAUT EXAM NOTES Units 1–4 | 5-Mark & 15-Mark Q&A

FIFO Simple queue. Oldest page replaced. Suffers Belady's Anomaly.

LRU Best practical. Hardware: timestamp or stack implementation.

Clock NRU approximation. Reference bit; circular pointer. Efficient.

LFU Least frequently used. Can be stale with historical popular pages.

■ Exam Tip: 5 sections; use tables for cache types and replacement. Mention AMAT formula and Belady's
anomaly.

★★ = Very Important This Year Page 11

ADVANCED COMPUTER ARCHITECTURE — MAKAUT EXAM NOTES Units 1–4 | 5-Mark & 15-Mark Q&A

UNIT 3 Instruction-Level Parallelism (ILP)

ILP Concepts · Superscalar · Superpipelined · VLIW · Array & Vector Processors

■ Core Concepts — Unit 3

ILP = Instruction-Level Parallelism: Executing multiple instructions simultaneously within a single processor.
ILP Limit: Data dependencies, control hazards, resource conflicts limit actual ILP.
Two approaches: (1) Dynamic — hardware finds and exploits ILP at runtime. (2) Static — compiler finds ILP at
compile time (VLIW).

Concept Explanation

Superscalar Multiple pipelines. Issues 2-8 instructions/cycle. Hardware detects ILP dynamically.

Superpipelined Very deep pipeline (20-30 stages). Higher clock frequency. One issue/cycle but very fast
clock.

VLIW Very Long Instruction Word. Compiler packs multiple operations into one wide instruction
word.

In-order Issue Instructions issued in original program order. Simple, but stalls if hazard occurs.

Out-of-order Instructions issued as soon as operands ready. Requires Tomasulo algorithm.

Tomasulo Dynamic scheduling algorithm. Reservation stations, register renaming, CDB broadcast.

Vector Processor Applies single operation to entire vector (array) of data. SIMD principle.

Array Processor Multiple PEs (Processing Elements) operating in parallel on different data elements.

■ 5-MARK QUESTIONS — UNIT 3

5 Marks ★★ VERY IMPORTANT

Q. Differentiate Superscalar, Superpipelined and VLIW architectures.

Superpipelined VLIW

1 instr/cycle Many ops/c

Very high (deep pipeline) Moderate

Hardware Compiler (s

Moderate hardware Simple hard

Hardware, many stall cycles Compiler m

★★ = Very Important This Year Page 12

ADVANCED COMPUTER ARCHITECTURE — MAKAUT EXAM NOTES Units 1–4 | 5-Mark & 15-Mark Q&A

Intel Pentium 4 (NetBurst) Intel Itanium

■ Exam Tip: Table with 6 features × 3 architectures = guaranteed full marks.

5 Marks ★★ VERY IMPORTANT

Q. What is VLIW architecture? Explain its advantages and disadvantages.

VLIW (Very Long Instruction Word): Architecture where the compiler packs multiple independent operations into
a single long instruction word, exploiting ILP statically.

Working: A 256-bit VLIW word might contain: [ALU op | ALU op | FP op | Load | Store | Branch]. All execute in
parallel in one cycle.

Advantages:
• Simple hardware — no dynamic scheduling needed.
• No complex hazard detection hardware.
• Lower power consumption than superscalar.
• Compiler can perform global optimisation.

Disadvantages:
• Complex compiler — must detect all parallelism at compile time.
• Code density problem — many NOP (no-operation) fields when parallelism is low.
• Binary incompatibility — different VLIW machines need different compiled code.
• Poor performance when dependencies limit ILP.
■ Exam Tip: Definition + working + 4 advantages + 4 disadvantages = 5/5.

5 Marks ★★ VERY IMPORTANT

Q. Explain Vector Processors and Array Processors.

Vector Processor: A processor that operates on entire arrays (vectors) of data with a single instruction.
• Example: ADD V1, V2, V3 — adds all elements of vector V2 and V3, stores in V1.
• Uses long vector registers (e.g., 64 elements of 64-bit floats).
• Efficient for scientific computing, signal processing, graphics.
• Avoids loop overhead — one instruction replaces an entire loop.
• Modern SIMD extensions (SSE, AVX in Intel) are descendents.

Array Processor (SIMD):

• Multiple Processing Elements (PEs), all executing the SAME instruction on DIFFERENT data simultaneously.
• Controlled by a single control unit — True SIMD (Single Instruction Multiple Data).
• Example: GPU shaders — thousands of cores doing same operation on different pixels.

Type Key Feature

Vector Processor Single processor, vector registers, pipelined functional units. Sequential vector ops.

Array Processor Multiple PEs, one control unit, truly parallel. Each PE has own data.

■ Exam Tip: Define both + key difference table + example = 5/5.

★★ = Very Important This Year Page 13

ADVANCED COMPUTER ARCHITECTURE — MAKAUT EXAM NOTES Units 1–4 | 5-Mark & 15-Mark Q&A

■ 15-MARK QUESTION — UNIT 3

15 Marks ★★ VERY IMPORTANT

Q. Explain Instruction-Level Parallelism: techniques, Tomasulo's algorithm, and various ILP

architectures.

SECTION A — ILP BASICS

• ILP: Number of instructions that can execute simultaneously without affecting program result.
• Theoretical ILP of real programs: very high. Practical ILP: limited by dependencies.
• Data dependence limits ILP; control dependence (branches) also reduces ILP.

SECTION B — TECHNIQUES FOR INCREASING ILP

Technique Description

Loop Unrolling Replicate loop body; schedule across copies; fills pipeline; reduces branch overhead.

Register Renaming Eliminate WAR/WAW; map logical→physical registers. Hardware does this (Tomasulo).

Dynamic Scheduling Hardware reorders instructions at runtime (out-of-order execution).

Branch Prediction Predict branch early; speculatively execute down predicted path.

Speculation Execute instructions before knowing if needed; rollback if wrong.

Software Pipelining Compiler overlaps iterations of a loop (like pipelining across loop iterations).

SECTION C — TOMASULO'S ALGORITHM

• Dynamic scheduling algorithm originally for IBM 360/91. Foundation of modern out-of-order processors.
• Key Components:
• • Reservation Stations (RS): Hold instruction + operands while waiting. Each FU has RS.
• • Common Data Bus (CDB): Broadcasts result to all RSs and register file simultaneously.
• • Register Renaming: RS tags replace register names — eliminates WAR/WAW hazards.
Steps: (1) Issue: Decode instr, get RS; (2) Execute: when operands ready, execute; (3) Write Result: broadcast on
CDB.

SECTION D — ILP ARCHITECTURES

Architecture Description

Superscalar Multiple parallel pipelines; hardware issues 2-8 instr/cycle; in-order or OOO; most modern
CPUs.

Superpipelined Very deep stages (20-30); high clock; one issue/cycle; Inter Pentium 4 style.

VLIW Compiler packs parallel ops in wide instruction; simple hardware; IA-64/DSPs.

EPIC Explicitly Parallel Instruction Computing; like VLIW but with stop bits; Intel Itanium.

SECTION E — VECTOR & ARRAY PROCESSORS

★★ = Very Important This Year Page 14

ADVANCED COMPUTER ARCHITECTURE — MAKAUT EXAM NOTES Units 1–4 | 5-Mark & 15-Mark Q&A

• Vector: Pipelined FUs; chaining (result of one vector op fed to next); stride access patterns.
• Array (SIMD): N PEs in lockstep; one controller; massive data parallelism; GPU basis.
• Modern relevance: Intel AVX-512, ARM SVE, NVIDIA CUDA — all SIMD/vector principles.
■ Exam Tip: 5 sections; Tomasulo is very likely 15-mark topic. Draw reservation station diagram if possible.

★★ = Very Important This Year Page 15

ADVANCED COMPUTER ARCHITECTURE — MAKAUT EXAM NOTES Units 1–4 | 5-Mark & 15-Mark Q&A

UNIT 4 Multiprocessor & Non-Von Neumann Architectures

Flynn's Taxonomy · Shared Memory · Interconnects · Clusters · Dataflow · Systolic

■ Core Concepts — Unit 4

Flynn's Taxonomy classifies parallel architectures by instruction and data streams:

SISD (single CPU), SIMD (vector/GPU), MISD (rare), MIMD (multiprocessors — most common).
Two types of MIMD: Shared Memory (UMA, NUMA) and Distributed Memory (clusters, message passing).

Concept Explanation

UMA (SMP) Uniform Memory Access. All CPUs share same memory bus. Equal access time. Example:
multi-core desktop.

NUMA Non-Uniform Memory Access. Each CPU has local memory; remote access slower.

Cache Coherence Ensures all cached copies of shared data stay consistent. Protocols: Snooping (MSI, MESI),
Directory.

MESI Protocol States: Modified, Exclusive, Shared, Invalid. Used in Intel SMP systems.

Memory Consistency Specifies order in which memory ops appear to execute. Sequential consistency = all see
same order.

Interconnection How CPUs/memories connect: Bus, Crossbar, Mesh, Hypercube, Omega network.

Cluster Loosely coupled independent computers connected by high-speed LAN. MPI used.

Dataflow Computer Instruction executes when ALL its operands available (data-driven). No program counter.

Systolic Array Network of simple PEs. Data flows rhythmically through PEs. Used for matrix ops, signal
processing.

Reduction Machine Evaluate expressions by repeatedly applying reduction rules. Functional programming model.

Flynn's Taxonomy — Quick Table

Class Description

SISD Single Instruction, Single Data. Traditional sequential CPU. Von Neumann. Example: Single-core CPU.

SIMD Single Instruction, Multiple Data. Same operation on many data. Example: GPU, Vector processor,
SSE/AVX.

MISD Multiple Instruction, Single Data. Rare/theoretical. Pipeline sometimes cited.

MIMD Multiple Instruction, Multiple Data. Each CPU runs different instructions on different data. Example:
Multi-core, Cluster.

■ 5-MARK QUESTIONS — UNIT 4

★★ = Very Important This Year Page 16

ADVANCED COMPUTER ARCHITECTURE — MAKAUT EXAM NOTES Units 1–4 | 5-Mark & 15-Mark Q&A

5 Marks ★★ VERY IMPORTANT

Q. Explain Flynn's Taxonomy of parallel architectures.

Flynn's Taxonomy (1966) classifies computer architectures based on the number of concurrent instruction
streams and data streams.

Class Description

SISD 1 instruction, 1 data. Classic sequential. Example: Single-core processor.

SIMD 1 instruction, N data. Ideal for data-parallel problems. Example: GPU, MMX, SSE.

MISD N instructions, 1 data. Theoretical. Example: Fault-tolerant pipelines (rare).

MIMD N instructions, N data. Most powerful and common. Example: Multi-core CPU, server clusters.

MIMD sub-types:
• Shared Memory MIMD: All processors access common memory (SMP, NUMA).
• Distributed Memory MIMD: Each has private memory; communicate via messages (cluster, MPP).
■ Exam Tip: Table + MIMD sub-types + examples = guaranteed 5/5.

5 Marks ★★ VERY IMPORTANT

Q. What is Cache Coherence? Explain MESI Protocol.

Cache Coherence Problem: In multiprocessors, multiple caches hold copies of same memory location. If one
CPU modifies it, others see stale data — incoherence!

MESI Protocol (most widely used snooping protocol):

State Meaning

M — Modified Cache has only valid copy; memory is stale. Cache must write back before eviction.

E — Exclusive Cache has only copy; memory is up-to-date. Can modify without notifying others.

S — Shared Multiple caches have copies; all match memory. Read-only.

I — Invalid Cache line is invalid/stale. Must fetch from memory or another cache before use.

Snooping: Each cache controller monitors (snoops) the shared bus. On a write, other caches seeing same
address invalidate their copies (Write-Invalidate Protocol).
■ Exam Tip: MESI table + snooping explanation = full marks. Draw state diagram if time permits.

5 Marks

Q. Explain interconnection networks in multiprocessors.

Interconnection Network: The communication fabric connecting processors and memories in a parallel system.

Network Properties

Bus Single shared wire. Simple, cheap. Bandwidth bottleneck. Works for 2-32 processors.

★★ = Very Important This Year Page 17

ADVANCED COMPUTER ARCHITECTURE — MAKAUT EXAM NOTES Units 1–4 | 5-Mark & 15-Mark Q&A

Crossbar Full N×N switch — every processor can connect to every memory simultaneously. Expensive:
O(N²) cost.

Mesh / Torus Processors at grid nodes; connect to neighbours. 2D mesh common in many-core chips. Scalable.

Hypercube N-dimensional cube. Each node connects to N neighbours. Diameter = log■(N). Excellent
bandwidth.

Omega Network Multi-stage interconnect. Log■N stages with N/2 switches per stage. Cost: O(N log N).

Fat Tree Tree with increasing bandwidth near root. Common in HPC clusters (InfiniBand).

■ Exam Tip: Table of 5-6 types + properties = 5/5.

5 Marks ★★ VERY IMPORTANT

Q. What are Dataflow Computers? Compare with Von Neumann architecture.

Von Neumann Model: Instructions executed sequentially driven by a Program Counter (PC). Instruction flow is
controlled by the programmer.

Dataflow Model: An instruction executes as soon as ALL its input operands are available — no PC needed.
Execution is data-driven.

Feature Von Neumann vs Dataflow

Control Von Neumann: PC-driven sequential. Dataflow: Data-token driven, asynchronous.

Parallelism Von Neumann: Sequential (unless parallel hardware added). Dataflow: Inherent, automatic.

Memory Von Neumann: Shared mutable state. Dataflow: No shared state — values passed as tokens.

Side Effects Von Neumann: Common. Dataflow: None — purely functional.

Scheduling Von Neumann: Static by compiler/programmer. Dataflow: Dynamic at runtime.

Example Von Neumann: All conventional CPUs. Dataflow: MIT Tagged Token, Manchester Dataflow.

■ Exam Tip: Comparison table is the key — 6 features clearly compared = full marks.

5 Marks ★★ VERY IMPORTANT

Q. Explain Systolic Architecture with an example.

Systolic Array: A network of tightly coupled simple Processing Elements (PEs) arranged in a regular pattern. Data
flows rhythmically (like heartbeats) from PE to PE, performing computation at each step.

Key Characteristics:
• Data flows in a pipeline-like manner through PEs.
• Each PE receives data, computes, and passes result to next PE.
• High throughput with simple, regular structure.
• Ideal for repetitive computations: matrix multiply, convolution, signal processing.

Example — 1D Systolic Array for Matrix-Vector Multiply (A×b):

• Each PE receives a row element a■■ and vector element b■.

★★ = Very Important This Year Page 18

ADVANCED COMPUTER ARCHITECTURE — MAKAUT EXAM NOTES Units 1–4 | 5-Mark & 15-Mark Q&A

• PE computes partial sum: sum += a■■ × b■, passes sum rightward.

• After all PEs process, output appears at end of array.

Applications: Signal processing chips, Google TPU (Tensor Processing Unit) uses systolic arrays for neural
network matrix multiplication.
■ Exam Tip: Definition + characteristics + example + application (TPU!) = 5/5.

■ 15-MARK QUESTIONS — UNIT 4

15 Marks ★★ VERY IMPORTANT

Q. Explain Multiprocessor Architecture: taxonomy, shared memory, cache coherence, memory

consistency, and interconnection networks.

SECTION A — TAXONOMY (Flynn's Classification)

Class Details

SISD Single CPU, sequential. All traditional computers.

SIMD One instr, multiple data. GPU, vector. Ideal for graphics, ML.

MISD Multiple instr, one data. Theoretical.

MIMD Multiple instr, multiple data. Multiprocessors. Most flexible.

SECTION B — CENTRALISED SHARED MEMORY (SMP / UMA)

• All processors share a single physical address space and a single memory bus.
• UMA: Equal memory access time for all processors.
• NUMA: Processors have local memory; remote access via interconnect is slower.
• SMP (Symmetric Multiprocessing): All CPUs equal; share OS and memory.
• Scalability limit: Bus becomes bottleneck beyond ~32 processors.

SECTION C — CACHE COHERENCE

Problem: Multiple caches hold copies of same variable. One CPU writes → others have stale data.
Snoopy (Bus-based) Protocol:
• Each cache controller monitors bus transactions.
• Write-Invalidate: On write, sender broadcasts — other caches invalidate their copy (MESI).
• Write-Update: On write, all caches update their copy. Wastes bandwidth.
MESI States: Modified | Exclusive | Shared | Invalid.
Directory Protocol: For large systems (no bus). A directory tracks which caches hold each block.

SECTION D — MEMORY CONSISTENCY

• Sequential Consistency (SC): All processors see all memory operations in same global order. Simple model;
hard to implement efficiently.
• Relaxed Consistency: Allows reordering of memory ops for performance. Programmer uses FENCE/BARRIER
instructions to enforce order when needed.
• Total Store Order (TSO): Writes may be reordered relative to reads. Used in Intel x86.

★★ = Very Important This Year Page 19

ADVANCED COMPUTER ARCHITECTURE — MAKAUT EXAM NOTES Units 1–4 | 5-Mark & 15-Mark Q&A

SECTION E — INTERCONNECTION NETWORKS

Network Properties

Bus Simple. Single broadcast medium. 2-32 CPUs. Bandwidth = bottleneck.

Crossbar N×N full connectivity. O(N²) switches. Best bandwidth, expensive.

Mesh 2D/3D grid. Diameter = O(√N). Scalable. Used in many-core chips.

Hypercube N-dim cube. Diameter = log■N. Excellent for N up to thousands.

Fat Tree Root has high bandwidth. Common in HPC (InfiniBand).

SECTION F — DISTRIBUTED SHARED MEMORY & CLUSTERS

• Clusters: Commodity nodes connected by high-speed network (InfiniBand, 10GbE). MPI used for messaging.
• DSM: Software layer makes distributed memory appear as shared. NUMA-like.
• Cluster advantages: Scalability, fault tolerance, cost-effectiveness.
■ Exam Tip: 6 sections × 2.5 marks each = 15. Always draw interconnect topology diagrams.

15 Marks ★★ VERY IMPORTANT

Q. Explain Non-Von Neumann architectures: Dataflow, Reduction, and Systolic with their
advantages.

INTRODUCTION — LIMITATIONS OF VON NEUMANN MODEL

• Von Neumann Bottleneck: CPU and memory connected by a single bus — data/instructions compete.
• Sequential execution limits parallelism.
• Non-Von Neumann models overcome these by rethinking computation model.

SECTION A — DATAFLOW COMPUTERS

Execution model: An instruction fires (executes) when ALL its input tokens (operands) are available. No PC.
• Dataflow Graph: Nodes = operations; Edges = data dependencies (tokens flow along edges).
• Static Dataflow: One token per edge at a time. Simpler but limited parallelism.
• Dynamic Dataflow: Tagged tokens allow multiple iterations simultaneously. Greater parallelism.
• Advantages: Implicit parallelism; no control flow dependencies; naturally exploits ILP.
• Disadvantages: Token management overhead; memory model; debugging difficulty.
• Examples: MIT Tagged Token Dataflow, Manchester Dataflow Machine.

SECTION B — REDUCTION COMPUTERS

Computation by reduction: Evaluate an expression by substituting values and reducing (simplifying) repeatedly.
• Graph Reduction: Expression represented as graph; reduction replaces sub-graphs with values.
• String Reduction: Textual substitution of expressions.
• Lazy Evaluation: Sub-expressions evaluated only when needed (demand-driven, unlike dataflow which is
supply-driven).
• Advantages: Pure functional — no side effects; safe parallelism; automatic memory management (GC).
• Disadvantages: Higher overhead than imperative; memory management cost.
• Application: Functional language runtimes (Haskell, ML). FPGA implementations.

★★ = Very Important This Year Page 20

ADVANCED COMPUTER ARCHITECTURE — MAKAUT EXAM NOTES Units 1–4 | 5-Mark & 15-Mark Q&A

SECTION C — SYSTOLIC ARCHITECTURES

Systolic arrays consist of a regular mesh of simple PEs connected to neighbours. Data 'pulses' through like blood
in veins (heart systole = contraction).
• Characteristics: Regular, modular structure; pipeline-like data flow; high throughput; simple PEs.
• Types of Data Flow in Systolic Arrays:
• • 1D linear arrays — for FIR filters, convolution.
• • 2D arrays — for matrix multiplication, image processing.
• Matrix Multiply Example: C = A × B. A flows left-to-right; B flows top-to-bottom; each PE accumulates partial
sum; result in C emerges at bottom.
• Advantages: Extremely high throughput; simple hardware; regular VLSI design; low external memory
bandwidth.
• Modern Usage: Google's TPU (Tensor Processing Unit) uses a 256×256 systolic array for DNN matrix
multiplication — processes 92 TOPS (Tera Operations Per Second).
• Applications: Signal processing, Neural networks, Cryptography, Image processing.

Architecture Key Feature

Dataflow Data-token driven. Maximum implicit parallelism. No PC. Functional style.

Reduction Demand-driven. Lazy evaluation. Pure functional. No side effects.

Systolic Rhythmic data flow. Regular PE mesh. High throughput. Matrix ops.

Von Neumann PC-driven. Sequential. Shared memory bottleneck. Imperative.

■ Exam Tip: 3 architectures × 4 marks + comparison table 3 marks = 15. Google TPU mention = bonus
impression.

★★ = Very Important This Year Page 21

ADVANCED COMPUTER ARCHITECTURE — MAKAUT EXAM NOTES Units 1–4 | 5-Mark & 15-Mark Q&A

UNIT
★
Master Cheat Sheet — Last Revision

Most Important Facts | Formulas | Definitions to Memorise Before Exam

■ Key Formulas
Formula Expression

CPU Time CPU Time = IC × CPI × Clock Cycle Time

Speedup (Pipelined) Speedup = Time_non-pipe / Time_pipe ≈ Number of stages (ideal)

Amdahl's Law Speedup = 1 / [(1-f) + f/S] where f = fraction improved, S = speedup of that part

AMAT AMAT = Hit Time + Miss Rate × Miss Penalty

AMAT Multi-level AMAT = HT_L1 + MR_L1 × (HT_L2 + MR_L2 × Miss Penalty_RAM)

Effective Access Time EAT = TLB hit rate × (TLB time + Mem time) + (1-hit rate) × (TLB + 2×Mem)

Throughput (Pipeline) Throughput = n / (k + n - 1) × clock where k=stages, n=instructions

■ Most Important Topics — Starred for Exam

Topic (★★ = Very Important) Why Important

★★ Pipeline hazards (all 3 types) Data + Control + Structural. Solutions for each. Most repeated topic.

★★ Cache organization (3 types) Direct, Set-Associative, Fully Associative. AMAT formula. Always asked.

★★ Page replacement (LRU, FIFO, Table + Belady's anomaly. Numerical very likely.
OPT)

★★ Flynn's Taxonomy SISD/SIMD/MISD/MIMD table. Simple but always 5 marks.

★★ MESI Cache Coherence 4 states, snooping protocol. 5-mark or part of 15-mark.

★★ Superscalar vs VLIW Table comparison. 5-mark favourite.

★★ Dataflow vs Von Neumann Comparison table. 5-mark or 15-mark.

★★ Systolic Architecture Definition + matrix multiply example + Google TPU.

★ Tomasulo Algorithm For 15-mark ILP question — components and steps.

★ Amdahl's Law Formula + numerical. Quantitative design question.

★ Virtual Memory + TLB Address translation steps. Likely in memory 15-mark.

★ Interconnection Networks Bus/Crossbar/Mesh/Hypercube comparison table.

★★ = Very Important This Year Page 22

ADVANCED COMPUTER ARCHITECTURE — MAKAUT EXAM NOTES Units 1–4 | 5-Mark & 15-Mark Q&A

■ Revise starred topics first. Write tables wherever possible. Mention examples and
formulas. Best of luck for MAKAUT! ■

★★ = Very Important This Year Page 23