CSC/ECE 506 Spring 2012/2a bm

SAS programming on distributed-memory machines

Shared Address Space (SAS) programming on distributed memory machines is a programming abstraction that provides less development effort than that of the traditional method of Message Passing (MP) on distributed memory machines, such as clusters of servers. Distributed systems are groups of computers that communicate through a network and share a common work goal. Distributed systems typically do not physically share the same memory (tightly coupled) but rather each processor or group of processors (e.g. Symmetric Multiprocessor (SMP)) must depend on other mechanisms besides direct memory access in order to communicate. Relevant concepts include memory coherence, types of memory access, data and process synchronization, and performance.

Background

Early distributed computer systems relied almost exclusively on message passing (MP) to communicate with one another, and this technique is still widely used today. In a message passing model, each processor's local memory is isolated from that of the rest of the system. Processes or objects can send or receive messages in order to communicate and this can occur in a synchronous or asynchronous manner. In distributed systems, and particularly with certain types of programs, the message passing model can become overly burdensome to the programmer as tracking data movement and maintaining data integrity can become quite challenging with many control threads. A shared address or shared-memory system, however, can provide a programming model that simplifies data sharing via uniform mechanisms of data structure reads and writes on common memory. Current distributed systems seek to take advantage both SAS and MP programming model principles in hybrid systems.

Distributed Shared Memory (DSM)

Generally a distributed system consists of a set of nodes connected by a network. Nodes may be comprised of individual processors or a multiprocessor system, the latter typically sharing a system bus. Each node itself contains a local memory, which maps (usually) partially to the distributed address space. Relevant design elements of early SAS implementations were scalability, coherence, structure and granularity. Most early examples did not structure memory, that is the layout of shared memory was simply a linear array of words. Some, however, structured as objects or data types. IVY , an early example of a DSM system, implemented shared memory as virtual memory. The granularity, or unit share size, for IVY was in 1-Kbyte pages and the memory was unstructured. A problem when considering optimal page size is the balance between a process likely needing quick access to a large range of the shared address space, which argues for a larger page size, countered by the greater contention for individual pages that the larger page may cause amongst processes and the false sharing it may lead to. Memory coherence is another important design element and there are semantics can be instituted that run gradations of strict to weak consistencies. The strictest consistency guarantees a read returns the most recently written value. Weaker consistencies may use synchronization operations to guarantee sequential consistency.

Mechanisms of distributed memory mapping

Distribution of shared memory pages

Implementations

There are

References

• Shan, H.; Singh, J.P.; Oliker, L.; Biswas, R.; , "Message passing vs. shared address space on a cluster of SMPs," Parallel and Distributed Processing Symposium., Proceedings 15th International , vol., no., pp.8 pp., Apr 2001
• Protic, J.; Tomasevic, M.; Milutinovic, V.; , "Distributed shared memory: concepts and systems," Parallel & Distributed Technology: Systems & Applications, IEEE , vol.4, no.2, pp.63-71, Summer 1996
• Chandola, V. , "Design Issues in Implementation of Distributed Shared Memory in User Space,"
• Nitzberg, B.; Lo, V. , "Distributed Shared Memory: A Survey of Issues and Algorithms"