Consider the following reservation table for a pipeline having three stages…
2015
Consider the following reservation table for a pipeline having three stages 𝑆1, 𝑆2 and 𝑆3.
The minimum average latency (MAL) is ________.
Attempted by 57 students.
Show answer & explanation
Correct answer: 3
Answer: Minimum Average Latency (MAL) = 3.
Reasoning:
1) Compute forbidden latencies: these are the positive differences between two X's in the same row (same stage).
Stage S1 has X at times 1 and 5 → forbidden latency 4.
Stage S2 has X at times 2 and 4 → forbidden latency 2.
Stage S3 has a single X → no additional forbidden latency.
So the set of forbidden latencies is F = {2, 4}.
2) A chosen initiation interval k is valid only if no multiple of k equals a forbidden latency (because instructions separated by m·k cycles must not collide).
k = 1: invalid because 2 = 2·1 is forbidden (instructions two apart collide).
k = 2: invalid because 2 = 1·2 is forbidden (adjacent starts collide).
k = 3: valid because no multiple of 3 equals 2 or 4 (3, 6, ... do not hit forbidden latencies).
k = 4: invalid because 4 = 1·4 is forbidden.
Therefore the smallest valid initiation interval is 3, so the Minimum Average Latency is 3.