Researchers double cell phone memory through software alone

Now computer engineers at Northwestern University and NEC Laboratories America, Inc. are the first to do what many thought impossible -- they have developed technology that doubles the usable memory on cell phones and other embedded systems without any changes to hardware or applications. (Embedded systems are computers within devices not generally considered to be computers, such as cell phones, cars, iPods, medical devices and digital cameras.) The improvement was made in the operating system software alone.

This innovation, the result of two years of close collaboration between researchers at Northwestern and NEC Labs, is featured in millions of new smartphones, the NEC-manufactured FOMA N904i, which first hit shelves in Japan this summer.

“All the things you do with a cell phone or personal digital assistant require memory,” said Robert P. Dick, assistant professor of electrical engineering and computer science in Northwestern’s Robert R. McCormick School of Engineering and Applied Science. “The technology we’ve developed automatically takes data and reduces it to less than half its original size without losing any information while the embedded system is running. It is like putting twice as much memory in the phone without increasing its cost or power consumption.”

In early 2004, NEC Labs researchers conceived the concept of integrating compression technologies into the operating system itself to provide compression as an operating system service. The idea was to transparently compress and decompress selected regions of memory (both code and data) to drastically reduce the memory footprint of embedded applications.

NEC Labs entered into a strategic partnership with Northwestern to jointly develop this idea. The team consisted of Dick, his first doctoral student, Lei Yang, and Haris Lekatsas and Srimat Chakradhar from NEC Labs America.

The research team needed a way to give NEC’s cell phones more memory to run its applications without redesigning the hardware. Top researchers in the embedded systems field had been skeptical that this could be done, but the Northwestern/NEC team had a different answer.

Yes, it could be done in the software alone.

Yang, with the benefit of advice and help from the other team members, led the design of CRAMES (compressed RAM for embedded systems), a software-only compression infrastructure technology that has minimal performance and power consumption penalties.

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.

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.

Other research and industry solutions to increasing memory in embedded systems have been addressed in hardware, some by simply putting in more memory and others by adding a custom hardware compression unit. Skeptics had thought a software solution would result in power consumption penalties that were too high.

“Our team proved it can be done entirely in software,” said Dick, an expert in embedded systems who worked as a visiting researcher at NEC Labs America before joining the Northwestern faculty. “You have to be pretty careful about the design of the compression software and algorithm. The phrase ‘heroic design effort’ comes to mind. That’s what Lei Yang did when designing CRAMES.”

Shortly after joining Dick’s lab, Yang worked at NEC Labs America as a summer intern in 2004, charged with tackling the memory problem. Yang continued to work on the early design and prototypes of the CRAMES system back at Northwestern and through a second NEC summer internship.

Each team member at NEC and Northwestern was involved in the technical aspects of the work from the start, meeting once or twice a week. When the work went from research prototyping to product development, NEC took over.

Northwestern and NEC have filed a joint patent application on the CRAMES technology.

Source: Northwestern University