An ideal pipeline will run a sequence of instructions with no delay. As usual, s

Question

An ideal pipeline will run a sequence of instructions with no delay. As usual, suppose that each stage takes one clock cycle. That is, given instructions I1, · · · , Ik running in this ordering, in the first clock cycle, I1 is in the first stage of the pipeline, in the second clock cycle, I1 is in the second stage of the pipeline and I2 is in the first stage of the pipeline, etc. Let Nk be the number of cycles needed till the last instruction Ik moving out of the pipeline. Prove that limk Nk/k = 1.

Explanation / Answer

We know that total number of clocks requried for a pipeline having x stages and

k instructions is x+k-1.

Given Number of instructions is = k.

         Number of stages is not given let assume it as x.

         Number of clocks required is = Nk

So here Nk = x+k-1.

Now limk Nk/k    = limk (x+k-1) / k

                            = limk x/k + k/k -1/k

                            = limk x/k + 1 -1/k

      Here as k x/k and 1/k will be 0 ( as 1/ = 0 )

                           = 0 + 1 - 0

                           = 1

Hence limk Nk/k = 1.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.