The Gateway to Computer Science Excellence

+47 votes

Consider the following reservation table for a pipeline having three stages $S_1, S_2 \text{ and } S_3$.

$$\begin{array}{|ccccc|} \hline \textbf{Time} \rightarrow \\\hline & \text{1}& \text{2} & \text{$3$} & \text{$4$} & \text{$5$} \\\hline \textbf{$S _1$} & \text{$X$} & & & & \text{$X$}\\\hline \textbf{$S _2$} & & \text{$X$} & & \text{$X$}\\\hline \textbf{$S _3$} & & & \text{$X$} & \\\hline \end{array}$$

The minimum average latency (MAL) is ______

$$\begin{array}{|ccccc|} \hline \textbf{Time} \rightarrow \\\hline & \text{1}& \text{2} & \text{$3$} & \text{$4$} & \text{$5$} \\\hline \textbf{$S _1$} & \text{$X$} & & & & \text{$X$}\\\hline \textbf{$S _2$} & & \text{$X$} & & \text{$X$}\\\hline \textbf{$S _3$} & & & \text{$X$} & \\\hline \end{array}$$

The minimum average latency (MAL) is ______

+42 votes

Best answer

Reference: Page 24 http://www2.cs.siu.edu/~cs401/Textbook/ch3.pdf

$S_1$ is needed at time $1$ and $5,$ so its forbidden latency is $5-1=4.$

$S_2$ is needed at time $2$ and $4,$ so its forbidden latency is $4-2=2.$

So, forbidden latency $= (2,4,0)$ ( $0$ by default is forbidden)

Allowed latency $= (1,3,5)$ (any value more than $5$ also).

Collision vector $(4,3,2,1,0) = 10101$ which is the initial state as well.

From initial state we can have a transition after $\text{“1"}$ or $\text{“3"}$ cycles and we reach new states with collision vectors $(10101 >> 1 + 10101 = 11111)$ and $(10101 >> 3 + 10101 = 10111)$ respectively.

These $2$ becomes states $2$ and $3$ respectively. For $\text{“5"}$ cycles we come back to state $1$ itself.

From state $2\ (11111),$ the new collision vector is $11111.$ We can have a transition only when we see the first $0$ from the right. So, here it happens on $5^{th}$ cycle only which goes to the initial state. (Any transition after $5$ or more cycles goes to initial state as we have $5$ time slices).

From state $3\ (10111),$ the new collision vector is $10111.$ So, we can have a transition on $3,$ which will give $(10111 >> 3 + 10101 = 10111)$ third state itself. For $5,$ we get the initial state. Thus all the transitions are complete.

$$\begin{array}{|c|c|c|} \hline \textbf {State\Time} & \textbf {1} & \textbf {3} & \textbf{5 } \\\hline \textbf{1(10101)} & \text{2}& \text{3} & \text{1} \\\hline \textbf{2(11111)} & \text{-} & \text{-}& \text{1}\\\hline \textbf{3(10111)}& \text{-}&\text{3} & \text{1}\\\hline \end{array}$$

So, minimum length cycle is of** length 3** either from $\text{3-3}$ or from $\text{1-3,3-1}$.

Not asked in the question, still.

**Pipeline throughput** is the number of instructions initiated per unit time.

So, with $MAL = 3,$ we have $2$ initiations in $1+3 = 4$ units of time (one at time unit $1$ and another at time unit $4$ ). So, throughput $=\dfrac{2}{4}=0.5$.

**Pipeline efficiency** is the $\%$ of time every stage of the pipeline is being used.

For the given question we can extend the reservation table and taking $MAL = 3,$ we can initiate new tasks after every $3$ cycles. So, we can consider the time interval from $\text{4-6}$ in the below figure. (The red color shows a stage not being used- affects efficiency).$$\begin{array}{|ccccc|} \hline \textbf{Time} \rightarrow \\\hline & \text{$1$}& \text{$2$} & \text{$3$} & \text{$4$} & \text{$5$} & \text{$6$} & \text{$7$} & \text{$8$} & \text{$9$} & \text{$10$} & \text{$11$} \\\hline \textbf{$S _{1}$} & \text{$X$} & & & \text{$Y$} & \text{$X$} & \times & \text{$Z$} & \text{$Y$} & \times & \text{$A$} & \text{$Z$} \\\hline \textbf{$S _{2}$} & & \text{$X$} & & \text{$X$} & \text{$Y$} & \times & \text{$Y$} & \text{$Z$} & & \text{$Z$} & \text{$A$} \\\hline \textbf{$S _{3}$} & & & \text{$X$} & \times & \times & \text{$Y$} & & & \text{$Z$} & & & \\\hline \end{array}$$

Here (during cycles $4-6$ ), $\text{stage 1}$ is used $\dfrac{2}{3},$ $\text{stage 2}$ is used $\dfrac{2}{3}$ and stage $3$ is used $\dfrac{1}{3}.$

So, total stage utilization $=\dfrac{(2+2+1)}{9}=\dfrac{5}{9}$ and efficiency $=\dfrac{500}{9} \%=55.55\ %$.

For simulation, Reference: http://www.ecs.umass.edu/ece/koren/architecture/ResTable/SimpRes/

Similar Question

0

I haven't heard about such term before while studying pipelining. When I read the pdf given by the link it has both static and dynamic pipelining scheduling. Are dynamic pipelines in syllabus??

0

This topic comes into which section of pipelining in syllabus? I am bit confused. Can anyone explain

+3

This should not have been asked for GATE in my opinion. But we cannot complain as they simply say "pipelining" in syllabus. So, there are free to ask anything. Usually 90% of questions in GATE come from base part of any topic and not advanced as happened here.

+2

@Arjun sir

Throughput is number of instruction that COMPLETE in a span of time.

Ref-

ece-research.unm.edu/jimp/611/slides/chap3_1.html

If we use this definition of throughput,we get throughout =1 /3

(On extending table we can see that on every 3 cycle, a instruction got completed)

Also I have learned in my college that Throughput = 1/MAL

So Throughput would be 1/3

Am I correct?

Throughput is number of instruction that COMPLETE in a span of time.

Ref-

ece-research.unm.edu/jimp/611/slides/chap3_1.html

If we use this definition of throughput,we get throughout =1 /3

(On extending table we can see that on every 3 cycle, a instruction got completed)

Also I have learned in my college that Throughput = 1/MAL

So Throughput would be 1/3

Am I correct?

+2

@Arjun sir:

I didn't understand the following:

"So, minimum length cycle is of

length 3either from 3-3 or from 1-3, 3-1. "

Do you mean MAL when you say "minimum length cycle of length 3" ? Also, average latency from 3-3 is 3, but average latency from 1-3,3-1 is (3+5)/2=4 right? I guess it should be 1-2,2-1 instead whose average latency is (1+5)/2=3.

0

0

@ PC, @ Arjun sir, plz explain the efficiency part calculation. stage utilization part. how is that drawn??

+1

@Satyam Chaudhary Yes, you are correct.

@Arjun Sir, we do not have 2 initiations in 1+3=4 cycles. You write the correct interpretation just a few lines after: "*we can initiate new tasks after every 3 cycles*". So yes, throughput should be 1/3.

Also, you write in one comment that "*we right shift the initial collision vector and OR with current CV"*. But in the reference you provided, we are doing the opposite, i.e., we right shift the current CV and OR with the initial CV.

0

yes we OR with the initial CV. in the nptel video also ORing is done with initial CV not current CV

Also 0 latency will not be taken

Also 0 latency will not be taken

0

I think the professor in the video has considered some other convention.Instead of '8+' he has taken '7+'.

So the result changes.

So the result changes.

0

in the link http://www2.cs.siu.edu/~cs401/Textbook/ch3.pdf

page number 25 has AB = (2,1,0), BA = (4,2,1,0) , so my question is how AB = (2,1,0), BA = (4,2,1,0) ? arjun sir please help .

+27 votes

first we find forbidden latency which is distance between each pair or X in the same row=(2,4) ... FL indicate another task can not initiated after this

permissible latency =(1,3) we may initiate another task after this.

now we can find collision vector using FL ..

this collision vector will b known as initial state of the pipeline

collision vector = cycles (4,3,2,1) (one bit for each cycle )and bit at 2 and 4 will b one because of collision=(1010)

now we can construct state diagram using permissible latency .

at 1 ..we will shift right 1 bit to collision vector (it is initial state ) and perform OR operation to result with collision vector =

1010 after one right shift 0101

1010+0101=1111

same for at 3 ..1011

same for at >=5 ..1010

now we have consider these points to find MAL

from the state diagram we can determine optimal latency cycle which result in MAL.

we have to find simple cycle which is a latency cycle in which each state appears only once

some simple cycle are greedy cycle which is one whose edges are all made with minimum latencies from their respective starting state

so here we find latency cycle (3) and (1,5)

so the answer will b min of (3 which have constant latency or avg latency of (1,5)=(1+5)/2=3)

so the **answer is 3 **

0

Got upto different states...From those states how to draw the state diagram and label the edges?? Please help

0

The reference mentioned says that:

"A collision vector is a string of binary digits of length N+1, where N is the largest forbidden latency in the forbidden list."

Then why the length of collision vector is taken as 4. It should be 5 as largest forbidden latency is 4.

Please justify

I also found this reference: http://www.csee.wvu.edu/~jdm/classes/cs555/notes/tech/pipectrl.html

Which says that length of collision vector is equal to total length of task.

"A collision vector is a string of binary digits of length N+1, where N is the largest forbidden latency in the forbidden list."

Then why the length of collision vector is taken as 4. It should be 5 as largest forbidden latency is 4.

Please justify

I also found this reference: http://www.csee.wvu.edu/~jdm/classes/cs555/notes/tech/pipectrl.html

Which says that length of collision vector is equal to total length of task.

+2

for state 1111 dont we need to consider transition on 3

for state 1011 dont we need to consider transition on 1

for state 1011 dont we need to consider transition on 1

0

@arjun sir, i was trying to ask you the same question in my below comments .

**Why did you says thats
for state 1011 SHOULD NOT consider transition on 1 ??**

if we consider , there has to be a line from 1011 to 1111... !

I am stuck with its reason for a long time...

Please do help. I didn't get that concepts

Also tell me How to calculate

- throughput
- efficiency

+2

In collision vector (1010) 1 indicates FL and 0 indicate PL. we will shift only 1,3 as this is our PL.

now after shifting if 0 emerged means there is no collision and if 1 emerged it means collision.

from 1011 we can't shift 1 as we don't have 0 for shift at last place and which leads to a collision but we can shift 3 as we have 0 at 3rd place.

same for 1111 here we can't other than 5 as we dont have 0 at any place.

0

@Anoop Sonkar @Sambhrant Maurya I also have the same query because after shifting 5 bits to the left, we will have 0000. Doing OR bit-wise operation between 1111 and 0000 will result in 1111

0 votes

The Forbidden Latencies { 0, 2, 4 }

The Pipeline Collision Vector ( 1 0 1 0 1 )

The State Diagram

State 1 : 10101

Reaches State 2 ( 11111 ) after 1 cycle.

Reaches State 3 ( 11101 ) after 3 cycles.

Reaches State 1 ( 10101 ) after 5 or more cycles.

State 2 : 11111

Reaches State 1 ( 10101 ) after 5 or more cycles.

State 3 : 11101

Reaches State 3 ( 11101 ) after 3 cycles.

Reaches State 1 ( 10101 ) after 5 or more cycles.

There are 3 states in the state diagram:

- State 1 represents 10101
- State 2 represents 11111
- State 3 represents 11101

The Greedy Cycle = (1, 5 )^{*}

The Minimum Average Latency = (1+ 5)/2 = 3

The Throughput 1/3*100 = 0.33333 instruction per cycle

0 votes

1. Latency means clock cycle difference b/w two successive initiations in the pipeline.

2. In the non-linear pipeline, latency value depends on the reservation table.

3. In this pipeline some of the latencies causes collisions called as forbidden latencies (non-permissible latency) and some of the latencies does not causes collisions called as non-forbidden latencies (permissible latency).

4. To detect the forbidden latencies we need to take the clock cycle difference b/w any two checkmarks in the same row i.e

Row 1: 5-1=4

Row 2: 4-2=2

Row 3: $X$

* Forbidden latencies$=0,2,4$

* Non-forbidden latencies$=1,3,5$ (any value more than 5 also)

5. Collision vector generated based on the reservation table i.e $[C_{n},C_{n-1}......C_{2}C_{1}]$

n: # of cycles

let's take C=0 as permissible and C=1 as non-permissible

Collision vector:

$C_{5}$ | $C_{4}$ | $C_{3}$ | $C_{2}$ | $C_{1}$ |

$0$ | $1$ | $0$ | $1$ | $0$ |

6. Latency sequence is generated wrt collision vector

* Latency sequence wrt $C_{1}$

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | |

S1 | 1 | 2 | 1 | 2 | 3 | 4 | 3 | 4 | 5 | 5 | |||||||

S2 | 1 | 2 | 1 | 2 | 3 | 4 | 3 | 4 | 5 | 5 | |||||||

S3 | 1 | 2 | 3 | 4 | 5 |

Latency cycle:

$2-1=1$

$7-2=5$

$8-7=1$

Avg latency $=\dfrac{1+5}{2}=3$

* Latency sequence wrt $C_{3}$

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | |

S1 | 1 | 2 | 1 | 3 | 2 | 4 | 3 | 5 | 4 | 5 | |||||||

S2 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 5 | 5 | |||||||

S3 | 1 | 2 | 3 | 4 | 5 |

Latency cycle:

$4-1=3$

$7-4=3$

$10-7=3$

Avg latency $=3$

* Latency sequence wrt $C_{5}$

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | |

S1 | 1 | 1 | 2 | 3 | 2 | 3 | 4 | 5 | 4 | 5 | |||||||

S2 | 1 | 1 | 2 | 3 | 2 | 3 | 4 | 5 | 4 | 5 | |||||||

S3 | 1 | 2 | 3 | 4 | 5 |

Latency cycle:

$6-1=5$

$7-6=1$

$12-7=5$

Avg latency $=\dfrac{1+5}{2}=3$

MAL: Minimum avg latency

$min(3,3,3)=3$

52,345 questions

60,501 answers

201,872 comments

95,325 users