retagged by
551 views
0 votes
0 votes
The book says that a total time required for a pipeline with $k$ stages to execute $n$ instructions is as follows.

$T  _{k,n} =[pqnk+(1-pq)(k+n-1)] \tau$

$p$ is the probability of encountering a branch instruction.

$q$ is the probability that execution of a branch instruction I causes a jump to a nonconsecutive address.

(Each jump requires the pipeline to be cleared)

 

And this is my solution.

There are $p*q*n$ instructions which are a branch instruction that is taken.

Because they make k stalls, the number of stages of them is $p*q*n*k$

And the number of the rest of the instructions are $(1-p*q)*n$

They can be executed with pipelined, the number of stages of them is $(k+(1-p*q)*n-1)$

Therefore, the total time required is

$T  _{k,n} =[pqnk+(k+(1-pq)n-1)] \tau$

 

I can't understand why $1-pq$ is multiplied to $(k+n-1)$

Shouldn't it be $k+(1-pq)n-1$ because there are $(1-pq)n$ pipelined instructions?
retagged by

1 Answer

0 votes
0 votes
consider it like to two cases 1 case for a branch taken p*q

one case for non branch instruction and branch not taken instruction which probability are 1 - pq

in second case forget about branch and think like you normally do for a pipeline question

Related questions

1 votes
1 votes
1 answer
1
1 votes
1 votes
0 answers
2
kidussss asked Sep 1, 2022
300 views
1. In memory hierarchy the fattest memory type is cache memory next to register. So describe mapping process(transformation data from memory to cache memory)