From: Brian Milnes (brianmilnes_at_qwest.net)
Date: Tue Feb 17 2004 - 23:19:16 PST
Memory Coherence in Shared Virtual Memory Systems - Kai Li and Paul Hudak
The authors devise a shared virtual memory system for loosely coupled
network that allows processor to processor page swapping and process
migration. They consider only invalidate algorithms with dynamic ownership
of architecture page size.
The first algorithm the consider is a centralized manager which tracks an
owner and a set of readers and keeps a lock for each page. It requires two
messages to find any page. They then improve this to reduce the number of
confirmation messages from machines that are reading the page.
The central manager may become a bottleneck so they consider five
distributed algorithms. The first case is they hash out the pages to all of
the machines; this works well but can always have a pathological case. The
second case is to broadcast out the requests to read and write a page; this
has the disadvantage that all processors must attend to all network traffic.
In the third case a central server has default ownership of all pages but
each customer follows a trail of probable owner links, worst case O(N-1).
The fourth case reduces broadcasts by only broadcasting on 1/Kth of the page
faults. The fifth case distributes the copy set as a tree.
The authors then test their algorithms using three distributed algorithms
and conclude that their shared virtual memory is practical. I would like to
see this redone given a more modern processor to network ratio and on
something other than a scientific workload. Something like a distributed
read emphasized database would be a more reasonable application.
This archive was generated by hypermail 2.1.6 : Tue Feb 17 2004 - 23:19:45 PST