Title:  Distributed Parallel Computing in Mermera:
	Mixing Noncoherent Shared Memories
Author: A. Heddaya and H.S. Sinha (GTE Labs)
Date:   March 7, 1996
                                                                
Abstract:

Programmers of parallel processes that communicate through shared globally
distributed data structures (DDS) face a difficult choice.  Either they must
explicitly program DDS management, by partitioning or replicating it over
multiple distributed memory modules, or be content with a high latency
coherent (sequentially consistent) memory abstraction that hides the DDS'
distribution.  We present Mermera, a formalism and system that enables a
smooth spectrum of noncoherent shared memory behaviors to coexist between the
above two extremes.  Our approach allows us to define known noncoherent
memories in a new simple way, to identify new memory behaviors, and to
characterize generic mixed-behavior computations.  The latter are useful for
programming using multiple behaviors that complement each others' advantages,
and for programming by step-wise refinement.

On the practical side, we show that the large class of programs that use
asynchronous iterative methods (AIM) can run correctly on slow memory, one of
the weakest, and hence most efficient and fault-tolerant, noncoherence
conditions.  An example AIM program to solve linear equations, is developed to
illustrate the need for concurrently mixing memory behaviors, and the
performance gains attainable via noncoherence.  Other program classes tolerate
weak memory consistency by synchronizing in such a way as to yield executions
indistinguishable from coherent ones.  AIM computations on noncoherent memory
yield noncoherent, yet correct, computations.  We present performance data
that illustrate the benefits of noncoherence, in terms of raw memory
performance, as well as application speed.

Keywords: Distributed parallel computing, noncoherent shared memory,
	  asynchronous iterative algorithms, network of workstations.