Distributed shared memory system with variable granularity

Details Distributed shared memory system with variable granularity Distributed shared memory system with variable granularity

2001-02-16

2003-07-08

Thai, Tuan V. (Department: 2186)

Electrical computers and digital processing systems: memory

Address formation

Address mapping

C711S203000, C711S147000, C709S213000

Reexamination Certificate

active

06591355

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to control of memory access in computer systems, and specifically to methods for enhancing the efficiency of memory access in distributed shared memory systems.
BACKGROUND OF THE INVENTION
Software-based distributed shared memory (DSM) systems combine the features of shared-memory and distributed-memory multiprocessors. The DSM is typically implemented as a middleware layer, between the operating system and user applications running on host processors that are linked by a local area network (LAN). It enables the application to relate to the local memory of the processor as though it were a coherent cache in a shared memory multiprocessor.
In order to control access to the shared memory by different applications running on the different hosts, software DSMs often rely on virtual memory page protection mechanisms provided by the operating system. The page size of common processors, such as the Intel Pentium™, is typically four kilobytes. In order to maintain memory consistency, all of the hosts maintain the same mapping of virtual memory to physical memory pages. Consequently, when applications running on two or more of the hosts need to access the same page of physical memory, they must take turns accessing the virtual page and swap the contents of the physical page back and forth between them. In page-based systems, this swapping will take place even when the applications are using different items of data, such as variables or other data structures, which are considerably smaller than the total page size and do not overlap. This phenomenon, known as false sharing, can substantially increase the network traffic and degrade performance of the applications running on the system.
The problem of false sharing is well known in DSMs, and various attempts have been made to alleviate it. For example, the requirements for memory consistency among the hosts can be relaxed, as in the Munin system, for example. This system is described by Carter in “Design of the Munin Distributed Shared Memory System,” in the
Journal of Parallel and Distributed Computing
29 (1995), pages 219-227, which is incorporated herein by reference. While relaxing memory consistency can reduce the need for communication among the hosts, it necessitates periodic calls to a synchronization routine, and requires that the application programmer be aware of the semantics of memory behavior and modify his or her code accordingly.
Lowenthal, et al., describe another software-based approach to reducing false sharing in “Using Fine-Grain Threads and Run-Time Decision Making in Parallel Computing,” in
Journal of Parallel and Distributed Computing
37 (1996), pages 41-54, which is incorporated herein by reference. False sharing is detected either at compilation or at run time and is then eliminated by relocating data in the memory. This approach maintains consistency and does not require changes to the host hardware or operating system, but it places limitations on the applications that can run on the system and in some cases adds run-time overhead. Groh et al., also describe an approach based on moving shared objects to different memory regions in “Shadow Stacks—A Hardware-Supported DSM for Objects of Any Granularity,” in
Proceedings of the Third International Conference on Algorithms and Architectures for Parallel Processing
(Melbourne, Australia, 1997), pages 225-238, which is incorporated herein by reference.
Another common approach is to reduce the granularity of sharing below the normal page level. For example, the “Shasta” system avoids using the virtual memory protection mechanism of conventional operating systems, and instead relies on instrumentation of the binary application code to provide fine-grained sharing. This system is described by Scales et al. in “Shasta: A Low Overhead, Software-Only Approach for Supporting Fine-Grain Shared Memory,” in
Proceedings of the Seventh Symposium on Architectural Support for Programming Languages and Operating Systems AS-PLOSVII
(Cambridge, Mass., 1996), pages 174-185, which is incorporated herein by reference. Aspects of the code instrumentation introduce high overhead, however, necessitating aggressive optimization techniques.
Similarly, Kadiyala et al. describe a new scheme for cache organization that provides fine-grain sharing in “A Dynamic Cache Sub-Block Design to Reduce False Sharing,” in
Proceedings of the International Conference on Computer Design:
VLSI in
Computers and Processors ICCD '
95 (Austin, Tex., 1995), pages 313-318, which is incorporated herein by reference. A cache coherence protocol attempts to dynamically locate the point of false reference in a shared memory block, and to partition the block into smaller sub-blocks based on the cache references.
A number of hardware-based approaches have also been proposed for reducing sharing granularity. For example, Jou et al. describe a scheme for reducing false sharing using a hardware extension of a traditional computer memory management unit (MMU) in “Two-Tier Paging and Its Performance Analysis for Network-based Distributed Shared Memory Systems,” in
IEEE Transactions on Information and Systems
E78-D (1995), pages 1021-1031, which is incorporated herein by reference.
To summarize, while there are many approaches known in the art for reducing false sharing in a DSM, nearly all of them require basic modifications to either the host and memory hardware or to the operating system (OS) software of the hosts, or to both. Those approaches that stay within the bounds of conventional hardware and OS software and use existing virtual memory protection mechanisms do so at the expense of relaxed consistency and/or special constraints on the application software. There is thus a need for a DSM that can reduce false sharing, preferably by reducing the granularity of sharing, without requiring substantial modification of OS or application software. The DSM should use existing protection mechanisms and should work without incurring substantial management overhead, which would otherwise offset the savings in network traffic due to the reduced sharing granularity.
While decreasing granularity typically leads to a concomitant decrease in false sharing, it also incurs a penalty in terms of the extra overhead required to deal with large blocks of memory data in small-grain units. Amza et al. studied this problem, and reported on their results in “Tradeoffs Between False Sharing and Aggregation in Software Distributed Shared Memory,” in
Proceedings of the Sixth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming PPOPP '
97 (Las Vegas, Nev., 1997), pages 90-99, which is incorporated herein by reference. They suggested that page faults should be monitored and used to decide whether pages should be grouped together or separated for purposes of maintaining memory consistency.
In a similar vein, Park et al. described an approach to memory sharing integrating two different protocols, one for small data sets and another for large data sets, in “Adaptive Granularity: Transparent Integration of Fine- and Coarse-Grain Communication,” in
Proceedings of the
1996
Conference on Parallel Architectures and Compilation Techniques
(Boston, Mass., 1996), pages 260-268, which is incorporated herein by reference. For small data sets, the granularity is fixed at a cache line, while for large array data, the granularity varies depending on the sharing behavior at run time, by grouping together adjacent data blocks with the same owner. Implementation of the protocol proposed by Park et al. requires special hardware support.
SUMMARY OF THE INVENTION
It is an object of some aspects of the present invention to provide a software DSM system that is capable of operating at reduced granularity, while using existing, conventional hardware and software substantially without modification.
It is a further object of some aspects of the present invention to provide a software DSM system that operates at reduced granularity, using the virtual page protection m

Affiliated with

Also associated with

Rating

Distributed shared memory system with variable granularity does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Distributed shared memory system with variable granularity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed shared memory system with variable granularity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3097945