EXtreme virtual memory

• US 9,852,079 B2
• Filed: 07/24/2007
• Issued: 12/26/2017
• Est. Priority Date: 08/01/2006
• Status: Active Grant

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Kepner, Jeremy, Kim, Hahn, Kahn, Crystal
• Primary Examiner(s): TSAI, SHENG JEN
• Application Number:
  US12/374,815
• Publication Number:
  US 20090313449A1
• Time in Patent Office: 3,808 Days
• Field of Search: 711117, 711202, 711173
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811

Abstract

A method and computer program product for orchestrating the distribution and management of parallel data on a parallel hierarchical storage system is presented. A hierarchical map of the parallel data is provided. The hierarchical map comprises a plurality of map objects, wherein each map object describes how to partition a given array of data into a plurality of subarrays of data created by a parent map object of the map object and how to store the parallel data into the parallel computer'"'"'s storage hierarchy.

Claims

1. A computer implemented method comprising:

in a hierarchical storage system associated with parallel processors, the storage system comprising a plurality of hierarchical levels of storage arranged based on storage capacity and proximity to the processors, a base level comprising persistent storage, having greatest storage capacity and being furthest from the processors;

representing, by a computer, an address space associated with the hierarchical storage system as a plurality of hierarchical maps, wherein each map is uniquely associated with one of the hierarchical levels of storage, an array of data is associated with a map of the base level, and for each level of storage other than the base level the uniquely associated map describes how to partition the array of data into a plurality of subarrays of data each of a size that can be accommodated by the storage capacity of storage at the level, the size of the subarrays decreasing at each successive level from a level that is closest to the base level to a level that is closest to the processors, a first map designating a first one of block, cyclic and block-cyclic data distribution and a second map designating a different one of said block, cyclic and block-cyclic data distribution; and

utilizing a selected one of the hierarchical maps to select one of the subarrays to select a page of data to write into the level of storage uniquely associated with the selected map.

2. The method of claim 1 further comprising one of the parallel processors accessing a page of parallel data associated with the hierarchical storage system by recursively translating array indices into subarray indices until a lowest level is reached.

3. The method of claim 1 further comprising one of the processors utilizing a map at level i in said hierarchical maps, where the map at level i describes how to partition subarrays created by a parent map object at level i-1.

4. The method of claim 1 comprising organizing the array and subarrays in a tree-like structure wherein each level is assigned to one of the levels of storage of one of the parallel processors.

5. The method of claim 4 comprising processing subarrays at a bottom level one subarray at a time.

6. The method of claim 1 further comprising managing, by a computer, the movement of data between adjacent levels of said storage hierarchy using out-of-core techniques.

7. The method of claim 1 comprising the maps designating a data distribution technique to use when partitioning the subarrays.

16. The method of claim 1 comprising loading a next subarray of said plurality of subarrays where contents of a current subarray are not needed, and not saving said current subarray with a parent subarray.

8. A non-transitory computer readable medium having computer readable code thereon, the medium comprising:

instructions that generate a representation of an address space associated with a hierarchical storage system comprising a plurality of hierarchical levels of storage arranged based on storage capacity and proximity to parallel processors, a base level comprising persistent storage, having greatest storage capacity and being furthest from the processors, the representation comprising a plurality of hierarchical maps, wherein each map is uniquely associated with one of the hierarchical levels of storage, an array of data is associated with a map of the base level, and for each level of storage other than the base level the uniquely associated map describes how to partition the array of data into a plurality of subarrays of data each of a size that can be accommodated by the storage capacity of storage at the level, the size of the subarrays decreasing at each successive level from a level that is closest to the base level to a level that is closest to the processors;

instructions responsive to a first map designating a first one of block, cyclic and block-cyclic data distribution and a second map designating a different one of said block, cyclic and block-cyclic data distribution to utilize the respective designated distribution for the first and second maps; and

instructions that utilize a selected one of the hierarchical maps to select one of the subarrays to select a page of data to write into the level of storage uniquely associated with the selected map.

9. The computer readable medium of claim 8 comprising instructions that cause one of the parallel processors to access a page of parallel data associated with the hierarchical storage system by recursively translating global array indices into subarray indices until a lowest level is reached.

10. The computer readable medium of claim 8 further comprising instructions that utilize a map at level i in said hierarchical maps, where the map at level i describes how to partition subarrays created by a parent map object at level i-1.

11. The computer readable medium of claim 8 comprising instructions that organize the array and subarrays in a tree-like structure wherein each level is assigned to one of the levels of storage of one of the parallel processors.

12. The computer readable medium of claim 11 further comprising instructions that process subarrays at a bottom level one subarray at a time.

13. The computer readable medium of claim 8 further comprising instructions for managing the movement of data between adjacent levels of said parallel hierarchical storage system using out-of-core techniques.

14. The computer readable medium of claim 8 further comprising instructions responsive to a designation in the maps to select a data distribution technique to use when partitioning the subarrays.

17. The computer readable medium of claim 8 further comprising instructions that load a next subarray of said plurality of subarrays where contents of a current subarray are not needed, and do not save said current subarray with a parent subarray.

15. A computer system comprising:

parallel processors;

a hierarchical storage system associated with the parallel processors, the storage system comprising a plurality of hierarchical levels of storage arranged based on storage capacity and proximity to the processor, a base level comprising persistent storage, having greatest storage capacity and being furthest from the processors;

a communications interface;

an interconnection mechanism coupling the hierarchical storage system, the processors and the communications interface; and

an application stored on a non-transitory computer-readable medium that represents an address space associated with the hierarchical storage system as a plurality of hierarchical maps, wherein each map is uniquely associated with one of the hierarchical levels of storage, an array of data is associated with a map of the base level, and for each level of storage other than the base level the uniquely associated map describes how to partition the array of data into a plurality of subarrays of data each of a size that can be accommodated by the storage capacity of storage at the level, the size of the subarrays decreasing at each successive level from a level that is closest to the base level to a level that is closest to the processors, wherein a first map uses a first one of block, cyclic and block-cyclic data distribution and wherein a second map uses a different one of said block, cyclic and block-cyclic data distribution; and

utilizes a selected one of the hierarchical maps to select one of the subarrays to select a page of data to write into the level of storage uniquely associated with the selected map.