Search

We are developing Munin y , a system that allows pro­ grams written for shared memory multiprocessors to be executed efficiently on distributed memory ma­chines. Thus, Munin overcomes the architectural lim­itations of shared memory machines, while maintain­ing their advantages in terms of ease of programming. A unique characteristic of Munin is the mechanism by which the shared memory programming model is translated to the distributed memory hardware. This translation is performed by runtime software, with the aid of semantic hints provided by the user. Each shared data object is supported by a memory coher­ence mechanism appropriate to the manner in which the object is accessed. This paper focuses on Munin's memory coherence mechanisms, and compares our approach to previous work in this area. This research was supported in part by the National Science Foundationunder Grants CCR­8716914 and DCA­8619893 and by a National Science Foundation Fellowship. y In Norse mythology, the ravens Munin (Memory) and Hugin (Thought) perched on Odin's shoulder, and each evening they flew across the world to bring Odin knowledge of man's memories and thoughts. Thus, the raven Munin can be considered to have been the first distributed shared memory mechanism.

Munin is a distributed shared memory (DSM) system that allows shared memory paral­lel programs to be executed efficiently on distributed memory multiprocessors. Munin is unique among existing DSM systems in its use of multiple consistency protocols and in its use of release consistency. In Munin, shared program variables are annotated with their expected access pattern, and these annotations are then used by the runtime system to choose a consistency protocol best suited to that access pattern. Release consistency allows Munin to mask network latency and reduce the number of messages required to keep memory consistent. Munin's multi­protocol release consistency is implemented in software using a delayed update queue that buffers and merges pending outgoing writes. A sixteen­processor prototype of Munin is currently operational. We evaluate its imple­ mentation and describe the execution of two Munin programs that achieve performance within ten percent of message passing implementations of the same programs. Munin achieves this level of performance with only minor annotations to the shared memory programs.

Distributed shared memory 8DSM) is an abstraction of shared memory on a distributed memory machine. Hardware DSM systems support this abstraction at the architecture level; software DSM systems support the abstraction within the runtime system. One of the key problems in building an efficient software DSM system is to reduce the amount of communication needed to keep the distributed memories consistent. In this paper we present four techniques for doing so: 1) software release consistency; 2) multiple consistency protocols; (3) write-shared protocols; and (4) an update-with-timeout mechanism. These techniques have been implemented in the Munin DSM system. We compare the performance of seven Munin application programs, first to their performance when implemented using message passing, and then to their performance when running on a conventional software DSM system that does not embody the above techniques. On a 16-processor cluster of workstations, Munin’s performance is within 5% of message passing for four out of the seven applications. For the other three, performance is within 29% to 33%. Detailed analysis of two of these three applications indicates that the addition of a function shipping capability would bring their performance to within 7% of the message passing performance. Compared to a conventional DSM system, Munin achieves performance improvements ranging from a few to several hundred percent, depending on the application.