So once, these locksense flags have been flipped, then all of the processors
that have been waiting on these locksense as respective nodes, they're going
to be released and everybody is now awake. So the tree barrier is a, a fairly
intuitive algorithm that builds on the simple centralized
sense reversal barrier except that it breaks up this And
processes into K-Sized groups, so that they can
all do spinning on a less contentious set
of shared variables. So that's good, that is
a, it's a recursive algorithm that builds on
the centralized sensor [UNKNOWN] algorithm, and allows scaling
up to a large number of processes. Because
the amount of shading is limited to k, and so long as the k is small,
like two or four, then the amount of contention
for shared variables is limited to, to that number.
So that's, those are all good things about that,
but there are lots of problems as well. The first
problem that I want you to notice is that
the spin location is not statically determined for each processor.
So for instance, if you take this particular execution
that I've shown you in this picture, P0 happens to
arrive later than P1. So P1 is the first
to arrive here and so when P1 arrived here, it
decremented count and it realized that oh, the count
is not zero, I'm going to spend here. And P0 arrived
later. And that's why it went up to the
next level. And, and it is spinning on this locksense
variable over here. So, in another execution of the same
program, it is possible that P0 arrives first. If P0
arrives first, then it'll spin on its locksense variable
that is in this data structure. And p one
will be the second guy to arrive, and therefore,
he'll be the guy that will move up. And
he'll be the guy that will be spinning on
this locksense flag. So, the locksense flag that a
particular processor is going to spin on, is not
statically detemined. But it is dynamically determined depending on
the arrival pattern of all these processes at a
barrier. And the arrival pattern, obviously, is going to be
different for different runs of the program. Since it
depends on the amount of code that is getting executed
on each one of these processors. And and other
variables such as how busy the processor is and so
on. And the second source of problem, is that
the airiness of the tree determines the amount of contention
for shared variables. I've mentioned that, you know, here it
is show, shown with two, two processors. But if you
increase the airiness of the tree to be key to
be something more than to maybe four or eight or something
like that. And if you have a large-scale multiprocessor with
with 1000 processors the editors of the tree may be much
more than 2, and in that case, the mode of
contention for said data structures is, is going be significant and
that can result in more contention on the network
as well. The other issue with this Tree Barrier
is that it depends on whether our multiprocessor that
we are executing this algorithm on is cache coherent
or not cache coherent. If it is cache coherent
multiprocessor, then, you know, the spin, even though it's
on a particular variable, it could be encached in
a private cache, and therefore, the cache coherent hardware
will indicate when the spin variable changes value. But if it's a non
cache coherent, multiprocessor, the fact the spin
variable that we have to associate with
a particular processor is not static, but
dynamic. Means that the spin may actually
be happening for P0 on a remote memory. Remember I mentioned to you that
one of the styles of architecture is a
distributive shared memory architecture? Sometimes the distributive shared
memory architecture is also called a non-uniform memory
access architecture, or NUMA And the reason it is
called numer architecture is because the access to
local memory for a particular processor is going to
be faster than the processor's access to a
remote memory. And if you don't have cache coherence,
then the spinning that has to be done, has to be done on a remote memory, and
that goes through the network. And so static association
of the spin location of the processor is very,
very crucial if it's a non-cache-coherent shared memory
machine. So the next algorithm that I'm going to
describe to you is due to the authors of
the paper that we are reviewing in this lesson,
which is [UNKNOWN] and Scott, and for this reason, that algorithm is
going to be called MCS barrier. It's also a tree barrier but you'll see that
in the MCS algorithm, the spin location is statically determined as opposed to
the dynamic situation that you have in the hierarchy of the tree barrier here.