In this question, we explore synchronous pipeline efficiency in less-than-ideal

Question

In this question, we explore synchronous pipeline efficiency in less-than-ideal scenarios. Let t be the typical length of a single task without pipelining. Let P2 be a pipeline with 2 stages, and P4 be a pipeline with 4 stages. (You may use the app to help you perform the simulation if that offers more convenience. Should you choose to do so, please provide screenshots to show the setup of each experiment.)

[1pt] Find the maximum efficiency of P2 and of P4, if they are ideal, at the following values of n (where n is the number of tasks/instructions executed).

n

P2 ideal

P4 ideal

1

n=1

b=0.5t

m=2

S=nt/[(m+n-1)b] = ?

n=1

b=?

m=?

S=nt/[(m+n-1)b] = ?

infinity

n=infinity

b=0.5t

m=2

S=nt/[(m+n-1)b] = ?

n=infinity

b=?

m=?

S=nt/[(m+n-1)b] = ?

[1pt] Suppose the overhead of pipelining is 0.1*t per stage, and this cost is independent of the number of stages. Find the maximum efficiency of P2 and of P4 with overhead at the following values of n.

n

P2 with overhead

P4 with overhead

1

n=1

b=?

m=?

S=nt/[(m+n-1)b] = ?

n=1

b=?

m=?

S=nt/[(m+n-1)b] = ?

infinity

n=infinity

b=?

m=?

S=nt/[(m+n-1)b] = ?

n=infinity

b=?

m=?

S=nt/[(m+n-1)b] = ?

[1pt] Suppose the workload in the 2 stages of P2 is unevenly distributed at the ratio of 2:1. Similarly, the workload in the 4 stages of P4 is unevenly distributed at the ratio of 2:1:1:1. Find the maximum efficiency of P2 and of P4 when overhead is negligible.

n

P2 with uneven workload

P4 with uneven workload

1

n=?

b=?

m=?

S=nt/[(m+n-1)b] = ?

n=?

b=?

m=?

S=nt/[(m+n-1)b] = ?

infinity

n=?

b=?

m=?

S=nt/[(m+n-1)b] = ?

n=?

b=?

m=?

S=nt/[(m+n-1)b] = ?

n

P2 ideal

P4 ideal

1

n=1

b=0.5t

m=2

S=nt/[(m+n-1)b] = ?

n=1

b=?

m=?

S=nt/[(m+n-1)b] = ?

infinity

n=infinity

b=0.5t

m=2

S=nt/[(m+n-1)b] = ?

n=infinity

b=?

m=?

S=nt/[(m+n-1)b] = ?

Explanation / Answer

For a pipelined system with equal stage delays

Let k be the total no. of stages

b= t/k

where k is no of stages of pipeline

Thus s=nt/(m+n-1)b, b=t/k

s=nk/(n+k-1)

Also if n=1

s=nk/k=n=1

For 1st sub part

For P2

s=1*2/(1+2-1)=1

For p4

s=1*4/(1+4-1)=1

if n->INFINITY then we have INFINITY/INFINITY indeterminate and dominating term is n. Thus, limit value will be ratio of coefficients of n i.e. k/1=1

Simply, n>>k

n+k-1~n

s=nk/n=k

For P2

s=2

For P4

s=4

For 2nd subproblem,overhead is 0.1t per stage

Thus s=nk/(1.1*(n+k-1))

For n=1

s=1/1.1=0.,909 for both P2 and P4

For n-> INFINITY

s=k/1.1

For P2

s=2/1.1=1.818

For P4

k=4/1.1=3.636

For 3rd subproblem

For uneven pipeline, we assume even pipeline with largest stage delay

For P2

Largest ratio would be 2/3(2:1 ratio)

Thus t'=4/3*t

But for speedup t gets cancelled and thus will not affect the sppedup value

Thus, answer of first and third subproblem will be same as overhead is neglegible.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.