From: Sellakumaran Kanagarathnam (sellak_at_windows.microsoft.com)
Date: Wed Feb 18 2004 - 11:45:37 PST
This paper discusses two sets of algorithms for solving the memory
coherence problem in the shared virtual memory systems on loosely
coupled multiprocessor systems. The authors also share the results of
their experiments with a prototype.
Loosely coupled multiprocessor system is one in which the physical
memory is distributed between the processors and the virtual address
space is shared among all the processors. This leads into memory
coherence problem. A memory is coherent if the value returned by a read
operation is always the same as the value written by the most recent
write operation. The authors discuss the granularity of the memory unit
that has to be coherent. A suitable value of this memory unit would be
same of that of the page size in the virtual memory implementation.
The authors then present a table of strategies based on page
synchronization and page ownership choices. There are two approaches to
page synchronization: invalidation and write back. Basically in the
invalidation approach, whenever a processor has a write fault, the
processor gets the true page from the owner, gets ownership and
invalidates all other copies. In the write-back approach, on write
fault, the processor will write to all copies of the page. This closely
simulates shared memory, but every write will update all copies which is
very expensive. And the authors do not consider write-back approach any
further. Similarly, the authors dismiss the static page ownership
approach. Henceforth the paper discusses the three dynamic page
ownership approaches using invalidation for memory coherence.
The paper first details a centralized manager approach and then improved
upon it. These approaches use two tables: info table and page table.
And the algorithm is characterized by read and writes fault handlers and
their servers. In this approach the manager multiple requests from
different processors. And the worst case number of messages to locate a
page is two. But there is also confirmation message involved in a
non-manager processor fault. The improved algorithm that is discussed
next takes away the synchronization of page ownership from the manager.
Still for a large N, the manager processor might become a bottleneck as
there is only one manager. Then the authors introduce distributed
manager algorithms: fixed distributed manager algorithm, broadcast
distributed manager algorithm, dynamic distributed manager algorithm and
a dynamic distributed manager with fewer broadcasts and finally a
refinement in the distribution of copy_sets (where copy_set is stored as
a tree of processors, which makes invalidation or finding the owner
faster). First two graphs show that dynamic distributed manager
algorithm outperforms the centralized manager algorithm for the chosen
programs. The next few graphs did not mention what algorithms are being
used.
The paper is systematic in introducing the approaches, and discussing
them further. It starts with a solution, and then improves upon it in
successive approaches. The discussion is very detail and the algorithm
is discussed to the level of pseudo code.
This archive was generated by hypermail 2.1.6 : Wed Feb 18 2004 - 11:46:01 PST