A new data compression technique for faster computer programs.



A novel technique developed by MIT researchers rethinks hardware data compression to free up more memory used by computers and mobile devices, allowing them to run faster and perform more tasks simultaneously.

Data compression takes advantage of redundant data to free up storage capacity, increase computing speed and provide other benefits. In current computer systems, accessing main memory is very expensive compared to the actual calculation. Because of this, the use of data compression in memory helps improve performance, since it reduces the frequency and amount of data that programs need to recover from main memory.

Memory in modern computers manages and transfers data in pieces of fixed size, in which traditional compression techniques must operate. However, the software, of course, does not store its data in pieces of fixed size. Instead, it uses "objects," data structures that contain various types of data and have varying sizes. Therefore, traditional hardware compression techniques handle objects poorly.

In a paper presented at the ACM International Conference on Architectural Support for Programming Languages ​​and Operating Systems this week, MIT researchers describe the first approach to compressing objects through the memory hierarchy. This reduces memory usage while improving performance and efficiency.

Programmers could benefit from this technique by programming in any modern programming language, such as Java, Python, and Go, which stores and manages data on objects without changing their code. In the end, consumers would see computers that can run much faster or can run many more applications at the same speed. Because each application consumes less memory, it runs faster, so a device can support more applications within its allocated memory.

In experiments with a modified Java virtual machine, the technique compressed twice as much data and reduced memory usage by half compared to traditional cache-based methods.

"The motivation was to try to create a new memory hierarchy that could do object-based compression, instead of cache line compression, because that's how most modern programming languages ​​manage data," says the first author. Po-An Tsai, a graduate student. in the Laboratory of Computer Science and Artificial Intelligence (CSAIL).

"All computer systems would benefit from this," adds co-author Daniel Sánchez, a professor of computer science and electrical engineering and a researcher at CSAIL. "Programs get faster because they are no longer affected by the bandwidth of memory."

The researchers developed their previous work that restructures the architecture of memory to directly manipulate objects. Traditional architectures store data in blocks in a hierarchy of ever larger and slower memories, called "caches." Recently accessed blocks go up to smaller and faster caches, while older blocks move to slower and larger caches, which eventually end up in main memory. Although this organization is flexible, it is expensive: to access the memory, each cache must search for the address among its contents.

"Because the natural unit of data management in modern programming languages ​​is the objects, why not make a memory hierarchy that deals with objects?" Sánchez says.

In an article published last October, researchers detailed a system called Hotpads, which stores entire objects, grouped into hierarchical levels, or "pads." These levels are completely in efficient memories, on chip and with direct addresses, without sophisticated searches. necessary.

Then, the programs refer directly to the location of all objects in the patch hierarchy. Newly badigned and recently referenced objects, and the objects they point to, remain at the fastest level. When the fastest level is filled, it executes an "eviction" process that keeps the objects that were recently referenced, but eliminates the oldest objects at slower levels and recycles the objects that are no longer useful, to free up space . The pointers are updated in each object to indicate the new locations of all the moved objects. In this way, programs can access objects much more economically than search through cache levels.

For their new work, the researchers designed a technique called "Zippads", which uses the Hotpads architecture to compress objects. When objects start at the fastest level for the first time, they are decompressed. But when they are evicted at slower levels, they are all compressed. Pointers on all objects across levels point to those compressed objects, which makes them easy to recover at the fastest levels and can be stored more compactly than previous techniques.

A compression algorithm takes advantage of redundancy between objects efficiently. This technique discovers more compression opportunities than the previous techniques, which were limited to finding redundancy within each block of fixed size. The algorithm first selects some representative objects as "base" objects. Then, in the new objects, it only stores the different data between those objects and the representative base objects.

Brandon Lucia, badistant professor of electrical and computer engineering at Carnegie Mellon University, praises the work for leveraging the features of object-oriented programming languages ​​to better compress memory. "Abstractions such as object-oriented programming are added to a system to simplify programming, but they often introduce a cost in the performance or efficiency of the system," he says. "The interesting thing about this work is that it uses the abstraction of existing objects as a way to make memory compression more effective, which in turn makes the system faster and more efficient with innovative architecture features. computers".


Source link