Pipelining GATE Questions and Pipelining Problems with Solution

Pipelining questions are generally asked in GATE exam every year. Today in this tutorial we will discuss Pipelining Problems with solutions in detail.

Some Pipelining GATE questions are discussed here. Students are suggested to practice these pipelining problems with their solution.

Pipelining Gate Questions with Solutions

Some pipelining gate questions with solution are explained here

Q1. There is an instruction pipeline with four stages. The stage delays for each stage is 5 nsec, 6 nsec, 11 nsec, and 8 nsec respectively. Consider the delay of an inter-stage

register in the  pipeline is 1 nsec. Find the approximate speedup of the pipeline in the steady state under ideal conditions as compare to to the corresponding non-pipelined implementation?

(a) 4.0

(b) 2.5

(c) 1.1

(d) 3.0

Answer : Correct option is (b).

Explanation-

When N instruction will be execute in non pipeline manner the time taken will be equal be (5 + 6 + 11 + 8) * N = 30N

Now we will calculate the clock period for pipelined implementation and it will be equal to  max{5,6,11,8} + 1 = 12.

Time taken in execution of N instruction through pipelined will be equal to  12N (approx.)

So Speedup = 30N / 12N = 2.5

Q2. An instruction in pipeline has five stages without any branch prediction and these stages are  Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Execute (EX) and Operand Write (OW). The stage delays for IF, ID, OF, EX and OW phases are 5 nsec, 7 nsec, 10 nsec, 8 nsec and 6 nsec, respectively.

There are intermediate storage buffers after each stage and the delay of each buffer is 1 nsec. A program consisting of 12 instructions I1, I2, …, I12 is executed in the pipelined processor. Instruction I4 is the only branch instruction and its branch target is I9. If the branch is taken during the execution of this program, the time needed to complete the program is:

(a) 132 nsec

(b) 154nsec

(c) 176 nsec

(d) 328 nsec

Answer: Option  (b) is correct.

Explanation

Minimum clock period = max{5,7,10,8,6} + 1 = 11

I1: IF ID EX ME WB

I2:    IF ID EX ME WB

I3:       IF ID EX ME WB

I4:          IF ID EX ME WB

I5:             . . . . .

I6:                . . . . .

I7:                 . . . . .

I8:          . . . . .

I9:                   IF ID EX ME WB

I10:                     IF ID EX ME WB

I11:                        IF ID EX ME WB

I12:                           IF ID EX ME WB

Total 14 clock cycles are needed, i.e. 14 x 11 = 154 nsec.

Q3.A RISC machine where length of each instruction is 4 bytes. Conditional and unconditional branch instructions are also used on that machine and these instructions use PC-relative addressing mode with Offset specified in bytes to the target location of the branch instruction.

It is important to note that the Offset is always with respect to the address of the next instruction in the program sequence.

Consider the following program consisting of 4 instructions

Instruction i: ADD R2,R3,R4

Instruction i+1: SUB R5,R6,R7

Instruction i+2: SEQ R1,R9,R10

Instruction i+3: BEQZ R1,Offset

Now If the target of the branch instruction is i, then what will be the decimal value of Offset will be

Answer  is -16.

Explanation-

First we assume that instruction “i” starts from memory at address X.

Then Address of instruction i+1 will be X + 4

Address of instruction i+2 will be X + 8

Address of instruction i+3 will be X + 12

Address of instruction i+4 will be X + 16

So, In this way Offset = X – (X + 16) = -16

Q4. There is a 5 stage processor having the stages Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Execute (EX) and Write Operand (WO).

If the phases IF, ID, OF, and WO stages take 1 clock cycle.

The EX stage takes 1 clock cycle for ADD and SUB instructions, 3 clock cycles for MUL instruction, and 6 clock cycles for DIV instruction. Operand forwarding is used in the pipeline (for data dependency, OF stage of the dependent instruction can be executed only.

Instruction           Meaning of instruction

I0 : MUL R2 ,R0 ,R1          R2 ¬ R0 *R1

I1 : DIV R5 ,R3 ,R4            R5 ¬ R3/R4

I2 : ADD R2 ,R5 ,R2          R2 ¬ R5+R2

I3 : SUB R5 ,R2 ,R6          R5 ¬ R2-R6

(A) 13

(B) 15

(C) 17

(D) 19

Answer: B

Explanation

MUL R2,R10,R1: IF ID OF EX EXEX WO

DIV R5,R3,R4: IF ID OF EX EXEXEXEXEX WO

ADD R2,R5,R2: IF ID – – – – – – OF EX WO

SUB R5,R2,R6: IF – – – – – – ID – OF EX WO

Number of clock cycles = 15.

Q5.Consider an instruction pipeline for the MIPS32 processor where data references constitute 42% of the instructions, and the ideal CPI ignoring memory structural hazards is 1.25. How much faster is the ideal machine without the memory structural hazard versus the machine with the hazard?

(a) 1.34

(b) 1.26

(c) 1.38

(d) None of the above

Answer : Correct option is (a).

From Speed Up Formula we know that

Speedup = (Ideal CPI x Pipeline Depth) / (Ideal CPI + Stall cycles per instruction)

So, Speedupideal= 1.25 x Depth / (1.25 + 0) = Depth

And, Speedupreal= 1.25 x Depth / (1.25 + 0.42 x 1) = 1.25 x Depth / 1.67

Hence answer = 1.67 / 1.25 = 1.34 (approx.)

Q6. Which among the following measures are considered to minimize the impact of Data Hazards in a MIPS32 Pipeline?

(a) Splitting the memory into separate Instruction and Data memories.

(b) Implement data forwarding in the datapath.

(c) Allow split register write and read during the two halves of the same clock cycle.

(d) Replicate the register bank.

Answers are (b) and (c).

Option (a) reduces the impact of structural hazard. Option (d) will also not help in mitigating data hazards. Data forwarding and split register access can reduce the number of stall

Cycles.

Q7. In the MIPS32 pipeline, which of the following scenarios of data dependency will always result in a pipeline stall due to data hazard without any instruction scheduling?

(a) An ADD instruction followed by a SUB instruction.

(b) A STORE instruction followed by a LOAD instruction

(c) A LOAD instruction followed by an ADD instruction.

(d) None of the above.

Answer is (c).

Only a LOAD followed by an immediate use will result in a mandatory stall

in the pipeline.

Q8.Which among the following is used by Instruction scheduling can be used to eliminate data and control hazard ?

(a) Schedule the execution of the instruction only if there is no hazard.

(b) Allowing the compiler the move instructions around to fill the LOAD/BRANCH delay slot(s) with meaningful instructions.

(c) Using a special hardware to check for hazard and issue instructions only when possible.

(d) None of the above.

Correct answer is (b).

Explanation

In Instruction scheduling instructions are moved  as per dependencies to minimize the cycles because of stalls. Instruction scheduling is a compiler technique.

Conclusion and Summary

In this tutorial we have explained the pipelining gate questions and pipelining problems with solution. I hope that these questions will be helpful for gate aspirants.

If you have any query then you can ask in comment section.