Patent FR522210A successfully refreshed from Google Patents.
Patent US212170A successfully refreshed from Google Patents.
Patent US3703151A successfully refreshed from Google Patents.
Patent US6016535A successfully refreshed from Google Patents.
US6016535A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for dynamically and efficiently caching objects by subdividing cache memory blocks into equally-sized sub-blocks
Assignee: Citrix Systems Inc
•
Filing: 1995-10-11
•
Granted: 2000-01-18
•
Expires: 2015-10-11
Abstract
Abstract A method for dynamically caching data objects in a logical cache memory begins by organizing the logical cache memory into a set of maximally equally-sized, contiguous pages that begin at a logical cache base address. Any one of the maximal size logical cache pages may be dynamically subdivided into a set of smaller pages of equal size. The smaller size pages cache data objects having a smaller size than the maximum possible data object size. Each subdivided page stores only those smaller size data objects. The logical address for a page is mapped to at least a maximal size page index identifying the position of the maximal size logical page in the cache and, if the page is a smaller size page, the page location is also mapped to a smaller size page index which identifies a particular one of the smaller size pages located within a maximal size page. Pages are dynamically reconfigured based on a least-recently-used policy. A maximal size page may be reconfigured to provide for storage of multiple smaller sized pages and a set of smaller sized pages may be reconfigured to provide storage for a maximal size page. In one aspect, maximally sized pages may be chained together to provide for storage of data objects which exceed the size of the pages. Chained pages may be contiguous or non-contiguous.
Inventors
- 👤 Jeffrey Isaac Krantz
- 👤 Marc Alan Bloomfield
- 👤 Thanh Luu
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 19:33
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0875; G06F12/0223; G06F12/023; G06F12/0806; G06F12/0813
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
175 words
In a logical cache memory including a plurality of maximal-size pages beginning at a logical cache base memory address, each maximal-size logical cache memory page configured to store data objects of a given size, a method for dynamically reconfiguring one of the logical cache memory pages to store data objects having a size different from the size of the data object previously stored by that cache page, the method comprising the steps of: (a) receiving a data object to be cached having a size smaller than the maximal size; (b) determining whether one of a plurality of logical cache memory pages is already configured to store data objects having the smaller size of the received data object; (c) selecting, when no logical cache memory page is already configured to store data objects having the smaller size of the received data object, one of the maximal logical cache memory pages; and (d) reconfiguring the selected cache page into more than two equally-sized blocks for storing data objects having the smaller size of the received data object.
Claim 2
Dependent Claim
175 words
In a logical cache memory including a plurality of maximal-size pages beginning at a logical cache base memory address, each maximal-size logical cache memory page configured to store data objects of a given size, a method for dynamically reconfiguring one of the logical cache memory pages to store data objects having a size different from the size of the data object previously stored by that cache page, the method comprising the steps of: (a) receiving a data object to be cached having a size smaller than the maximal size; (b) determining whether one of a plurality of logical cache memory pages is already configured to store data objects having the smaller size of the received data object; (c) selecting, when no logical cache memory page is already configured to store data objects having the smaller size of the received data object, one of the maximal logical cache memory pages; and (d) reconfiguring the selected cache page into more than two equally-sized blocks for storing data objects having the smaller size of the received data object.
Claim 3
Dependent Claim
48 words
The method of claim 1 wherein step (a) comprises: (a-a) receiving a data object to be cached, having a size smaller than the maximal size; and (a-b) assigning the data object a quantized size by rounding the size of the received data object up to a predetermined quanta.
Claim 4
Dependent Claim
60 words
The method of claim 1 wherein step (a) comprises: (a-a) receiving a data object to be cached; and (a-b) assigning the data object a quantized size selected from the set consisting of 128 bytes, 512 bytes, and 2 kilobytes, wherein the quantized size is assigned by rounding the size of the received data object up to the next predetermined size.
Claim 5
Dependent Claim
29 words
The method of claim 1 wherein step (a) comprises receiving a graphical user interface data object to be cached the object having a size smaller than the maximal size.
Claim 6
Dependent Claim
37 words
The method of claim 1 wherein step (b) comprises determining more than one of a plurality of logical cache memory pages that is configured to store data objects having the smaller size of the received data object.
Claim 7
Dependent Claim
47 words
The method of claim 1 wherein step (c) comprises selecting, when no logical cache memory page is already configured to store data objects having the smaller size of the received data object, one of a plurality of logical cache memory pages on least recently used (LRU) basis.
Claim 8
Dependent Claim
44 words
The method of claim 2 wherein step (d) comprises subdividing the selected cache page into a plurality of equally-sized smaller pages, each equally-sized smaller page configured to store data objects of the quantized size and identified as storing data objects of the quantized size.
Claim 9
Dependent Claim
98 words
The method of claim 7, further comprising the step of mapping a logical address for the data object relative to the logical cache base memory address by: (i) mapping a logical address for the data object to a maximal-size page index corresponding to the page location of the maximal-size logical cache memory page relative to the logical cache memory base address; and (ii) mapping the logical address for the data object to a smaller page index that describes which of the plurality of smaller pages is being addressed within the maximal-size page designated by the maximal-size page index.
Claim 10
Dependent Claim
81 words
The method of claim 8 further comprising the step of generating a logical address for the data object by forming a product of the maximal-size page index of the maximal-size page that contains the data object and a value corresponding to the maximum number of objects of the smaller size that can be contained within the maximal-size page, forming a sum of the product and the smaller page index, and multiplying the sum by the quantized size of the data object.
Claim 11
Dependent Claim
23 words
The method of claim 8, further comprising the step of providing the mapped logical address for the data object as a single handle.
Claim 12
Dependent Claim
167 words
In a logical cache memory including a plurality of maximal-size pages beginning at a logical cache base memory address, each maximal-size logical cache memory page configured to store data objects of a given size, a method for dynamically reconfiguring one of the logical cache memory pages to store data objects having a size different from the size of the data object previously stored by that cache page, the method comprising the steps of: (a) receiving a data object to be cached having a size greater than the maximal size; (b) subdividing the data object into first and second data chunks; (c) assigning a first chunk index to the first data chunk and a second chunk index to the second data chunk, each index representing the maximal-size page in which the respective data chunk is stored; and (d) storing the second chunk index at a location in a control store that corresponds to the first chunk index for use in identifying the location of the second data chunk.
Claim 13
Dependent Claim
167 words
In a logical cache memory including a plurality of maximal-size pages beginning at a logical cache base memory address, each maximal-size logical cache memory page configured to store data objects of a given size, a method for dynamically reconfiguring one of the logical cache memory pages to store data objects having a size different from the size of the data object previously stored by that cache page, the method comprising the steps of: (a) receiving a data object to be cached having a size greater than the maximal size; (b) subdividing the data object into first and second data chunks; (c) assigning a first chunk index to the first data chunk and a second chunk index to the second data chunk, each index representing the maximal-size page in which the respective data chunk is stored; and (d) storing the second chunk index at a location in a control store that corresponds to the first chunk index for use in identifying the location of the second data chunk.
Claim 14
Dependent Claim
41 words
The method of claim 11 wherein step (d) comprises storing the second chunk index at a location in a control store that corresponds to the first chunk index for use in identifying the location of the first and second data chunks.
Claim 15
Dependent Claim
59 words
The method of claim 11 further comprising the steps of: (e) accessing the control store using the first page index corresponding to the first chunk index; (f) recovering an index stored in the control store starting at a location corresponding to the first chunk index; and (g) reading a maximal-size logical cache page corresponding to the first chunk index.
Claim 16
Independent Claim
265 words
A method for efficiently caching data objects in a logical cache memory including a plurality of maximal-size pages beginning at a logical base memory address, the logical cache memory using prescribed portions of a plurality of heterogeneous physical memory units for storage of data, the method comprising: (a) labeling each of the plurality of physical memory units with a unique rank index, the rank index indicative of the relative memory speed of the physical memory unit; (b) allocating a portion of each physical memory unit for use by the logical cache memory; (c) forming a continuous, addressable logical address space for the logical cache memory that encompasses the allocated portions of the physical memory units by ordering the allocated portions of the physical memory units based on the rank indices the logical cache memory beginning at a logical cache memory base address, each maximal-size page configured to store data objects of a maximal size and identified as storing data objects of a maximal-size, (d) receiving a data object to be cached having a size smaller than the maximal size; (e) determining whether one of the plurality of logical cache memory pages is already configured to store data objects having the smaller size of the received data object; (f) selecting, when no logical cache memory page is already configured to store data objects having the smaller size of the received data object, one of the maximal-size logical cache memory pages; and (g) reconfiguring the selected cache page into more than two equally-sized blocks for storing data objects having the smaller size of the received data object.
Claim 17
Independent Claim
265 words
A method for efficiently caching data objects in a logical cache memory including a plurality of maximal-size pages beginning at a logical base memory address, the logical cache memory using prescribed portions of a plurality of heterogeneous physical memory units for storage of data, the method comprising: (a) labeling each of the plurality of physical memory units with a unique rank index, the rank index indicative of the relative memory speed of the physical memory unit; (b) allocating a portion of each physical memory unit for use by the logical cache memory; (c) forming a continuous, addressable logical address space for the logical cache memory that encompasses the allocated portions of the physical memory units by ordering the allocated portions of the physical memory units based on the rank indices the logical cache memory beginning at a logical cache memory base address, each maximal-size page configured to store data objects of a maximal size and identified as storing data objects of a maximal-size, (d) receiving a data object to be cached having a size smaller than the maximal size; (e) determining whether one of the plurality of logical cache memory pages is already configured to store data objects having the smaller size of the received data object; (f) selecting, when no logical cache memory page is already configured to store data objects having the smaller size of the received data object, one of the maximal-size logical cache memory pages; and (g) reconfiguring the selected cache page into more than two equally-sized blocks for storing data objects having the smaller size of the received data object.
Claim 18
Dependent Claim
47 words
The method of claim 14 wherein step (d) comprises: (d-a) receiving a data object to be cached having a size smaller than the maximal-size; and (d-b) assigning the data object a quantized size by rounding the size of the received data object up to a predetermined quanta.
Claim 19
Dependent Claim
60 words
The method of claim 14 wherein step (d) comprises: (d-a) receiving a data object to be cached; and (d-b) assigning the data object a quantized size selected from the set consisting of 128 bytes, 512 bytes and 2 kilobytes; wherein the quantized size is assigned by rounding the size of the reviewed data object up to the next predetermined size.
Claim 20
Dependent Claim
29 words
The method of claim 14 wherein step (d) comprises receiving a graphical user interface data object to be cached, the object having a size smaller than the maximal size.
Claim 21
Dependent Claim
37 words
The method of claim 14 wherein step (e) comprises determining more than one of a plurality of logical cache memory pages that is configured to store data objects having the smaller size of the received data object.
Claim 22
Dependent Claim
48 words
The method of claim 14 wherein step (f) comprises selecting, when no logical cache memory page is already configured to store data objects having the smaller size of the received data object, one of the logical cache memory pages for reconfiguring on a least recently used (LRU) basis.
Claim 23
Dependent Claim
44 words
The method of claim 15 wherein step (g) comprises subdividing the selected cache page into a plurality of equally-sized smaller pages, each equally-sized smaller page configured to store data objects of the quantized size and identified as storing data objects of the quantized size.
Claim 24
Dependent Claim
98 words
The method of claim 20, further comprising the step of mapping a logical address for the data object relative to the logical cache base memory address by: (i) mapping a logical address for the data object to a maximal-size page index corresponding to the page location of the maximal-size logical cache memory page relative to the logical cache memory base address; and (ii) mapping the logical address for the data object to a smaller page index that describes which of the plurality of smaller pages is being addressed within the maximal-size page designated by the maximal-size page index.
Claim 25
Dependent Claim
81 words
The method of claim 21 further comprising the step of generating a logical address for the data object by forming a product of the maximal-size page index of the maximal-size page that contains the data object and a value corresponding to the maximum number of objects of the smaller size that can be contained within the maximal-size page, forming a sum of the product and the smaller page index, and multiplying the sum by the quantized size of the data object.
Claim 26
Dependent Claim
23 words
The method of claim 21, further comprising the step of providing the mapped logical address for the data object as a single handle.
References Cited (Backward Citations)
US3596257A
Cited
US4395754A
Cited
US4322795A
Cited
US4463424A
Cited
US4430712A
Cited
US4503501A
Cited
US4691281A
Cited
US4779189A
Cited
US5233701A
Cited
US4905141A
Cited
US5717893A
Cited
US5394531A
Cited
US5426752A
Cited
US5390318A
Cited
US5357623A
Cited
US5339411A
Cited
US5652854A
Cited
US5561786A
Cited
US5579507A
Cited
US5434992A
Cited
US5491808A
Cited
US5537635A
Cited
US5651136A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-01-17 | 2003-07-19 | 2004-01-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-01-17 | 2007-07-19 | 2008-01-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-01-17 | 2011-07-19 | 2012-01-18 | $7700.00 | Window Closed / Lapsed |