Operating System-Based Memory Compression for Embedded Systems

• US 20070005911A1
• Filed: 06/30/2006
• Published: 01/04/2007
• Est. Priority Date: 07/01/2005
• Status: Abandoned Application

• Current Assignee: NEC Laboratories America Inc (NEC Corporation), Northwestern University
• Original Assignee: NEC Laboratories America Inc (NEC Corporation), Northwestern University
• Inventors: Dick, Robert, Chakradhar, Srimat, Lekatsas, Haris, Yang, Lei
• Application Number:
  US11/427,824
• Publication Number:
  US 20070005911A1
• Time in Patent Office: Days
• US Class Current: 711/154
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06F 2212/401 Compressed data

Abstract

A dynamic memory compression architecture is disclosed which allows applications with working data sets exceeding the physical memory of an embedded system to still execute correctly. The dynamic memory compression architecture provides “on-the-fly” compression and decompression of the working data in a manner which is transparent to the user and which does not require special-purpose hardware. A new compression technique is also herein disclosed which is particularly advantageous when utilized with the above-mentioned dynamic memory compression architecture.

Claims

1. A method of memory compression in an embedded system with an operating system supporting memory management, the method comprising the steps of:

receiving a request from the operating system to swap a page of data to a swap area;

compressing the data into a compressed page of data; and

allocating space in a compressed area of memory to which the compressed page of data is swapped where, if the compressed data does not fit within the compressed area of memory, additional memory is requested from the operating system to enlarge the compressed area of memory.

2. The method of claim 1 wherein, if there is a request from the operating system to swap the page of data back from the swap area, the compressed page of data is retrieved from the compressed area of memory, decompressed, and returned back to the operating system.

3. The method of claim 1 wherein executable code for the embedded system is stored in a compressed filesystem in memory such that the executable code need not be swapped out to the compressed area of memory.

4. The method of claim 1 wherein the compressed data is allocated to the compressed area of memory using a mapping table which tracks addresses of the compressed data and size of the compressed data.

5. The method of claim 1 wherein the additional memory for the compressed area of memory is tracked by a linked list.

6. An embedded system comprising:

a processor;

memory partitioned into a compressed area and an uncompressed working area;

a memory management module which selects pages of data to swap out of the uncompressed working area;

a compression module which compresses the pages of data into compressed pages; and

a memory allocator which allocates space in the compressed area of memory to which the compressed pages of data can be swapped where, if the compressed data do not fit within the compressed area of memory, additional memory in the memory can be requested to enlarge the compressed area of memory.

8. The embedded system of claim 8 wherein executable code for the embedded system is stored in a compressed filesystem in memory such that the executable code need not be swapped out to the compressed area of memory.

7. The embedded system of claim 8 wherein, if there is a request from the operating system to swap the page of data back from the swap area, the compressed page of data is retrieved from the compressed area of memory, decompressed, and returned back to the operating system.

9. The embedded system of claim 8 wherein the compressed data is allocated to the compressed area of memory using a mapping table which tracks addresses of the compressed data and size of the compressed data.

10. The embedded system of claim 8 wherein the additional memory for the compressed area of memory is tracked by a linked list.

11. A method of data compression comprising:

receiving a next word in a data sequence;

replacing the word with a first encoded data sequence if the word matches a frequently-occurring pattern;

or

replacing the word with a second encoded data sequence if the word matches or partially matches an entry in a lookup table;

or

if the word neither matches the frequently-occurring nor matches or partially matches an entry in the lookup table, then adding a third encoded data sequence to the word and storing the word in the lookup table.

12. The method of claim 11 wherein the lookup table is two-way set associative dictionary wherein entries are indexed by a hash of a portion of the word.

13. The method of claim 11 wherein the least recently accessed entry in the lookup table is selected to be replaced as the word is stored in the lookup table.

14. The method of claim 11 wherein the frequently-occurring patterns include a sequence of zero bytes.

15. The method of claim 11 wherein the frequently-occurring patterns include a sequence of zero bytes with one or more arbitrary bytes in pre-specified places where the arbitrary bytes are encoded in the first encoded data sequence.