So at this point, when p0 is declared the champion
of the tournament, what we know is that everybody has
arrived at the barrier. And this knowledge is available with
p0 but not with anybody else. So everybody, everybody has arrived
at the barrier, but P0 is the only one who
knows because he's a champion, he knows that, that everybody has
arrived at the barrier. So clearly, the next thing that
has to happen is of course free up all the processors
to indicate to them that you know, its time to
move on to the next phase of your computation. So let's
talk about the wake up. So what p0 is going to do
is is going to tell p4 that it's time to wake up.
And you know, if you want to use the tournament
analogy again, in any tournament the winner walks over to the
loser and shakes hands, right? So, you can sort of think
of the same thing happening over here, P4 with the [INAUDIBLE]
face is waiting for P0 to come over, and let
him know that okay, its a good match and shake
hands with you. And so, P0 is going to come
over and let him know, shake hands. So that's the first
thing that happens. So in other words, at this point
P0 is awake of course, and he is also waking
up P4 saying that well barrier is done. And now
one of these guys can go to the next level and
do the honours at every level so, just as I
said about P0 coming in and shaking hands with P4, what
P0 is going to do is, go to the next round
and shake hands with P2, P4 go to the next round
and shake hands with P6 and, and so on. And
of course, if you think about the analogy of a tournament,
as soon as the match is over, the winner is
going to shake hands with the loser. But in this case,
the winner shakes hands with the loser after the
tournament is all done. So at every level, we're going to
have that. So, its essentially, P0 and P4 come down
to the next level and they shake hands with the
respective losers of that level. And as I said, if
we have for some arbitrary N, where N is a
binary power, you're going to have this kind of propagation
of wake-up signals going from the winner to the loser
at every round. And all of them wake-up and go
to the next level. Because all of these guys are winners
from the previous level. So, all of these winners will
go down to the next level and wake up the losers
at that level. So that's what is going to happen. Again, what that means from
the point of view of a shared memory multiprocessor is that the spin location
for P4, P2, and P6, it's all fixed, right? Statically determined. If P4 knows
that P0 is going to come over and shake hands, and so that he can spin on a
local variable that is close to it's processor, and so again this is important
for NCC NUMA machines in which there is
no cache coherence and therefore it is convenient
if P4 can be spinning on a memory
location that is close to the processor. Same thing
with P2 and P6 at the next level. So this process of waking up the losers at
every level goes on till we reach round 1. And when at round 1, all the winners
have congratulated. Well, not congratulated, [LAUGH] but shook
hands with the respective losers at the first round.
At that point, the wake up is complete. Everybody's
awake now. And, and, the, the barrier is done.
So all are awake, and the barrier is done, and
they can move on, the next phase of the computation.
And once again, in order to make sure that there
is sense reversal, everybody knows that this barrier is done, and
they're going to go to the next phase of the computation
where they will wait on the different [INAUDIBLE] of the barrier.
. So, that's Tournament Barrier Algorithm. So the 2 things
that I want you to take away is, the arrival moves
up the tree like this, with match fixing. And all the respective winners at
every round, waiting on a statically determined
spin location. And similarly, when the wake up
happens, the losers are all waiting on
statically determined spin location in their respective
processors and the winner comes over at
every level at every round of the tournament,
the winner comes over and tells the loser that
it's time to wake up. So that's how this
whole thing works. So now that we understand this
tournament algorithm let's talk about the virtues of this algorithm.