0
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Feb 26, 2014 at 6:23

3 Answers 3

Reset to default
3
+50
$\begingroup$

enter image description here

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ do you have any source for this method? any links. $\endgroup$
    – harish.venkat
    Feb 25, 2014 at 8:17
  • $\begingroup$ 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) $\endgroup$
    – Gaurav
    Feb 25, 2014 at 8:59
  • $\begingroup$ 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. $\endgroup$
    – KGhatak
    Jun 14, 2019 at 19:52
  • $\begingroup$ How do you know if cpu cycle time is 1ns? $\endgroup$
    – Darshan
    Dec 23, 2019 at 6:58
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – vignesh
    Feb 24, 2014 at 1:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.