Gatementor.com

[piyushhurpade]

* What is theory behind formula: average execution time: (1 + stall frequency * stall cycle)

[sameer2009]

If a pipelined processor is used for executing a large number "N" of instruction and while execution there are some stalls needed then
the average execution time =
1 + (TOTAL STALLS NEEDED TO EXECUTE "N" INSTRUCIONS) * (STALL CYCLE TIME)

[sameer2009]

If a pipelined processor, in absence of stall cycles time = K + (N-1)

If a pipelined processor is used for executing a large number ["N"] of instruction and while execution there are some stalls needed then
the execution time =
1 + (TOTAL STALLS NEEDED TO EXECUTE "N" INSTRUCIONS) * (STALL CYCLE TIME)

1 : because, in pipelining after "K" (K=total pipline stages) cycles, 1 instruction gets completed in every next cycle.
K + (N-1)

In presence of stall cycles, total execution time includes the time wasted in all stall cycles.
If 1 instr has x stall cycles (x=frequency of stalls), so N instr will have Nx stall cycles
so total time wasted in stall cycles = Nx(stall cycle time)

In the formula
1 + (TOTAL STALLS NEEDED TO EXECUTE "N" INSTRUCIONS) * (STALL CYCLE TIME)
1 + Nx * (stall cycle time)
K is ignored, since N is much larger than K and assumed that every instr will get completed in 1 cycle.

so avg time to execute N instr
= [1 + Nx * (stall cycle time)] / N
~ 1 + x * (stall cycle time)