"Instruction Pipelining & Hazards" — Practice

Question 1

A 4-stage pipeline executes 12 instructions with no hazards. How many clock cycles are required?

Accepted Answer

B

Question 2

In a simple in-order 5-stage pipeline, which dependence causes an actual hazard?

Accepted Answer

A

Question 3

A pipeline has stage delays of 5, 9, 6 and 7 ns with a 1 ns register overhead. What is the clock period?

Accepted Answer

C

Question 4

A non-pipelined processor takes 15 ns per instruction. It is redesigned as a 5-stage pipeline with equal stages and a 1 ns register overhead per stage. Find the speedup for 1000 instructions.

Accepted Answer

Split the 15 ns into 5 equal stages of 3 ns each.

The clock period is the stage delay plus the register overhead, so 3 + 1 = 4 ns.

Pipelined time for 1000 instructions is (5 + 1000 - 1) times 4 ns = 1004 times 4 = 4016 ns.

Unpipelined time is 1000 times 15 = 15,000 ns.

Speedup is 15,000 divided by 4016, approximately 3.74.

Note why this falls short of the ideal 5. Two effects reduce it. The fill time of 4 cycles costs a little, contributing the difference between 1000 and 1004. Far more significant is the register overhead: each stage costs 4 ns instead of 3, so the pipelined machine completes an instruction every 4 ns rather than every 3, and the ideal ratio drops from 5 to 15 divided by 4, which is 3.75. The fill time then trims that to 3.74.

This is the practical reason pipelines are not made arbitrarily deep: the per-stage register overhead becomes a larger fraction of a shorter stage.

Question 5

A processor executes a program with 25 per cent branch instructions and a 3-cycle misprediction penalty. Compare the CPI with a predictor that is 70 per cent accurate and one that is 95 per cent accurate.

Accepted Answer

The CPI contribution of branches is the branch frequency times the misprediction rate times the penalty.

With 70 per cent accuracy, the misprediction rate is 0.30.

Added CPI = 0.25 times 0.30 times 3 = 0.225, giving a CPI of 1.225.

With 95 per cent accuracy, the misprediction rate is 0.05.

Added CPI = 0.25 times 0.05 times 3 = 0.0375, giving a CPI of 1.0375.

The improvement is 1.225 divided by 1.0375, approximately 1.18, or 18 per cent faster.

Two observations follow. The penalty is applied only to mispredicted branches, not to all of them, so omitting the misprediction rate would overstate the cost fourfold in the first case. And the benefit of good prediction scales with the penalty: at a 10-cycle penalty typical of a deep pipeline, the same accuracies would give CPIs of 1.75 and 1.125, a 56 per cent difference.

Question 6

Given the sequence LOAD R1, 0(R2) followed by ADD R3, R1, R4 followed by SUB R5, R3, R6, how many stall cycles are needed with full forwarding in a 5-stage pipeline?

Accepted Answer

Handle each dependence separately.

The first dependence is a load-use hazard. The load produces its value at the end of its memory stage, which is cycle 4 of its own progress. The add needs that value at the start of its execute stage, which without a stall would be cycle 3 overall. The value is needed before it exists, so one stall cycle is required. After the bubble, the add's execute aligns with the end of the load's memory stage and a memory-to-execute forwarding path supplies the value.

The second dependence is between the add and the sub. The add produces its result at the end of its execute stage, and the sub needs it at the start of its own execute stage, one cycle later. An execute-to-execute forwarding path covers this exactly, with no stall.

The total is 1 stall cycle.

The general rule extracted from this: an arithmetic result can always be forwarded to the immediately following instruction, but a loaded value cannot, because the load's result arrives one stage later in the pipeline. That single stage of difference is the entire reason the load-use hazard exists.

Question 7

A loop body executes 8 times and the whole loop is entered 100 times. Compare the total mispredictions of a one-bit and a two-bit predictor on the loop-closing branch.

Accepted Answer

The loop-closing branch is taken 7 times and not taken once per entry, since the eighth iteration exits.

One-bit predictor. It stores the last outcome. During the 7 taken iterations it predicts taken and is correct after the first. On the eighth iteration the branch is not taken, so it mispredicts and flips its bit to not-taken. On the next entry, the first iteration is taken but the stored bit still says not-taken, so it mispredicts again and flips back.

That is 2 mispredictions per entry, so 200 across 100 entries.

Two-bit predictor. It uses a saturating counter and changes its prediction only after two consecutive mispredictions. During the taken iterations the counter saturates at strongly-taken. On the exit it mispredicts once and moves to weakly-taken, but its prediction is still taken. On the next entry the branch is taken, which is correct, and the counter returns to strongly-taken.

That is 1 misprediction per entry, so 100 across 100 entries.

The two-bit predictor halves the mispredictions, from 200 to 100. The saving comes entirely from eliminating the re-entry misprediction, which is why the two-bit scheme became standard: loops are the commonest branch pattern in real code, and the one-bit predictor gets their boundaries wrong twice over.

Question 8

A 5-stage pipeline has delays 4, 9, 5, 8 and 6 ns with 1 ns register overhead. Determine the throughput, then find the best achievable throughput by splitting exactly one stage into two equal halves.

Accepted Answer

The clock period is the slowest stage plus overhead: 9 + 1 = 10 ns. Throughput in steady state is one instruction per clock, so 1 per 10 ns, which is 100 million instructions per second.

Now consider splitting one stage. Splitting the 9 ns stage into two 4.5 ns halves gives stage delays 4, 4.5, 4.5, 5, 8, 6. The new bottleneck is the 8 ns stage, so the clock period becomes 8 + 1 = 9 ns and throughput rises to about 111 million instructions per second.

Splitting the 8 ns stage instead leaves the 9 ns stage as the bottleneck, so the period stays at 10 ns and nothing is gained.

Splitting any other stage likewise achieves nothing.

So the best achievable is 9 ns per instruction, obtained by splitting the 9 ns stage, and the improvement is limited by the 8 ns stage that becomes the new bottleneck.

The general lesson is that only splitting the current bottleneck helps, and the gain stops at the next-slowest stage. The design has also gained a stage, raising the branch penalty by one cycle, so the 11 per cent throughput gain must be weighed against extra misprediction cost before the change is worthwhile.

Question 9

A 5-stage pipeline uses a unified memory serving both the fetch stage and the memory stage. Explain the structural hazard, quantify its cost, and state the standard fix.

Accepted Answer

In a five-stage pipeline the instruction fetch stage and the memory access stage are separated by three stages, so at any moment one instruction is fetching while another, issued three cycles earlier, is accessing data memory.

With a unified memory having a single port, those two accesses cannot both proceed in the same cycle. One must wait, which stalls the pipeline.

Quantifying the cost: the conflict arises whenever an instruction in the memory stage actually accesses memory, which is only for loads and stores. If loads and stores are, say, 30 per cent of instructions, then 30 per cent of cycles contain a conflict, each costing one stall.

That adds 0.30 to the CPI, taking it from 1.00 to 1.30, a 30 per cent slowdown from a single shared resource.

The standard fix is duplication: separate instruction and data caches, so that fetch and data access use physically different memories and never contend. This is one of the principal reasons the split first-level cache design is universal, alongside the different access patterns of the two streams.

Where duplication is genuinely too expensive, such as a single divider or floating-point unit, the hazard is resolved by stalling instead, and the cost is accepted because the affected instructions are rare.

Practice — "Instruction Pipelining & Hazards"

Sign in to save attempts to your dashboard and track your accuracy over time

Find a verified tutor

Join a live course

Browse coaching centres

About

Categories

Support

Documentation

Get Study Tips & Updates

Download Our App

Download for iOS

Download for Android

Popular Cities