Distributed shared memory system with variable granularity

• US 6,591,355 B2
• Filed: 02/16/2001
• Issued: 07/08/2003
• Est. Priority Date: 09/28/1998
• Status: Expired due to Term

• Current Assignee: Foothills IP LLC
• Original Assignee: TECHNION RESEARCH AND DEVELOPMENT FOUNDATION, LTD.
• Inventors: Itzkovitz, Ayal, Schuster, Assaf
• Primary Examiner(s): Thai, Tuan V.
• Application Number:
  US09/788,024
• Publication Number:
  US 20020013889A1
• Time in Patent Office: 872 Days
• Field of Search: 709/213, 711/100, 711/147, 711/150, 711/200, 711/202, 711/203
• US Class Current: 711/202
• CPC Class Codes: G06F 12/1072 Decentralised address translation, e.g. in distributed shared memory systems
• CPC Class Codes: G06F 12/145 the protection being virtual, e.g. for virtual blocks or segments before a translation mechanism
• CPC Class Codes: G06F 2212/652 Page size control

Abstract

A method for controlling access to a physical memory in a distributed shared memory system (DSM) includes selecting a page of the physical memory in which to store a plurality of data items, including at least first and second data items. The selected page of the physical memory is divided into a plurality of minipages, including at least first and second minipages containing the first and second data items, respectively. First and second virtual pages are mapped to the selected page of the physical memory, such that the first and second virtual pages are associated respectively with the first and second minipages, with first and second access permissions applied to the first and second virtual pages, respectively. A process is permitted to access the first data item subject to the first access permission and the second data item subject to the second access permission, via the respective first and second virtual pages.

Claims

1. A method for controlling access to a physical memory in a distributed shared memory system (DSM), which includes a plurality of host processors that are configured to access pages having a predetermined page size in the physical memory, the method comprising:

selecting one of the pages of the physical memory in which to store a plurality of data items, including at least first and second data items;

dividing the selected page of the physical memory into a plurality of minipages, including at least first and second minipages containing the first and second data items, respectively;

mapping both first and second virtual pages, in a virtual memory space of the processors, to the selected page of the physical memory, such that the first and second virtual pages are associated respectively with the first and second minipages, and the first data item receives a first address on the first virtual page, while the second data item receives a second address on the second virtual page;

applying first and second access permissions to the first and second virtual pages, respectively;

receiving requests by a process running on one of the host processors to access the first and second data items via the respective first and second addresses on the first and second virtual pages; and

permitting the process, responsive to the requests, to access the first data item subject to the first access permission and the second data item subject to the second access permission.

2. A method according to claim 1, wherein mapping the first and second virtual pages comprises mapping the virtual memory space such that all of the processors access the first and second data items via the same respective addresses on the first and second virtual pages.

3. A method according to claim 1, wherein applying the first and second access permissions comprises applying the permissions substantially independently of one another.

4. A method according to claim 3, wherein receiving the requests comprises receiving a first request by a first process running on a first one of the host processors to access the first data item, and a second request by a second process running on a second one of the host processors, and wherein permitting the process to access the data items comprises permitting the first process to access the first data item and the second process to access the second data item, subject to the respective access permissions and substantially independently of one another.

5. A method according to claim 1, wherein permitting the process to access the first and second data items comprises controlling the access permissions so that sequential consistency is maintained in the data items among all of the processors.

6. A method according to claim 5, wherein controlling the access permissions comprises setting the access permissions for each of the first and second virtual pages on all of the host processors.

7. A method according to claim 6, wherein setting the access permissions comprises setting the permissions at each of the host processors to one of the settings in a group of settings consisting of No Access, Read/Write and Read Only.

8. A method according to claim 7, wherein receiving the requests comprises receiving a write request by the process to write data to the first minipage, and wherein controlling the access permissions comprises setting the permissions for the first virtual page such that the requesting process receives exclusive Read/Write permission for the first virtual page, while other processes running on the host processors receive No Access permission for the first virtual page.

9. A method according to claim 7, wherein receiving the requests comprises receiving a read request by the process to read data from the first minipage, and wherein permitting the process to access the first data item comprises conveying an up-to-date copy of the first data item to the host processor on which the requesting process is running, and wherein controlling the access comprises setting the permission for the first virtual page such that the requesting process receives Read Only permission for the first virtual page.

10. A method according to claim 5, wherein receiving the requests comprises receiving the request by the process to access the first data item while handling another request to access the first data item by another process, and wherein permitting the process to access the first data item comprises queuing the request by the process until the handling of the other request is completed.

11. A method according to claim 10, and comprising choosing one of the host processors to serve as a DSM manager, and wherein receiving the request and queuing the request comprise receiving and queuing the request at the manager.

12. A method according to claim 1, wherein the distributed shared memory system is configured such that the physical memory comprises a local memory associated with each of the processors, and wherein mapping the virtual pages comprises using a local operating system running on each of the processors to map the virtual pages to the local memory of the processor.

13. A method according to claim 12, wherein applying the first and second access permissions comprises applying a protection mechanism of the operating system, such that the first and second virtual pages have respective first and second levels of protection.

14. A method according to claim 13, wherein receiving the requests comprises receiving a page fault from the operating system when one of the requests violates the protection of the operating system, and wherein permitting the process to access the first and second data items comprises altering at least one of the permissions responsive to the page fault so as to permit the process to access the data item.

15. A method according to claim 13, wherein permitting the process to access the first data item comprises determining whether a copy of the data item in the local memory is up to date and, if so, altering the level of protection of the first virtual page using the protection mechanism of the operating system so as to permit the process to access the data item.

16. A method according to claim 13, wherein permitting the process to access the first data item comprises determining whether a copy of the data item in the local memory is up to date and, if not, requesting an up-to-date copy of the data item from another one of the hosts.

17. A method according to claim 16, and comprising mapping a privileged virtual page to the selected page of the physical memory, in addition to the first and second virtual pages, the privileged virtual page having a Read/Write access permission to all of the minipages in the selected page, wherein permitting the process to access the first data item comprises writing the up-to-date copy of the data item to the local memory using the privileged virtual page.

18. A method according to claim 1, and comprising:

bunching the plurality of minipages together to form minipage groups, each group comprising two or more of the minipages;

mapping a third virtual page to the selected page of the physical memory, such that the third virtual page is associated with the minipage group containing the first and second minipages, and the first and second data items both receive respective third addresses on the third virtual page;

applying a third access permission to the third virtual page;

receiving a further request by the process to access both of the first and second data items via the respective third addresses on the third virtual page; and

permitting the process, responsive to the further request, to access both of the first and second data items subject to the third access permission.

19. A method according to claim 18, wherein bunching the plurality of minipages together comprises bunching together two or more of the minipage groups that are not mutually overlapping to form another of the minipage groups.

20. A method according to claim 18, wherein receiving the requests by the process to access the first and second data items via the first and second virtual pages comprises receiving the requests from an application process during a first, fine-granularity phase of the process, and wherein receiving the further request to access both of the data items via the third virtual page comprises receiving the further request during a second, coarse-granularity phase of the process.

21. A method according to claim 20, and comprising setting a barrier point in an application program corresponding to the process, at which point the process switches between the fine- and coarse-granularity phases.

22. A method according to claim 20, and comprising detecting a pattern of access to the minipages by the host processors, and switching between the fine- and coarse-granularity phases responsive to the pattern.

23. A method according to claim 22, wherein detecting the pattern comprises detecting, during the coarse-granularity phase, a likelihood of false sharing among the host processors accessing the third virtual page.

24. A method according to claim 22, wherein detecting the pattern comprises detecting, during the fine-granularity phase, that one of the host processors is accessing consecutively a predetermined number of the minipages that are arranged in succession on the page of the physical memory.

25. A method according to claim 20, wherein permitting the process to access the first data item subject to the first access permission, comprises, after switching from the coarse- to the fine-granularity phase, determining the third access permission that was in effect in the coarse-granularity phase.

26. A method according to claim 18, wherein permitting the process to access both of the first and second data items comprises conveying to the host processor an up-to-date copy of the first data item from a first one of the other host processors, and conveying an up-to-date copy of the second data item from a second one of the host processors.

27. A method according to claim 26, wherein permitting the process to access both of the first and second data items comprises setting the third access permission so as to forbid access by the process until the up-to-date copies have been conveyed to the host processor, and then setting the third access permission so as to permit the requested access.

28. A method according to claim 18, wherein permitting the process to access the first data item subject to the first access permission comprises, after permitting the process to access the data items subject to the third access permission, setting the first access permission to enable the process to access the first data item based on the third access permission that was applied previously.

29. A method for controlling access to a physical memory in a distributed shared memory system (DSM), which includes a plurality of host processors that are configured to access pages having a predetermined page size in the physical memory, the method comprising:

selecting a sequence of the pages of the physical memory in which to store a plurality of data items;

dividing each of the pages of the physical memory in the sequence into a plurality of minipages, including at least first and second minipages;

storing a respective first one of the data items in each of the first minipages, and a respective second one of the data items in each of the second minipages, whereby the data items stored in the first minipages constitute a first group, and the data items stored in the second minipages constitute a second group;

mapping respective first and second virtual pages, in a virtual memory space of the processors, to each of the pages of the physical memory in the sequence, such that the first and second virtual pages are associated respectively with the first and second minipages on each of the pages in the physical memory, and the first data item on each of the pages of the physical memory receives a first address on the respective first virtual page, while the second data item on each of the pages of the physical memory receives a second address on the respective second virtual pages;

applying respective access permissions to the virtual pages;

receiving a request by a process running on one of the host processors to access the data items in a selected one of the first and second groups over a sequential range of the pages of the physical memory via the respective addresses on the virtual pages that are associated with the minipages of the selected group; and

permitting the process, responsive to the requests, to access the data items over the sequential range subject to the access permissions applied to the virtual pages.

30. A method according to claim 29, wherein mapping the virtual pages comprises mapping the first virtual pages in a first consecutive range corresponding to the sequence of the pages of the physical memory, and mapping the second virtual pages in a second consecutive range corresponding to the sequence of the pages of the physical memory.

31. A method according to claim 29, wherein receiving the request to access the data items comprises receiving a specification of the virtual pages corresponding to the sequential range, comprising a number of virtual pages between one virtual page and all of the virtual pages corresponding to the minipages in the selected group.

32. A method according to claim 29, wherein permitting the process to access the data items comprises altering the access permissions of all of the virtual pages in the sequential range so as to enable the process to access the data items.

33. A method according to claim 32, wherein mapping the virtual pages comprises using a local operating system running on each of the processors to map the virtual pages to the physical pages in a local memory associated with each of the processors, and wherein altering the access permissions comprises altering the permissions for all of the virtual pages in the sequential range with a single operating system call.

34. A method according to claim 29, wherein receiving the request comprises receiving a first request by the process during a first, fine-granularity phase of the process, to access a single one of the data items in the selected group, and receiving a second request by the process during a second, coarse-granularity phase of the process, to access a multiplicity of the data items over the sequential range.

35. Multiprocessor computing apparatus, comprising:

a plurality of host processors, which are mutually linked by a data communication network; and

a physical memory, arranged as a distributed shared memory among the processors, wherein the processors are configured to access pages having a predetermined page size in the physical memory,

wherein the processors are programmed to select one of the pages of the physical memory in which to store a plurality of data items, including at least first and second data items, to divide the selected page of the physical memory into a plurality of minipages, including at least first and second minipages containing the first and second data items, respectively, to map both first and second virtual pages, in a virtual memory space of the processors, to the selected page of the physical memory, such that the first and second virtual pages are associated respectively with the first and second minipages, and the first data item receives a first address on the first virtual page, while the second data item receives a second address on the second virtual page, and to apply first and second access permissions to the first and second virtual pages, respectively,

such that upon receiving requests by a process running on one of the host processors to access the first and second data items via the respective first and second addresses on the first and second virtual pages, the processors are adapted to permit the process, responsive to the requests, to access the first data item subject to the first access permission and the second data item subject to the second access permission.

36. Multiprocessor computing apparatus, comprising:

a plurality of host processors, which are mutually linked by a data communication network; and

a physical memory, arranged as a distributed shared memory among the processors, wherein the processors are configured to access pages having a predetermined page size in the physical memory,

wherein the processors are programmed to select a sequence of the pages of the physical memory in which to store a plurality of data items, to divide each of the pages of the physical memory in the sequence into a plurality of minipages, including at least first and second minipages, to store a respective first one of the data items in each of the first minipages, and a respective second one of the data items in each of the second minipages, whereby the data items stored in the first minipages constitute a first group, and the data items stored in the second minipages constitute a second group, to map respective first and second virtual pages, in a virtual memory space of the processors, to each of the pages of the physical memory in the sequence, such that the first and second virtual pages are associated respectively with the first and second minipages on each of the pages in the physical memory, and the first data item on each of the pages of the physical memory receives a first address on the respective first virtual page, while the second data item on each of the pages of the physical memory receives a second address on the respective second virtual pages, and to apply respective access permissions to the virtual pages,

such that upon receiving a request by a process running on one of the host processors to access the data items in a selected one of the first and second groups over a sequential range of the pages of the physical memory via the respective addresses on the virtual pages that are associated with the minipages of the selected group, the processors are adapted to permit the process, responsive to the requests, to access the data items over the sequential range subject to the access permissions applied to the virtual pages.

37. A computer software product, for controlling access to a physical memory in a distributed shared memory system (DSM), which includes a plurality of host processors that are configured to access pages having a predetermined page size in the physical memory, the product comprising a computer-readable medium in which program instructions are stored, which instructions, when read by the host processors, cause the processors to select one of the pages of the physical memory in which to store a plurality of data items, including at least first and second data items, to divide the selected page of the physical memory into a plurality of minipages, including at least first and second minipages containing the first and second data items, respectively, to map both first and second virtual pages, in a virtual memory space of the processors, to the selected page of the physical memory, such that the first and second virtual pages are associated respectively with the first and second minipages, and the first data item receives a first address on the first virtual page, while the second data item receives a second address on the second virtual page, and to apply first and second access permissions to the first and second virtual pages, respectively,

wherein when the processors receive requests by a process running on one of the host processors to access the first and second data items via the respective first and second addresses on the first and second virtual pages, the instructions cause the processors to permit the process, responsive to the requests, to access the first data item subject to the first access permission and the second data item subject to the second access permission.

38. A computer software product, for controlling access to a physical memory in a distributed shared memory system (DSM), which includes a plurality of host processors that are configured to access pages having a predetermined page size in the physical memory, the product comprising a computer-readable medium in which program instructions are stored, which instructions, when read by the host processors, cause the processors to select a sequence of the pages of the physical memory in which to store a plurality of data items, to divide each of the pages of the physical memory in the sequence into a plurality of minipages, including at least first and second minipages, to store a respective first one of the data items in each of the first minipages, and a respective second one of the data items in each of the second minipages, whereby the data items stored in the first minipages constitute a first group, and the data items stored in the second minipages constitute a second group, to map respective first and second virtual pages, in a virtual memory space of the processors, to each of the pages of the physical memory in the sequence, such that the first and second virtual pages are associated respectively with the first and second minipages on each of the pages in the physical memory, and the first data item on each of the pages of the physical memory receives a first address on the respective first virtual page, while the second data item on each of the pages of the physical memory receives a second address on the respective second virtual pages, and to apply respective access permissions to the virtual pages,

wherein when the processors receive a request by a process running on one of the host processors to access the data items in a selected one of the first and second groups over a sequential range of the pages of the physical memory via the respective addresses on the virtual pages that are associated with the minipages of the selected group, the instructions cause the processors to permit the process, responsive to the requests, to access the data items over the sequential range subject to the access permissions applied to the virtual pages.