Electrical computers and digital processing systems: memory – Address formation – Generating prefetch – look-ahead – jump – or predictive address
Reexamination Certificate
2001-05-22
2003-11-25
Nguyen, T. V. (Department: 2187)
Electrical computers and digital processing systems: memory
Address formation
Generating prefetch, look-ahead, jump, or predictive address
C710S052000, C710S068000, C711S137000, C711S150000, C711S167000, C711S170000
Reexamination Certificate
active
06654867
ABSTRACT:
TECHNICAL FIELD
The present invention relates to the field of computer memory management. Specifically, the present invention relates to a method and system for pre-fetching compressed memory blocks using pointers while decompressing a previously fetched block.
BACKGROUND ART
As the gap between hard drive access time and memory access time increases, it is increasingly desirable to locate more data in memory. This is increasingly important because the size of applications and data sets are increasing at a faster rate than the density of main memory. Furthermore, systems with multiprocessors may have many programs running simultaneously with each program having a relatively small number of pages of instructions and data in main memory. Hence, page faults may occur frequently. One way to increase the effective storage capacity of main memory is to compress the contents of main memory. However, conventional computer systems may be unable to efficiently manage the compressed data in main memory.
Because the compression ratio will vary from one page of data to the next, it is not known beforehand the resulting size of the compressed data. One conventional method uses compressed blocks of variable size, which may waste substantial memory. Moreover, this method uses garbage collection in the background, and hence consumes system resources. Another conventional system allows for compressed blocks of several different fixed sizes. For example, data which compressed down to a small size is placed in a small bucket and data which compressed down to a medium size is put in a medium size bucket, etc. However, there will still be space left over in each bucket. Furthermore, managing the multiple size buckets adds complexity.
Another conventional method for storing such compressed data is in small equal sized blocks. However, quickly retrieving such compressed data for decompression presents problems. One conventional method of accessing such compressed data is to construct a table with one entry for the compressed data corresponding to each uncompressed page. Each entry contains storage for pointers to the maximum number of compressed blocks possible. Furthermore, in order to avoid wasting space, the size of the multiple compressed blocks per uncompressed page is desirably kept small. Unfortunately, small compressed blocks means many blocks per uncompressed page, and hence this requires many pointers in the table. Alternatively, the size of the compressed blocks may be designed to be larger. While this may reduce the size of the table of pointers, larger compressed blocks leads to less efficient storage of compressed data.
Accordingly, it would be advantageous to provide a method and a system which allows a computer system to quickly read compressed data that is distributed by relatively small blocks within a memory system. A further need exists for a system which efficiently uses resources, such as the memory required for a table specifying the locations of the compressed data. A further need exists to be able to alter the size of the compressed data blocks. These and other advantages of the present invention will become apparent within discussions of the present invention herein.
DISCLOSURE OF THE INVENTION
The present invention provides for a method and system which allows a computer system to quickly read compressed data that is distributed in blocks within a memory system. Embodiments of the present invention efficiently use memory by minimizing the number of pointers placed in a table that is used to specify the location of compressed blocks of data. Embodiments further provide for a method and system for altering the size of compressed data blocks.
A method and system for parallel fetch and decompression of compressed data blocks is disclosed. In one method embodiment, the present invention recites accessing a table of pointers specifying the location of compressed data to obtain a pointer to a first block of compressed data. Using the pointer, the present embodiment recites reading a pointer in the first block of data and transferring the rest of the first compressed data block to be decompressed. The pointer in the first compressed data block specifies the location of the next block of compressed data in a chain of compressed data blocks. The present embodiment then recites pre-fetching the next compressed data block using the second pointer while decompressing the first compressed data block. Using a pointer in each successive compressed data block in the chain, the present embodiment recites pre-fetching the next compressed data block while the previous compressed data block is being decompressed.
Another embodiment provides for a way to decompress a plurality of data blocks chains which are formed from an uncompressed page which was divided before decompression. In this embodiment, there is a chain of compressed blocks for each division of the uncompressed page. The page table still requires only a single pointer to access each page of compressed data. When accessing the first block of compressed data, the present embodiment recites using a pointer in that block to find the next block in the chain. The present embodiment also recites adding an offset to the value of the pointer to the first block to locate a block at the head of another chain.
REFERENCES:
patent: 5150462 (1992-09-01), Takeda et al.
patent: 6266091 (2001-07-01), Saha et al.
patent: 6279062 (2001-08-01), Adiletta et al.
patent: 6310918 (2001-10-01), Saha et al.
patent: 6320521 (2001-11-01), Har et al.
patent: 6324621 (2001-11-01), Singh et al.
patent: 6415280 (2002-07-01), Farber et al.
patent: 6516397 (2003-02-01), Roy et al.
Aglietti Robert Bruce
Roy Sumit
Wilson Kenneth Mark
LandOfFree
Method and system to pre-fetch compressed memory blocks... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system to pre-fetch compressed memory blocks..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system to pre-fetch compressed memory blocks... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3182705