The Gateway to Computer Science Excellence
+40 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 ______
in CO and Architecture by Veteran (105k points)
edited by | 12.1k views

3 Answers

+36 votes
Best answer

Reference: Page 24

$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:

Similar Question

by Veteran (424k points)
edited by
Thanks. Corrected.

Yes, the reservation table in question has efficiency 33.33%.

Why only 4 bits? I suppose 4 is enough. but I'm not entirely sure and hence followed the procedure given in text.
4 because number of bits = highest digit in set of forbidden latencies.
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??
This topic comes into which section of pipelining in syllabus? I am bit confused. Can anyone explain
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.
should we also know how to calculate MAL for dynamic pipelines??
Asked once :(
when?? i didnt find it, which year??
@Arjun sir


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


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?

@Arjun sir:

I didn't understand the following:

"So, minimum length cycle is of length 3 either 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.

Sir if we had MAL=4, then using which cycle we would have calculated efficiency???

By using 5-8???
why  Task is present at cycle 5? it is supposed to be after 3 cycles right since mal=3??
@ PC, @ Arjun sir, plz explain the efficiency part calculation. stage utilization part. how is that drawn??
gotcha, thanks!!

MAL will be 3. and CV is 1010.

refer this.,

ohh, thanks :)
is this a question we can solve in 3 minutes ?? i dont think so
That is why it has a "difficult" tag :)

@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.

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
+22 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
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

by Active (5k points)
edited by
Got upto different states...From those states how to draw the state diagram and label the edges?? Please help
Thank you
@Arjun sir ,  Will there be a line from state 1011 to 1111 upon latency 1  ?
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:
Which says that length of collision vector is equal to total length of task.
for state 1111 dont we need to consider transition  on 3

for state 1011 dont we need to consider transition on 1
no. because "1111" means next 4 cycles are blocked and "1011" mean next cycle is blocked.

@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
I have added this to my answer. See below..
Thx :)

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.

Isn't it from advance section?

@Anoop Sonkar Shouldn't 1111 on 5+ loop on 1111 also? Other than going back to 1010?


@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:

  1. State 1 represents 10101
  2. State 2 represents 11111
  3. 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

by Junior (813 points)
edited by

Please give explanation of finding Throughput in ur answer.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,648 questions
56,422 answers
99,825 users