Compression algorithms are not really new, so I've looked cautiously at the work of U.S. computer scientists claiming that 'they have developed technology that doubles the usable memory on cell phones and other embedded systems without any changes to hardware or applications.' The CRAMES (Compressed RAM for Embedded Systems) technology uses the Linux kernel's swapping mechanism to determine which pages should be compressed. According to the researchers, cell phones equipped with this technology don't use more power than regular ones and show a very small performance loss. The first phone to use the CRAMES technology is sold by NEC -- but only in Japan right now.
You can see on the left a diagram showing the CRAMES On-Line Memory Compression concept. (Credit: Northwestern University) This project has been done at the Robert R. McCormick School of Engineering and Applied Science at Northwestern University. The project has been led by Lei Yang, a doctoral student, under the supervision of Robert Dick, an assistant professor of electrical engineering and computer science.
Now, how did the researchers designed their software? "The team’s approach was to divide the memory in the system into two different regions, one regular and one where the data is greatly compressed. A very simple example of data compression is converting a list of 50 individual 'A's into the phrase '50 As,' which takes up less space but communicates the same information. Later on this can be converted back to an identical copy of the original text. The software applications run along and when an application needs data from the compressed region the hardware pauses the software, the operating system accesses the data, uncompresses it and puts the data into the regular region where the application can access it. The application continues running without ever knowing the data it needed was compressed."
And is the technology efficient? In a word, yes. "The CRAMES technology in the new NEC smartphones uses an existing data compression algorithm, called LZ0. In ongoing work, Yang has developed a compression algorithm that is more advanced, taking advantage of recently seen patterns in the data. Her algorithm is twice as fast, allowing negligible reduction in performance and battery life even when 60 percent of an embedded system's memory is removed. The algorithm works for a wide range of applications and may be used in future NEC phones."
It is interesting to note that Computerworld gave Yang one of its 10 Horizon Awards in August 2007, naming CRAMES as one of the ten "cool cutting edge technologies" of the year. In this article named Power-Packed Memory, Computerworld provides some additional details about the technology. "Dick says researchers had previously tried compressing software but rejected that approach because it drained power and hurt performance. The Northwestern team aimed to find a way to run applications that required more memory, but without the drain."
The article also gives more details about the algorithm and its efficiency. "To manage compressed memory, the development team decided to use the Linux kernel’s swapping mechanism to determine which pages should be compressed. Initially, they were able to reduce the drain to 10% using the established LZO compression algorithm. To further boost performance, the team developed a new compression algorithm called PBPM (Partial Based Partial Match). Other refinements include compressing data only when memory is low, modifying the memory management technology to reduce fragmentation and modifying the Linux kernel so it can eliminate defunct processes when necessary. Together, these steps held power drain and performance loss to 2.7%."
For even more information, one of the latest technical papers about CRAMES will soon be published in ACM's Transactions on Embedded Computing Systems (TECS) under the title "On-Line Memory Compression for Embedded Systems." Here is a link to a non-definitive version of this paper(PDF format, 29 pages, 315 KB).
Sources: Northwestern University news article, September 26, 2007; and various websites
You'll find related stories by following the links below.