Consider a pipe-lined process with s stages. Assuming n tasks are being processe

Question

Consider a pipe-lined process with s stages. Assuming n tasks are being processed by this pipe-line Both s and n are positive integers. In each of the scenarios listed below in (2.1), (2.2) and (2.3), compute formulas giving the following quantities: C(n, s): the total number of clock-cycles during which the pipe-lined process runs R(n, s): the speedup ratio with respect a non-pipe-lined serial execution, F(n, s): the fill time, that is, the total number of clock-cycles before the pipe-line runs at full occupancy (that is, before all pipe-line stages are used), no longer runs at full occupano which all pipe-line stages are used) D(n, s): the drain time, that is, the total number of clock-cycles remaining after the pipe-line O(n, s): the percentage of time during which the pipe-line runs at full occupancy (that is, during The three considered scenarios are the following ones 2.1 Each stage runs within the same amount of time. 2.2 Each stage, but the first one, runs within t units of time (say pico-seconds) meanwhile the first stage runs within r t units of time where r is a constant greater than one, thus, the first stage is slower than the other ones. You can assume t-1 in order to simplify calculations. Keeping t non-specialized (so as a symbol instead of letting be 1) yields a bonus of 5 marks 2.3 Each stage, but the last one, runs within t units of time (say pico-seconds) meanwhile the last stage runs within rt units of time where r is a constant greater than one, thus the last stage is slower than the other ones. You can assume t - 1 in order to simplify calculations In each of the scenarios (2.1), (2.2) and (2.3), you can assume that every stage runs within one clock-cycle. Moreover, you can assume that this clock-cycle is equal in time to the longest stage of the pipeline.

Explanation / Answer

Let us get familiar with the basics of pipeline first. The concept of pipelining is to divide the task among different working units so that different sub tasks of more than one task can be performed at the same time. Taking a real life example, suppose that at a coffe shop, there is only one counter. whoever needs a coffee needs to stand in a queue on that counter, the person at the shop takes the order, another person makes the coffee and and a 3rd person generate bill for the customer, the customer keeps on standing in the line untill this whole process takes place.

Consider another coffee, here one person takes the order of the customer and pass the slip to the second person, who prepare coffee. after passing slip, the pirst person takes the order from next customer. Second person after making coffee passes the slip to 3rd person who generates the bill, and start making coffee for next customer. This is an example of pipelining.

If a pipeline has s stages, it means a task can be divided into s sub tasks. We can not give the subtask simultaneously to all stages as all the subtaks are series of steps that need to be performed one after another. So, at first,, we provide the first subtask of the first task, after this subtask is completed, this subtask is given to second stage of the pipeline and first subtask of the second task is given to first stage. And similarly, subtasks are forwarded to next stages and sbtaks of new task are added to pipeline. When no stage of the pipeline is empty, pipeline is said to operate at its full capacity.

Let us take a short example:

Folowing points needs to be considered from above diagram:

1) The above pipeline has 3 stages namely F, E and D, pipeline runs at its full capacity from t=3 to t=4. or in generat we can say the pipeline runs at its full capacity from t=s to t=n time

2) Also notice that once the pipeline start operating at its full capacity, we start getting one task completed every time unit.

3) First task is taking s time units to complete and rest of the n-1 tasks are taking 1 time unit to complete.

Now, coming to the question, we have s stages and n tasks.

solution 2.1

Since all stages are taking t time units, it is a simple pipeline, from point 3, we have

C(n , s) = s + n-1

speed up ratio = total time taken by non pipeline structure/ time taken by pipeline

time taken by non-pipeline = n*s

So, R(n , s) = (n*s)/(s+n-1)

Pipeline runs at full capacity at time=s time. So,

F(n , s) = s-1

Pipeline runs at full capacity till t=n time

total time = s+n-1

D(n , s) = total time - time untill pipeline run at full capacity = s+n-1 - n = s-1

Pipeline runs at full occupancy from time=s to time=n

O(n , s) = ((n-s+1)/(n+s-1))*100

solution 2.2

if first stage runs in rt units of time and rest of the stages in t time units, every stage will be delayed untill first stage is in use.

First stage becomes idle when first subtask of all tasks is performed by first stage i.e after time=n time unit.

So, in this case every stage will take a time of rt units till time=n and time of t units after time=n

C'(n , s) = n*(r*t) + (s-1)*t

in this case non pipeline sructure would have taken time = n*(rt + (s-1)*t)

So, R(n , s) = n*(rt+(s-1)*t)/(n*(r*t) + (s-1)*t)) = (n*r+n*(s-1))/(n*r + s-1)

here also, pipeline runs at full capacity for s-1 time units

F(n , s) = (s-1)*rt

D(n , s) = n*(r*t) + (s-1)*t - n*(r*t) = (s-1)*t

O(n , d) = (((n-s+1)*rt)/(n*(r*t) + (s-1)*t))*100 = ((n-s+1)/(n*r+(s-1)*t))*100

solution 2.3

when last stage is active, every stage will take r*t time unit and when last stage not active, it will take t time unit

last stage becomes active at time=s time

C(n , s) = (s-1)*t + n*r*t

in this case non pipeline sructure would have taken time = n*(rt + (s-1)*t)

So, R(n , s) = n*(rt+(s-1)*t)/(n*r*t + (s-1)*t) = (n*r + n*(s-1))/(n*r + (s-1))

here also, pipeline runs at full capacity for s-1 time units

F(n , s) = (s-1)*t

D(n , s) = (s-1)*rt

O(n , d) = (((n-s+1)*rt)/(n*(r*t) + (s-1)*t))*100 = ((n-s+1)/(n*r+(s-1)*t))*100

Instruction t=1 t=2 t=3 t=4 t=5 t=6 I1 F1 D1 E1 I2 F2 D2 E2 I3 F3 D3 E3 I4 F4 D4 E4

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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