Data compression method for supporting virtual memory management in a demand paging system

• US 7,512,767 B2
• Filed: 02/15/2006
• Issued: 03/31/2009
• Est. Priority Date: 01/04/2006
• Status: Expired due to Fees

• Current Assignee: Sony Ericsson Mobile Communications USA Incorporated (Sony Group Corp.)
• Original Assignee: Sony Ericsson Mobile Communications USA Incorporated (Sony Group Corp.)
• Inventors: Ritzau, Tobias
• Primary Examiner(s): Ellis; Kevin L
• Assistant Examiner(s): Farrokh; Hashem
• Application Number:
  US11/355,221
• Publication Number:
  US 20070157001A1
• Time in Patent Office: 1,140 Days
• Field of Search: 711/170, 711/6, 375/240
• US Class Current: 711/170
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06F 12/1027 using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 2212/684 TLB miss handling

Abstract

A virtual memory management unit (306) includes a redundancy insertion module (307) which is used for inserting redundancy into an encoded data stream to be compressed, such that after being compressed each logical data block fits into a different one from a set of equal-sized physical data blocks of a given size. For example, said redundancy may be given by no-operation (NOP) instructions represented by a number of dummy sequences of a given length (L) into an encoded data stream to be compressed, each dummy sequence being composed of a number of identical binary or hexadecimal fill-in values.

Claims

1. A virtual memory management unit of a demand paging system installed on a computing device, said demand paging system being controlled by an operating system organized according to a virtual memory management technique for translating a virtual address space accessible by a data processing unit of said computing device into a physical address space by swapping data from an addressable storage area of a memory module integrated within said computing device to a storage means used for permanently storing these data, said virtual memory management unit comprising a redundancy insertion module for inserting redundancy into an encoded data stream to be compressed, such that after compression each logical data block fits into a different one from a set of equal-sized physical data blocks of a given size, wherein said redundancy is given by no-operation (NOP) instructions represented by a number of dummy sequences of a given length (L), each dummy sequence being composed of a number of identical fill-in values.

2. The virtual memory management unit according to claim 1, wherein said redundancy comprises data or functions which are easy to compress.

3. The virtual memory management unit according to claim 1, wherein the redundancy is chosen such that each logical data block from the encoded data stream to be stored in the storage means is compressed to a fraction of its original size such that after compression each logical data block fits into a different one from a set of equal-sized physical data blocks, each physical data block having a size of said fraction of the logical data block'"'"'s original size.

4. A data compression method for supporting virtual memory management and demand paging on a computing device, wherein said computing device runs an operating system organized according to a virtual memory management technique for translating a virtual address space accessible by a data processing unit of said computing device into a physical address space by swapping data from an addressable storage area of a memory module integrated within said computing device to a storage means used for permanently storing these data, said data compression method comprising:

inserting redundancy into an encoded data stream to be compressed, thus yielding an extended data stream;

submitting the extended data stream to a data compression procedure, such that after compression each logical data block fits into a different one from a set of equal-sized physical data blocks of a given size; and

storing the obtained compressed version of the extended data stream in the storage means;

wherein said redundancy is given by no-operation (NOP) instructions represented by a number of dummy sequences of a given length (L), each dummy sequence being composed of a number of identical fill-in values.

5. The data compression method according to claim 4, further comprising:

compressing each logical data block of an encoded data stream to be stored in the storage means;

adding redundancy to the encoded data stream in case the applied compression procedure yields a sequence of compressed data blocks in which each compressed data block is larger than the given size prescribed for physical data blocks to be stored in the storage means; and

recompressing the encoded data stream until each compressed data block fits into a physical data block of the given size.

6. The data compression method according to claim 4, wherein said redundancy comprises data or functions which are easy to compress.

7. The data compression method according to claim 4, wherein said dummy sequences are inserted between consecutive function calls of a software program executed by an application running on said computing device, said function calls causing any changes to the application'"'"'s behavior, or inside a subroutine of the application'"'"'s software program if the source code of said software program contains an unconditional jump to bypass said subroutine.

8. The data compression method according to claim 4, wherein the number of said dummy sequences is chosen such that each logical data block from the encoded data stream to be stored in the storage means is compressed to a fraction of its original size such that after compression each logical data block fits into a different one from a set of equal-sized physical data blocks, each physical data block having a size of said fraction of the logical data block'"'"'s original size.

9. A computer program product stored on an internal memory of a computer device, said computer program product comprising source code for executing a data compression method when running on said computing device and includes code that:

inserts redundancy into an encoded data stream to be compressed, thus yielding an extended data stream;

submits the extended data stream to a data compression procedure, such that after compression each logical data block fits into a different one from a set of equal-sized physical data blocks of a given size; and

stores the obtained compressed version of the extended data stream in the storage means;

wherein said redundancy is given by no-operation (NOP) instructions represented by a number of dummy sequences of a given length (L), each dummy sequence being composed of a number of identical fill-in values.

10. The computer program product according to claim 9, wherein the code further includes code that:

compresses each logical data block of an encoded data stream to be stored in the storage means;

adds redundancy to the encoded data stream in case the applied compression procedure yields a sequence of compressed data blocks in which each compressed data block is larger than the given size prescribed for physical data blocks to be stored in the storage means; and

recompresses the encoded data stream until each compressed data block fits into a physical data block of the given size.

11. The computer program product according to claim 9, wherein said redundancy comprises data or functions which are easy to compress.

12. The computer program product according to claim 9, wherein said dummy sequences are inserted between consecutive function calls of a software program executed by an application running on said computing device, said function calls causing any changes to the application'"'"'s behavior, or inside a subroutine of the application'"'"'s software program if the source code of said software program contains an unconditional jump to bypass said subroutine.

13. The computer program product according to claim 9, wherein the number of said dummy sequences is chosen such that each logical data block from the encoded data stream to be stored in the storage means is compressed to a fraction of its original size such that after compression each logical data block fits into a different one from a set of equal-sized physical data blocks, each physical data block having a size of said fraction of the logical data block'"'"'s original size.

14. A virtual memory management unit of a demand paging system installed on a computing device, said demand paging system being controlled by an operating system organized according to a virtual memory management technique for translating a virtual address space accessible by a data processing unit of said computing device into a physical address space by swapping data from an addressable storage area of a memory module integrated within said computing device to a storage means used for permanently storing these data, said virtual memory management unit comprising a redundancy insertion module for inserting redundancy into an encoded data stream to be compressed, such that after compression each logical data block fits into a different one from a set of equal-sized physical data blocks of a given size, wherein the redundancy is chosen such that each logical data block from the encoded data stream to be stored in the storage means is compressed to a fraction of its original size such that after compression each logical data block fits into a different one from a set of equal-sized physical data blocks, each physical data block having a size of said fraction of the logical data block'"'"'s original size.

15. A data compression method for supporting virtual memory management and demand paging on a computing device, wherein said computing device runs an operating system organized according to a virtual memory management technique for translating a virtual address space accessible by a data processing unit of said computing device into a physical address space by swapping data from an addressable storage area of a memory module integrated within said computing device to a storage means used for permanently storing these data, said data compression method comprising:

inserting redundancy into an encoded data stream to be compressed, thus yielding an extended data stream;

submitting the extended data stream to a data compression procedure, such that after compression each logical data block fits into a different one from a set of equal-sized physical data blocks of a given size;

storing the obtained compressed version of the extended data stream in the storage means;

compressing each logical data block of an encoded data stream to be stored in the storage means;

adding redundancy to the encoded data stream in case the applied compression procedure yields a sequence of compressed data blocks in which each compressed data block is larger than the given size prescribed for physical data blocks to be stored in the storage means; and

recompressing the encoded data stream until each compressed data block fits into a physical data block of the given size.

16. A computer program product stored on an internal memory of a computer device, said computer program product comprising source code for executing a data compression method when running on said computing device and includes code that:

inserts redundancy into an encoded data stream to be compressed, thus yielding an extended data stream;

submits the extended data stream to a data compression procedure, such that after compression each logical data block fits into a different one from a set of equal-sized physical data blocks of a given size;

stores the obtained compressed version of the extended data stream in the storage means;

compresses each logical data block of an encoded data stream to be stored in the storage means;

adds redundancy to the encoded data stream in case the applied compression procedure yields a sequence of compressed data blocks in which each compressed data block is larger than the given size prescribed for physical data blocks to be stored in the storage means; and

recompresses the encoded data stream until each compressed data block fits into a physical data block of the given size.