GATE CSE 2009 | Question: 28

Question

Consider a $4$ stage pipeline processor. The number of cycles needed by the four instructions $I1, I2, I3, I4$ in stages $S1, S2, S3, S4$ is shown below:

$$\begin{array}{|c|c|c|c|c|} \hline \textbf{} & \textbf {S1} &\textbf {S2} & \textbf {S3} &  \textbf{S4 } \\\hline \textbf{I1}& 2 & 1  & 1 & 1 \\\hline \textbf{I2} & 1 & 3 & 2  & 2\\\hline  \textbf{I3}& 2 & 1  & 1 & 3 \\\hline \textbf{I4} & 1 & 2 & 2  & 2 \\\hline  \end{array}$$

 

What is the number of cycles needed to execute the following loop?

For (i=1 to 2) {I1; I2; I3; I4;}

• A. $16$
• B. $23$
• C. $28$
• D. $30$

Comments

nice explanation @rish-18

---

	S1	S2	S3	S4
I1	2	3	4	5
I2	2 + 1= 3	max(3,3)+3 = 6	max(4,6)+2 = 8	max(5,8) + 2 = 10
I3	3+ 2 = 5	max(5,6)+1 = 7	max(7,8)+1 = 9	max(9,10)+3 = 13
I4	5+1 = 6	max(6,7)+2 = 9	11	max(11,13)+2 = 15

 

for 2 iteration

I1	6+2 = 8	max ( 8,9) +1 = 10	max(10,11)+1 = 12	max(12,15)+1 = 16
I2	8 + 1= 9	max(9,10)+3 = 13	max(12,13)+2 = 15	max(15,16) + 2 = 18
I3	9+ 2 = 11	max(11,13)+1 = 14	max(14,15)+1 = 16	max(16,18)+3 = 21
I4	11+1 = 12	max(12,14)+2 = 16	18	max(18,21)+2 = 23

 

In every row (except first ) the logic will be check  for diagonal entries , find out which is maximum and add time

so ans is 23.

---

In case it helps anybody, consider the following analogy –

Imagine you were going to a polling station to cast your vote. Inside the polling station, one person is assigned the job of checking your voter ID card, and registering your name. Probably, on the adjacent bench, a person puts the ink-mark on your index finger. There might be many more such people in charge (each doing a certain work), before you ultimately stand before the EVM to cast your vote. All these people (and the EVM) can be considered as stages of a (voting) pipeline.

Now, let say you were to go to the polling station at 3pm in a Sunday afternoon. Chances are you would encounter a sea of people there. Now, imagine what would happen if the people in charge refused any queues inside the polling station. In that case, there would a treacherously long queue of agitated people waiting outside the entry gate. Instead, if the people in charge did allow queues inside the polling station, then the queue outside it would be shorter, and people would be less agitated seeing the crowd move more quickly (through the stages of the voting pipeline).

Drawing comparison from the above analogy, we can imagine what would happen when the stages of the hardware pipeline do not have buffers. The processes/instructions start getting blocked just to enter the pipeline! When multiple stall cycles from previous instructions are involved, the later instructions can’t even enter the pipeline! Given that pipelines are used by a large number of instructions of various kinds, and for a long period of time, such kind of instructions with multiple stall cycles are indeed quite frequently encountered. If this happens, then what remains of the benefits that a pipeline promises? To keep everything moving, a practical hardware pipeline must implement stage buffers. Yes, this does increases the delay in the system. Yes, processes/instructions can still get blocked before entering the pipeline. But, it’s still far better than the former case of not using stage buffers!

Answer 1

Got it in 1 go

Do upvote if you got anything

 

Answer 2

First find the max of diagonal elements and the add the clock cycle.