Compression store addressing

Details Compression store addressing Compression store addressing

1998-10-08

2001-05-29

Black, Thomas G. (Department: 2771)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000

Reexamination Certificate

active

06240419

ABSTRACT:

I. BACKGROUND OF THE INVENTION
a. Field of the Invention
This invention relates generally to computer architecture and more specifically to modes of addressing in random access memories.
b. Related Art
In today's computer architectures, translation between virtual and real (physical) memory is generally done via page tables, which have, for each virtual page, its corresponding location within real memory. Access to a location within a virtual page, given by an offset from the beginning of the page, can be performed by fetching the contents of the real memory address of the page, as modified by the same offset.
An emerging development in computer architecture is the use of data compression in main or random access memory. Here, each virtual page, after compression, can be stored in some number of smaller storage blocks of either uniform or variable size with the number being dependent on the effectiveness of the compression means on this particular page. For example, virtual pages of 4k bytes might be stored, after compression, in some number of blocks of 256 byte size. The virtual page can then be retrieved by providing to the memory controller the identities of the corresponding blocks.
As noted above, it is often desirable to access, not the entire page, but rather some location within the page, specified by the offset from the page start. In general, this may require that the entire page be first decompressed. An exception to this is when the page contents are divided into two or more lines, for example four 1k lines per 4k page, and the lines compressed and decompressed individually. This latter form of organization is desirable in that the amount of work required to access a particular location within a page is reduced, and with it the required latency or delay. In this latter form of organization addressing is provided to the beginning of each line, which in general may start anywhere within any of the blocks within which the compressed line is stored. This is illustrated in FIG.
1
.
In
FIG. 1
, the page
1
consists of four lines,
1
a,
1
b,
1
c,
1
d,
which are stored in compressed form
1
a
′,
1
b
′,
1
c
′,
1
d
′ in three fixed size blocks
2
a,
2
b,
2
c.
Pointers to locations within these blocks are provided (by way of a table, not shown) in order to enable immediate access to the beginning of any desired line. This is awkward, however, as four such pointers need be provided to the addressing mechanism. In contrast, most of today's machines require only one such pointer, corresponding to the page frame. Moreover, in the latter form of organization the four pointers need be long enough to specify the location within the block, not just the block, within which the desired line resides. This increases the number of bits per pointer.
II. SUMMARY OF THE INVENTION
It is an object of this invention to provide for storing and accessing lines within a compressed page so that only a single address need be provided to gain access to any or all lines within a compressed page, with all lines accessed simultaneously for example if the entire page is to be decompressed in parallel. It is also an object of this invention to provide for processing the address to the compressed page so as to determine the location of the beginning of the desired line or lines. A yet further object of this invention is to provide immediate access to sufficient compressed data from any line so as to start the decompression process.
These and further objects and features are provided by (a) storing the beginning of all lines from a page at fixed positions within a single block, termed the anchor block, and (b) continuing the lines within some number of required blocks, as determined by the compression means. That is, even though each line has a compressed length which may be different, the starting locations of the lines within the anchor block are fixed. This fixed format then permits a simple calculation to obtain the start of each line, given the address of the anchor block.


REFERENCES:
patent: 4660130 (1987-04-01), Bartley
patent: 5864859 (1999-01-01), Franaszek

Affiliated with

Also associated with

Rating

Compression store addressing does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Compression store addressing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compression store addressing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2464289