5) Suppose that a processor has a 20-stage pipeline execution unit running a pro

Question

5) Suppose that a processor has a 20-stage pipeline execution unit running a program with 100 executed instructions.

a) In an ideal situation, except for the initial pipeline start-up delay, every instruction can finish execution at the end of each cycle. Calculate the CPI for the program. (Hint: pipeline start-up needs to be considered.)

b) Assume that there are 7 branches and 5 loads among the 100 instructions. For 3 out of 7 branches, each encounters 2 stall cycles and each load causes 1 cycle stall. Calculate the new CPI.

Explanation / Answer

Let us understand pipeline and it's function for better understanding of question.

In a pipeline, if there are n stages, then at a given time, each stage perform it's own function. So, istead of waiting for the instruction to complete, we give the next instruction to the stage as soon as it has finished the previous instruction.

Consider the example that there are three man working at a icecream shop. first takes the order , second prepares the icecream and third delievers the icecream to customer. In this, instead of waiting for delievery of first icecream, first person can write the next order and similary third person can prepare next ordered icecream while first one is being delievered. This comcept is pipelining

CPI is a measure to evaluate how better is the pipeline. It is the average number of clocks per instruction.

Consider a smaller pipeline say of 3 stages namely fetch, decode and execute. and having 4 instruction:

Table below repersents the functioning of different stages of pipiline at different time:

In the above pipeline instructions are given to system at time 0, 1 2 and 3.

First instruction is coming out of the pipeline after 3 cycles, which is equal to no of stages in pipeline.

Rest of the instructions are coming out after 1 cycle.

Extra time taken by first instruction is known as startup delay.

we can generalise the result as,

if there are s stages in the pipeline and n no of instruction, then total time taken is

T = s + (n-1)

CPI = T/n

solution (a)

In the given question, we have s = 20 and n=100

So, CPI as per the above formula is:

CPI = (20 + 99)/100 = 119/100 = 1.19

solution (b)

Whenever there is are delay in the pipeline instruction, some clock cycles are wasted.

we need to add this delay to our calculated time T and need to calculate the CPI again.

In the question, it is given that there are 7 branched instruction and 3 out of the 7 causes a delay of 2 cycles.

Also, there are 5 loads , which causes a delay of 1 cycle each

We need to add delay due to 3 branch instruction which is 3*2= 6 and delay due to 5 loads which equals 5

Total time = (20 + 99) + 3*2 + 5 = 119 + 6 + 5 = 130

new CPI = 130/100 = 1.3

Ins/time 0 1 2 3 4 5 I1 F1 D1 E1 I2 F2 D2 E2 I3 F3 D3 E3 I4 F4 D4 E4

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

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