7.5 Distributed shared memory
5 min read•august 15, 2024
(DSM) systems create a virtual shared address space across networked computers. They combine the ease of shared memory programming with the scalability of distributed systems, abstracting the underlying memory distribution for simpler application development.
DSM implementations can be hardware-based, software-based, or hybrid. Each approach balances performance, flexibility, and cost differently. Consistency models and coherence protocols are key to maintaining data integrity, while caching strategies and synchronization mechanisms optimize performance in these complex distributed environments.
Distributed Shared Memory Systems
Concept and Goals of DSM
Top images from around the web for Concept and Goals of DSM
Reading 20: Concurrency View original
Is this image relevant?
Parallel Programming - HPC Wiki View original
Is this image relevant?
Reading 20: Concurrency View original
Is this image relevant?
Parallel Programming - HPC Wiki View original
Is this image relevant?
1 of 2
Top images from around the web for Concept and Goals of DSM
Reading 20: Concurrency View original
Is this image relevant?
Parallel Programming - HPC Wiki View original
Is this image relevant?
Reading 20: Concurrency View original
Is this image relevant?
Parallel Programming - HPC Wiki View original
Is this image relevant?
1 of 2
- Distributed Shared Memory (DSM) creates a virtual shared address space across physically distributed memory systems in a network of computers
- DSM provides a transparent and efficient mechanism for sharing data among processes running on different nodes in a distributed system
- Combines advantages of shared memory programming models with scalability and fault tolerance of distributed systems
- Abstracts underlying distributed nature of memory, presenting a single, unified view to applications and programmers
- Implements complex mechanisms for maintaining data consistency, managing access permissions, and optimizing performance across the network
- Employs page-based or object-based approaches to manage shared data units and their distribution across nodes
- Page-based: shares fixed-size memory pages (4KB or 8KB)
- Object-based: shares programmer-defined data structures
- Offers benefits including simplified programming models, improved resource utilization, and increased parallel processing capabilities
- Simplified programming: developers can use familiar shared memory paradigms
- Resource utilization: allows idle memory on one node to be used by processes on other nodes
- Parallel processing: enables efficient data sharing for parallel algorithms (matrix multiplication)
DSM Implementation Approaches
- Hardware-based DSM systems utilize specialized hardware components to manage shared memory
- Offers high performance but limited flexibility and higher cost
- Examples include SGI Origin and Cray T3D systems
- Software-based DSM systems implement shared memory abstractions entirely in software
- Provides greater flexibility and easier deployment but potentially lower performance due to software overhead
- Examples include and systems
- Hybrid approaches combine hardware and software techniques to balance performance and flexibility
- May use hardware support for basic operations and software for higher-level functionality
- Examples include ScaleMP vSMP and NumaScale NumaConnect technologies
DSM Architectures and Consistency Models
DSM Architecture Types
- Hardware-based DSM architectures leverage specialized hardware for shared memory management
- Utilize custom memory controllers and network interfaces
- Provide low- access and efficient coherence protocols
- Examples include cache-coherent non-uniform memory access (ccNUMA) systems
- Software-based DSM architectures implement shared memory entirely through software mechanisms
- Use standard hardware and modify operating systems or runtime environments
- Offer flexibility in deployment and customization
- Examples include distributed shared memory libraries (OpenMP)
- Hybrid DSM architectures combine hardware and software approaches
- Balance performance benefits of hardware with flexibility of software
- May use hardware support for local operations and software for remote accesses
- Examples include cluster-based systems with hardware-assisted page fault handling
Consistency Models in DSM
- Strict consistency models provide intuitive programming but can limit performance and scalability
- Sequential consistency ensures all processors see the same order of memory operations
- Linearizability provides the illusion of instantaneous updates to shared data
- Relaxed consistency models offer better performance by allowing more asynchronous operations
- Release consistency delays propagation of updates until specific synchronization points
- Entry consistency associates shared data with synchronization objects for fine-grained control
- Lazy release consistency further optimizes by delaying update propagation until data is accessed
- choice impacts design of synchronization mechanisms and coherence protocols
- Strict models require more frequent global synchronization (barriers)
- Relaxed models allow for more localized and optimized synchronization (locks)
- Trade-offs between programming simplicity and system performance guide consistency model selection
- Strict models simplify reasoning about program behavior but may introduce unnecessary synchronization
- Relaxed models require careful programming to avoid data races but can significantly improve performance
Challenges and Techniques for DSM
Coherence and Caching Strategies
- leads to unnecessary communication and performance degradation
- Occurs when unrelated data items share the same coherence unit (cache line)
- Mitigation involves careful data alignment and padding techniques
- Coherence protocols maintain data consistency across distributed caches
- Directory-based protocols maintain a centralized directory of cache states
- Snooping protocols broadcast cache operations to all nodes
- Examples include MESI (Modified, Exclusive, Shared, Invalid) and MOESI protocols
- Caching strategies balance data locality, network traffic, and consistency maintenance
- Write-through caches immediately propagate updates to main memory
- Write-back caches defer updates, reducing network traffic but complicating consistency
- and migration techniques optimize data access patterns
- Replication creates multiple copies of data to reduce access latency
- Migration moves data closer to frequently accessing nodes
- Examples include home-based lazy release consistency (HLRC) protocol
Synchronization and Failure Handling
- Synchronization mechanisms coordinate access to shared data
- Distributed locks ensure mutually exclusive access to shared resources
- Barriers synchronize multiple processes at specific points in execution
- Examples include ticket locks and tree barriers for scalable synchronization
- Node failures and network partitions challenge consistency and availability
- Replication strategies can improve fault tolerance (primary-backup replication)
- Consensus protocols maintain system state across failures (Paxos algorithm)
- Optimizing memory access patterns reduces false sharing
- Careful data structuring aligns data to cache line boundaries
- Padding techniques separate unrelated data items
- Examples include using aligned allocators and structure padding in C/C++
Performance and Scalability of DSM
Performance Factors and Optimization
- Network characteristics heavily influence DSM performance
- Latency impacts response time for remote memory accesses
- limits the amount of data that can be transferred
- Examples of optimizations include message aggregation and compression techniques
- Coherence protocol efficiency affects overall system performance
- Adaptive protocols adjust behavior based on access patterns
- Hierarchical protocols reduce global communication
- Examples include adaptive home-based protocols and hierarchical
- Profiling and analysis tools identify performance bottlenecks
- Distributed system profilers capture inter-node communication patterns
- Memory access analyzers detect inefficient data layouts
- Examples include TAU (Tuning and Analysis Utilities) and Intel VTune Profiler
Scalability Considerations
- Increased coherence traffic and synchronization overhead limit scalability
- Communication grows with the number of nodes, potentially leading to network congestion
- Global synchronization becomes more expensive in larger systems
- Techniques like hierarchical locking and localized consistency domains address these issues
- Load balancing and data distribution strategies crucial for scalability
- Dynamic load balancing adjusts work distribution at runtime
- Data partitioning schemes minimize cross-node communication
- Examples include work-stealing schedulers and domain decomposition techniques
- Hybrid approaches combine shared memory and message passing
- Utilize shared memory within nodes and message passing between nodes
- Improve scalability for certain applications (hierarchical N-body simulations)
- Evaluating trade-offs guides DSM adoption for specific applications
- Consider programming model simplicity versus raw performance
- Analyze scalability requirements and potential bottlenecks
- Examples of suitable applications include parallel scientific simulations and distributed databases
Key Terms to Review (19)
Andrew S. Tanenbaum: Andrew S. Tanenbaum is a prominent computer scientist known for his influential work in operating systems and computer networks. He authored the widely-used textbook 'Operating Systems: Design and Implementation' and contributed significantly to the development of microkernel architecture. His ideas have shaped both academic and practical aspects of operating systems, including concepts like distributed systems and shared memory.
Bandwidth: Bandwidth refers to the maximum rate of data transfer across a network path, measured in bits per second (bps). In the context of distributed shared memory, bandwidth is crucial because it determines how quickly data can be exchanged between different nodes in a system, impacting the overall performance and efficiency of memory access across multiple processes. High bandwidth can significantly enhance the responsiveness and speed of applications that rely on sharing data among distributed components.
Cache coherence: Cache coherence refers to the consistency of data stored in local caches of a shared resource, ensuring that multiple caches reflect the same data. This is crucial in distributed shared memory systems where multiple processors or nodes can access and modify shared data simultaneously. Maintaining cache coherence helps prevent scenarios where one cache's changes are not recognized by others, thereby avoiding inconsistencies and ensuring reliable performance across the system.
Checkpointing: Checkpointing is a technique used in distributed systems to save the state of a system at a specific point in time, allowing it to be restored later if necessary. This process is crucial for ensuring fault tolerance and data consistency, especially in environments where multiple processes are running concurrently and may experience failures. By periodically creating snapshots of the system's state, checkpointing allows for recovery from crashes without losing significant amounts of work.
Consistency Model: A consistency model defines the rules and guarantees regarding the visibility of updates to shared data in a distributed system. It dictates how operations on shared data are seen by different processes, ensuring that all nodes have a coherent view of that data. The choice of a consistency model affects performance, usability, and how developers interact with the distributed shared memory.
David T. Lee: David T. Lee is a prominent figure in the field of computer science, particularly known for his contributions to distributed shared memory systems. His work has focused on improving the efficiency and reliability of memory management in distributed computing environments, which is crucial for enhancing the performance of parallel applications and systems.
Distributed Shared Memory: Distributed Shared Memory (DSM) is an abstraction that allows multiple computers in a distributed system to share a memory space as if it were a single memory. This concept simplifies programming in a distributed environment by enabling processes on different machines to access shared data without the complexity of message passing.
False Sharing: False sharing occurs in multi-threaded environments when two or more threads operate on different variables that happen to reside on the same cache line. This leads to unnecessary cache coherency traffic, as changes to one variable may cause other variables on the same line to be fetched again, wasting performance and resources. Understanding false sharing is crucial for optimizing performance in systems that employ distributed shared memory, as it directly affects data access patterns and overall system efficiency.
Latency: Latency refers to the time delay from the moment a request is made until the first response is received. It plays a crucial role in various computing contexts, affecting performance and user experience by determining how quickly processes and threads can execute, how memory operations are completed, and how effectively resources are managed across distributed systems.
Memory consistency: Memory consistency refers to the consistency of views of memory across multiple processes in a distributed shared memory system. It ensures that all processes have a uniform view of memory operations, allowing for predictable behavior and coordination among concurrent processes. This is crucial in distributed systems, where different nodes may access shared memory at different times, potentially leading to confusion and inconsistency.
Munin: Munin is a tool used in the context of distributed shared memory systems, which allows for the management and monitoring of shared resources across multiple nodes in a network. It plays a crucial role in optimizing performance by tracking system metrics, enabling effective resource allocation, and facilitating communication between different parts of the distributed system. The integration of munin helps to ensure that memory access and consistency are maintained efficiently across various processes.
Mutex: A mutex, or mutual exclusion object, is a synchronization primitive used to manage access to shared resources in concurrent programming. It ensures that only one thread or process can access a resource at a time, preventing race conditions and maintaining data integrity. Mutexes are crucial for enabling safe communication and coordination among threads in multithreading environments, as well as in distributed systems where multiple processes may need to access shared data simultaneously.
Object-based dsm: Object-based distributed shared memory (DSM) is a programming model that allows multiple processes running on different nodes in a distributed system to access shared objects as if they were in a single memory space. This abstraction simplifies the complexity of data sharing, allowing developers to focus on object manipulation without worrying about the underlying network communication details. It effectively merges the concepts of object-oriented programming and distributed systems, enhancing performance through locality and coherence management.
Page-based dsm: Page-based distributed shared memory (DSM) is a method for allowing multiple computers to share data in a distributed computing environment by using virtual memory pages as the unit of sharing. In this model, each computer has its own local memory, but portions of memory can be mapped into the address space of other computers, enabling seamless data access as if it were in local memory. This approach simplifies programming for distributed systems by allowing processes on different machines to share data without having to manage low-level communication explicitly.
Remote memory access: Remote memory access refers to the capability of a computer system to access memory located in another machine over a network. This allows different systems to share data and resources efficiently, as if they were accessing their own local memory. In distributed environments, remote memory access is vital for enabling processes on separate nodes to collaborate seamlessly, ultimately leading to improved performance and resource utilization.
Replication: Replication refers to the process of duplicating data or resources across multiple nodes in a distributed system to ensure consistency, availability, and fault tolerance. By creating copies of data, systems can continue to function smoothly even if one or more nodes fail, while also providing users with faster access to information. This concept is vital for maintaining data integrity and performance in distributed environments.
Semaphore: A semaphore is a synchronization mechanism used to control access to a shared resource in concurrent programming. It helps manage processes and threads to prevent race conditions by signaling when a resource is available or when it is being used. This concept is essential in understanding how multiple processes or threads can work together efficiently without interfering with each other, especially in systems involving process states, multithreading, distributed coordination, and shared memory.
Thrashing: Thrashing occurs when a system spends more time swapping pages in and out of memory than executing actual processes, leading to significant performance degradation. This situation arises primarily when there is insufficient physical memory available, causing excessive paging and resource contention. As a result, the system becomes inefficient, resulting in longer wait times and reduced throughput, ultimately hindering effective resource allocation and scheduling.
Treadmarks: Treadmarks is a system used in distributed shared memory environments that allows multiple processes on different machines to share memory in a way that mimics a single shared memory space. This system is particularly useful in distributed computing as it provides a simplified programming model, allowing developers to focus on the application logic without worrying about the complexities of memory management across different nodes.