Apparatus and method for directly accessing compressed data utilizing a compressed memory address translation unit and compression descriptor table

• US 5,960,465 A
• Filed: 02/27/1997
• Issued: 09/28/1999
• Est. Priority Date: 02/27/1997
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Novell Incorporated (Open Text Corporation)
• Inventors: Adams, Phillip M.
• Primary Examiner(s): Gossage, Glenn
• Application Number:
  US08/807,477
• Time in Patent Office: 943 Days
• Field of Search: 711/202, 711/203, 711/205, 711/206, 711/207, 711/208, 711/209, 395/888
• US Class Current: 711/208
• CPC Class Codes: G06F 12/0292 using tables or multilevel address translation means G06F12/023 takes precedence; address translation in virtual memory systems G06F12/10
• CPC Class Codes: G06F 2212/401 Compressed data

Abstract

A method and apparatus for directly accessing data compressed by a dictionary-based compression scheme are disclosed. The apparatus may include an execution unit for processing data and an address generation unit connected to the execution unit for generating a logical address corresponding to the data. A compressed memory address translation unit operably connected to the address generation unit maps the logical address to a linear address corresponding to a physical address at which the data is stored as compressed data. The compressed memory address translation unit may include comparison elements. Each comparison element is adapted to determine whether an input address is within an address range associated therewith. Each comparison element may further include a map logic circuit for computing the linear address as an offset and a base linear address. One single comparison element uniquely provides the linear address to be output by the compressed memory address translation unit. A memory device may store a compression descriptor table comprising memory descriptors. The compression descriptor table may comprise both local and global tables mapping logical address ranges to physical address ranges within the memory device, with each descriptor including a logical address, a length, and a linear address. Each descriptor relates a unique logical address range (corresponding to a portion of a logical address space), to a physical address range (corresponding to space in the memory device).

Claims

1. An apparatus for executing directly compressed data, the apparatus comprising:

an execution unit for processing data;

an address generation unit operably connected to the execution unit for generating a logical address corresponding to the data; and

a compressed memory address translation unit operably connected to the address translation unit to map the logical address to a linear address corresponding to a physical address at which the data is stored as compressed data;

a memory device to store the compressed data to which the physical address corresponds, wherein the memory device further contains a compression descriptor table comprising memory descriptors, each relating a unique logical address range, corresponding to a portion of a logical address space, to a physical address range in the memory device; and

wherein the execution unit is programmed to access and execute on the compressed data directly from the physical address thereof.

2. The apparatus of claim 1, wherein the compressed memory address translation unit comprises a map logic circuit for computing the linear address as an offset and a base linear address.

3. The apparatus of claim 1, wherein the memory address translation unit comprises a plurality of comparison elements for comparing the logical address to an input address, and in which a single comparison element uniquely provides the linear address to be output by the compressed memory address translation unit.

4. The apparatus of claim 1, wherein the memory device further contains the linear address relating the logical address range to the physical address range.

5. The apparatus of claim 4, wherein the memory device further contains a compression descriptor table register storing a base address associated with the compression descriptor table.

6. The apparatus of claim 1, wherein the execution unit, address generation unit, and the compressed memory address translation unit are contained in a processor.

7. The apparatus of claim 6 wherein the memory device also contains the data to which the logical address corresponds.

8. The apparatus of claim 6, wherein the processor is configured to initialize the compressed memory address translation unit.

9. The apparatus of claim 8 wherein the processor is programmed to initiate memory transfers from the memory device to the compressed memory address translation unit upon execution of an instruction to load the contents of the compression descriptor table register.

10. The apparatus of claim 1, wherein the compressed memory address translation unit comprises a comparison element for comparing the logical address to an input address.

11. The apparatus of claim 10, wherein the comparison element is adapted to determine whether an input address is within the address range associated with the comparison element.

12. The apparatus of claim 11, wherein the comparison element is further adapted to determine whether the input address is greater than the address range and whether the input address is less than the address range.

13. The apparatus of claim 12, wherein the memory address translation unit comprises:

a plurality of comparison elements each having an address range associated therewith; and

a map and hole logic circuit adapted to determine whether the input address lies between consecutive address ranges of the address ranges.

14. A computer readable memory device comprising a storage medium having data structures supporting direct access to compressed data by a processor operably connected to a memory device, the memory device comprising:

a memory element storing compressed data, compressed by a dictionary-based compression;

a memory element storing a compression descriptor table relating logical address ranges associated with a logical address space to physical address ranges within the memory device; and

a memory element storing an executable, executable by the processor to initialize a compressed memory address translation unit in the processor for directly executing the compressed data.

15. The memory device of claim 14, wherein the memory device further comprises a memory element storing:

a loading executable to load a base address associated with the compression descriptor table into a compression descriptor table register in the processor.

16. The memory device of claim 14 wherein the compression descriptor table comprises a plurality of descriptor data structures, each including a logical address, a length, and a linear address.

17. The memory device of claim 16, wherein each logical address corresponds to a logical location at which a section of data occurs, each length corresponds to the length of a corresponding section of data;

and each linear address corresponds to a physical location at which a unique copy of a corresponding section of data is stored in the compressed data.

18. The memory device of claim 14, wherein the compression descriptor table comprises:

a local table mapping local logical address ranges to local physical address ranges within the memory device; and

a global table mapping global logical address ranges to global physical address ranges within the memory device.

19. The memory device of claim 18, wherein the local and global tables each comprise a plurality of descriptor data structures, each including a logical address, a length, and a linear address.

20. A method for directly accessing, by a processor, compressed data in a memory device, the method comprising:

storing compressed data, compressed by dictionary-based compression, at a physical address, the compressed data corresponding to original data;

relating, by use of a compression descriptor table, a logical address space to a physical address space in a memory device;

computing a logical address;

mapping the logical address to the physical address using the compression descriptor table; and

executing the original data at the physical address.

21. The method of claim 20, wherein the mapping step comprises:

mapping the logical address to a linear address; and

mapping the linear address to the physical address.