Speed up factor of a pipeline?

[davide940]

A RISC processor has got a pipeline with k = 5 stages. On average 1/20 of the total instructions is a load or store and it requires an additional access to the memory. The memory accesses are optimized with a cache memory with an average hit rate of 85%, every miss in the cache causes a pipeline stall of one stage. Calculate the speed up factor neglecting the pipeline loading phase thus assuming that the number of instructions tend to infinity.

The speed up factor is the ratio between the time required without a pipeline and the time with a pipeline.
Usually if tk is the stage period, k the number of stages and N the instruction number the speed up factor is:
.............N * k * tk..............N* k
sk = ________________ = ____________
..........k * tk + (N - 1) tk .... k + N - 1

With our data the answer should be

......... N * k * tk + (1/40) * N*tk.......................... k+ (1/40)
sk = __________________________________= ________________________= 4.8845
.....N*tk + (1/40)*N*tk + (1/40)* 0.15 * tk..........1+ (1/40) + (1/40)* 0.15

But the right answer is 4.466956 , so where is my mistake?

 

[sm625]

It looks like you are starting with this equation:

.............N * k * tk
sk = ________________
..........k * tk + (N - 1) tk

which you then factor out tk to get this:

.............N* k
sk = ________________
..........k + N - 1

But from there its just gobbledegook. You arent plugging any numbers into either of those equations. And you dont explicitly tell us what k or N are, although it would seem that N is 1/40. I'm amazed you arrived at a number anywhere close to the correct answer; that could just be blind luck.

If

.............N* k
sk = ________________
..........k + N - 1

then how do you get to

......... k+ (1/40)
sk = _____________
.......1+ (1/40) + (1/40)* 0.15

The numerator seems straight forward substitution for N. But in the denominator you are going from k + N - 1 to 1+ (1/40) + (1/40)* 0.15 and those numbers seem to come from nowhere.

 

[TuxDave]

But from there its just gobbledegook. You arent plugging any numbers into either of those equations. And you dont explicitly tell us what k or N are, although it would seem that N is 1/40. I'm amazed you arrived at a number anywhere close to the correct answer; that could just be blind luck.

Unfortunately this isn't one of those "plug and chug" algebra problems. The speedup equation given in the OP is true for a given set of assumptions and so the following set of equations don't necessarily follow because he's modifying it based on the new set of assumption.

If you get to the intent of the speedup equation, it's basically:

Time to execute N instructions in a non-pipelined design
______________________________________________
Time to execute N instructions in a pipelined design


So for the most basic example where you have k stages and each stage takes tk time:

The time for a pipelined design is:
1) The first instruction takes k*tk time just to get through the whole logic.
2) All instructions after that take tk time because they're one stage behind in the pipeline.

So the time to execute N instructions in a pipelined design is:
k*tk + (N-1)*tk

For a non-pipelined design, all instructions take k*tk time to get through all the logic and so it's simply:
N*k*tk

However in the OP, now you have a disturbance in the time it takes to execute an instruction due to the type of instruction and the fact that cache misses can occur and so you go back to the above and make a new equation (which will use some weighted latency per instruction).