Modern parallel machines offer a lot of challenges
in converting the algorithms and the techniques that
we have learned so far into scalable implementations.
Now what are some of these challenges? Well
first of all, there's a size bloat of
the operating system. And the size bloat comes
because of additional features that we have to
add to the operating system and so on.
And that results in, in system software bottlenecks, especially
for global data structures. And then, of course, we
already have been discussing this quite a bit, that
the memory latency to go from the processor to
memory is, is huge. All the cores of the processor are on a chip, and if you go
outside the chip to the memory, that latency is
huge. 100 to one ratio is what we've been talking
about and that latency is only growing. The
other thing that happens in parallel machines is the
fact that, this is a single node. And
we're talking about the memory latency going from the
processor to the memory. But in a parallel machine, it's typically constructed
as a non-uniform memory access machine. And that is, you take
individual nodes like this that contains a processor and memory and
put all them together and connect them through an
interconnection network. And what happens with this NUMA architecture
is that access, there's differential access to memory whether
this processor is accessing memory that is local to it,
or it has to reach out into the network
and access some memory that is farther away from
where it is. In addition to the NUMA effect,
there is also the memory hierarchy itself is very deep.
We already talked about the fact a single
processor these days contains multiple levels of caches before
it goes to the memory. And this deep memory
hierarchy is another thing that, that you have to
worry about in building the operating system for a
parallel machine. And there is the issue of false
sharing. And false sharing is essentially saying that even
though programmatically there is no connection between a piece
of memory that is being touched by a
particular thread executing on this core, another thread
that is executing on, on this core. The
cache hierarchy may make the block that contains the
individual memory touched by different threads on different
cores to be on the same cache block. So,
programmatically, there's no sharing, but because of the
fact that the memory that is being touched by
a thread on this core, and a memory that
is being touched by a thread on this core happen
to be on the same cache line, they appear
to be shared. That's what is false sharing. False sharing
is essentially saying that there is no programmatic sharing
But, because of the way the cache coherence mechanism operates,
they appear shared. And this is happening more and more
in modern processors, because modern processors tend to employ larger
cache blocks. Why is that? Well, the analogy I'm
gong to give you is that of a handyman. If
you're good at doing chores around the house, then
you might relate to this analogy quite well. You probably
have a tool box if you're a handyman. And
if you want to do some work, let's say a
leaky faucet that you want to fix, what you
do is you put the tools that you need into
a, a tool tray and bring it from the tool box
to the site where you're doing, doing the work. And basically, what
you're doing there is, you know, collecting the set of tools
that you need for the project so that you don't have to
go running back to the tool tray all the time. That's
the same sort of thing that's happening with caching and memory. Memory
contains all this stuff but what I need, I want to
bring it in. And the more I bring in from the memory,
the less time that I have to go out to
memory in order to fetch it. That means that I want
to keep increasing the block size of the cache, in
order to make sure that I take advantage of spatial locality
in the cache design. And that increases the chances that
false sharing is going to happen. The larger the cache line,
the more chances are that memory that is being touched
by different threads happen to be on the same cache block,
and that results in false shading. So all of
these effects, the NUMA effect, the deep memory hierarchy,
and increasing block size leading to false sharing, all
of these are things that the operating system designer
has to worry about in making sure that the
algorithms and the techniques that we have learned, when
it is translated to a large scale parallel machine,
it remains scalable. So that's really the challenge that
the operating system designer faces. So some of
the things that the OS designer would have to
do is work hard to avoid false sharing, work
hard to reduce write sharing the same cache line.
Because if you write share the same cache
line, then it is going to result among different
cores of the same processor, then it's going to
result in the cache line migrating from one processor
to another. And even within the same core
and even within the same processor, multiple cores,
and across processors that are on different nodes
of parallel machine, connected by the interconnection network.