# Execution time of an uneven pipeline

I was trying to solve a question dealing with n instructions in an uneven pipeline with k stages. I came across a generic formula for even pipelines i.e. (k + n - 1) * clock cycle. But I feel this should not work for uneven pipelines as the above formula is based on fact that the 1st instruction takes time = sum(time of k stages) and the 2nd instruction onwards takes time = maximum of stage delays.

A example: A pipeline is designed with 5 stages having execution times respectively as 3ns, 4ns, 2ns and 4ns. How much time will it take to execute 1000 instructions?

• What have you done to try to answer your question on your own? Have you tried working some concrete examples by hand, for specific values of $k,n$? Have you tried contacting your instructor? We expect you to make a serious effort on your own before asking here, and to show us in the question what you've tried. – D.W. Feb 26 '14 at 6:23

The first instruction (I1) will pass through all the stages one by one without any stall and will take $3+4+2+4=13$ cycles.

The second instruction (I2) goes next and it begins at the end of cycle 3. As soon as it finishes the execution of S1, it is ready to go to next stage. But it is occupied by the previous instruction. Hence, I2 needs to stall for 1 cycle (as in yellow). After this stall, it need not to pause for any cycle and finishes at cycle 17.

The same pattern is followed by the coming instructions.

So, the first instruction finishes in 13 cycles. Each of the remaining $n-1$ instructions finishes after 4 cycles taking $(n-1)*4$ cycles.

You put $n=1000$ and the total number of cycles comes to be $13+999*4 =4009.$

Hope it helps.

• do you have any source for this method? any links. – harish.venkat Feb 25 '14 at 8:17
• No. It is just collection of experiences gained by solving such problems. But these type of problems are common in GATE. May be the NPTEL lecture videos can give an authenticated answer. (nptel.ac.in/courses/106102062/24) – Gaurav Feb 25 '14 at 8:59
• This is not correct. In an execution, the cycle duration is always fixed. So, for the 1st instruction, all stages must be of equal duration i.e. 4ns. – KGhatak Jun 14 at 19:52

This is a very basic concept of pipeline. There is no general formula for execution time of instructions in pipeline in real life because there might be dependencies (raw,war, waw ) or there might be branch instructions. Although the question you asked is pretty straight forward. The first instruction needs 13 cycles to complete then each of the rest takes max(3,4,2,4) = 4 cycles to complete. So the time needed is 13 + (1000-1)*4. Here you are assuming execution of same type of instructions 1000 times and without any data dependency or branch, this does not happen in real life. In real life to solve pipeline problems you have to draw the timing diagram, check for dependencies and branching and apply optimizations. So do not try to develop any formula just clear your concepts.

In case of uneven pipelines like you mentioned in the question, you take the execution time of the largest pipeline and treat the whole pipeline as an even pipeline with that execution time using the formula you mentioned in the question. See this pdf

• what you have mentioned is correct when pipeline is in stable state. but if i start from initial state and want to find time to execute some n instruction then the formula should not be correct.rather total time= time for 1st instruction to execute + n-1* largest stage delay.this is what i have understood. it is correct – vignesh Feb 24 '14 at 1:35