Pipeline Speedup ||Stalling 12.11

Question

Consider an instruction sequence of length n that is streaming through the instruction pipeline. Let p be the probability of encountering a conditional or unconditional branch instruction, and let q be the probability that execution of a branch instruction $I_x$ causes a jump to a nonconsecutive address. Assume that each such jump requires the pipeline to be cleared, destroying all ongoing instruction processing, when $I_x$ emerges from the last stage.

If no of stages of pipeline = $k$ , what is the expression for speedup over non pipeline in terms of 

• $t_{np}$ = one instruction execution time in non pipeline
• $k$ = no of stages in the pipeline
• $t_p$ = cycle time in pipeline
• $p$ and $q$ are given probabilities.
• $n$ is the no of instruction

Comments

Flushing is done at the end of kth stage of a branch instruction, so (k-1) is no of stall cycles. I found it to be $\frac{t_{np}}{\left ( 1+pq(k-1) \right )*t_p}$. Please clarify.

---

Yes stall is (k - 1) cycles

---

plz chk my solution @Debasish @Kapil

Answer 1

An instruction sequence of length n

 The probability that execution of a branch instruction q

The instruction without branch (n-q)

p  be the probability of conditional and unconditional branch instruction

$I_x$  causes a jump to a nonconsecutive address

means $I_x$  is conditional branch instruction.

Unconditional branch instruction (p-$I_x$)

So, execution time of pipeline processor =$(n-q)\times t _{p}+q((p-I_{x})\times kt_{p}+I_{x}\times t _{p})$

Speedup=$\frac{t_{np}}{(n-q)\times t _{p}+q((p-I_{x})\times kt_{p}+I_{x}\times t _{p})}$

Reference:https://gateoverflow.in/683/gate2000-12

Comments

you have considered only stalls it made after flashing.

But, the question is branching and non branching instruction, also conditional and unconditional branch.

Here 'jump' is conditional branch instruction($I_x$)

And if p is conditional and unconditional branch instruction, among which ($I_x$) is conditional branch

Then unconditional branch is p-($I_x$)

---

U mean as the pipeline flashes throughly, that is why we have to use design 1-stalling.

http://stackoverflow.com/questions/19142559/understanding-stalls-and-branch-delay-slots/19146327#19146327

But, if then why conditional and unconditional branch is given, if it is without branch prediction

---

@Debashish

how time taken for non branching inst. is (k+n-1) ??