From: Nathan Dire (ndire_at_cs.washington.edu)
Date: Wed Feb 18 2004 - 12:59:36 PST
In "Memory Coherence in Shared Virtual Memory Systems", Li and Hudak discuss
alternatives for . The shared virtual memory system described in the paper is
a single address space shared by processors with private memories. Data can
migrate into any processor's memory, in fact, images of whole processes can be
migrated. The main difficulty of this system is coherence.
This paper lists three basic design choices for the shared vm system. First,
the granularity of the pages is a trade-off between locality and contention
since larger pages reduce the number of faults, but may increase the number of
faults due to invalidation. Page synchronization may be "invalidation" or
"writeback". Finally, page ownership may be static or dynamic. In this
paper, the authors restrict their discussion to invalidation with dynamic page
ownership.
The first option for managing dynamic page ownership is centralized--only one
processor knows the owner for each page. The authors' proposed algorithm is
similar to a monitor. The central page manager has a control block to provide
synchronization and keep track of which processors have a copy of the page. A
suggested improvement is to let the owner of a page handle the synchronization
by having the central manager simply forward requests to owner, chaining the
owner on each request. Ultimately, this approach suffers from the bottleneck
created at the manager.
The obvious solution to the central bottleneck is to distribute the management
of page ownership among the processors. The first proposal is to give each
manager a predetermined subset, defined by some hashing function. This is not
flexible enough for all applications; another option is to broadcast to find
the true owner of a page, but broadcasting of course loads the interconnect.
Another approach is to have each node keep track processor which obtained the
page from the local processor, leaving a trail to the current owner.
One refinement to this is to periodically broadcast the owner of a highly
contended page so that the trail to the owner is likely to be short. The
final refinement is to keep track of the copy_sets as a tree, allowing the
trail to be log(n) in the number of processors.
I suspect that the idea of shared virtual memory becomes less and less useful
as the difference between processor speed and interconnect latency grows, but
I think the principles outlined in this paper have wide application to
distributed systems. For example, finding the owner of a page might be
comparable to finding the registry of a name in a Grapevine distribution list.
Or, the owner of page might be analogous to the owner of a lock for a
distributed lock manager. Also, the evolution of the algorithms for page
management are slightly suggestive of the methods outlined in the thread
management paper. So I see the relevance of the ideas in this paper, even if
shared virtual memory itself is not viable.
The paper seems weak on empirical measurements, though I suppose the
methodology is typical for papers of that time. It seems that there are a lot
of factors that would influence the results which aren't discussed.
This archive was generated by hypermail 2.1.6 : Wed Feb 18 2004 - 12:59:38 PST