So let me briefly introduce here the idea of cache
aware scheduling, when you have
these multithreaded multi-core processors. And to
make things concrete, let's assume that you have a pool of
ready threads, and in this case I'm going to tell you that
the pool of ready threads I have is 32. So I
have 32 ready threads and I have a four way multi-core
per CPU. Meaning that there are four cores in the CPU,
and each core is four way hardware multithreaded. Or in other
words, at any point of time the operating system
can choose from this pool of ready threads, 16
threads to be run on the processor. Because that's
the number of hardware multi-threads that are available if
you pool together all the four cores. So each
core has four multi, hardware multi-threads, together they have
1,600 threads that can be run on the CPU at any point of time. And the, the job
of the operating scheduler is to pick from
the available pool of ready threads, 16 candidates
to be scheduled on the CPU. So how
does the operating system choose the 16 threads
to be run on the CPU at any point of time? What the operating system should
try to do, is it should call schedule
some number of cache frugal threads, and some number
of cache hungry threads on the different course so that together the sum of all
the cache hungriness of the 16 threads that
are executing at any point of time in
the CPU is less than the total size of the L2 cache. And as I said,
L2 cache in this simple example, I gave you two levels of caching, a caching
that is associated with each of these cores, and an
L2 cache that is sitting outside of these cores, but
it is, it is common to all the four cores.
But of course, you can generalize this and say it is
the last level cache, or in other words, you want to
make sure that this, the universe of threads that are scheduled
at any point of time, on the CPU, the sum
total of the cache requirements of the universe of thread schedule
on the processor, is less than the total capacity
of the last level cache in the CPU. Because
if it's missing the last level cache on the
CPU, you're going outside the chip, out of memory,
long latency operation, bad news. That's the thing that
you're trying to do. So we're going to categorize threads
as either cache frugal threads, or cache hungry threads.
So cache frugal threads are one in, ones that require
only a small portion of the cache to keep them
happy. On the other hand, a cache hungry thread is
one that requires a huge amount of cache space in
order to keep it happy, meaning that the working set of
cache hungry threads is much bigger than the working set
of cache frugal threads. Now how do we know which
threads are cache frugal and which threads are cache hungry?
Well that's something that we can know only by profiling the
execution of the threads overtime. So the assumption is
that many of these threads get to run on
the CPU over and over again, so overtime you
can profile these threads and figure out whether a
particular thread belongs to this category of cache frugal
thread or this category of cache hungry thread. And
the criterion that you want to use in picking the
set of threads to be populated in the CPU
at any point of time from the pool of available threads, is to make sure that
the sum of the cache requirement of all
the cache frugal threads is that there are
N cache frugal threads and there are M cache hungry
threads, then the cumulative cache requirement of all the threads
put together is less than the total size of the L2 cache.
And then I told you, we can generalize this L2 cache
to the last level cache, that is the cache that is
sitting at the last level inside the CPU beyond which you
had to go out of the chip, go out to memory,
and so that last level cache becomes the determinant in saying
whether the size of that last level cache is within bounds
of the cache requirements of all the threads that I want to
schedule. So this is the set of threads that I want to pick,
where, in this particular case, since the total
number of hardware threads that I have available to
me is 16, I want to make sure that
M, the cache hungry threads, N, the cache frugal
threads, is 16 and this inequality is satisfied
as well. So that's what we want to shoot
for in picking the set of threads to run on the processor at any point of time.
I mentioned that we have to profile these
threads, or monitor these threads as they're executing
in order to figure out their cache occupancy
over time so that we can categorize these
threads as cache frugal or cache hungry, and
the more information the scheduler has, the better
decision it can take in terms of scheduling.
Be we have to be careful about that.
In order for the system to do this monitoring
and profiling, clearly, the operating system has to lose some
work in the middle of these threads doing useful
work. And I always maintain that a good operating system
gives you the resources that you need and gets
out of the way very quickly. And so, you have
to be very careful about the amount of time
that the operating system takes in terms of doing this
kind of monitoring and profiling, and this information is
useful in scheduling decisions, but it should not be
disrupting useful work that these guys have to do
in the first place. Or in other words, the
overhead for information gathering has to be kept minimal
so that the OS does not consume too many
cycles in doing this kind of overhead work accounting
for making better decisions in, in terms of scheduling.