Instruction Scheduling - Compiler Design, Computer Science & Engineering Video Lecture - Computer Science Engineering (CSE)

the lecture on instruction scheduling so
in this lecture we will be looking at
machine independent you know machine
dependent optimization and instruction
scheduling is one of them we have seen
one type of machine dependent
optimizations before that is the
peephole optimization that was a very
simple optimization looking at a window
of instructions to find patterns and
then you know replace that pattern with
a more efficient sequence of
instructions and so on
instruction scheduling is different so
there are many types of instruction
scheduling mechanisms we are going to
see a few of them basically all
instruction scheduling mechanisms
consider a sequence of instructions in
one or more basic blocks the minimum of
course is one basic block then based on
different criteria they try to reorder
the instructions why should these
instructions be reordered well basically
we want to make sure that the pipeline's
in the processor they remain full most
of the time and any hiccups in this
pipeline are avoided so we see how best
it can be done by using instruction
reordering so simple basic block
scheduling then automaton based
scheduling integer programming based
scheduling optimal relate load
scheduling for trees and then trace a
super block and hyper block scheduling
is our sum of the instruction scheduling
mechanisms algorithms that we are going
to consider
so what exactly is instruction
scheduling as I mentioned it's nothing
but reordering of instructions so as to
keep the pipeline's of the functional
units of a processor with full with no
stalls so no hiccups and instruction
scheduling in general is an np-complete
problem and therefore there is a need
for heuristics to take care of
instruction scheduling
if it is applied on basic blocks then it
is called local instruction scheduling
and if it is applied on a sequence of
basic blocks then it is called global
instruction scheduling so global
scheduling requires elongation of basic
blocks so and these are called super
blocks hyper blocks etcetera etcetera so
let's look at some motivation why
exactly instruction scheduling is needed
what are its advantages and so on
consider you know this sequence of
instructions here so we have seven
instructions and we are considering a
load store architecture in other words
any operand must be in a register so we
have to load the operand into a register
and then use it that's the model that we
are considering here so time to load is
two cycles and each operation requires
one cycle the in this code and this is
the dependency graph directed acyclic
graph for this particular code if you
observe this code with the latency
that's given here two cycles for load
and one cycle for off we immediately see
that there are two stalls one at a three
and another at i-5 let's see why so i
three loads you know r1 plus r2 computes
r1 plus r2 and puts it into r3 and r1
and r2 are loaded into
you know loaded from a and we in the
instructions i1 and i2 the instruction I
even would have completed by the time we
reach I three because two cycles would
have been completed but the instruction
i2 which loads B into r2 would not have
completed when we come at come to i3 so
there is a need to skip one cycle here
and that's the stall that we are talking
about and once the result of lowered
instruction in i2 is ready the
computation of r1 plus r2 can take place
similarly the instruction I 5 it has r5
equal to R 3 minus R 4 R 4 is being
loaded from a memory location C in the
instruction i-4 it's not yet complete
and therefore there is a stall at this
point we have to skip an instruction and
then you know execute the instruction I
5 so that means instead of these seven
instructions will really require nine
cycles in order to complete so now
suppose we want to get rid of these
stalls
is it possible to reorder these
instructions such that the dependences
as given in the directed acyclic graph
are still satisfied in other words we
definitely want to wait for the loads
you know to be completed before we come
to i3 that is the operands must be ready
before we come to i3 similarly we want
to make sure that our four is ready
before we come to I 5
only thing is some reordering of
instructions may be possible let's see
how so here is a new sequence of
instructions there are no stalls here
but dependences are indeed satisfied how
are the stalls eliminated I even remains
as it is I 2 remains as it is but I 4 is
actually replacing the instruction i3
and i3 has been pushed down
by one cycle so in the ones step so now
when we arrive at the instruction i3
which is R 1 plus R 2 both R 1 and R 2
already
the reason is R 1 takes two cycles so it
will be ready by the time my four is
executed our two who takes two cycles so
that will also be ready by the time I
three is executed so R 1 and R 2 will
now contain operands
there is no stall our 4 of course would
not have completed by the time we
execute i3 but it is not required in the
instruction i3
so once we finish I 3 we execute I fi
which requires r4 and r4 would have got
its operand by the time we reach i-5
because two cycles have elapsed so this
particular sequence of instructions
actually completes just in just seven
cycles it does not take nine cycles at
all that's because we have just swapped
this instructions I four and I three all
of us have remained the same so I four
is in this slot with the load
instruction and i3 is in this slot with
the computation instruction so this is a
very simple example it shows that a
subtle change in the order of execution
of the instructions will lead to removal
of the stalls
that does not mean every stall can be
removed there will be some stalls which
cannot be removed as we will see in
later examples and we will have to
insert no ops in those stalls in those
you know cycles so quickly to
recapitulate what we need here we
definitely want to look at the same
dependences flow and T and output as we
studied in parallelization but these are
now at the register and lowered levels
okay they are not at the higher levels
but between statements etcetera they are
at the machine instruction level for
example I even is our one is loaded with
our Lord Allah I know r2 so
and then I - is r3 equal to r1 + 4 + i3
I - is r3 equal to r1 + 4 + i3 is r1
equal to r4 plus r5 so here the value
which is actually loaded into r1 is used
in I - so i1 Delta I 2 holds similarly
whatever is loaded into r3 okay is
actually it is a sorry whatever is read
from r1 is later replaced in instruction
i3 so there is an anti-dependence
between I 2 and I 3 so that is i2 Delta
bar i3 and then we also have a 1 Delta
not a 3 because we are actually loading
into the same register R 1 I 1 and I 3
are related by output dependence so anti
and output dependences can be eliminated
by a register renaming we have seen some
examples of this in parallelization so
for example here if we don't use R 1 we
just use say maybe r6 or something like
that then automatically there is no
output dependence between these two
similar so and that automatically
eliminates this anti dependence as well
so what is a dependence directed acyclic
graph well it is the same dependence
graph as we studied in parallelization
it is just that here we have at the
machine instruction level so here is a
simple example this is the sequence of
instructions which is a running example
that we are going to use so I want to
i99 instructions there are nine
instructions here nine nodes here these
are the nodes of the directed acyclic
graph each instruction is a node there
is a solid dark from one node to another
node and that shows a flow dependence
for example you know between I 1 and I 3
ok so T 1 is equal to load yet T 3 equal
to t 1 plus 4 so there is a load
and there is a flow dependence similarly
another flow dependence between i1 and
i-4 and so on and so forth so all the
flow dependences are shown in solid
lines then the anti dependences are
shown using the dashed line so this is
the dashed line from i1 to i9 so here is
i1 and here is i9 so you may wonder why
load a in I 1 and V equal to store t5 in
I 9 have been linked by an
anti-dependence the reason is memory
disambiguation which says that this CA
and this we are different it has not
been done so no algorithm has been
applied to find out whether a and B are
the same location are all different
locations so because of that
conservatively we will have to assume
that there is an anti-dependence from i1
to i9 because he and B could be the same
similarly B a this B of course is the
same so i2 and i9 also have independence
so this is i2 and this is i-9 okay so
here I 2 and I then similarly you know I
won and I ate I even I 2 and I ate also
have similar anti dependence so here and
here okay so these are anti dependences
that need to be depicted in this
dependence diagram then there may be
output dependences so those are shown by
a dash-dot line so here is an output
dependence and output dependences
between these two again memory
disambiguation has not been done so we
don't know that B and C are different
memory locations so there is an
anti-dependence from I ate to I know
sorry there is an output dependence from
ia to i9 so the dependence diagram show
us all this now the problem of
instruction scheduling would be to
rearrange instructions in this sequence
so as to expect all the
floo anti and output dependences yet to
minimize the number of stalls that may
occur in the sequence so the first
algorithm that we are going to study is
the basic block scheduling so what is
our model we need to study the model of
a basic block so a basic block is
assumed to consist of what are known as
micro operation sequences MOS which are
indivisible in other words if a if an
instruction contains three or four micro
operations in it we need to once they
start that instruction all the micro
operations in it will have to be
completed and there is no way we can
divide this sequence of four micro
operations into to each and schedule
them separately so once the instruction
is started all the micro operations will
run one after another they are
indivisible each MOS has several steps
and each one of these steps will require
resources each step of an M voice
requires one cycle for execution so this
is the assumption there are precedence
constraints and there are also resource
constraints these must be satisfied by
the reordered a scheduled program so we
have the diagram I showed here this
shows the precedence constraints see so
once we say there is a delay between
these two or the delay on this edge
could be the time of execution of the
load instruction automatically this
becomes a weighted directed acyclic
graph and that shows all the precedences
that must be satisfied the precedence is
relate to data dependencies and
execution delays as I mentioned just now
but the dependence diagram does not show
the resource constraints so resource
constraints relate to limited
availability of shared resources so in
other words
all I want to execute this are this sub
and this ad and there is only one matter
it is even though we may find that these
three can be executed at the same step
it is not possible for us to schedule
them in the same step because there is
only one adder compulsorily we may have
to schedule them in three successive
cycles so that's what resource
constraint is all about here is the
basic block scheduling problem so first
of all the basic block is modeled as a
digraph G with a set of nodes V and a
set of edges e and r is the number of
resources that we are going to have in
the system in the processor the nodes of
for the graph G or micro operation
sequences and edges of the graph II show
the precedences there is also a label on
the node V instead of you know the edge
alone we also have a label on the node
so the label on the node indicates a
resource usage function so what is this
that is a resource usage function Rho VI
for each step of the Amoy is associated
with I have with the node V so in other
words if there are four steps in n MOS
associated with node V each of these
four steps will require resources so Rho
V of one says how many resources of a
particular type are needed for this
particular micro operation sequence step
so Rho V 2 similarly for the second demo
a step and so on and so forth so these
things actually you know we are
considering only a single type of
resource R is the total number of
resources so it is a simplified problem
as such if we have many resources many
types of resources it is definitely
possible to you know
extend this problem to take care of
those as well it's just a question of
checking all the resource constraints
you know at a particular point in time
so instead of for just one vector of
resources you know or rather one number
indicating the number of resources we
would have a vector of these numbers
saying how many are there in each
particular type so the length L V of a
node we show us how many substrates are
included in the micro operation sequence
at node V and the label on edge any
particular AG shows the execution delay
of the MOS and it is denoted by D of e
so we have the resource available
resource requirements of for a
particular node V he indicated by Rho V
of I for each sub step I of that node
and we have on the label on the edges
coming out of the node V or incoming
edges of Nouri the execution delay of
the particular MOS it's now the formal
notation and the description of the
problem is here the problem is to find
the shortest schedule Sigma and Sigma is
a mapping from V to n right for each
node V we need to find a time slot the
time slot is nothing but a natural
number so which is the time slot in
which we can be executed that's the
schedule that we want to find for each
node V we want to find a particular
number of that kind and there are no
restrictions so what are the
restrictions for all the edges e say u
comma V in the set of edges E Sigma V
minus Sigma u must be greater than or
equal to D of E so what does this tell
us let us look at the picture so here is
a node u here is a node V u has been
scheduled at the time slot Sigma u let
us say node V has been scheduled at the
timeslot Sigma V obviously Sigma V comes
later than Sigma yo because you must be
executed before we there is a precedence
constraint there are rather edge
connecting U and V which says you must
be completed before we the delay on the
edge UV is D so this delay D must be
less than or equal to the schedule of V
which is Sigma V minus the schedule of U
that is Sigma yo this is quite easy to
understand because we cannot star tree
before we complete Sigma u so how much
time does Sigma u rather they are
completing you how much time does you
take it starts at the slot Sigma u then
it requires at least these slots more in
order to complete so Sigma u plus D is
the minimum time at which we can start
that's why D less than or equal to Sigma
V u minus Sigma u so that is the
precedence constraint and Sigma V minus
Sigma u greater than or equal to the
delay on the edge e what about resources
this says if you sum up all the resource
requirements at a particular point in
time all the resource requirements must
be less than or equal to R so let us
understand this better so let us say you
know we have this matrix each row
indicates in my is corresponding to a
node say V 1 V 2 V 3 V 4 etcetera
etcetera so each one of these is a MOS
and since we know that one time slot is
required for each one of these my sub
steps so here is the time slot of the
MOS sub steps okay
so we are going to this is not a valid
schedule it violates certain conditions
but this will tell you what the resource
constraint is all about let us say the
first my is V 1 has been scheduled at
time 0 second my is at time 4 so 1 2 3 4
four steps are needed for time slots are
needed for Sigma V one to complete we
want to complete so Sigma V three cannot
be started before the fourth time slot
then we require five time slots for V 2
so V 3 starts at 9 then we need 3 for V
3 so V 4 starts at 12 we have taken care
of all the precedence constraints the
delays and so on but then this did not
check the resource requirements so let's
consider the red diagonal and the blue
diagonal okay so first look at the blue
diagonal so let's say we are looking at
you know V 4 okay in its second time
step rather sub step okay so at this
point the the elements in the matrix
really show how many resource elements
are needed for that particular sub step
so for example Sigma V 1 in time slot 0
requires one resource in time slot 1
requires one resource time slot 2
requires two resources etcetera etcetera
so similarly V 4 requires 1 2 3 and 2
resources in the time start 0 1 2 & 3
are starting at 12 so at this point in
time that is we are looking at this is
time slot 12 time slot 13 14 and 15 time
slot 12 we require 2 resources because
of before but remember v3 has not yet
completed v3 started at 9 so it's
actually at you know it requires 9 10 11
right so you know all so these are all
the time slots that are needed for this
particular particular node to complete
so
what we really say is okay let's see how
what are the various you know timing
requirements and resource requirements
of these slots so for example this
requires two here two here and two here
these are all the concurrently executing
threads that we have so the sum of all
these is five right so when we have
assuming that there are five resources
in this particular system so the number
of resources that we are using at a
particular time let us say is five so we
have five resources and utilization is
also five so the resource constraints
are satisfied but when you look at the
read resources okay red circles here we
find that there is a violation if you
add up these three and three and two we
really make it eight right so because
there are eight resources being used but
there are only five at least we want to
use eight but there are only five that
means the number of resources available
is less than the number of resources
that we are trying to use so there is a
violation
so that's precisely what I said this is
not a valid schedule if this were to be
a valid schedule this would not have
occurred you would have actually summed
up these things to be less than or equal
to five so this is not a valid schedule
because the resource requirements at a
particular point in time or actually you
know beyond what is available in the
system so that's what this is Rho V I of
I minus Sigma V is less than or equal to
R that is what it should be but it is
not and the length of the schedule a
valid schedule would be maximum of Sigma
V Plus L V where V is in V so we just
take the maximum Sigma V and LV that is
if that is not the maximum of whole
thing we know one of the previous steps
may have
smaller Sigma V but a larger LV so that
may contribute to the maximum of the
schedule so that's the you know meaning
of this right so we have demonstrated
that at some point in time May there may
be satisfied resource requirements but
it's another point in time in an invalid
schedule there will be violation of
resource requirements so this should
never happen resource requirements must
be satisfied at every point in time so
how do we schedule the instructions so
that the resource constraints and the
precedence constraints are both
satisfied they find the shortest dial
here is a simple algorithm and this is a
variation of the very well-known list
scheduling algorithm that's where our
people have studied in operating systems
in job shop scheduling and so on the
requirement is find the shortest
schedule Sigma which is a mapping from V
to n such that precedence and resource
constraints are satisfied and whenever
there are holes we assume that they are
filled with no opps so here is a basic
outline of the function called list
schedule which takes the drag as its
input V comma E how does it work it
really does a topological sort of the
graph so it starts with those nodes in
the graph which do not have any
predecessors those are the root nodes of
V okay so the dag may not be a single
component you know it may be a forest of
you know our tax right it is not
necessary to have just one so in such a
case the number of root nodes of that
graph will be more than one there is a
queue called a ready queue which shows
all the nodes which are eligible to be
scheduled okay so root nodes of V RS
able to be scheduled because they have
no predecessors and when we begin with
the root nodes of V all the resources
are assumed to be available it does not
mean that every node in the radicchio
can be scheduled in the same timeslot we
still haven't found time slots for all
the nodes in the ready queue okay so we
just come from the top and include nodes
as we go along the schedule to begin
with this fight
it has nothing so there is a loop while
ready not equal to if I do so in which
we actually take out nodes from the
ready queue and then schedule it put
something else into the ready queue and
keep doing this until all the nodes in
the graph are scheduled
so in that case ready node cannot ready
list cannot get any more nodes so we
stop when ready becomes by speaking out
of highest priority from the ready queue
and call that as V so how to do this we
will see a little later so let us assume
that there is a prioritization of nodes
in the ready list and one of the highest
priority nodes the highest priority node
is picked then we need to compute the
lower bound on the time slots at which
the nor we can be scheduled so this is
done by the function satisfy precedence
constraints which we are going to see
very soon V comma schedule comma Sigma
then once we have found the minimum time
slot in which we can be scheduled this
is done by looking at the precedence
requirements we need to check whether
that minimum time slot satisfies
resource constraints whether all the
resources which are needed are available
to us and if so fine otherwise we need
to actually keep that slot vacant
take the next slot check whether
resources are available at that point
and so on and so forth so this is done
by the routine satisfied resource
constraints become a schedule comma
Sigma comma lb so once we have found
Sigma V which is the timeslot which
satisfies both the precedence and
resource constraints we include that
node as a scheduled or social schedule
equal to schedule + V then the ready
list needs to be updated
so what do we mean by updating we take
out the node V from the ready list here
remember we did not take it out we take
it out then we try to add those
successors of the node V which actually
you know are now ready to be scheduled
in other words their own you know
successors you know for example V is the
node to be scheduled which has been just
now scheduled there are three successors
u1 u2 and u3 for this particular node
then w1 and w2 are two other processors
of u1 and u3 they have already been
scheduled so if you one was waiting for
me to be scheduled so now he also has
been scheduled so u1 is now ready for
scheduling u2 has only V as its
predecessor so u2 is also ready for its
scheduling u3 is similarly ready because
w2 is already scheduled so V is now just
now scheduled so this is also ready for
scheduling but another successor of V
which is x2 as a predecessor x1 which is
not yet scheduled so even though we has
been scheduled x2 cannot be scheduled
because x1 has not yet been scheduled it
can be scheduled only after x1 is
scheduled so
that's what we do here we take out V and
then include all those nodes u such that
u is not in schedule list
so obviously you should not have been
scheduled already and then and for all W
comma you in E you W must be already
scheduled so for this node all its
predecessors must be scheduled W is the
predecessor of U and U is now being
considered
put into the ready list so all its
predecessors must already be scheduled
that is what we said here x1 cannot be
is not yet scheduled so x2 cannot be
included in the ready list but u1 u2 and
u3 will be included in the ready list
now what are the two functions satisfy
precedence constraint and satisfy
resource constraint do they consider
Sigma u plus D of U V over all the
schedule nodes you okay
so far so and then return the maximum of
for this value so let's see what it
really means so we are looking at V okay
and now we are looking at all the
predecessors of V so that's what this
said see Sigma V is our node we are
looking at u comma V where u is a
predecessor so all the predecessors
which have been scheduled you know they
are already we know that they are
scheduled because otherwise we would not
have included V in the ready list okay
so these are all the scheduled
predecessors already now there's they
have been scheduled at ten twenty five
and eighteen right so what is the time
slot at which V can be lower bound at
which V can be scheduled so just look at
this this is ten the delay is two so ten
plus two is twelve
this is twenty five plus four is twenty
nine and 18 plus three is 21 so 29 is
the large value so before the timeslot
29 we cannot really schedule v-y if we
do that then Yuto would not have
completed by that time so we take twenty
eight for example you do completes it
twenty nine so the values computed by u2
will not be available to V therefore 28
is an illegal slot so that's what this
really is all about so the max in this
case was this okay 29 the others were
did not contribute to the maximum so
this gives you the lower bound at which
the nor we can be scheduled but the
precedence constraint on its own will
not tell us whether the sources
available are available for executing V
at that lower bound value will say of 29
the function satisfy a resource
constraint checks this availability so
for example we start at LV and every
time slot lv + 1 lv + 2 lv + 3 etcetera
from that point onwards is checked
this says infinity but you really don't
go to infinity because there are only a
finite number of instructions number 1
each instruction has a finite number of
MOS steps and we know that every
instruction terminates so eventually
after a certain number of steps every
instruction preceding we would have
completed execution so resources must
become available so this will never be
really an infinite loop it is just shown
that we don't know how many instructions
we need how many slams loss we need to
check that's why this says lb to
infinity so from well beyond words we
check lb lb + 1 lb plus 2 lb plus 3
etcetera etcetera and what we check are
exactly the same as what we showed you
beforehand the sum of the resources
resource requirements of various time
steps must be less than or equal to R so
this is the sum of the resource
requirements of the other instructions
which are concurrently executing with V
Rho V J is the resource requirement of
the J sub step of node V so these two
together tell you about the total
resource requirements of the entire
sequence so this must be true for all
values of j from 0 to LV that is for all
subscripts of the node V so once we find
a timeslot
ie at which the resource requirements
are also satisfied and that is that may
be lb lb plus 1 will be plus 2 etcetera
etcetera we return that value I as the
slot at which V can be scheduled so for
example take the previous schedule
itself so here we this is Sigma V 1 this
is V 1 this is V 2 etcetera etcetera
this is V 3 and this is before why did
we show these two in red so this is time
dot 0 this is time slot for this is time
slot 9 10 11 14 etcetera etcetera so
what this particular these two times
thoughts have been left free nothing has
been scheduled simply because the
scheduling this instruction you know v3
in any one of these violates the
resource constraint so if we leave this
two free then you know the resource
constraints will not be violated this is
just for the sake of example you know it
may be one slot it may be two slots or
three slots in practice but here I have
just shown these two as vacant saying
that it is possible that two slots would
be left free and then the you know
resource constraints would be satisfied
if we schedule v3 at 11 and v4 at 14 so
that is why we have left these two slots
free so
the LB would have been 9 okay because of
residence constraints so this is 0 then
plus
for ten plus five nine but lb ply lb and
lb plus one are not suitable for
scheduling v3 because the resources are
not available let's say resources are
available at eleven that is eleven
twelve thirteen these three time staffs
resources become available so therefore
we can schedule them at that time slot
and you know then resource constraints
will be satisfied no violations occur
now how do we actually order these nodes
so in the priority ordering here you
know I said pick the highest priority
node in the ready list right we did not
say what is the priority ordering that
we use that's what we want to see now
let us consider two or three of these
varieties one of them is the height of a
node in the directed acyclic graph that
is longest path from the node to a
terminal node so if the longer the path
the higher the priority y-you know if
the path is longer that means there are
many instructions which depend on this
particular node so it is better if that
node is scheduled early
that's the heuristic that one uses so
let me show you an example so here is a
simple directed acyclic graph the legend
says inside is node number left side is
path length and right side is execution
time below is latency so if you look at
the nodes here these are the leaf nodes
for the leaf nodes we say that execution
time of the node is the you know path
length so execution time is 1 here so
pot length is also 1 execution time is 2
here so path length is 2
when we go to this particular node so we
take the execution time here path length
here add the delay so that becomes three
we take the path length here add the
delay that is zero so it becomes two so
the maximum of these really becomes the
path length for this particular node
four that's what this is latency income
I am plus path length of M so max over
all the successors of the node en so
that we did so then for this C is 3 plus
0 so that is 3 and 3 plus 2 that is 5
here cut line and this becomes 3 plus 1
that is 4 so this is how path lengths
are computed and let us say when we
start scheduling let us say we consider
these two nodes then 4 & 5 so this has a
longer path length larger path length so
this node would be scheduled first and
not this particular node then so you
know okay maybe we can even look at the
scheduling of this particular dag with
before we go to the other heuristic so
the algorithm says consider the root
nodes of the dag so that is 1 & 3 these
are the only 2 which will be put into
the ready list
so 1 & 3 are in the ready list we need
to pick the highest priority node from
the treadle list that is pot length so 5
& 4 so no or 3 which has a path length 5
is picked because it's higher so that's
why the schedule indicates node 3 as the
first node let us assume that there are
enough number of resources to execute
any number of instructions in parallel
so we don't have to worry about the
resource constraints in this simple
example the next example will look at
that also then 3 is completed but then
the successor instruction is for that
cannot be executed until 2 is completed
and 2 cannot be completed unless one is
completed so one is in the hole one is
the only instruction in the ready queue
right now
so we are going to include one in you
know in the schedule schedule it in the
next time step after three there is s
the you know the number of resources
available is very large no limitation so
there is no problem about using
resources so one can be scheduled in the
my next time slot because one does not
depend on three so the next one after
one the node number two can now be
included in the ready list so because
two has only one as its predecessor two
can be now included in the ready list
the minimum time slot at which two can
be scheduled is you know this was
scheduled let us say time slot zero plus
one so that's the time slot at which two
can be scheduled okay so if so we can
compute the time slots at which these
instructions can be scheduled in this
manner so now whereas if we assume that
only one instruction can be showed in
every cycle that is you cannot have more
than one instruction each cycle then you
know we have scheduled three at time
slot zero one night time slot one right
so the minimum available time slot for
this node number 2 is Sigma of 1 plus 1
so that is time slot number 2
so after at the time slot 2 we schedule
this node 2 because it has no other
predecessors and once 2 is complete you
know after time slot number of time
slots 0 and that 4 can be scheduled
the reason is node number 3 which was
initiated in time slot 0 will complete
in 2 time slots so by the time we
reached time slot 2 3 would have
completed so 4 can be scheduled in time
slot 3 so because both its operands are
ready and once 4 is completed we again
have 5 & 6 put into the ready queue
now which of these should be baked again
we use the path length as the criterion
two and one so node 6 has path length 2
which is higher than part length one of
node 5
so scheduled node 6 first and followed
by node 5
now the ready list is empty and we have
assigned a time slot for each one of the
nodes in the directed acyclic graph so
that completes the this particular
scheduling process for the example now
what is the second heuristic that can be
used we can compute what are known as
earliest start time and latest start
time east art and he'll start for each
of the nodes so what exactly is east art
it tells you that you cannot schedule a
particular node earlier than the value
of his start and if you say what is yell
start yes start tells you that this is
the latest time by which you should
schedule the node and if you violate
either the e start value or the lstart
value and schedule it outside these
limits this may result in pipeline
stalls okay so as far as possible we
should try to stick to the time stops
between e start and lstart and schedule
the nodes but e start and lstart are
really based on precedence constraints
they do not consider any resource
constraints therefore we may still have
to violate the start and lstart value
sometimes because of resource
constraints but then since there are not
many resources available there will be
pipeline stalls and that cannot be
helped how do you compute e start we
East our tree is computed as the maximum
over all the nodes 1 2 K you know so you
are really looking at the predecessors
of then Audrey UI comma V so UI are all
the
predecessor's there are K of them so you
consider the e start value of UI and the
delay of the edge UI comma V take the
max over it that gives you a start of V
so let's see how this is done so you
have node V here which is to be for
which you need to want you want to
compute e start these are the three
predecessors so u 1 u 2 au 3 so they
have their you know e start values
already computed ok so that is 25 45 and
16 let us say the delays are D 1 D 2 D 3
4 7 and 2 respectively so you look at 25
plus for the add 45 + 7 + 16 + 2 so that
means 29 52 18 the max is obviously 52
so this is how you compute the e start
value so this tells you that we cannot
start before timeslot 52 okay
so that is that makes sense because we
are really looking at the you know one
time at which all the three predecessors
of the node V complete that is 45 plus
seven okay now the e start value of the
source node is taken as zero we begin
the computation of the e start value
from the top assuming the source node
has a zero e start value what about L
start its from the bottom so yes start
you is computed as a minimum over all
the successors so you want to compute
the lstart value of you
there are successors for you those are
all the VI nodes 1 2 k take the year
sort of for the successor node subtract
the latency and take the minimum of this
particular computation over all the
successors so let us see what we mean
there are three successors again we want
to compute the lstart value for V W 1 W
2 W 3 very lstart values are 12 36 and
21 so now what is the lstart value for
node V 12 minus 2 36 minus 1 and 21
minus 3 so the minimum
of all this is 10 so that is the latest
time at which node we can be scheduled
so if you're scheduled later than that
then you know we are going to create
some pipeline stalls that is very
obvious you see so if this is let us say
10 so 10 plus 2 is 12 here and 10 plus 1
is 36 and 10 plus 3 is 13 right so if
you this can be scheduled at time slot 2
that's why 10 plus 2 is 12 so if you
actually exceed L then this node will
not be scheduled at 12 it will be
scheduled at some other value so there
would be some kind of a stall but that
cannot be helped if there are not many
resources available now once we compute
the e start value of starting from the
top the lstart value of the sync node is
set that is its east start value and we
start computing the yes travel use from
the bottom towards the top so he start
and L will start can be computed using a
top-down and bottom-up pass respectively
either statically before scheduling
begins or dynamically during the
scheduling itself okay so you know if
you actually want to schedule the the
precedences rather the e start and it'll
use during the scheduling process
because the graph is going to change as
and when we schedule certain nodes it
can be done but that requires a little
extra computation at scheduled time so
in node with a lower east arturo start
value has a higher priority that is one
possible you know heuristic but a
slightly better heuristic would be
consider slack which is your start - e
start you are really looking at the
interval u star lstart minus estart
during which you want to compute and we
want to schedule a node so it makes
sense to consider nodes with the lower
slack and give them higher priority that
is because you know you started in star
very close so you there's not much gap
between them so those nodes get higher
priority and those which have higher
slack value they can be star you know
they can be they have many more slots
der in which they can be scheduled so
they get a slightly lower priority
instructions on the critical path may
have a slack value of zero the real
start and restart values actually may
coincide and hence they get the maximum
priority so this is an example which we
saw already so here is another example
so let me show you how the e start
values and lstart values are really
computed so for example if you look at
this particular graph the ad sub and
store values are supposed to have one
cycle two cycles and three cycles
respectively in other ad sub store has
one cycle latency lower has two cycles
latency and mult has three cycle latency
the path length and slack are shown on
the left side and the right side of the
parentheses okay so eight is the path
length and zero is the slack okay
whereas within the parentheses we are
showing else east art and lstart so we
start with a value of 0 for e start and
then you know we compute 0 plus 2 as the
e start value for ad zero plus two for
the estart value of sub and from here to
plus you know this add 1 3 is one
possibility for this particular ad node
whereas on this side two plus one is
three is the only possibility for the
node mult and then we have you know for
this particular node we have three delay
slot the prior slots for multiply so 3
plus 3 6 is the start value for ad so
this side we get 3 and this side we get
6 so he start really is the max of these
so it is computed as 6 and then plus 1
is 7 for this particular
yes tea so this is how we start values
are computed so we will stop at this
point continue this example in the next
lecture when we're we are going to
discuss in more detail how the lstart
values are also computed and used for
scheduling thank you
you