Question

Two computers have 7-stage fetch-execute cycles where branches are determined in stage 4. One computer is not pipelined, and the other is pipelined. Assuming that tp = 1, answer the following questions when running a program with 50,000 instructions where 1,000 of the instructions are conditional branches and each branch, if taken, skips over 10 instructions.a.How much faster is the pipelined machine over the non-pipelined machine assuming that no branches are taken.b.How much faster is the pipelined machine over the non-pipelined machine assuming that all branches are taken.c.Bonus question: How many branches would the program have to have assuming every branch is taken (and every branch skips over 10 instructions) for the non-pipelined machine to execute the program in the same time as the pipelined machine?

Answer 1

Given there are 7 stages, k =7

Branches are determined in stage 4.

One computer is pipelined and other is non-pipelined.

Given Cycle time, tp = 1

Number of instructions in the program, n = 50000

Number of conditional branches =1000, if taken skips over 10 instructions.

a) speed up of pipelined over non-pipelined (no branches taken):

Time taken on pipelined processor = (k+n-1)tp = (7+50000-1)*1 = 50006

Time taken on non-pipelined processor = n*k*tp = 50000*7*1 = 350000

speed up of pipelined over non-pipelined = Execution time on non-pipelined / execution time on pipelined processor = 350000 / 50006 = 6.99

b) speed up of pipelined processor over non-pipelined if all branches taken:

Time taken on non-pipelined:

k and tp do not change.

But whenever condition branch instruction occurs and is taken then 10 instructions are skipped.hence n = 50000 - 1000 * 10 = 40000

Time taken on non-pipelined processor = 40000 * 7 * 1 = 280000

Time taken on pipelined:

k do not change.

But tp of conditional branches will have a delay as branch are determined at stage 4. so, Each branch instruction will have a delay of 3 cycles.

and n = 50000 - 1000*10 = 40000

Time taken on pipelined processor = (7+40000-1)*1 + 1000 * 3 (For the conditional branche 3 additional cycles needed) = 43006

Speed up of pipelined over non-pipelined = 280000 / 43006 = 6.51

c) Number of branch instructions needed to make performance of both processor equal:

Let there are b branch instructions.

Then time taken on non-pipelined processor = (50000 - b*10) * 7 * 1= 350000 - 70b

Time taken on pipelined processor = (7+(50000 - b*10))+b*3 = 50007 - 7b

Lets equate both to get b value:

350000 - 70b = 50007 - 7b

70b-7b = 350000 - 50007

63b = 299993

b = 4761.7 = 4762 (Approx.)

Hence if there are 4762 branch instructions then both processor will have equal performance.