Question
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 ______.
Official answer and solution
- Official answer
- 219
- From
- Official GATE 2018 answer key
Solution
Sum the execution times in the multi-cycle bottleneck stage and account for initial fill and final drain cycles.
The pipeline has 5 stages: IF, ID, OF, PO, WB. All stages except PO take 1 clock cycle for every instruction.
Because PO takes 1, 2, or 3 cycles, it serves as the bottleneck stage. An instruction cannot enter PO until the previous instruction vacates PO. Thus, PO operates non-pipelined across instructions, executing sequentially:
Trace pipeline startup and completion:
- Instruction 1 requires 3 cycles (IF, ID, OF) before it begins execution in PO.
- The PO stage executes all 100 instructions consecutively for 215 cycles.
- After Instruction 100 finishes PO, it requires 1 cycle (WB) to complete writeback.
Total clock cycles required:
219
The answer is the one in the official GATE answer key. The solution is this site's own explanation.
Source
- Paper
- GATE 2018 Computer Science and Information Technology (CS)
- Question
- 60 of 65, printed as CS Q.50
- Section
- Computer Science and Information Technology
Report an error in this question
GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.