You will immediately notice that there's a lot of
similarity between the Tournament algorithm and the the sensor
verse, interversing tree algorithm and also similarity to the
[UNKNOWN] algorithm. So let's talk about the difference between
the tree barrier and the tournament barrier first. So
the, the, the main difference is that in the
tournament barrier, the spin locations are statically determined, whereas
in the tree barrier we saw that the spin locations
are dynamically determined based on who arrives
at a particular node in the barrier,
in the tree in that algorithm. And what that means in the tournament barrier is
that we can statically assign. The spin
location for the processes at every round
of the tournament. Another important difference between
the tournament barrier and the the tree barrier,
is that there is no need for a fetch
and free operation. Because all that's happening at every
level. At every round of the tournament, there is
spinning happening. And what is spinning? Basically reading. And
there is the signaling happening, what is this? This
is just writing. So, so long as we have
atomic read and write operations in the multi-processor, that's
all we need in order to implement the tournament barrier.
Whereas uh, if you recall in the tree barrier
we need fetch and free operation in order to atomically
decrement the count variable. So that doesn't exist in
the tournament barrier. That's, that's another good use. Now what
about the total amount of communication that is needed.
Well, it's exactly similar because of the tree arrangement. As
you go up the tree the amount of communication that
happens is going to decrease. Because the tree is getting pruned
as you go towards the root of the tree and
so the amount of communication in the tournament barrier in
terms of all the notation is exactly similar to the
tree barrier it is older, login. That's the amount of communication
that is needed. Now the other important thing that that
I should mention is that at every round of the
tournament you can see that there, there's quite a bit
of communication happening. In the first round going up the tree,
P1 is communicating with P0, P3 with P2 and so on. All of these red arrows. Are
parallel communications that potentially take advantage of any
inherent parallelism that exists in the interconnection network. So
that's good news. That, that all of this
communication can happen in parallel if the interconnection network
allows that kind of parallelism. That can be exploited.
And the, the other important point that I want
you notice is that the tournament barrier works even
if the processor is not a shared-memory machine. Because
all that we're showing here is a message communication.
So P1, P0 is waiting for a message from
P1, and so on. So all of these arrows you can think of them as messages. And so
even if the processor the multiprocessor is a cluster,
well by a cluster what I mean is a
set of processes in which the only way
they can communicate with one another is through
message passing. There is no shared memory, no
physical shared memory. And even in that situation the,
the tournament barrier will work perfectly fine to
implement the barrier algorithm. Now let's make a comparison
of tournament to to NCS. Now because this
tournament is arranged as a tournament there are only
two processes involved in this communication at any
point of time in the parallel. So it means
that it cannot exploit the spatial locality that
may be there in the caches. If you recall,
one of the virtues of the NCS algorithm
is that it could exploit spatial locality. And that
is, multiple spin variables could be located in
the same cache line and, and the, the parent
for instance could spin on a spin location
to which multiple children are going to come and indicate
that they are done. That's not possible in the,
the tournament barrier because it is arranged as a
tournament where there are two players playing against
each other in every match. Similar to MCS, Tournament
Barrier does not need a fetch and fee operation,
so that's good. A common good property of both
MCS and Tournament. The other important thing what tournament
has an edge over MCS is the fact that tournament
barrier works even if the processors are in a
cluster. Meaning, it's not a shared memory machine and is
only a cluster machine where only message passing is
really good communicator to one another. Even in [INAUDIBLE] that
situation, you can implement the tournament barrier. So that's, another
good thing. Now is a good time for me to
mention to you. I've been using the word cluster what that means is that the
set of nodes in the multiprocessor they don't
physically share memory and the only way they
can communicate with one another is through
message passing. And is important for you to
know this particular terminology cluster because clusters become
the work horses for data intensive computing today.
The data centers and content distribution networks we're
going to see a lot of that when we
talk about giant skin services later on in
this course, and those environments, they all use this
kind of a, a, a computation cluster. And
these computation clusters employ on the order of thousands
or 10000 nodes connected together through an interconnected
network and they can operate as a parallel machine
with only message passing as the vehicle for communication among the processes.