Pipeline Processor Practice Questions

Superscalar processors have multiple execution units (e.g., multiple ALUs) that allow them to issue and execute several independent instructions per clock cycle, thereby exploiting instruction-level parallelism (ILP).

Single Instruction, Multiple Data (SIMD) architectures perform the same operation on multiple data elements in parallel, which is characteristic of vector processors.

Misprediction rate = 10% of branches. Branch penalty cycles per branch = 3 × 0.1 = 0.3 cycles per branch. Since 20% of instructions are branches, average stall cycles per instruction = 0.2 × 0.3 = 0.06. Ideal CPI = 1, so average CPI = 1 + 0.06 = 1.06. This calculation is based on standard branch hazard formulas from GATE 2021 and 2023 questions.[reference:8]

Misprediction ratio = 1 - 0.9 = 0.1. Extra cycles per branch = 0.1 × 3 = 0.3. Since branches are 0.2 of all instructions, average extra cycles per instruction = 0.2 × 0.3 = 0.06. Thus CPI = 1 + 0.06 = 1.06.

(1) Traditional single-core CPU: Single Instruction, Single Data (SISD). (2) Vector processor: Single Instruction stream, Multiple Data streams (SIMD). (3) SMP: Multiple Instruction streams, Multiple Data streams (MIMD). (4) Systolic array performing different operations on different data: Multiple Instruction, Single Data (MISD).

Cache coherence and memory consistency are unique to multiprocessor systems. Data races occur when multiple threads access shared data while lacking proper synchronization. Compulsory misses also occur in uniprocessor caches, so they are not a multiprocessor- specific challenge.

Non-pipelined time = 1,000,000 × 10 ns = 10^7 ns. Pipelined time = (5 + 999,999) × 3 ns = 3,000,012 ns. Speedup = 10^7 / 3,000,012 ≈ 3.33. As the number of instructions grows, speedup approaches 10/3 = 3.33. This highlights that pipeline depth doesn't always give a speedup equal to the number of stages due to latch overheads and pipeline fill time. Derived from GATE 2008 and 2016 questions. For a more detailed mathematical proof of this convergence, you can consult standard textbooks on computer architecture and performance analysis.

In SMP, all processors share memory, I/O, and one OS instance, with equal access. However, single-thread performance is not inherently higher-the advantage is multi-thread throughput, not faster single-thread execution.

With forwarding: I2 reads R1 → use forwarding from EX stage of I1 to EX stage of I2 → 0 stall needed, but I2's ID stage is after I1's WB? Actually, I2 can start ID immediately, I1's result is forwarded from EX to I2's EX. However, I2 still needs to wait for I1's EX? Actually, I1's EX happens at cycle 3, I2's EX at cycle 4, so no stall. With forwarding, the only stalls might be for load-use hazards. Without forwarding: I2 must stall 2 cycles until I1's WB is complete. I4 depends on I2's result, needing another stall. Total stalls without forwarding is 3 cycles. With forwarding, only 1 stall if any. This mirrors GATE 2018 questions on forwarding benefits.[reference:7]

If work is perfectly parallelizable, execution time scales inversely with the number of cores. Therefore, time = 60 seconds / 4 = 15 seconds. (This is an ideal upper bound.)

Let n be the number of cores. Serial portion = 10 ns; parallel portion = 90 ns. Execution time T(n) = 10 + 90/n + 10×(n−1). Differentiating and setting derivative to zero: -90/n² + 10 = 0 ⇒ n = 3. T(2)=75 ns; T(3)=60 ns; T(4)=62.5 ns, so minimum at n=3.

The speedup of a pipelined processor over a non-pipelined processor is ideally equal to the number of pipeline stages, assuming perfectly balanced delays and no hazards. A 5-stage pipeline can ideally have a speedup of 5 over a non-pipelined processor. Adding multiple ALUs in a stage does not increase the ideal speedup beyond the pipeline depth, as the throughput is still one instruction per clock (when considering a scalar pipeline). This question tests the fundamental concept of pipeline speedup from GATE 2005.

By Amdahl's law, Speedup = 1 / [ (1 - p) + p/n ]. Here p=0.6, n=3 ⇒ Speedup = 1 / [0.4 + 0.2] = 1/0.6 = 1.666... ≈ 1.67.

In sequential consistency, the program order of each thread is preserved, and writes of one thread can only become visible to the other according to some global order. The possible outcomes: (0,0) if both writes of thread 1 haven't been seen; (1,0) if thread 2 runs after X=1 but before Y=1; (1,1) if thread 2 runs after both writes. Pair (0,1) is impossible because thread 2 cannot see Y=1 without also seeing X=1.

Queueing and positioning time: seek + rotational latency = 8 ms. Transfer time = block size / transfer rate = 4 KB / (5 MB/s) = 0.8 ms. Controller overhead = 2 ms. Total = 8 + 0.8 + 2 = 10.8 ms.

Pipelining increases ILP by overlapping instruction stages. Superscalar issue allows multiple instructions to be issued each cycle. Out-of-order execution rearranges instructions to reduce stalls and better utilize execution resources. While cache size affects memory access, it does not directly affect ILP.

Non-pipelined time per instruction = 5 + 6 + 11 + 8 = 30 ns. Clock period for pipelined implementation = max(5,6,11,8) + 1 = 12 ns. For large number of instructions (N), speedup = (30N) / ((4 + N - 1) * 12) ≈ 30/12 = 2.5.[reference:0]

If a branch is resolved at the end of the EX stage, two instructions following the branch would have been fetched and need to be flushed if the branch is taken. Therefore, the branch penalty is typically 2 cycles. For a 4-stage pipeline, speedup being 3 suggests ideal CPI of 1, with branch penalty of 2 cycles. This aligns with GATE 2015 and 2017 questions on branch penalty evaluation. For a detailed, step-by-step exploration of how branch resolution and penalty cycles interact to affect pipeline speedup, consider reviewing recommended GATE textbooks or coaching materials.