From: Muench, Joanna (jmuench_at_fhcrc.org)
Date: Wed Feb 18 2004 - 13:59:27 PST
Li and Hudak (1986) explore the issues involved in implementing a shared
virtual memory within a multiprocessor system. The paper illuminates the
multiprocessor issues touched on by Rashid et al. (1987) earlier in our
syllabus, specifically maintaining coherence. The authors not only present
their final design, but also cover the roads not taken, providing a solid
basis for the prototype they built.
Some of the issues that the authors touch on are the optimal size of the
memory units, the benefits of invalidation over writeback and the efficiency
of dynamic vs. static page ownership. More important to their implementation
is the manager algorithm, a topic echoing many of the issues we discussed
earlier in RPC. The authors start by presenting a centralized manager
algorithm, which requires a maximum of two messages to locate a page, and
discuss an improved centralized manager algorithm that is able to eliminate
a confirmation step. To avoid the potential bottleneck of having a central
manager processor, the authors propose a distributed manager algorithm. They
explore using broadcast mechanism but settle on a chained approach where
each processor knows only the prob_owner of a page, allowing a chain of
forwarding addresses. We've seen this idea a few times now, for instance in
the Emerald system, with the shadow objects in Mach seeming somewhat similar
as well. Since this paper pre-dates both of those efforts, I would be
interested in knowing who first thought up this scheme.
The accompanying suite of pseudo-code, lemmas, theorems and corollaries were
a nice component of the paper. While some of the earlier theorems seemed
obvious, some (such as Theorem 4.5) helped motivate further improvements to
the distributed manager algorithm.
Finally, the results provided a good sanity check on how the system worked
in a ring network of Apollo workstations. The benefit of the distributed
manager algorithm was quite clear. The problems of efficient sorting made me
wonder if there is a better algorithm for performing a parallel sorting on
multiprocessors.
This archive was generated by hypermail 2.1.6 : Wed Feb 18 2004 - 14:01:48 PST