CSE 121 Spring 2003 Homework 4

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.

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