Previous Year Questions

(i) CPI of super scalar pipeline is:
Answer: (a) less than 1
Explanation: Superscalar pipelines can issue and complete multiple instructions per clock cycle. Therefore, Instructions Per Cycle (IPC) > 1, which implies Cycles Per Instruction (CPI) = 1/IPC is less than 1.

(ii) Pipelining uses:
Answer: (b) temporal parallelism
Explanation: Pipelining achieves parallelism by overlapping the execution of sequential instructions in time (temporal parallelism), as opposed to multiple physical ALUs executing simultaneously (spatial parallelism).

(iii) Utilization pattern of successive stages of a synchronous pipeline are specified by:
Answer: (c) Reservation table
Explanation: A reservation table is a 2D diagram (Space vs. Time) that explicitly shows which hardware stages are utilized in which clock cycle by a task.

(iv) Dynamic pipeline allows:
Answer: (a) multiple functions to evaluate
Explanation: Unlike static pipelines that are hardwired for a single operation (e.g., just floating point addition), dynamic pipelines can be reconfigured dynamically to perform multiple different functions.

(v) the equations for Amdahl's law is:
Answer: (a) S(n) = 1/f where n → ∞
Explanation: If $f$ is the strictly sequential portion of a program, Speedup $S = rac{1}{f + (1-f)/n}$. As the number of processors $n$ approaches infinity, the term $(1-f)/n$ becomes zero, and the maximum theoretical speedup is bounded by $1/f$.

(vi) Array Processors are put under which one of the following categories?
Answer: (b) SIMD
Explanation: Array processors (like the ILLIAC IV) execute a Single Instruction stream on Multiple Data elements simultaneously across multiple processing elements.

(vii) The number of cycles required to complete n tasks in a k stage pipeline is:
Answer: (a) k + n - 1
Explanation: The first task requires $k$ cycles to pass through all stages. The remaining $(n-1)$ tasks follow immediately, completing one per cycle, giving a total of $k + n - 1$ cycles.

(viii) an n-dimensional hypercube has:
Answer: (c) $2^n$ nodes
Explanation: A hypercube of dimension $n$ connects $2^n$ nodes, where each node is connected to exactly $n$ neighbours (its degree).

(ix) Which of the following is a recursive network?
Answer: (a) Benes network
Explanation: A Benes network is a strictly non-blocking multistage interconnection network that is defined recursively (a $2N imes 2N$ Benes network is built using two $N imes N$ Benes networks).

(x) The compiler optimization technique is used to reduce:
Answer: (b) cache miss rate
Explanation: Compilers use techniques like loop interchange, loop blocking (tiling), array padding, and prefetching specifically to improve spatial and temporal locality, thereby minimizing the cache miss rate.

Partially True, but practically bounded.

Ideal Case (True): Theoretically, if a task taking time $T$ is divided into $k$ perfectly balanced pipeline stages, the cycle time becomes $T/k$. The throughput (instructions completed per second) becomes $k/T$, which increases in direct proportion to the number of stages $k$.

Practical Case (False): In reality, throughput does NOT increase infinitely with $k$ due to several factors:

• Pipeline Latch Overhead: Each stage requires a pipeline register (latch) at its output. If the latch delay is $t_l$, the cycle time is $(T/k) + t_l$. As $k$ increases, $T/k$ shrinks, but $t_l$ remains constant, eventually dominating the cycle time.
• Hazards: Deeper pipelines suffer much higher penalties for Control Hazards (branch mispredictions) and Data Hazards (longer stalls for RAW dependencies).
• Stage Imbalance: It is physically impossible to divide an instruction into infinitely many, perfectly equal time segments.

Because of these overheads, performance peaks at an optimal number of stages (typically 10-15) and degrades if made deeper (as seen with Intel's 31-stage Pentium 4).

(a) Amdahl's Law:

Amdahl's law provides the theoretical maximum speedup in latency of the execution of a task at fixed workload that can be expected of a system whose resources are improved.

Where:
$P$ = fraction of the program that is parallelizable.
$(1 - P)$ = strictly sequential fraction of the program.
$N$ = number of processors.

(b) Speedup Calculation:

• Sequential portion $(1 - P) = 10\% = 0.1$
• Parallelizable portion $P = 90\% = 0.9$
• Desired Speedup $S = 5$

Applying Amdahl's Law:
$5 = rac{1}{0.1 + rac{0.9}{N}}$
$0.1 + rac{0.9}{N} = rac{1}{5} = 0.2$
$rac{0.9}{N} = 0.2 - 0.1 = 0.1$
$N = rac{0.9}{0.1} = \mathbf{9 ext{ processors}}$

A Branch Hazard (or Control Hazard) occurs when the pipeline fetches subsequent instructions before a branch instruction has been fully evaluated and the correct target address is determined. If the branch is taken, the speculatively fetched instructions are wrong and must be flushed, wasting clock cycles (branch penalty).

Methods to Handle Branch Hazards:

• Dynamic Branch Prediction: Hardware uses a Branch History Table (BHT) or Branch Target Buffer (BTB) to track the past behavior of branches. When a branch is fetched, the hardware predicts whether it will be taken or not based on history. If predicted correctly, there is no penalty. Mispredictions require a flush.
• Delayed Branching: A compiler-driven technique where the instruction immediately following the branch (the branch delay slot) is filled with a useful, independent instruction from before the branch. The hardware executes this delay slot instruction regardless of whether the branch is taken or not, hiding 1 cycle of the branch penalty.

Note: This is an exact repeat of Q5 from the 2016 paper.

Cache Coherence Problem: In multiprocessor systems, each CPU has its own private cache. If CPU 1 modifies a shared variable `X` in its local cache, CPU 2's cached copy of `X` becomes stale (outdated data). If CPU 2 reads `X`, it gets the wrong value. Maintaining consistency across all caches is the coherence problem.

Solution (Write-Invalidate Snoopy Protocol):
Every cache controller monitors (snoops) the shared bus. When CPU 1 wants to write to `X`, it first broadcasts an "invalidate" signal on the bus. All other caches containing `X` mark their copies as invalid. CPU 1 then writes locally. Later, if CPU 2 needs `X`, it will experience a cache miss and fetch the fresh data from CPU 1 or main memory.

Limitations:
The primary limitation is scalability. Since all invalidation messages must be broadcast over a single shared bus, the bus quickly becomes a bottleneck as the number of processors increases (typically failing to scale beyond 16-32 processors).

Drawback of Direct Mapped Cache:

In a direct mapped cache, each block from main memory maps to exactly one specific cache line (determined by `Block Address mod Number of Cache Lines`).

Drawback: Conflict Misses (Thrashing). If a program actively accesses two different memory blocks that happen to map to the exact same cache line, they will constantly evict each other. Even if 99% of the cache is empty, these two blocks will cause a 100% miss rate for those accesses. This severe performance penalty is called thrashing.

Resolution in Set Associative Cache:

A set associative cache groups multiple cache lines into a single "set" (e.g., an $N$-way set associative cache has $N$ lines per set). A memory block maps to a specific set, but can be placed in any of the $N$ available ways (slots) within that set.

If two active blocks map to the same set, they can simply occupy different "ways" in that set simultaneously, completely eliminating the conflict miss that would have occurred in a direct-mapped cache. A replacement policy (like LRU) is only needed when all $N$ ways in the set are full.

Note: The schematic diagram provided in the paper implies a 4-stage non-linear pipeline with feedback. The question explicitly requests a reservation table with 4 rows and 6 columns. A standard academic example fitting this description assumes the task flows sequentially, then feeds back from S4 to S1 at cycle 5.

(a) Proposed Reservation Table:

(b) Forbidden Latencies:

• Distance in S1: $5 - 1 = 4$
• Distance in S2: $6 - 2 = 4$
• Forbidden Latencies (FL) = {4}
• Permissible Latencies (PL) = {1, 2, 3, 5, 6, 7+}

(c) State Diagram:

Initial Collision Vector (CV) = 1000 (since latency 4 is forbidden, bit 4 is 1).

• From 1000, Shift by 1: $0100$ OR $1000$ = 1100
• From 1000, Shift by 2: $0010$ OR $1000$ = 1010
• From 1000, Shift by 3: $0001$ OR $1000$ = 1001
• From 1000, Shift by 5+: $0000$ OR $1000$ = 1000
• From 1100, Shift by 1: $0110$ OR $1000$ = 1110
• From 1100, Shift by 2: $0011$ OR $1000$ = 1011
• (This process continues generating states like 1110, 1011, etc., forming the nodes of the state transition diagram).

(d) Greedy Cycles:

A greedy cycle always takes the shortest permissible path from any state.

• From 1000, shortest is 1 → 1100.
• From 1100, shortest is 1 → 1110.
• From 1110, shortest is 1 → 1111 (Wait, if state is 1111, permissible is 5+). So from 1110, shift by 1 is 0111 OR 1000 = 1111.
• From 1111, shortest is 5 → 1000.
• One greedy cycle is (1, 1, 1, 5). Average latency = $(1+1+1+5)/4 = 8/4 = 2$.
• Another greedy cycle: From 1000, take 2 → 1010. Shortest is 1 → 1101. Shortest is 2 → 1010. Cycle (2, 1). Average = $3/2 = 1.5$.

(e) Minimal Average Latency (MAL):

The MAL is the minimum average latency among all simple/greedy cycles. From the greedy cycles, the minimum average is 1.5. However, checking constant latency cycles: can we initiate every 2 cycles? From 1000, take 2 → 1010. Take 2 → 1010. Constant cycle (2) exists. Average = 2. Can we initiate every 1 cycle? From 1111, 1 is forbidden. So MAL cannot be 1. The cycle (2, 1) yields an average of 1.5, which is the MAL = 1.5.

(f) Maximal Throughput:

If cycle time $ au$, Max Throughput = $1 / ( ext{MAL} imes au) = \mathbf{1 / 1.5 au}$.

(a) Given: Cache size = 512 KB, Main Memory = 2 MB, Block Size = 64 Bytes.

• Physical Address Space = 2 MB = $2^{21}$ bytes → Physical Address = 21 bits
• Block Offset = $\log_2(64)$ = 6 bits
• Number of Cache Blocks (Lines) = 512 KB / 64 B = $2^{19} / 2^6 = 2^{13}$ lines

i) Associative Memory (Fully Associative):

No index bits are needed. The address is split into Tag and Offset.

• Tag = Total Address - Offset = $21 - 6 = \mathbf{15 ext{ bits}}$
• Offset = $\mathbf{6 ext{ bits}}$

ii) Direct Mapping:

Index bits = $\log_2( ext{Number of Cache Lines}) = \log_2(2^{13}) = 13$ bits.

• Tag = Total - Index - Offset = $21 - 13 - 6 = \mathbf{2 ext{ bits}}$
• Index = $\mathbf{13 ext{ bits}}$
• Offset = $\mathbf{6 ext{ bits}}$

iii) Set-Associative Mapping (Assuming 4-way):

Number of Sets = Total Cache Lines / 4 = $2^{13} / 2^2 = 2^{11}$ sets. Index bits = 11 bits.

• Tag = Total - Index - Offset = $21 - 11 - 6 = \mathbf{4 ext{ bits}}$
• Index = $\mathbf{11 ext{ bits}}$
• Offset = $\mathbf{6 ext{ bits}}$

(b) How Cache Memory Increases Processing Speed:

The CPU operates at a much faster clock speed (e.g., 3 GHz) than Main Memory (DRAM), which takes hundreds of cycles to respond. Cache memory bridges this gap.

• Technology: Cache uses SRAM, which is significantly faster than DRAM. It responds in 1-4 cycles instead of 100+.
• Principle of Locality: Programs do not access memory randomly.
  • Temporal Locality: If a variable is accessed (e.g., a loop counter), it will likely be accessed again very soon. Cache keeps this data close to the CPU, making subsequent accesses instant.
  • Spatial Locality: Programs tend to access data sequentially (e.g., arrays, sequential instructions). When the CPU requests 1 byte, the cache fetches an entire 64-byte block. The next 63 bytes requested will result in instant cache hits.

By serving 90-95% of memory requests from the extremely fast SRAM, the CPU avoids stalling for main memory, dramatically increasing overall processing throughput.

(a) Different Types of Addressing Modes:

• Immediate: The operand is explicitly specified in the instruction itself (e.g., ADD R1, #5). Fastest, but limited by instruction width.
• Direct (Absolute): The instruction contains the exact memory address of the operand (e.g., LOAD R1, 1000). Inflexible for relocatable code.
• Indirect: The instruction specifies a register or memory location that contains the actual address of the operand. Useful for pointers.
• Register: The operand is held in a CPU register (e.g., ADD R1, R2). Very fast.
• Displacement (Indexed/Base): Effective Address = Base Register + Constant Offset. Used for arrays or object properties.
• Relative: Effective Address = Program Counter (PC) + Offset. Used for short branching/loops.

(b) Advantages of Relative Addressing over Direct Addressing:

• Position-Independent Code (Relocatable): Relative addressing calculates targets relative to the current PC. The entire program can be loaded anywhere in memory without modifying the branch targets. Direct addressing hardcodes absolute addresses, which break if the program is moved.
• Instruction Size: Relative offsets are usually small (e.g., jumping +12 bytes in a loop) and fit into 8 or 16 bits. Direct addressing on modern systems requires full 32-bit or 64-bit addresses, bloating the instruction size.

(c) Vectored vs Non-vectored Interrupts:

(a) Structure of Arithmetic Pipeline for (A*B+C):

To evaluate $F = A imes B + C$, we need a floating-point multiplier pipeline followed by a floating-point adder pipeline.

• Multiplier Pipeline (Evaluates X = A * B):
  • Stage 1: Compare exponents and subtract.
  • Stage 2: Multiply mantissas.
  • Stage 3: Normalize result.
• Adder Pipeline (Evaluates F = X + C):
  • Stage 1: Compare exponents of X and C.
  • Stage 2: Shift mantissa of the smaller number.
  • Stage 3: Add mantissas.
  • Stage 4: Normalize result.

(A schematic diagram would show A and B entering the 3-stage multiplier, its output X entering the 4-stage adder along with operand C, flowing through latches between each stage).

(b) Hierarchical Cache Main Memory Sub-system:

Given: $T_c = 50$ ns, $T_m = 500$ ns.
Read operations = 80% (0.8), Write operations = 20% (0.2).
Read Hit Ratio ($H_r$) = 0.9. Scheme = Write-Through.

i) Average access time considering ONLY memory read cycle:

For reads, if data is in cache, it takes $T_c$. If not, it takes $T_c$ to check plus $T_m$ to fetch from main memory.

$ ext{AMAT}_{read} = 50 + (1 - 0.9) imes 500 = 50 + (0.1 imes 500) = 50 + 50 = \mathbf{100 ext{ ns}}$.

ii) Average access time for BOTH read and write cycles:

In a strict Write-Through scheme without a write buffer, every write must go to main memory, taking the full $T_m$ time (the cache is updated simultaneously).

$ ext{AMAT}_{write} = T_m = 500 ext{ ns}$.

The overall average access time is the weighted average of reads and writes:

$ ext{AMAT}_{total} = (0.8 imes 100) + (0.2 imes 500) = 80 + 100 = \mathbf{180 ext{ ns}}$.