benefit from running in the same domain. In that case, they may access the
shared resources cooperatively; for example, prefetch the data for each other
into the cache. While the effects of cooperative sharing must be factored into
a good thread-placement algorithm
for multicores, this subject has been
explored elsewhere. 9 The focus here is
managing resource contention.
understanding
Resource contention
To build a contention-aware scheduler,
we must first understand how to model
contention for shared resources. Modeling allows us to predict whether a
particular group of threads is likely
to compete for shared resources and
to what extent. Most of the academic
work in this area has focused on modeling contention for LLCs, as this was
believed to have the greatest effect on
performance. This is where we started
our investigation as well.
Cache contention occurs when two
or more threads are assigned to run on
the cores of the same memory domain
(for example, Core 0 and Core 1 in Figure 1). In this case, the threads share
the LLC. A cache consists of cache lines
that are allocated to hold the memory
of threads as the threads issue cache
requests. When a thread requests a line
that is not in the cache—that is, when it
issues a cache miss—a new cache line
must be allocated. The issue here is
that when a cache line must be allocated but the cache is full (which is to say
whenever all the other cache lines are
being used to hold other data), some
data must be evicted to free up a line
for the new piece of data. The evicted
line might belong to a different thread
from the one that issued the cache
miss (modern CPUs do not assure any
fairness in that regard), so an aggressive thread might end up evicting data
for some other thread and thus hurting
its performance.
Although several researchers have
proposed hardware mechanisms for
mitigating LLC contention, 3, 7 to the
best of our knowledge these have not
been implemented in any currently
available systems. We therefore looked
for a way to address contention in the
systems that people are running now
and ended up turning our attention to
scheduling as a result. Before building
a scheduler that avoids cache conten-
tion, however, we needed to find ways
to predict contention.
