paper evaluations: 05/30

Alejandro Hevia (ahevia@cs.ucsd.edu)
Tue, 30 May 2000 03:33:06 -0700 (PDT)


Evaluation of paper
"Memory Coherence in Shared Virtual Memory Systems"
by K. Li and P. Hudak

The paper discusses several protocols to implement shared virtual memory
on loosely coupled multiprocessors. Since, at any time, each processor may
reference arbitrary memory pages, multiple read or write operations
may be requested concurrently on the same pages. This is called the
memory coherence problem: any shared memory system must guarantee that
the value returned by a read operation must be the same as the value written
by the most recent write operation on the same address.

The paper describes several algorithms to implement a controlled access to
shared pages among processors. Roughly, it describes two classes of solutions:
centralized and distributed algorithms. In the former, there is a 'manager'
process that handles requests (from processors) to read/write pages owned by other
processors in such a way that consistency is maintained. In the latter,
processes themselves manage requests and grant permissions for accessing
memory pages. The basic page synchronization mechanism used by the algorithms
involves invalidation of all shared pages when any copy of it is written, and
dynamic page ownership (that is, the owner of each page may change with every
write operation). The three proposed algorithms are (a) an improved
centralized manager algorithm, where a manager process answers the question of
where a page owner is and each (owner) process handles read/write requests
re-assigning page ownership; (b) a fixed distributed manager algorithm, where
each process just manages a fix set of pages, and (c) a dynamic distributed manager
algorithm, where each process just keep track of its 'own' local pages (this
is claimed to be the most efficient one).

The paper's main contribution resides on providing concrete and efficient
implementation of solutions to the memory consistent problem. The paper is
remarkably clear regarding the considerations and factors required to solve
the coherence problem and how it can be solve based on primitives as simple
as page copy and locking. The experimental methodology seems slightly incomplete,
since a less synthetic experimental tests may have provide more realistic
performance performance of each proposed algorithm.

Interestingly, the paper mentioned several open problems in the area. Among
them, scalability (on the number of processes) of the shared memory algorithms
and optimal page size determining.

------------------------------------------

Evaluation of paper
"Implementing Global Memory Management in a Workstation Cluster"
by M.J. Feeley et al.

This paper describes the design and implementation of a global memory
management system (GMS) oriented to a workstation cluster in a fast network.
The system uses a probabilistic algorithm that manages and uses global information
about memory pages (age, status) and available memory resources on nodes.
The goal of the system is to minimize the total cost of all memory references
within the cluster. The authors propose an algorithm that is essentially an
extension of the LRU algorithm but incorporating factors as incomplete
(distributed) information and global/local location of the pages.
As a result, the resultant system promotes that active nodes get local pages
in their memory and inactive nodes get global pages in their memory,
thus optimizing global performance in the cluster. The algorithm relies on
several interesting techniques as careful page location (based on broadcast
information about available resources on nodes), replacing policies (page age,
global/local) and directory distribution schemes (which allow efficient
distribution of global information as mappings between virtual pages and node
location of physical pages).

The main contribution of the paper is to show that the use of distributed memory,
used as an efficient alternative to disk caching, can be implemented efficiently.
In principle, the success of this approach is justified by the fact that network
and CPU speed are far greater than disk speed in current workstation clusters.
Nevertheless, the actual proposed system outstands by its use of a smart, well
designed protocol that both efficiently identifies idle-memory machines (and keeps
global pages on them), and correctly locates pages in nodes where they are
likely to be most used again.

A rich set of open problems is also mentioned in the paper. Among them, improving
the system in several ways: against memory-greedy, non-trusted or malicious
processes, or imposing limits on the use of memory of remote nodes based on
the load of such nodes.