CSE 121 Spring 2003 Homework 4
Solutions
Problem 1
Consider the Successive Over-Relaxation example
in the Munin paper. They give a "detailed analysis" of how the communication
occurs when declaring the matrix to be producer-consumer. Give
a similar analysis of how the communication would occur if the matrix were
instead declared to be write-shared.
I'm copying the text right from the paper, but changing
it to reflect the different annotation. The main difference between the two
(as noted in Table 1) is that producer-consumer assumes a stable sharing
pattern, while write-shared does not.
- During the first compute
phase, when the new average of the neighbors is computed in the scratch array,
the node read-faults in copies of the pages of the matrix as needed.
- During the first copy phase, when the newly computed values are copied
to the matrix, nodes write-fault, enqueue to appropriate pages on the DUQ,
create twins of these pages, make the originals read-write, and resume.
- When the first copy phase ends and the worker thread reaches the barrier,
each page in the DUQ is flushed to the processors in its Copyset.
Since there is a twin, a "diff" of the page is sent.
- Subsequent phases behave in the same manner, since Munin assumes no
stable sharing pattern.
Problem 2
The Ivy paper Memory Coherence in Shared
Virtual Memory Systems describes several different methods of implementing
a manager. In Section 5.3 they describe a dynamic distributed manager. Give
an execution in which it would take more than one forwarding request message
to locate the owner of a page.
This can happen in the most direct manner. Assume that processor 1 has write
access to the page, and processors 2 and 3 both have the probable owner set
to processor 1. Only processor 1 has the page mapped, of course. Processor
1 passes the page ownership to processor 2 as a result of a write fault on
2.At this point, processor 1 and 2 have the probable owner set to 2, while
processor 3 still has the probable owner set to 1. If processor 3 has a page
fault, it will ask processor 1 for the page, which will need to forward it
to processor 2.
last edited by Keith Marzullo on 11 June 2003