Solid-state RAM data storage for virtual memory computer using fixed-sized swap pages with selective compressed/uncompressed data store

What is claimed is:

1. A method of storing pages of data in a semiconductor memory, the pages of data being of fixed size before compression, said method comprising the steps of:

a) partitioning the semiconductor memory to provide first, second, and third memory spaces, each of said memory spaces containing a large number of memory locations, the memory locations of the first memory space being of a first size for storing one of said pages of data compressed to at most said first size, the memory locations of the second memory space being of a second size for storing one of said pages of data compressed to at most said second size; the memory locations of said third memory space being of said fixed size;

b) receiving said pages of data from a data source and compressing each of said pages of data to produce a compressed page, and detecting if each said compressed page is as small as said first size and is as small as said second size, and producing an output indicative of the size of each compressed page;

c) storing each of said compressed pages of data in said semiconductor memory, a compressed page being stored in said first memory space in response to said output from said step of detecting if a compressed page is of said first size, and a compressed page being stored in said second memory space in response to said output of said step of detecting if a compressed page is of said second size, and, if a page is not compressed to as small as either said first or second size, then said page uncompressed in said third memory space.

2. A method according to claim 1 wherein said first and second memory spaces are larger than said third memory space.

3. A method according to claim 2 wherein said fixed size is substantially twice as large as said first size, and wherein said second size is smaller than said fixed size and larger than said first size.

4. A method according to claim 1 including the steps of providing a separate address for each of said pages and storing said address in a table corresponding to a location of a page in said first or second memory spaces.

5. A method according to claim 4 including the step of recalling one of said pages of data by

d) receiving a request for said one of said pages using said address for said page;

e) reading said page from said first or second memory space using said address;

f) decompressing said page.

6. A method according to claim 1 including the step of generating an error-correcting code for each of a plurality of blocks of each of said compressed pages, and wherein said step of storing includes storing said error-correcting codes with said compressed pages.

7. A method according to claim 6 wherein said compressed pages are transferred as parallel 9-bit symbols to said step of generating an error-correcting code, and wherein said blocks are transferred to said step of storing as parallel 9-bit symbols.

8. A memory device for storing pages of data, the pages of data being of fixed size, said memory device comprising:

a) a first memory space in said memory device containing a first large number of memory locations of a first size, each of said memory locations of said first size storing a compressed version of one of said pages of data;

b) a second memory space in said memory device containing a second large number of memory locations of a second size larger than said first size but smaller than said fixed size, each of said memory locations of said second size storing a compressed form of one of said pages of data;

c) means for compressing each of said pages of data to produce a plurality of compressed pages, and means for detecting if each one of said compressed pages is as small as said first size and if each one of said compressed pages is as small as said second size, said means for detecting producing an output indicating the size of each one of said compressed pages;

d) and means for selectively storing each one of said compressed pages of data in said first memory space as said compressed version if of said first size and in said second memory space as said compressed form if of said second size, in response to said output of said means for detecting.

9. A memory device according to claim 8 wherein said first and second memory spaces are defined in semiconductor memory.

10. A memory device according to claim 9 wherein said fixed size is substantially twice as large as said first size; and wherein said second size is substantially 70% as large as said fixed size.

11. A memory device according to claim 8 including means for receiving a separate address with each of said compressed pages and storing said address in said memory device corresponding to a location of said compressed page in said first or second memory spaces.

12. A memory device according to claim 11 including means for recalling said data pages, including:

e) means for receiving a request for one of said pages including said address for said page;

f) means for finding said address for said page in said stored addresses and determining the location of said page;

g) means for detecting whether or not said page was stored in said first or second memory space, and, if so, decompressing said page.

13. A memory device according to claim 8 including means for generating an error-correcting code for each one of a plurality of blocks of each of said compressed pages, and wherein said means for storing stores said error-correcting codes with said compressed pages; and including means for transferring said compressed pages as parallel 9-bit symbols to said means for generating an error-correcting code, and wherein said blocks are transferred to said means for storing as parallel 9-bit symbols.

14. A memory device according to claim 8 wherein said means for compressing includes a lookahead buffer storing a first number of bytes of incoming data, and includes a window buffer containing a second number of bytes of recent incoming data, said second number being larger than said first number, and means for comparing the bytes in said lookahead buffer to all of the bytes in said window buffer and generating match symbols if multiple-byte matches are found in said comparing.

15. A memory device according to claim 14 wherein said lookahead buffer and said window buffer are of bit-parallel format, and said means for compressing has an output which includes an added bit that indicates whether or not said output of the means for compressing represents a compressed or non-compressed symbol.

16. A method of storing page-swap data in a virtual memory system, comprising the steps of:

storing in a semiconductor memory unit a large number of swap pages which are (a) compressed to a first level no more than a first value and stored in a first area of said memory if compressible to said first level, and Co) compressed to a second level no more than a second value but greater than said first value and stored in a second area of said memory if compressible to said second level, and (c) if not compressible to said second level then stored uncompressed in a third area of said memory;

recording the number of pages stored in each of said first, second and third areas as recorded numbers;

partitioning said memory in response to said recorded numbers to provide altered boundaries between said first, second and third areas defined by addresses, and again storing said page-swap data in a minimum of space in said memory; said altered boundaries re-defining said first, second, and third memory areas, said first memory area having blocks of said first value, said second memory area having blocks of said second value, and said third memory area having blocks of a size equal to that of said swap pages when said swap pages are stored uncompressed.

17. A method according to claim 16 wherein said first and second memory areas are larger than said third memory area; and wherein said pages are of a fixed size substantially twice as large as said first value, and wherein said second value is smaller than said fixed size and larger than said first value.

18. A method according to claim 16 including the steps of providing a separate address for each of said pages and storing said address in a table corresponding to a location of a page in said first or second memory areas; and further including the step of recalling one of said pages of data by

a) receiving a request for said one of said pages using said address for said page;

b) reading said page from said first or second memory areas using said address;

c) decompressing said page.

19. A method according to claim 16 including the step of generating an error-correcting code for each of a plurality of blocks of each of said compressed pages, and wherein said step of storing includes storing said error-correcting codes with said compressed pages.

20. A method according to claim 19 wherein said compressed pages are transferred as parallel 9-bit symbols to said step of generating an error-correcting code, and wherein said blocks are transferred to said step of storing as parallel 9-bit symbols.

Description Submit all comments and votes

BACKGROUND OF THE INVENTION

This invention relates to digital data storage and retrieval, and more particularly to page-oriented storing of compressed or uncompressed data in randomly-accessed locations of fixed sizes in partitioned storage devices. The invention is particularly adapted for storing fixed-size pages swapped with main memory in a computer system using a virtual memory management scheme.

A computer implementing a virtual memory system typically employs a certain amount of "physical" memory composed of relatively fast semiconductor RAM devices, along with a much larger amount of "virtual" memory composed of hard disk, where the access time of the hard disk is perhaps several hundred times that of the RAM devices. The physical memory or "main memory" in a virtual memory system is addressed as words, while the virtual "disk memory" is addressed as pages. The virtual memory management scheme uses an operating system such as UNIX.TM. along with hardware including a translation buffer, as is well known. In multi-tasking operation where more than one program runs at the same time, each running in a time slice of its own, each program appears to have an entire memory space to itself. To make room in the physical memory to run a new program, or to allocate more memory for an already-running program, the memory management mechanism either "swaps" out an entire program (process) to disk memory or "pages" out a portion (page) of an existing process to disk. A typical page size is 4Kbytes.

Transferring data to and from disk memory is very slow compared to the transfer time to main memory, and so "solid state disks" (composed of semiconductor RAMs like the main memory) have been used as a substitute for magnetic disk to improve system performance. This is at a much higher cost per megabyte of storage, however, due to the cost of semiconductor RAMs. Data compression has not been used because of the variable-length record problem as discussed below, i.e., compressed data blocks are of variable size, making random access of compressed "pages" of data impractical.

As explained in application Ser. No. 627,722, now U.S. Pat. No. 5,237,460 data compression encoding algorithms are commonly applied to data which is to be archived or stored at the tertiary storage level. In a hierarchy of data storage, a RAM directly accessed by a CPU is often referred to a the primary level, the hard disk as the secondary level, and tape (back up) as the tertiary level. The characteristic of tertiary level storage as commonly implemented which supports use of compression is that the data access is largely sequential. Data is stored in variable-length units, sequentially, without boundaries or constraints on the number of bytes or words in a storage unit. Thus, if a file or page being stored compresses to some arbitrary number of bytes this can be stored as such, without unused memory due to fixed sizes of storage units. Compression can be easily applied in any such case where the data is not randomly accessed but instead is sequentially accessed. For this reason, data compression works well for data streaming devices such as magnetic tape. It has been applied to databases holding very large records on magnetic and optical disks.

Data compression is not readily adaptable for use with random access storage devices such as hard disks or solid-state disks, although in many cases it would be desirable to do so. The reason for this lack of use of data compression is that algorithms for data compression produce compressed data units which are of variable size. Blocks of data of fixed size compress to differing sizes depending upon the patterns of characters in the blocks; data with large numbers of repeating patterns compress to a greater degree than a more random distribution of characters. Text files and spreadsheet files compress to smaller units than executable code or graphics files. This problem of variable-length records has made random access of compressed data records, as managed by operating systems and controllers in computer systems, impractical.

It is the principal object of this invention to provide a low-cost, high-speed, semiconductor memory device useful in a computer implementing page swapping, as required in virtual memory computer architecture, particularly a device employing data compression to reduce cost, and using error detecting and correcting techniques to increase reliability. Another object is to provide an improved method of storing data in a computer system or the like, and particularly to provide a method of compressing data pages for storage in a storage medium having an access capability for storing data units of fixed size. Another object is to provide an improved data compression arrangement using a random-access type of storage device, where the data units to be stored and recalled are of fixed length and the storage device is accessed in fixed-length increments, where the length is small enough for this to be considered random access of data. A further object is to reduce the amount of unused storage space in a storage device when compressed data units are stored, and therefore increase the storage density. An additional object is to provide an improvement in the cost per byte of storage capacity in a storage device.

SUMMARY OF THE INVENTION

In accordance with one embodiment of the invention, a solid-state memory unit for page-swap storage employs data compression in which compressed data partitions are provided in DRAM memory for at least two different compressed data sizes. Data that will not compress to the block sizes specified for compressed data is stored uncompressed, in another partition in the DRAM memory, for example. As set for in application Ser. No. 627,722, now U.S. Pat. No. 5,237,460 a storage arrangement for compressed data may advantageously use multiple partitions, where each partition is a section of available physical storage space having an address known to the system which differentiates it from other partitions. The data to be stored is in blocks, i.e., units of data of some fixed size, as distinguished from byte or word oriented data of variable length. The partitions are capable of holding multiple blocks, each randomly accessible. The data blocks may be compressed if the compressed size fits in the fixed block size of one of the partitions in the storage device. To accommodate data which is compressible to a varying degree, yet avoid waste of unused space in the partitioned memory device, the partitions are made of differing block sizes; for example, there may be two partitions, these two having block sizes corresponding to the typical compressed sizes of the blocks of data. These compressed sizes may be perhaps one-half and two-thirds the size of the original data blocks in a typical situation. Data which cannot be compressed to the two-thirds value or less is either stored in other storage (e.g., the hard disk) or preferably is stored in a third partition of the memory device with block size of the original (uncompressed) data. The storage arrangement may preferably use a semiconductor RAM array, or it may use a combination of RAM and disk as described in the application Ser. No. 627,722 now U.S. Pat. No. 5,237,460.

In one embodiment, a data storage device, such as a bank of DRAMs, is employed for storing all page-swap data for a virtual memory management system. The semiconductor memory is partitioned into three parts, two of these for compressed pages and one for the small percentage of page that will not compress to a given size. The two fixed-size compressed block partitions are formatted for two different compressed block sizes equal to what a compressed version of the original block size will fit into for the majority of cases. One of these partitions is for blocks 50% of the original size, and the other for 70% of original, in one example. The relative number of blocks in each partition (e.g., the physical storage capacity of each partition) is set at the average ratio of compressible blocks to uncompressible blocks for the compression algorithm used. By compressible it is meant that the block of data can be compressed to the block size of one of the compressed block partitions, and by uncompressible it is meant that the block will not compress to the required block size to fit in the compressed block partition. It is reasonable to select an algorithm that will compress 90% of the blocks to either 50% or 70% of their original size, so in this case a ratio of the number of blocks in the compressed partitions to the number of blocks in the uncompressed partition is selected as 90:10. The size of the blocks is selected to be some efficient value depending upon the system and the way data is handled in the system; for example, the block size is probably best selected to be the page size of 4Kbytes, or a submultiple of the page size. Although the page size is typically 2K-bytes or 4K-bytes in the most commonly-used operating systems, other sizes may be appropriate. In the example embodiment, the block size of uncompressed data is selected to be 4Kbytes (actually 4096-bytes), while compression to 50% would mean one of the compressed data block size is 2Kbytes (2048-bytes) and compression to 70% would mean the other block size is about 2.8-Kbytes. A hit rate of approximately 90% may be achieved with this partitioning. The 10% of pages found not compressible to the 70% size are stored uncompressed in the third partition of the DRAM memory.

In one embodiment, a method is provided for collecting statistics on the page data being handled, and adapts the partitions to optimize capacity based on the kind of data encountered. Thus, the partitioning is adaptive, changing according to the compressibility of the page data.

In an alternative embodiment, instead of using the third partition of the DRAM memory, the ordinary storage device, such as a hard disk, is employed for pages that cannot be compressed to the threshold 70% size. The disk storage is used as uncompressed storage, functioning as a partition made up of addressable locations of a block size equal to that of the original uncompressed data (e.g., page size of 4KB).

In operation of the preferred embodiment, the computer system sends (writes) data in blocks (pages) to the storage device, and before being written the data blocks pass through a compression unit which attempts to compress the blocks using the algorithm of choice. A counter keeps track of how many bytes of physical storage are required to store the compressed data. If the number exceeds the size of the blocks used for physical data storage in the larger of the two compressed data partitions, then the actual amount of storage required (value in the counter) is returned to the operating system, which resends the page to the correct partition, so the data block is written uncompressed in the other partition and the addressing information maintained by the operating system reflects this. But if the block is compressed to the number of bytes of the smallest compressed partition then the data is stored in this compressed partition, or if compressed to the size of the larger compressed data partition it is stored thus, and in either event the location is recorded as such by driver software (added to the operating system). The driver records the values in the operating system kernel data structures which map the page-swap device translations. Upon recall, a request from the computer for a given page is checked against these stored addresses, and retrieved from the partition where it is found, then, if necessary, decompressed before sending to the computer. The average performance of the page swapping operation is greatly enhanced, the pages are stored in much faster semiconductor memory.

The performance of the page-swap memory unit as described will depend upon the speed of the compression and decompression mechanism. If the data compression requires too long, then the speed advantage of semiconductor RAMs over hard disk is lost. Therefore, in one embodiment, a compression arrangement is employed which operates upon one to four byte segments of data and performs a single-clock compression of this data if a match is found. In particular, Lempel-Ziv compression circuitry is employed which performs comparisons of all match sizes of a lookahead buffer to all positions in a window, for single-clock compression of all matches (one to four bytes). A tuned Lempel-Ziv algorithm uses 8-bit symbols, with a 64-symbol window, and a four-symbol lookahead buffer. This algorithm produces output values that are the same bit-width (9-bits) for either match or no-match to greatly simplify the task of bit-packing the compressed output. The DRAM storage for compressed data is arranged in a bit-width (36-bits) that is a multiple of the compressed data size (9-bits) to simplify the task of circuitry which bit-packs the compressed output. This compression mechanism is pipelined so that one byte is passed every clock cycle.

An important feature is the use of ECC (error correcting code) to maintain data integrity, even though DRAMs with potentially high soft error rates are employed. That is, the DRAMs may have soft error rates which are not acceptable for use in main memory, and may indeed be slower than ordinarily used for DRAM storage and have other relaxed specifications; these devices are referred to as "audio grade" DRAMs by some in the industry. The data being stored in the memory unit (whether compressed or uncompressed) passes through an ECC generator circuit to produce a code that is stored with each block of bytes, then upon recall the ECC circuit checks the code and makes a correction if a recoverable error is detected. The ECC logic uses a BCH code with a 9-bit character size to effectively correct errors on the 9-bit compressed data.

Another feature of the invention is the use of high-performance DMA interface to the system bus. A FIFO is included to buffer write data coming into the compression unit or read data going from the compression unit to the system bus, and when a bus grant is received a burst of data is sent instead of just one word. In the interface between the memory controller and the DRAM memory, a 2-word buffer is employed so that a page-mode read or write can be implemented if two words are waiting to be accessed.

BRIEF DESCRIPTION OF THE DRAWINGS

The novel features believed characteristic of the invention are set forth in the appended claims. The invention itself, however, as well as other features and advantages thereof, will be best understood by reference to the detailed description of specific embodiments which follows, when read in conjunction with the accompanying drawings, wherein:

FIG. 1 is an electrical diagram in block form of a digital system including a memory for storing pages of data, using features of one embodiment of the invention;

FIGS. 2a, 2b and 2c are detailed electrical diagram in block form of a data compression unit and ECC unit used in the system of FIG. 1.

FIG. 3 is a more detailed electrical diagram of the compression and decompression circuits in the system of FIG. 2;

FIG. 4