GATE CS 2021 Set 2 — Question 63
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.NAT+2 / -0HardData ForwardingInstruction PipeliningComputer Organization & ArchitectureSpeedup & EfficiencyData Hazards (RAW, WAR, WAW)
Computer Organization & Architecture → Instruction Pipelining → Data Forwarding
Last updated
Question
Consider a pipelined processor with 5 stages, Instruction Fetch (IF), Instruction Decode (ID), Execute (EX), Memory Access (MEM), and Write Back (WB). Each stage of the pipeline, except the EX stage, takes one cycle. Assume that the ID stage merely decodes the instruction and the register read is performed in the EX stage. The EX stage takes one cycle for ADD instruction and two cycles for MUL instruction. Ignore pipeline register latencies.
Consider the following sequence of 8 instructions:Assume that every MUL instruction is data-dependent on the ADD instruction just before it and every ADD instruction (except the first ADD) is data-dependent on the MUL instruction just before it. The Speedup is defined as follows:The Speedup achieved in executing the given instruction sequence on the pipelined processor (rounded to 2 decimal places) is _______.
Consider the following sequence of 8 instructions:Assume that every MUL instruction is data-dependent on the ADD instruction just before it and every ADD instruction (except the first ADD) is data-dependent on the MUL instruction just before it. The Speedup is defined as follows:The Speedup achieved in executing the given instruction sequence on the pipelined processor (rounded to 2 decimal places) is _______.
Correct answer
1.87 to 1.88
Solution
Let the sequence of instructions be (ADD), (MUL), (ADD), (MUL), (ADD), (MUL), (ADD), (MUL).Case 1: Without Operand Forwarding
In this case, a dependent instruction must wait for the producer to write back (WB) the result to the register file before it can read the operands. The problem states that register read is performed in the EX stage. Thus, the EX stage of the consumer can only start after the WB stage of the producer is completed.
With forwarding, the result is available at the end of the EX stage of the producer and can be forwarded to the start of the EX stage of the consumer. Thus, the consumer's EX stage can start immediately after the producer's EX stage finishes.
Total execution time with forwarding = 16 cycles.Speedup CalculationRounded to 2 decimal places, the speedup is 1.88.
In this case, a dependent instruction must wait for the producer to write back (WB) the result to the register file before it can read the operands. The problem states that register read is performed in the EX stage. Thus, the EX stage of the consumer can only start after the WB stage of the producer is completed.
- (ADD): 1 cycle EX. Pipeline: IF, ID, EX, MEM, WB. Completes WB at cycle 5.
- (MUL): Depends on . Can start EX at cycle . EX takes 2 cycles (6, 7). MEM 8, WB 9.
- (ADD): Depends on . Can start EX at cycle . EX takes 1 cycle (10). MEM 11, WB 12.
- (MUL): Depends on . Can start EX at cycle . EX takes 2 cycles (13, 14). MEM 15, WB 16.
- (ADD): Depends on . Can start EX at cycle . EX takes 1 cycle (17). MEM 18, WB 19.
- (MUL): Depends on . Can start EX at cycle . EX takes 2 cycles (20, 21). MEM 22, WB 23.
- (ADD): Depends on . Can start EX at cycle . EX takes 1 cycle (24). MEM 25, WB 26.
- (MUL): Depends on . Can start EX at cycle . EX takes 2 cycles (27, 28). MEM 29, WB 30.
With forwarding, the result is available at the end of the EX stage of the producer and can be forwarded to the start of the EX stage of the consumer. Thus, the consumer's EX stage can start immediately after the producer's EX stage finishes.
- (ADD): EX finishes at cycle 3.
- (MUL): EX starts at 4. Duration 2. Finishes at 5.
- (ADD): EX starts at 6. Duration 1. Finishes at 6.
- (MUL): EX starts at 7. Duration 2. Finishes at 8.
- (ADD): EX starts at 9. Duration 1. Finishes at 9.
- (MUL): EX starts at 10. Duration 2. Finishes at 11.
- (ADD): EX starts at 12. Duration 1. Finishes at 12.
- (MUL): EX starts at 13. Duration 2. Finishes at 14.
Total execution time with forwarding = 16 cycles.Speedup CalculationRounded to 2 decimal places, the speedup is 1.88.
Continue learning with Success Tracker
A step still unclear? Work through it with support
Use Success Tracker to ask about the reasoning, then try another GATE CS question to check your understanding.
AI-powered practice· Unlimited practice on eligible plans
- PYQs with solutions
- Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
- Practice that adapts
- Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
- AI doubt support
- Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.
Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.
This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.
More questions on Instruction Pipelining
2026 Set 1 Q14Match each addressing mode in List I with a data element or an element of a data structure (in…2026 Set 1 Q15Consider a processor P whose instruction set architecture is the load-store architecture. The…2026 Set 1 Q16Which one of the following dependencies among the register operands of different instructions can…2026 Set 2 Q18Consider the following two statements about interrupt handling mechanisms in a CPU. S1: In…2026 Set 1 Q38The size of the physical address space of a processor is bytes. The capacity of a cache…