Previous Year Questions

(i) The main memory of a computer has 2 cm blocks while the cache has 2c blocks. If the cache uses the set associative mapping scheme with 2 blocks per set; then block k of the main memory maps to the set:
Answer: (b) (k mod c) of the cache
Explanation: In set-associative mapping, the number of sets $M = ext{Total Cache Blocks} / ext{Blocks per Set} = 2c / 2 = c$ sets. A main memory block $k$ maps to set number $(k \pmod M)$, which is $(k \pmod c)$.

(ii) Suppose the time delay of the four stages of a pipeline are t1=60ns, t2=50ns, t3=90ns, t4=80ns respectively and the interface latch has a delay tl = 10 ns, then the maximum clock frequency (cycle time) for the pipeline is:
Answer: (a) 100 ns
Explanation: The clock cycle time $T$ must be large enough to accommodate the slowest pipeline stage plus the latch delay. $T = \max(t_1, t_2, t_3, t_4) + t_l = 90 + 10 = 100$ ns. (Note: The options are in nanoseconds, which represents the cycle time, not frequency).

(iii) As the bus in a multiprocessor is a shared resource, so there must be some mechanism to resolve the conflict. The ............ algorithm form the below mentioned is not a conflict resolution technique.
Answer: (a) State priority Algorithm
Explanation: Common bus arbitration (conflict resolution) techniques include Daisy Chaining, FIFO, LRU, Polling, and Static Priority. "State priority" is not a standard recognized bus arbitration algorithm.

(iv) Dynamic pipeline allows:
Answer: (a) Multiple functions to evaluate
Explanation: A dynamic (multi-functional) pipeline can be reconfigured dynamically to perform different functions at different times, as opposed to a static pipeline which performs a fixed function.

(v) A computer with cache access time of 100 ns, a main memory access time of 1000 ns and a hit ratio of 0.9 produces an average access time of:
Answer: (b) 200 ns
Explanation: Average Memory Access Time (AMAT) = $T_{cache} + (1 - ext{Hit Ratio}) imes T_{main\_memory} = 100 + (1 - 0.9) imes 1000 = 100 + 100 = 200$ ns.

(vi) The number of cycles required to complete n tasks in a k stage pipeline is:
Answer: (a) k + n - 1
Explanation: The first task takes $k$ cycles to complete. The remaining $(n-1)$ tasks each complete in $1$ cycle. Total cycles = $k + (n - 1)$.

(vii) The prefetching technique is a solution for:
Answer: (c) Control Hazard
Explanation: Instruction prefetching (often coupled with branch prediction) is primarily used to mitigate control hazards by fetching instructions down the predicted path before the branch is fully resolved, keeping the pipeline fed.

(viii) In general an n input Omega network requires ............ stages of 2 * 2 switches.
Answer: (b) 4 (Assuming a 16-input network)
Explanation: An $N$-input Omega network requires $\log_2 N$ stages. Since the options are constants (2, 4, 8, 16), the question likely had a typo and meant a 16-input network, which requires $\log_2 16 = 4$ stages.

(ix) Which of the following has no practical usage?
Answer: (c) MISD
Explanation: In Flynn's taxonomy, Multiple Instruction, Single Data (MISD) has no mainstream commercial implementation, unlike SISD (uniprocessors), SIMD (GPUs/Vectors), and MIMD (multiprocessors).

(x) The expression for Amdahl's law is:
Answer: (a) S(n) = 1/f where n → ∞
Explanation: If $f$ represents the sequential fraction of the code, Amdahl's Law states Speedup $S = rac{1}{f + (1-f)/n}$. As the number of processors $n o \infty$, the speedup asymptotically approaches $1/f$.

Let a pipeline have $k$ stages, and assume each stage takes $t_p$ time to execute. Let there be $n$ tasks to execute.

• Non-pipelined execution time ($T_1$): A single task takes $k imes t_p$ time. So, $n$ tasks will take $T_1 = n imes k imes t_p$.
• Pipelined execution time ($T_k$): The first task takes $k$ cycles to fill the pipeline. After that, one task completes every cycle. So, $n$ tasks require $k + (n-1)$ cycles. Time $T_k = (k + n - 1) imes t_p$.

The speedup $S_k$ is the ratio of non-pipelined time to pipelined time:

To find the maximum (ideal) speedup, we take the limit as the number of tasks $n$ becomes very large ($n o \infty$):

Thus, ideally, a pipeline with $k$ stages can yield a maximum speedup equal to its depth $k$.

Given Instructions:

I1: MUL R1, R2, R3
I2: ADD R2, R3, R4
I3: INC R4
I4: SUB R6, R3, R7
    

Assumption: To make the dependency analysis meaningful (as per standard academic problems), we assume the instruction format is OP Source1, Source2, Destination. Therefore:

• I1: MUL R1, R2, R3 → R3 = R1 * R2 (Writes R3)
• I2: ADD R2, R3, R4 → R4 = R2 + R3 (Reads R3, Writes R4). RAW hazard on R3 with I1.
• I3: INC R4 → R4 = R4 + 1 (Reads R4, Writes R4). RAW hazard on R4 with I2.
• I4: SUB R6, R3, R7 → R7 = R6 - R3 (Reads R3). RAW hazard on R3 with I1 (but resolved by the time I4 executes).

Pipeline Execution Diagram (assuming a 5-stage pipeline: IF, ID, EX, MEM, WB and no hardware forwarding):

Delay Analysis:

• I2 needs R3 written by I1. I1 writes R3 in CC5 (WB). I2 can read it in CC6 (ID). This introduces a 2-cycle delay (stall).
• I3 needs R4 written by I2. I2 writes R4 in CC8 (WB). I3 can read it in CC9 (ID). This introduces another 2-cycle delay (stall).
• Total Delay = 2 + 2 = 4 clock cycles of delay due to data dependencies.

A Reservation Table is a 2D space-time diagram representing the flow of data through the stages (or functional units) of a pipeline over successive clock cycles. The rows represent the functional units (hardware resources) and the columns represent clock cycles.

How it helps study pipeline performance:

• Resource Conflict Detection: By mapping out which unit is used in which cycle, the reservation table allows designers to visually identify structural hazards (when two tasks try to use the same unit in the same cycle).
• Forbidden Latencies: It is used to calculate the set of forbidden latencies — the intervals (in clock cycles) between initiating two successive tasks that would result in a resource collision. This is found by calculating the distance between all pairs of 'X's in every row.
• Collision Vector formulation: The forbidden latencies are converted into a binary Collision Vector, which serves as the initial state of the pipeline.
• State Transition Diagram: From the collision vector, a state diagram can be drawn to find all permissible scheduling cycles.
• Minimal Average Latency (MAL): By analyzing the simple and greedy cycles in the state diagram, the reservation table ultimately helps determine the MAL, which dictates the maximum sustainable throughput of the pipeline.

Cache Coherence Problem: In a multiprocessor system where each processor has its own private cache, multiple copies of the same main memory data can exist in different caches. If Processor P1 modifies its local copy of variable X, Processor P2's cached copy of X becomes stale (outdated). If P2 reads X, it will read an incorrect value. Ensuring all processors see a consistent, updated view of shared memory is the cache coherence problem.

Method to Resolve (Snoopy Protocol - Write Invalidate):

In a bus-based multiprocessor, all cache controllers "snoop" (monitor) the shared bus. When P1 wants to write to variable X:

1. P1 places an invalidation signal on the bus for address X.
2. All other caches snooping the bus see this signal. If they have a copy of X, they mark their cache line as Invalid.
3. P1 proceeds to write the new value to its local cache.
4. If P2 subsequently tries to read X, it encounters a cache miss (since its copy was invalidated) and is forced to fetch the fresh data.

Limitations:

• Bus Bottleneck: Snoopy protocols require a shared bus so all caches can monitor all traffic. As the number of processors increases (usually beyond 16-32), the bus traffic from broadcasted invalidation messages saturates the bus bandwidth, making it unscalable.
• High Power Consumption: Every cache controller must constantly snoop and perform tag lookups for every bus transaction, consuming significant power.

Given: Number of instructions $n = 15000$, Clock rate = $25$ MHz, Pipeline stages $k = 5$.

Clock cycle time $t_p = 1 / (25 imes 10^6)$ seconds = $40$ ns.

(i) Speedup compared to non-pipelined processor:

• Time taken by non-pipelined processor ($T_1$): $n imes k imes t_p = 15000 imes 5 imes 40 ext{ ns} = 3,000,000$ ns = $3$ ms.
• Time taken by pipelined processor ($T_k$): $(k + n - 1) imes t_p = (5 + 15000 - 1) imes 40 ext{ ns} = 15004 imes 40 = 600,160$ ns = $0.60016$ ms.
• Speedup (S) = $T_1 / T_k = 3,000,000 / 600,160 pprox \mathbf{4.998}$

(ii) Efficiency and Throughput:

• Efficiency (E) = $rac{Speedup}{k} = rac{4.998}{5} = \mathbf{99.97\%}$
• Throughput (W) = $rac{n}{T_k} = rac{15000}{600.16 ext{ \mu s}} pprox \mathbf{24.99 ext{ MIPS}}$ (Millions of Instructions Per Second).

1. Broadcast (Write-Update) vs Write-Invalidate Protocols:

2. MESI Protocol:

MESI is a popular write-invalidate cache coherence protocol. Each cache line is in one of 4 states:

• Modified (M): The cache line is present only in the current cache and is dirty (modified). Main memory is stale.
• Exclusive (E): The cache line is present only in the current cache but is clean (matches main memory). A write can happen without generating bus traffic.
• Shared (S): Copies of the cache line may exist in multiple caches. A write to it requires broadcasting an invalidation first.
• Invalid (I): The cache line is empty or its contents are invalid.

3. Centralized vs Distributed Shared Memory:

• Centralized Shared Memory (UMA - Uniform Memory Access): All processors share a single, central physical memory. Memory access time is uniform for all processors. It uses symmetric multiprocessing (SMP) and bus-based snoopy protocols. It scales poorly beyond a few dozen processors due to bus bottleneck.
• Distributed Shared Memory (NUMA - Non-Uniform Memory Access): Main memory is physically distributed across the processors (each has a local memory module), but all memory shares a single global logical address space. Accessing local memory is fast; accessing remote memory over the interconnection network is slower. It scales to hundreds of processors using directory-based coherence protocols.

4. Superscalar, Super-pipelined, and VLIW Processors:

• Superscalar: The hardware dynamically issues multiple independent instructions per clock cycle to multiple execution units. Hardware handles dependency checking and out-of-order execution. (e.g., Intel Core).
• Super-pipelined: The pipeline is divided into a very large number of extremely fine-grained stages (e.g., 15-20+ stages). This allows the processor to run at a very high clock frequency, but increases the branch penalty.
• VLIW (Very Long Instruction Word): The compiler groups multiple independent operations into a single wide instruction word (e.g., 128-bits). The hardware is simple as it relies entirely on the compiler for scheduling and dependency resolution (static scheduling).

1. Flynn's Classification: Classifies computers based on the number of concurrent instruction streams and data streams.

• SISD (Single Instruction, Single Data): Traditional uniprocessor (e.g., old PCs).
• SIMD (Single Instruction, Multiple Data): A single instruction operates on multiple data elements simultaneously (e.g., Vector processors, GPUs).
• MISD (Multiple Instruction, Single Data): Multiple instructions operate on a single data stream (rare, fault-tolerant systems).
• MIMD (Multiple Instruction, Multiple Data): Multiple independent processors executing different instructions on different data (e.g., Multi-core processors, Clusters).

2. Loosely Coupled vs Tightly Coupled Systems:

• Tightly Coupled (Multiprocessors): Processors share a common main memory. Communication is fast via shared variables. They usually share a single OS instance. Delay is very low.
• Loosely Coupled (Multicomputers/Clusters): Each processor has its own private local memory. Communication occurs via message passing over a network (e.g., Ethernet). Delays are higher, and each node may run its own OS instance.

3. Network Designs:

• Multiport network (3 Processors to 3 Memory Modules): In a multiport memory system, each memory module has multiple ports (one for each processor). Here, each of the 3 memory modules has 3 ports. Every processor is directly connected to a port on every memory module.
• Crossbar Network (25 Inputs to 9 Outputs): A crossbar switch matrix requires $N imes M$ crosspoint switches. For 25 inputs and 9 outputs, the network requires $25 imes 9 = \mathbf{225 ext{ crosspoint switches}}$.

4. Omega vs Delta Network:

• Omega Network: A specific type of blocking multistage interconnection network (MIN) built using $2 imes 2$ switches and perfect shuffle interconnections between all stages.
• Delta Network: A broader class of digit-controlled routing networks where any input can route to an output based purely on the base-$b$ digits of the destination address. An Omega network is a specific subclass of a Delta network.

5. Constructing an Omega Network for N=8:

An $N=8$ Omega network requires $\log_2(8) = 3$ stages. Each stage has $8/2 = 4$ switches (total 12 switches). The routing between stages follows a Perfect Shuffle pattern.

Inputs (0-7) undergo Perfect Shuffle before Stage 1:
0 -> 0, 4 -> 1, 1 -> 2, 5 -> 3, 2 -> 4, 6 -> 5, 3 -> 6, 7 -> 7
This shuffle is repeated between Stage 1 & 2, and Stage 2 & 3.
    

(a) Given Reservation Table:

(b) Forbidden Latencies (FL):

The distance between pairs of 'X's in each row:

• Row S1: $(5-1)=4$, $(7-5)=2$, $(7-1)=6$. FL = {2, 4, 6}
• Row S2: $(4-2)=2$. FL = {2}
• Row S3: $(5-3)=2$, $(7-5)=2$, $(7-3)=4$. FL = {2, 4}

Union of Forbidden Latencies = {2, 4, 6}.
Permissible Latencies = {1, 3, 5, >=7}.

(c) Initial Collision Vector (CV):

CV is represented as $C_6 C_5 C_4 C_3 C_2 C_1$. Since 2, 4, 6 are forbidden, bits 2, 4, 6 are 1.
CV = 101010

State Transition Diagram generation:

• Start at State 101010.
• Shift right by Permissible Latencies (1, 3, 5, 7+) and bitwise OR with initial CV.
• Shift by 1: $010101 ext{ OR } 101010 = \mathbf{111111}$. (New state)
• Shift by 3: $000101 ext{ OR } 101010 = \mathbf{101111}$. (New state)
• Shift by 5: $000001 ext{ OR } 101010 = \mathbf{101011}$. (New state)
• Shift by 7+: $000000 ext{ OR } 101010 = \mathbf{101010}$. (Back to initial)

(The full state transition diagram connects these states via directed edges representing the latency taken).

(d) Simple and Greedy Cycles:

• Simple cycles: Closed loops in the state diagram where no state is repeated (except start/end). Examples from initial state (assuming self loops for >=7): (1, 7), (3, 5), (5, 3), (3, 7), etc. Wait, tracing from 101010: cycle (7) is a simple cycle of latency 7.
• Greedy cycles: A simple cycle whose edges are all formed by choosing the minimum permissible latency from each state. From 101010, min latency is 1. Goes to 111111. From 111111, min permissible is 7+. Goes to 101010. So the cycle (1, 7) is greedy. Average latency = (1+7)/2 = 4. Another greedy path might start elsewhere, but (1,7) is dominant. Another path: from 101010 take 3 -> 101111. From 101111 min is 5 -> 101011. From 101011 min is 3 -> 101111. Cycle is (3, 5). Average = 4.

(e) Optimal Constant Latency Cycle & Minimal Average Latency:

A constant latency cycle uses the same latency repeatedly. From the permissible latencies {1, 3, 5, 7}, we can try initiating repeatedly:
Trying latency 3: 3, 3, 3... This involves jumping from 101010 (takes 3) -> 101111. From 101111, latency 3 is NOT permissible (bit 3 is 1). So constant latency 3 is not possible.
Trying latency 5: from 101010 (takes 5) -> 101011. From 101011 (takes 5) -> 101011. This forms a constant latency cycle of (5).
Thus, the optimal constant latency cycle is 5.
The Minimal Average Latency (MAL) is the minimum average of any greedy cycle. Comparing (1,7) avg 4, and (3,5) avg 4. MAL = 4.

(f) Throughput:

Pipeline clock period $ au = 20$ ns. MAL = 4 cycles.
Average time between initiations = $MAL imes au = 4 imes 20 = 80$ ns.
Max Throughput = $1 / 80 ext{ ns} = 12.5 imes 10^6$ tasks/sec = 12.5 MIPS.

(a) Amdahl's Law calculations:

Base CPI = $(0.4 imes 1) + (0.2 imes 4) + (0.3 imes 2) + (0.1 imes 3) = 0.4 + 0.8 + 0.6 + 0.3 = \mathbf{2.1}$
Base Execution Time $\propto rac{Base\_CPI}{Base\_Clock}$

• Improvement 1 (Branch CPI 4 → 3):
  New CPI = $2.1 - (0.2 imes 4) + (0.2 imes 3) = 2.1 - 0.8 + 0.6 = 1.9$.
  Speedup = $rac{2.1}{1.9} = \mathbf{1.105 imes}$
• Improvement 2 (Clock 2.0 GHz → 2.3 GHz):
  Speedup = $rac{2.3}{2.0} = \mathbf{1.15 imes}$
• Improvement 3 (Store CPI 3 → 2):
  New CPI = $2.1 - (0.1 imes 3) + (0.1 imes 2) = 2.1 - 0.3 + 0.2 = 2.0$.
  Speedup = $rac{2.1}{2.0} = \mathbf{1.05 imes}$

Conclusion: Improvement 2 (Increasing clock frequency to 2.3 GHz) provides the highest speedup (1.15x) and is the best option.

(b) Virtual Memory Concepts:

• Memory Fragmentation: Occurs when free memory is broken into small, non-contiguous blocks. External fragmentation happens when total free space exists to satisfy a request, but it is not contiguous. Internal fragmentation happens when allocated blocks are slightly larger than requested memory, wasting space inside the block.
• Advantage of Paging: Paging eliminates external fragmentation by allowing a process's physical memory to be non-contiguous. Any free physical frame can be allocated to any virtual page.
• Virtual Memory Example: Logical address space = 8 KB, Physical = 4 KB, Page size = 1 KB.
  • Logical Pages = 8 KB / 1 KB = 8 pages (Pages 0 to 7).
  • Physical Frames = 4 KB / 1 KB = 4 frames (Frames 0 to 3).
  • Because logical pages > physical frames, the OS must map only the active 4 pages into RAM, keeping the other 4 on disk (swap).
• Page Fault with FIFO & LRU: A page fault occurs when a requested page is not in physical RAM.
  • FIFO (First-In, First-Out): Evicts the page that has been in memory the longest.
  • LRU (Least Recently Used): Evicts the page that has not been accessed for the longest time, which is usually a better predictor of future use than FIFO.