Sparse matrix paging system

• US 7,197,620 B1
• Filed: 12/10/2002
• Issued: 03/27/2007
• Est. Priority Date: 12/10/2002
• Status: Expired due to Fees

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Adcock, James W.
• Primary Examiner(s): Bragdon; Reginald
• Assistant Examiner(s): Namazi; Mehdi
• Application Number:
  US10/315,557
• Time in Patent Office: 1,568 Days
• Field of Search: 711/202, 711/206, 711/207
• US Class Current: 711/202
• CPC Class Codes: G06F 12/1018 involving hashing techniques, e.g. inverted page tables

Abstract

A sparse matrix paging system is provided that dynamically allocates memory resources on demand. In some cases, this is accomplished by dynamically allocating memory resources, preferably only after a page has been requested. Such a sparse matrix paging system may allow a platform with a large linear address space to more efficiently execute on a platform with a smaller linear address space. Preferably, the sparse matrix paging system only indexes those pages that are actually requested and used in the address space on main store pages or backing store pages. Further, the backing store is preferably not involved unless the total address space allocated by the operating system exceeds the available main store pages.

Claims

1. A data processing system, comprising:

one or more requesters for accessing data by providing a corresponding first address from a first address range;

a sparse matrix paging system for converting the first address provided by the one or more requesters to a second address of a second address range, wherein the second address range is smaller than the first address range; and

wherein the first address is an absolute address.

2. A data processing system according to claim 1 wherein the second address is a virtual address.

3. A data processing system according to claim 1 wherein the second address is a real address.

4. A data processing system according to claim 1 wherein the sparse matrix paging system indexes one or more pages, wherein at least one of the pages includes the data corresponding to the first address.

5. A data processing system according to claim 4 wherein the sparse matrix paging system only indexes those pages that have been requested by the one or more requestors.

6. A data processing system according to claim 5 further including:

a main memory;

a backing store; and

wherein the sparse matrix paging system does not index pages on the backing store until the number of requested pages exceed a capacity of the main memory.

7. A data processing system according to claim 1 further comprising an operating system, wherein the sparse matrix paging system is implemented as part of the operating system.

8. A data processing system according to claim 1 further comprising an operating system, wherein the sparse matrix paging system is implemented separate from the operating system.

9. A data processing system according to claim 8 wherein the sparse matrix paging system is implemented as an emulator.

10. A data processing system according to claim 1 wherein the sparse matrix paging system includes one or more levels of index tables.

11. A data processing system according to claim 10 wherein at least some of the one or more levels of index tables are hashed using, at least in part, the first address provided by the one or more requesters.

12. A data processing system according to claim 11 wherein the sparse matrix paging system dynamically creates another index table level when a predetermined threshold is reached.

13. A data processing system according to claim 11 wherein the sparse matrix paging system dynamically eliminates an index table level when a predetermined threshold is reached.

14. A data processing system according to claim 1 wherein the sparse matrix paging system dynamically creates a page for the requested data if a page does not yet exist.

15. A data processing system according to claim 1 wherein the sparse matrix paging system dynamically eliminates a page if the page has been squashed.

16. A data processing system according to claim 1 wherein the sparse matrix paging system selectively eliminates a page if the page is a least recently used page.

17. A method for accessing data, the method comprising the steps of:

requesting data by providing a first address from a first address range;

converting the first address to a second address of a second address range through indexing, wherein the second address range is smaller than the first address range, and wherein the second address corresponds to an indexed storage page, the storage pages being stored in a main memory and/or a backing store;

wherein the converting step uses one or more levels of index tables, wherein at least one of the levels of index tables is hashed using, at least in part, the first address provided by the requesting step, and dynamically creating another index table level when a predetermined threshold is reached;

only indexing those storage pages that are requested by the requesting step; and

only storing pages on the backing store after the storage capacity of the main memory is reached.

18. A data processing system, comprising:

one or more requestors for accessing data by providing a corresponding first address from a first address range;

a sparse matrix paging system for converting the first address provided by the one or more requestors to a second address of a second address range, wherein the second address range is smaller than the first address range; and

wherein the second address is a virtual address.

19. A data processing system, comprising:

one or more requesters for accessing data by providing a corresponding first address from a first address range;

a sparse matrix paging system for converting the first address provided by the one or more requestors to a second address of a second address range, wherein the second address range is smaller than the first address range; and

an operating system, wherein the sparse matrix paging system is implemented as an emulator that is separate from the operating system.

20. A data processing system, comprising:

one or more requesters for accessing data by providing a corresponding first address from a first address range;

a sparse matrix paging system for converting the first address provided by the one or more requestors to a second address of a second address range, wherein the second address range is smaller than the first address range; and

wherein the sparse matrix paging system includes one or more levels of index tables wherein at least some of the one or more levels of index tables are hashed using, at least in part, the first address provided by the one or more requesters, and wherein the sparse matrix paging system dynamically creates another index table level when a first predetermined threshold is reached.

21. A data processing system according to claim 20 wherein the sparse matrix paging system dynamically eliminates an index table level when a second predetermined threshold is reached.

22. A method for accessing data, the method comprising the steps of:

requesting data by providing a first address from a first address range;

converting the first address to a second address of a second address range through indexing, wherein the second address range is smaller than the first address range, and wherein the second address corresponds to an indexed storage page, the storage pages being stored in a main memory and/or a backing store;

wherein the converting step uses one or more levels of index tables, wherein at least one of the levels of index tables is hashed using, at least in part, the first address provided by the requesting step, and dynamically eliminating an index table level when a predetermined threshold is reached;

only indexing those storage pages that are requested by the requesting step; and

only storing pages on the backing store after the storage capacity of the main memory is reached.

23. A method for accessing data, the method comprising the steps of:

requesting data by providing a first address from a first address range;

converting the first address to a second address of a second address range through indexing, wherein the second address range is smaller than the first address range, and wherein the second address corresponds to an indexed storage page, the storage pages being stored in a main memory and/or a backing store;

wherein the converting step uses one or more levels of index tables, wherein at least one of the levels of index tables is hashed using, at least in part, the first address provided by the requesting step, and dynamically eliminating a storage page if the storage page has been squashed;

only indexing those storage pages that are requested by the requesting step; and

only storing pages on the backing store after the storage capacity of the main memory is reached.

24. A method for accessing data, the method comprising the steps of:

requesting data by providing a first address from a first address range;

converting the first address to a second address of a second address range through indexing, wherein the second address range is smaller than the first address range, and wherein the second address corresponds to an indexed storage page, the storage pages being stored in a main memory and/or a backing store;

wherein the converting step uses one or more levels of index tables, wherein at least one of the levels of index tables is hashed using, at least in part, the first address provided by the requesting step, and selectively eliminating a storage page if the storage page is a least recently used page;

only indexing those storage pages that are requested by the requesting step; and

only storing pages on the backing store after the storage capacity of the main memory is reached.