|
Abstract : |
The widespread availability of cheap workstations connected by a network has made possible their collective use as a parallel computer to solve large problems. The problem of implementing shared memory on the high latency networks that connect workstations, without suffering severe degradation in memory access times as the number of workstations increases, poses a special challenge. Traditional coherent memories are not scalable to more than a few tens of machines for most applications. Non-coherent memories that promise good scalability properties have been proposed and studied, in both the distributed systems and parallel architectures communities, albeit in the absence of a single unifying formal framework. In this paper we present a formal model, based on partial orders, within which we define and relate coherent memory and many of the existing non-coherent memories. Our framework enables us to define the notion of Local Consistency, a new non-coherent memory behavior that we view as the weakest constraint that should be required of shared memory. We briefly argue for mixing coherent and non-coherent memory in the same shared memory system, thus offering the programmer a choice of memory behaviors at different stages of program development or program execution. In a separate paper, we describe Mermera, a system that develops this approach. As evidence of the practical utility of non-coherent memory, we include in an appendix, a proof that Slow memory, a known very weak memory, is sufficient for a large class of parallel asynchronous iterative numerical algorithms., |
