GATE CS

Instruction pipelining and pipeline hazards

Instruction pipelining overlaps the execution of successive instructions by splitting the datapath into stages. This raises throughput, but structural, data and control hazards can force stalls that push the average CPI above the ideal value of 1. These notes use the classic in-order, single-issue 5-stage pipeline (IF, ID, EX, MEM, WB) as the standing convention and state every other assumption where it is used. They cover how to compute the clock period, speed-up, throughput, efficiency and CPI with stalls. They also cover how to count stalls exactly, with and without forwarding: which stage reads or writes in which half-cycle, and where a branch is resolved.

12 previous-year questions · 12 solved · 5 practice questions

Pipeline Fundamentals: Stages, Clock Period and Speed-up

Instruction pipelining splits the datapath into $k$ stages and overlaps successive instructions, so that one instruction is being decoded while the next is being fetched. The model used throughout these notes is the classic in-order, single-issue 5-stage pipeline: IF (fetch), ID (decode and register read), EX (execute), MEM (memory access) and WB (register write-back). Pipelining raises throughput, the number of instructions completed per unit time. It does not reduce the latency of a single instruction, and it generally increases it: every instruction now takes $k \times T_{p}$ , and that is at least the sum of the stage delays whenever the stages are unbalanced or the latches add delay.

PIPELINE CLOCK PERIOD

T_{p} = max (t_{1}, t_{2}, \dots, t_{k}) + t_{latch}

$t_{i}$ is the delay of stage $i$ and $t_{latch}$ is the inter-stage register (latch) delay, taken as 0 only if the question says so. The slowest stage sets the clock for every stage.

TOTAL TIME FOR N INSTRUCTIONS, K STAGES (NO STALLS)

T (n) = (k + n - 1) T_{p}

The first instruction needs $k$ cycles to pass through all the stages (pipeline fill). After that, one instruction completes every cycle. Valid for an ideal pipeline with no stalls.

SPEED-UP OVER NON-PIPELINED EXECUTION (GENERAL)

S = \frac{n t _{np}}{( k + n - 1 ) T _{p}}

$t_{np}$ is the time one instruction takes on the non-pipelined machine, as the question defines it: usually the sum of the stage delays. As $n \to \infty$ , $S \to t_{np} / T_{p}$ .

SPEED-UP, BALANCED STAGES (SPECIAL CASE)

S = \frac{n k}{k + n - 1}

Only when $t_{np} = k T_{p}$ , i.e. all stages have equal delay and latch delay is ignored (or the non-pipelined machine is defined as taking $k$ pipelined cycles per instruction). Then $S \to k$ as $n \to \infty$ : the ideal maximum speed-up equals the number of stages.

EXAM TIP

With unequal stage delays, the non-pipelined time 'sum of stage delays' and the time ' $k \times T_{p}$ ' are different numbers. Read which one the question defines before you substitute. Only the second one gives $S = nk / (k + n - 1)$ .

Performance Metrics: Throughput, Efficiency and CPI with Stalls

Besides speed-up, the standard measures are throughput, efficiency and, once hazards appear, the average CPI (cycles per instruction). CPI is where every kind of stall ends up, whatever hazard caused it.

THROUGHPUT

Throughput = \frac{n}{( k + n - 1 ) T _{p}}

Instructions completed per unit time with no stalls. It approaches $1/ T_{p}$ as $n \to \infty$ .

PIPELINE EFFICIENCY

η = \frac{n}{k + n - 1}

Efficiency is the fraction of stage-cycles that do useful work: $nk$ busy stage-cycles out of $k (k + n - 1)$ . It is below 1 for any finite $n$ because of fill and drain, and it tends to 1 as $n \to \infty$ . It equals $S / k$ only in the balanced-stage case, where $t_{np} = k T_{p}$ .

AVERAGE CPI WITH STALLS

CPI_{avg} = CPI_{ideal} + i \sum p_{i} \times penalty_{i}

For a scalar in-order pipeline, $CPI_{ideal} = 1$ . Here $p_{i}$ is the fraction of all instructions that suffer hazard type $i$ , and $penalty_{i}$ is the number of stall cycles it costs. The sum is the average number of stall cycles per instruction. This is the steady-state figure: pipeline fill cycles are ignored.

EXECUTION TIME FROM CPI

T_{exec} = Instruction count \times CPI_{avg} \times T_{clk}

The standard performance equation. On the pipelined machine, $T_{clk} = T_{p}$ .

SPEED-UP WITH STALLS

S = \frac{t _{np}}{CPI _{avg} \times T _{p}} = \frac{k}{1 + stall cycles per instruction} (if t_{np} = k T_{p})

$t_{np}$ is the non-pipelined time per instruction. The second line holds only for balanced stages with no latch overhead. Both lines ignore fill cycles, so they describe a long program.

EXAM TIP

"Ideal CPI = 1" holds only for a pipeline that issues at most one instruction per cycle. Do not apply it to a multiple-issue (superscalar or VLIW) machine.

Structural Hazards

A structural hazard occurs when two instructions in different pipeline stages need the same hardware resource in the same cycle, such as a memory port, a register-file port or a single non-pipelined multiplier, and the hardware cannot serve both. The classic case is a single memory shared by instructions and data. In the 5-stage pipeline, instruction $i$ is in MEM in the same cycle that instruction $i + 3$ is in IF. With one memory port, the two accesses conflict whenever instruction $i$ is a load or a store.

Standard fixes for structural hazards

Duplicate the resource. For example, separate instruction and data memories (or caches) mean that IF and MEM never contend.
Add ports to the register file so that one write (from WB) and two reads (from ID) can happen in the same cycle.
Pipeline or replicate a functional unit that would otherwise stay busy for several cycles, e.g. use a pipelined multiplier.
Otherwise, stall (insert a bubble) until the resource is free. This always increases CPI.

EXAM TIP

Suppose a question states that one memory port serves both instruction fetch and data access. Then count one stall for every cycle in which a load or store is in MEM while a fetch is also due, unless the question gives a different stall rule.

Data Hazards and Forwarding

A data hazard exists when an instruction depends on a register value that an earlier instruction still in the pipeline has not yet written. In the classic 5-stage in-order pipeline, every instruction reads its registers in ID and writes them only in WB, in program order. As a result, only RAW (Read-After-Write) hazards can occur there. WAR and WAW hazards arise only when a later instruction can write a register before an earlier one has read or written it. That happens with out-of-order execution, or with functional units of different latencies that let instructions complete out of order.

Hazard definitions (instruction i precedes instruction j in program order)

RAW (true dependence): j reads a register that i writes, and the read must see i's result. This is the only type possible in the classic 5-stage in-order pipeline.
WAR (anti-dependence): j writes a register that i reads. It is a hazard only if j's write could happen before i's read.
WAW (output dependence): i and j write the same register. It is a hazard only if the writes could complete out of order.

RAW STALLS WITHOUT FORWARDING (5-STAGE, SPLIT-CYCLE REGISTER FILE)

stalls = max (0, 3 - d)

$d$ is the distance in program order: $d = 1$ for the very next instruction. This assumes the register file is written in the first half of WB and read in the second half of ID, so a read in the same cycle as the write sees the new value. The consumer's ID must then fall no earlier than the producer's WB, so $d \geq 3$ needs no stall. If the register file is not split-cycle (the read must come in a cycle after the write), the result becomes $max (0, 4 - d)$ .

Forwarding (bypassing) sends a result straight from a pipeline register to the ALU inputs of a later instruction, instead of waiting for it to reach the register file. Full forwarding uses the EX/MEM -> EX path and the MEM/WB -> EX path. It removes every RAW stall whose producer is an ALU instruction: the result exists at the end of the producer's EX, which is exactly when the next instruction needs it at the start of its own EX. A load's result exists only at the end of MEM, one cycle later. The instruction right after a load cannot receive the result in time, so it must stall one cycle: this is the load-use hazard.

RAW stall cycles in the classic 5-stage pipeline (split-cycle register file)

Producer	Distance d	No forwarding	Full forwarding
ALU instruction	1	2	0
ALU instruction	2	1	0
ALU instruction	≥ 3	0	0
Load	1	2	1
Load	2	1	0
Load	≥ 3	0	0

WORKED EXAMPLE

Trace the following sequence on a 5-stage pipeline (IF, ID, EX, MEM, WB) with full forwarding (EX/MEM -> EX and MEM/WB -> EX). How many stall cycles are needed, and why?

ADD R1, R2, R3
SUB R4, R1, R5
LW  R6, 0(R1)
ADD R7, R6, R1

Solution

Timing with no stalls: ADD: IF 1, ID 2, EX 3, MEM 4, WB 5. SUB: EX in cycle 4. LW: EX in cycle 5. Second ADD: EX in cycle 6.
ADD -> SUB (R1, d = 1): SUB needs R1 at the start of cycle 4, and ADD produced it at the end of cycle 3. The EX/MEM -> EX path supplies it, so 0 stalls.
ADD -> LW (R1, d = 2): LW needs R1 to compute its address at the start of its EX in cycle 5. ADD is in WB then, so the MEM/WB -> EX path supplies it: 0 stalls.
LW -> ADD (R6, d = 1): R6 exists only at the end of LW's MEM, in cycle 6. The second ADD would need it at the start of its EX, also in cycle 6, which is one cycle too early. This is a load-use hazard.
The second ADD therefore stalls 1 cycle and executes in cycle 7, receiving R6 through the MEM/WB -> EX path. Its other operand, R1, was written by the first ADD in cycle 5, so it is read from the register file.
Total stalls = 1.

Answer: 1 stall cycle, caused by the load-use hazard between LW and the ADD that follows it.

EXAM TIP

In the classic 5-stage pipeline with full forwarding, an instruction that uses a loaded register immediately after the load needs exactly 1 stall. If one independent instruction separates them, no stall is needed. The compiler can often reorder code to put one there.

Control Hazards, Branch Penalty and Delayed Branching

A control hazard arises because the pipeline keeps fetching instructions before it knows a branch's outcome (taken or not taken) or its target address. Instructions fetched down the wrong path must be squashed (flushed). The number of cycles lost depends on the stage at which the branch is resolved.

BRANCH PENALTY (PER TAKEN OR MISPREDICTED BRANCH)

Penalty = s_{resolve} - 1

$s_{resolve}$ is the number of the stage at whose end both the outcome and the target are known. The correct instruction is fetched in the next cycle. No delay slot or prediction is assumed. For example, resolving at the end of EX (stage 3) squashes the 2 instructions in IF and ID, a penalty of 2 cycles; resolving at the end of ID gives 1.

AVERAGE CPI CONTRIBUTION FROM BRANCHES

Δ CPI = p_{branch} \times p_{penalised} \times Penalty

$p_{branch}$ is the fraction of all instructions that are branches. $p_{penalised}$ is the fraction of those branches that pay the penalty: under predict-not-taken, the taken fraction; under a predictor, the mispredicted fraction. If the pipeline stalls on every branch regardless of outcome, $p_{penalised} = 1$ .

Techniques to reduce the control-hazard penalty

Stall until resolved: freeze fetch after every branch until its outcome and target are known. This is simple, but every branch pays the full penalty.
Predict not-taken: keep fetching sequentially, and pay the penalty only when the branch is taken.
Predict taken: fetch from the branch target. This needs the target address early, e.g. from a branch target buffer; otherwise the pipeline must wait for the target anyway. The penalty is paid when the branch turns out not taken.
Delayed branch: the instruction(s) in the delay slot(s) after the branch always execute, whatever the outcome. The compiler fills each slot with an instruction that is useful or harmless on both paths, hiding part or all of the penalty without prediction hardware. A slot the compiler cannot fill holds a NOP and saves nothing.
Dynamic branch prediction (e.g. a branch history table with a branch target buffer): predicts each branch's direction and target from its past behaviour. The penalty is paid only on a misprediction.

EXAM TIP

Check whether the branch penalty a question gives is a misprediction penalty or the resolve-stage penalty paid by every taken branch. Then multiply it by the matching fraction in the CPI formula.

Pipeline Timing Diagrams

A timing (space-time) diagram lists the instructions down the rows and the clock cycles across the columns, showing which stage each instruction occupies in each cycle. A stall appears as a stage held for an extra cycle. Every later stage of that instruction, and every instruction behind it, shifts one cycle to the right.

WORKED EXAMPLE

Draw the timing diagram for the sequence below on a 5-stage (IF, ID, EX, MEM, WB) pipeline with full forwarding. A load-use hazard costs 1 stall cycle, and there are no other hazards. Find (a) the total number of cycles to complete the three instructions, and (b) the CPI excluding pipeline fill, $1 + stalls / n$ .

LW  R1, 0(R2)
ADD R3, R1, R4
SUB R5, R6, R7

Solution

LW: IF 1, ID 2, EX 3, MEM 4, WB 5. R1 is available at the end of cycle 4.
ADD uses R1 immediately after the load, which is a load-use hazard. ADD: IF 2, ID 3, held in ID in cycle 4 (stall), EX 5 (R1 forwarded from MEM/WB), MEM 6, WB 7.
SUB is independent, but it is stuck behind ADD: IF 3, held in IF in cycle 4 because ID is occupied, ID 5, EX 6, MEM 7, WB 8.
In the table below, '*' marks a stage held for one extra cycle because of the stall.
(a) Total cycles = (k + n − 1) + stalls = (5 + 3 − 1) + 1 = 8.
(b) CPI excluding fill = 1 + 1/3 = 4/3 ≈ 1.33. Including fill cycles, cycles per instruction = 8/3 ≈ 2.67. For a long program in which this three-instruction pattern repeats, the average CPI tends to 4/3.

Answer: (a) 8 clock cycles. (b) CPI excluding fill = 4/3 ≈ 1.33. Including fill, 8/3 ≈ 2.67 cycles per instruction for this short sequence.

Timing diagram for the worked example ('*' = stage held because of the stall)

Instruction	1	2	3	4	5	6	7	8
LW R1,0(R2)	IF	ID	EX	MEM	WB
ADD R3,R1,R4		IF	ID	ID*	EX	MEM	WB
SUB R5,R6,R7			IF	IF*	ID	EX	MEM	WB

EXAM TIP

'Total cycles to run this exact sequence' includes the $k - 1$ fill cycles. 'Average CPI of a long program' does not. For small $n$ the two give very different numbers, so answer the one the question asks for.

PREVIOUS-YEAR QUESTIONS

12 questions from the CS papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE CSE 2026 Set 1 · GATE CSE 2026 Set 2 · GATE CSE 2025 Set 2 · GATE CSE 2024 Set 1 · GATE CSE 2024 Set 2 · GATE CSE 2023 · GATE CSE 2022 · GATE CSE 2020 · GATE CSE 2018

GATE 2026 CS1 Q.16

GATE 2026 · CS1Q.16 · 1 mark · MCQ

Which one of the following dependencies among the register operands of different instructions can cause a data hazard in a pipelined processor?

(A)
Read-after-read
(B)
Read-after-write
(C)
Write-after-read
(D)
Write-after-write

Answer and solution

GATE 2026 CS1 Q.16: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 CS1 Q.16: answer and solution

GATE 2026 CS1 Q.60

GATE 2026 · CS1Q.60 · 2 marks · NAT

The EX stage of a pipelined processor performs the memory read operations for LOAD instructions, and the operations for the arithmetic and logic instructions. Let $t_{E X}$ denote the time taken by the EX stage to perform the operation for an instruction. For each instruction type, the values of $t_{E X}$ and $M$ (the number of instructions of that type in a sequence of 100 instructions for a program P), are given in the table below.

The duration of the pipeline clock cycle is 1 nanosecond. Assume that the latch time for the interstage buffers in the pipeline is negligible.

| Instruction | $t_{E X}$ in nanoseconds | $M$ |
|---|---|---|
| LOAD | 1.8 | 15 |
| IMUL | 1.5 | 10 |
| IDIV | 2.5 | 5 |
| FADD | 1.7 | 10 |
| FSUB | 1.7 | 5 |
| FMUL | 2.8 | 15 |
| FDIV | 3.2 | 5 |
| All other instructions | Less than 1.0 | 35 |

When program P is executed, the number of clock cycles for which the pipeline is stalled due to structural hazards in the EX stage is ______. (answer in integer)

GATE 2026 CS1 question 60: A table with columns Instruction, t_EX in nanoseconds, M (count out of 100). — Figure from the GATE 2026 CS1 paper. It is part of the question.

Answer and solution

GATE 2026 CS1 Q.60: answer and solution

GATE 2026 CS2 Q.57

GATE 2026 · CS2Q.57 · 2 marks · NAT

A non-pipelined instruction execution unit that operates at 1.6 GHz clock takes an average of 5 clock cycles to complete the execution of an instruction. To improve the performance, the system was pipelined with a goal of achieving an average throughput of one instruction per clock cycle. However, it could operate only at 1.2 GHz due to pipeline overheads. While executing a program in the pipelined design, 30% of instructions encountered a stall of 2 cycles due to pipeline hazards. The speed-up obtained by the pipelined design over the non-pipelined one for this program is ____________. (rounded off to two decimal places)

Note: 1G= $1 0^{9}$

Answer and solution

GATE 2026 CS2 Q.57: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 CS2 Q.57: answer and solution

GATE 2025 CS2 Q.56

GATE 2025 · CS2Q.56 · 2 marks · NAT

A 5-stage instruction pipeline has stage delays of 180, 250, 150, 170, and 250, respectively, in nanoseconds. The delay of an inter-stage latch is 10 nanoseconds. Assume that there are no pipeline stalls due to branches and other hazards. The time taken to process 1000 instructions in microseconds is __________ . (rounded off to two decimal places)

Answer and solution

GATE 2025 CS2 Q.56: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 CS2 Q.56: answer and solution

GATE 2025 CS2 Q.61

GATE 2025 · CS2Q.61 · 2 marks · NAT

An application executes $6.4 \times 1 0^{8}$ number of instructions in 6.3 seconds. There are four types of instructions, the details of which are given in the table. The duration of a clock cycle in nanoseconds is __________. (rounded off to one decimal place)

| Instruction type | Clock cycles required per instruction (CPI) | Number of instructions executed |
|---|---|---|
| Branch | 2 | $2.25 \times 1 0^{8}$ |
| Load | 5 | $1.20 \times 1 0^{8}$ |
| Store | 4 | $1.65 \times 1 0^{8}$ |
| Arithmetic | 3 | $1.30 \times 1 0^{8}$ |

GATE 2025 CS2 question 61: A 4-row × 3-column table. — Figure from the GATE 2025 CS2 paper. It is part of the question.

Answer and solution

GATE 2025 CS2 Q.61: answer and solution

GATE 2024 CS1 Q.30

GATE 2024 · CS1Q.30 · 1 mark · MSQ

Consider a 5-stage pipelined processor with Instruction Fetch (IF), Instruction Decode (ID), Execute (EX), Memory Access (MEM), and Register Writeback (WB) stages. Which of the following statements about forwarding is/are CORRECT?

(A)
In a pipelined execution, forwarding means the result from a source stage of an earlier instruction is passed on to the destination stage of a later instruction
(B)
In forwarding, data from the output of the MEM stage can be passed on to the input of the EX stage of the next instruction
(C)
Forwarding cannot prevent all pipeline stalls
(D)
Forwarding does not require any extra hardware to retrieve the data from the pipeline stages

Answer and solution

GATE 2024 CS1 Q.30: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 CS1 Q.30: answer and solution

GATE 2024 CS2 Q.31

GATE 2024 · CS2Q.31 · 1 mark · MSQ

An instruction format has the following structure:

Instruction Number: Opcode destination reg, source reg-1, source reg-2

Consider the following sequence of instructions to be executed in a pipelined processor:

I1: DIV R3, R1, R2
I2: SUB R5, R3, R4
I3: ADD R3, R5, R6
I4: MUL R7, R3, R8

Which of the following statements is/are TRUE?

(A)
There is a RAW dependency on R3 between I1 and I2
(B)
There is a WAR dependency on R3 between I1 and I3
(C)
There is a RAW dependency on R3 between I2 and I3
(D)
There is a WAW dependency on R3 between I3 and I4

Answer and solution

GATE 2024 CS2 Q.31: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 CS2 Q.31: answer and solution

GATE 2024 CS2 Q.58

GATE 2024 · CS2Q.58 · 2 marks · NAT

A non-pipelined instruction execution unit operating at 2 GHz takes an average of 6 cycles to execute an instruction of a program P. The unit is then redesigned to operate on a 5-stage pipeline at 2 GHz. Assume that the ideal throughput of the pipelined unit is 1 instruction per cycle. In the execution of program P, 20% instructions incur an average of 2 cycles stall due to data hazards and 20% instructions incur an average of 3 cycles stall due to control hazards. The speedup (rounded off to one decimal place) obtained by the pipelined design over the non-pipelined design is ____________

Answer and solution

GATE 2024 CS2 Q.58: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 CS2 Q.58: answer and solution

GATE 2023 CS Q.33

GATE 2023 · CSQ.33 · 1 mark · NAT

Consider a 3-stage pipelined processor having a delay of 10 ns (nanoseconds), 20 ns, and 14 ns, for the first, second, and the third stages, respectively. Assume that there is no other delay and the processor does not suffer from any pipeline hazards. Also assume that one instruction is fetched every cycle.

The total execution time for executing 100 instructions on this processor is ______ ns.

Answer and solution

GATE 2023 CS Q.33: answer and solution

See the question in the paper

Tap to open full size

GATE 2023 CS Q.33: answer and solution

GATE 2022 CS Q.61

GATE 2022 · CSQ.61 · 2 marks · NAT

A processor X₁ operating at 2 GHz has a standard 5-stage RISC instruction pipeline having a base CPI (cycles per instruction) of one without any pipeline hazards. For a given program P that has 30% branch instructions, control hazards incur 2 cycles stall for every branch. A new version of the processor X₂ operating at same clock frequency has an additional branch predictor unit (BPU) that completely eliminates stalls for correctly predicted branches. There is neither any savings nor any additional stalls for wrong predictions. There are no structural hazards and data hazards for X₁ and X₂. If the BPU has a prediction accuracy of 80%, the speed up (rounded off to two decimal places) obtained by X₂ over X₁ in executing P is ____.

Answer and solution

GATE 2022 CS Q.61: answer and solution

See the question in the paper

Tap to open full size

GATE 2022 CS Q.61: answer and solution

GATE 2020 CS Q.43

GATE 2020 · CSQ.43 · 2 marks · NAT

Consider a non-pipelined processor operating at 2.5 GHz. It takes 5 clock cycles to complete an instruction. You are going to make a 5-stage pipeline out of this processor. Overheads associated with pipelining force you to operate the pipelined processor at 2 GHz. In a given program, assume that 30% are memory instructions, 60% are ALU instructions and the rest are branch instructions. 5% of the memory instructions cause stalls of 50 clock cycles each due to cache misses and 50% of the branch instructions cause stalls of 2 cycles each. Assume that there are no stalls associated with the execution of ALU instructions. For this program, the speedup achieved by the pipelined processor over the non-pipelined processor (round off to 2 decimal places) is ____.

Answer and solution

GATE 2020 CS Q.43: answer and solution

See the question in the paper

Tap to open full size

GATE 2020 CS Q.43: answer and solution

GATE 2018 CS Q.50

GATE 2018 · CSQ.50 · 2 marks · NAT

The instruction pipeline of a RISC processor has the following stages: Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Perform Operation (PO) and Writeback (WB). The IF, ID, OF and WB stages take 1 clock cycle each for every instruction. Consider a sequence of 100 instructions. In the PO stage, 40 instructions take 3 clock cycles each, 35 instructions take 2 clock cycles each, and the remaining 25 instructions take 1 clock cycle each. Assume that there are no data hazards and no control hazards.

The number of clock cycles required for completion of execution of the sequence of instructions is ______.

Answer and solution

GATE 2018 CS Q.50: answer and solution

See the question in the paper

Tap to open full size

GATE 2018 CS Q.50: answer and solution

PRACTICE

5 questions to test yourself

PRACTICE 12 marks · NAT

A 5-stage instruction pipeline (IF, ID, EX, MEM, WB) has stage delays of 200 ps, 150 ps, 120 ps, 180 ps and 100 ps respectively. Inter-stage latch delay is negligible. A non-pipelined implementation of the same processor takes, for each instruction, the sum of all five stage delays, executed one after another. What is the speed-up of the pipelined processor over the non-pipelined one for a program of 100 instructions (no stalls, no hazards)? (Give the answer correct to two decimal places.)

Answer and solution

Answer: $3.61$ (accepted range $\pm 0.05$ )

Pipeline clock period = max(stage delays) = max(200, 150, 120, 180, 100) = 200 ps.
Non-pipelined time per instruction = sum of the stage delays = 200 + 150 + 120 + 180 + 100 = 750 ps.
Non-pipelined total time for n = 100 instructions = 100 × 750 = 75000 ps.
Pipelined total time = (k + n − 1) × T_p = (5 + 100 − 1) × 200 = 104 × 200 = 20800 ps.
Speed-up = 75000 / 20800 ≈ 3.606 ≈ 3.61.

PRACTICE 21 mark · MCQ

A processor has only one functional unit of a certain kind, such as one memory port. Two instructions in a pipelined processor try to use that unit in the same clock cycle. What kind of hazard is this?

(A)
Data hazard
(B)
Structural hazard
(C)
Control hazard
(D)
WAW hazard

Answer and solution

Answer: (B)

A structural hazard occurs when two instructions in different pipeline stages need the same hardware resource in the same cycle.
A data hazard, by contrast, is a dependence on a value, and a control hazard is a dependence on a branch outcome.
So this is a structural hazard.

PRACTICE 32 marks · MSQ

Consider a classic in-order 5-stage pipeline (IF, ID, EX, MEM, WB) with no forwarding. Registers are written in the first half of WB and read in the second half of ID, so a read in the same cycle as the matching write sees the new value. Each sequence below is issued back to back, with no stalls inserted yet. Select the sequence(s) that need at least one stall cycle to avoid reading a stale operand.

(A)
ADD R1, R2, R3 ; SUB R4, R1, R5
(B)
ADD R1, R2, R3 ; MUL R6, R7, R8 ; SUB R4, R1, R5
(C)
ADD R1, R2, R3 ; MUL R6, R7, R8 ; DIV R9, R10, R11 ; SUB R4, R1, R5
(D)
ADD R1, R2, R3 ; SUB R4, R5, R6

Answer and solution

Answer: (A), (B)

With back-to-back issue, the j-th instruction in program order has its ID in cycle j + 1 and its WB in cycle j + 4. ADD is always the 1st instruction, so it writes R1 in WB in cycle 5.
Option A: SUB is the 2nd instruction, so it reads R1 in ID in cycle 3. That is before ADD's write in cycle 5, so a stall is needed.
Option B: SUB is the 3rd instruction, so its ID is in cycle 4, still before cycle 5. A stall is needed.
Option C: SUB is the 4th instruction, so its ID is in cycle 5, the same cycle as ADD's WB. Because the write happens in the first half of the cycle and the read in the second, no stall is needed.
Option D: SUB reads R5 and R6, which ADD does not write. There is no dependence, so no stall.
Only A and B need a stall.

PRACTICE 41 mark · MCQ

With delayed branching, the instruction placed in the branch delay slot is one that

(A)
always executes, whatever the branch outcome, and is chosen to be safe or useful on both outcomes
(B)
never executes and is only a placeholder (a NOP)
(C)
executes only if the branch is taken
(D)
executes only if the branch is not taken

Answer and solution

Answer: (A)

The hardware always executes the delay-slot instruction, whether the branch is taken or not.
So the compiler fills the slot with an instruction that is useful, or at least harmless, on both outcomes. For example, it can move up an instruction from before the branch that the branch condition does not depend on. If no such instruction exists, it uses a NOP.
The defining property is unconditional execution.

PRACTICE 52 marks · NAT

A 5-stage pipelined processor resolves conditional branches at the end of the EX stage. A taken branch squashes the 2 instructions already fetched after it (in IF and ID), a penalty of 2 stall cycles; a not-taken branch causes no stall. A program of 200 instructions has 20% conditional branches, and 60% of those are taken. There are no other hazards or stalls. Ignoring the cycles needed to fill and drain the pipeline, what is the average CPI of this program? (Give the answer correct to two decimal places.)

Answer and solution

Answer: $1.24$ (accepted range $\pm 0.02$ )

Base CPI with no stalls = 1.
Taken branches = 200 × 0.20 × 0.60 = 24, which is 0.12 of all instructions.
Stall cycles = 24 × 2 = 48, i.e. 0.12 × 2 = 0.24 stall cycles per instruction.
Average CPI = 1 + 0.24 = 1.24.

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE CS

Instruction pipelining, pipeline hazards

Preparing in Kolkata? IAE Academy's course for GATE CSE.