Memory Coherence in Shared VM Systems

A single address space is shared by all processors

	Any processor can access memories of other processors plus its own local memory
	Local memory is a big cache for the local processor
	Read-only pages can have multiple copies residing multiple local memories and these multiple copies need to be maintained coherent to each other
	Each processor has a mapping manager, which: translates virtual address to physical address handles page faults by bringing the page from disk or other processor's memory cooperates with other mapping manager to achieve cache coherence

Model of parallel program: multiple threads possibly running on multiple processors share a single virtual address space

To achieve high parallelism, process manager(= tread manager) and memory allocator should be tightly coupled with mapping manager. This paper does not deal with process manager nor memory allocator

Previous works

	Massive works on VM, but mainly on uniprocessor system
	Previous works on data sharing were mainly done on distributed computing rather than parallel computing

Alternatives for data sharing in loosely coupled multiprocessor system

	Message passing No transparency: programming application is difficult Passing complicated data structures is difficult
	Providing programmers a set of primitives handling shared global data Need user's explicit control Inefficient: even if data are in local memory, they should be accessed via those primitives(=function call) Difficult to migrate program
	Shared virtual memory Transparent Once paged in, memory reference is as efficient as conventional one

The system was redesigned for Lotus OS Kernel

Why not multi-cache coherence algorithm?

	Multi-cache algorithms are mainly for the setting of A single memory shared by multiple processors with its own cache cache is relatively small bus connecting the memory and caches is fast Time delay for resolving conflict writes must be short
	But in loosely coupled environment of this paper, communication cost is relatively high, so the number of communication should be much reduced

Two design issues: page size & memory coherence strategy

Spectrum of solutions to the memory coherence problem: X-axis - ownership & Y-axis - synchronization

This paper only considers green cells

Each process usually has its own page table, whose fields are:

	access: rights of the processor to the page
	copy set: the set of processors which have read copy of the page
	lock: tag indicating whether the page is locked or not

lock is an atomic operation which blocks the requesting process until the lock is granted

unlock releases the lock and schedule a process from the queue of processes waiting for the lock

To invalidate a page, the requesting processor should usually broadcast a message to processors in the copy set of the page

Central manager has a table called 'info' which has an entry for each page, each entry having fields:

	owner: the owner process, namely the most recent processor which has write access to it
	copy set
	lock

Each processor has a page table, PTable, with fields: access & lock

Read page fault

(11) manager: unlock info[page#]

Central manager could become a bottleneck, so synchronization is moved to each owner

Read page fault

(11) requestor: unlock PTable[page#]

At this point you may want a quick review of Locus file systems

Each processor is given a predetermined subset of pages to manage

Mapping pages to appropriate processors is a difficult task and uses a hash function

Page fault handling applies the hash function to get the manager for the page and follows the same procedure as centralized manager

It is difficult to find a good fixed distribution function that fits all application well

Owner = Manager, actually no manager at all

All broadcast operation should be atomic. I don't know why. Consider the situation:

	P1 and P2 request write access at the same time
	P1's request gets to the owner P3 first
	In the meantime that P3 releases its ownership and P1 has not accepted the new ownership, P2's broadcast could arrive P1. But the P2's request will be queue because PTable[page#] is locked at this moment!

Too many messages are generated and unrelated processors wastes time processing and ignoring those messages

Note: probOwner is just a hint and a starting point to find the real owner of the page

Two questions

	Does forwarding request eventually arrive at the true owner? Yes
	How many forwarding requests are needed? At most (N - 1), N = # of processors. O(N + K log N) for K tries for the same page

Important observation

The number of messages for finding the owner is logarithmically proportional to the number of contending processors

By periodically broadcasting the real owner, the number of steps to find the owner can be reduced. Then how often? See the table II and III.

So far only the copy-set of the owner is correct and complete. This requires that:

	the page should be copied from the owner to maintain the copy-set correct
	invalidation should be broadcasted from the owner to every copy-holders

Ideas

	copy the page from any of copy holder
	maintain copy-holders in a tree (with the owner as the root)  and propagate invalidation from the owner

(12) copy holders: unlock PTable[page#]

Parallel Jacobi program

Parallel sorting

Parallel matrix multiplication

Parallel dot-product

Super ideal speed-up for Jacobi program!

Virtual big memory gives more speed-up to the speed-up gained by multiprocessor

Why did shared virtual memory show poor speed-up for parallel dot-product problem? Communication cost is too high