From: Richard Jackson (richja_at_expedia.com)
Date: Wed Feb 18 2004 - 11:01:42 PST
This 1989 paper by Li and Hudak discusses various methods for managing
memory coherence in a virtual memory system. The paper covers each of
the main alternatives in detail, so it can be used as a reference when
building these systems. The authors also identify their method of
choice and give some analysis regarding performance.
The paper is divided into the following sections: 1) overview of
problem space, 2) high-level discussion of various memory coherence
schemes, 3) drill-down into various flavors of dynamic memory coherence
schemes, 4) performance analysis.
First, the general problem is described - it is the management of
virtual memory among "loosely-coupled" multiprocessors. The term
"loosely" was used throughout the paper and was not well-defined,
although it seems to mean that we're using distributed virtual memory
that is shared among the processors vs. a single non-virtual memory that
is shared. First, two key design considerations are presented:
granularity vs coherence. Granularity is the size of each memory unit,
where smaller is generally better for preventing concurrency issues.
Granularity of 256 to 2k bytes is suggested as a best practice .
Regarding coherence schemes, which is the main focus of the paper,
various options are presented. These options can be roughly be divided
into two classes: static and dynamic. Static means that each portion of
the memory space is managed by each processor and therefore requires
that all other processes negotiate with this processor when accessing
its data. Dynamic means that each processor's memory space can be
managed according to its needs or the overall needs of the system in a
much more dynamic fashion. The authors quickly discard the static
schemes, saying that they don't work for a loosely-coupled distributed
system. The rest of the paper discusses the dynamic schemes.
Various methods for dynamic memory coherence are discussed. There are
two classes of managing dynamic memory coherence: central and
distributed. For central the paper discussed two options, which are:
1) monitor-like central manager - handles page location,
synchronization, and locking, 2)improved central manager - handles only
page location, synchronization is done by the individual processors.
For distributed, the paper discussed five different options : 1) fixed
distributed manager - each processor manages access to a fixed set of
pages(it was unclear to me how this differs from the static scheme), 2)
broadcast distributed manager - discovery is done by broadcasting to all
nodes(results in a communication bottleneck), 3) dynamic distributed
manager - each processor attempts to keep pointers to location of each
page, though some may be incorrect. Incorrect pointers are fixed by
querying other nodes(somewhat like CFS algorithm, I think) 4) dynamic
distributed manager with fewer broadcasts - optimization of #3, 5)
dynamic distributed manager with distributed copy_sets - a further
optimization of #3 and #4. For most of the schemes discussed, the
paper also provides pseudocode to supplement the explanation.
Finally, performance is discussed. The paper only compares 2 dynamic
algorithms : central and dynamic distributed, and the graphs show that
the latter performs better. It was not clear exactly which version of
each of these algorithms was used, the base version or the refined
version. I found the analysis in this section to be very confusing and
lacking in necessary details. They should have included performance
analysis for all of the schemes that were discussed, not just a couple.
This leads me to believe that their results are not completely valid, or
may be overstated. The main point of this section is that dynamic
management schemes perform better than central management schemes.
Overall, this paper seemed to share some of the same general concepts as
the Anderson paper on thread management alternatives. That is, more
processor-local control gives better performance.
This archive was generated by hypermail 2.1.6 : Wed Feb 18 2004 - 11:02:53 PST