Zeropoint Technologies Ab

Telefonaktiebolaget Lm Ericsson (Publ)

Per Stenström

Angelos Arelakis

Andras Vajda

Erik Sintorn

Daniel Moreau

Henrik Häggebrant

Vasileios Spiliopoulos

Chloe Alverti

Ioannis Nikolakopoulos

Alexandra Angerd

Pedro Petersen Moura Trancoso

A data compression method is disclosed which involves obtaining a plurality of data blocks, each data block comprising a plurality of data values. The method performs base-delta encoding of the obtained plurality of data blocks, wherein a delta value means a difference between a data value and a base value. This involves determining, among the data values of the plurality of data blocks, a set of global base values common to said plurality of data blocks. The set of global base values is selected to minimize delta values for the data values of the plurality of data blocks with respect to the global base values in said set of global base values. The method further involve encoding individual data values of the plurality of data blocks by selecting, in the set of global base values, for each individual data value a global base value that is numerically closest to the individual data value and thus results in a smallest delta value, and then generating metadata for the encoded individual data value to represent the selected global base value and the resulting delta value.

Systems, methods and devices for exploiting value similarity in computer memories

A computer memory compression method involves analyzing computer memory content with respect to occurrence of duplicate memory objects as well as value redundancy of data values in unique memory objects. The computer memory content is encoded by eliminating the duplicate memory objects and compressing each remaining unique memory object by exploiting data value locality of the data values thereof. Metadata is provided to represent the memory objects of the encoded computer memory content. The metadata reflects eliminated duplicate memory objects, remaining unique memory objects as well as a type of compression used for compressing each remaining unique memory object. A memory object in the encoded computer memory content is located using the metadata.

Systems, methods and devices for eliminating duplicates and value redundancy in computer memories

Disclosed is a compressed memory management method for a computer system having one or more processors (P-PN), compressible main memory, secondary memory and an operating system. The compressible main memory has a compressed memory space comprising an active part directly accessible to said one or more processors (P-PN), as well as an inactive part not directly accessible to said one or more processors (P-PN) in the form of memory freed up by memory compression. The compressed memory management method comprises maintaining, in an auxiliary memory, a layout of the compressed memory space of the compressible main memory, the layout including size and location of individual memory pages as well as free memory regions in said compressed memory space; triggering the compression of a memory page in the compressible main memory; intercepting a page-in request from said operating system to said secondary memory, using the layout of the compressed memory space maintained by the auxiliary memory to locate, when available, in said auxiliary memory a page requested by the page-in request, and making the located requested page available in the active part of the compressed memory space; and intercepting a page-out request from said operating system to said secondary memory, using the layout of the compressed memory space maintained by the auxiliary memory to obtain a free region for a page requested by the page-out request, and accommodating the requested page in the obtained free region of the auxiliary memory.

Managing free space in a compressed memory system

A method for accessing compressed computer memory residing in physical computer memory is disclosed. In the method, compressed memory blocks are represented as sectors, wherein all sectors contain a fixed number of compressed memory blocks, have a fixed logical size in the form of the fixed number of compressed memory blocks, and have varying physical sizes in the form of the total size of data stored in the respective compressed memory blocks. The method involves providing sector-based translation metadata to keep track of the sectors within a compressed memory page, receiving a physical memory access request comprising an address in the physical computer memory, using the address in the physical memory access request to derive a memory block index, using the memory block index and the fixed logical size of the sectors to determine a sector id, using the sector-based translation metadata to locate a sector having the sector id in the compressed memory page, and using the address of the physical memory access request to locate the requested data within said sector.

Accessing compressed computer memory

A decompression system has a plurality of decompression devices in an array or chain layout for decompressing respective compressed data values of a compressed data block. A first decompression device is connected to a next decompression device, and a last decompression device is connected to a preceding decompression device. The first decompression device decompresses a compressed data value and reduces the compressed data block by extracting a codeword of the compressed data value and removing the compressed data value from the compressed data block, retrieving a decompressed data value out of the extracted codeword, and passing the reduced compressed data block to the next decompression device. The last decompression device receives a reduced compressed data block from the preceding decompression device and decompresses another compressed data value by extracting a codeword of the other compressed data value, and retrieving another decompressed data value out of the extracted codeword. Elected for publication; FIG.

Methods, devices and systems for efficient compression and decompression for higher throughput

Methods, devices and systems for data compression and decompression are disclosed. A collection of data is obtained. The collection of data is sampled to establish, for a plurality of different symbol sizes, relative frequencies of symbols of the respective sizes in the collection of data. A code is generated to contain variable-length codewords by entropy encoding sampled symbols in the collection of data based on a metric which reflects the relative frequencies of the sampled symbols as well as their sizes. Symbols in the collection of data are compressed into compressed representations using the generated code, wherein the compressed representation of a symbol comprises a codeword which represents the symbol as well as metadata for decompressing the compressed representation.

Variable-sized symbol entropy-based data compression

Methods, devices and systems for a compressor and a decompressor for encoding and decoding data in the cache/memory/data transferring subsystem in a computer system or in a communication network are described herein. An example variable-length compressor is able to compress blocks of data values and the compressed blocks may include mixes of compressed and uncompressed values, wherein metadata in the form of a unique special-meaning codeword (UUIC) indicates uncompressed values. An example variable-length decompressor is able to decompress the compressed data blocks. The compressor and decompressor are able to support compression and decompression of common compression scenarios that are used in combination with variable-length compression to improve compressibility in the cache/memory/data transferring subsystem in a computer system or in a communication network.

Methods, devices and systems for compressing and decompressing data

Methods, devices and systems for a compressor and a decompressor for encoding and decoding data in the cache/memory/data transferring subsystem in a computer system or in a communication network are described herein. Example variable-length compressors and decompressors are able to: compress more densely when specific values occur in specific positions in a data block; to improve compression and decompression latency when specific values that appear frequently occur in a data block; to also improve decompression latency by recording the lengths of variable-length encoded values of a compressed data block. The compressor and decompressor are able to support compression and decompression of common compression scenarios that are used in combination with variable-length compression to improve compressibility in the cache/memory/data transferring subsystem in a computer system or in a communication network.

Methods, devices and systems enhance compression and decompression of data blocks of data values by selecting the best suited compression method and device among two or a plurality of compression methods and devices, which are combined together and which said compression methods and devices compress effectively data values of particular data types; said best suited compression method and device is selected using as main selection criterion the dominating data type in a data block by predicting the data types within said data block.

Methods, devices and systems for hybrid data compression and decompression

Methods, devices and systems enhance compression and decompression of data values when they comprise a plurality of semantically meaningful data fields. Compression is sometimes not applied to each data value as a whole, but instead to at least one of the semantically meaningful data fields of each data value, and in isolation from the other ones. Data fields can be organized that share the same semantic meaning together to accelerate compression and decompression as multiple compressors and decompressors can be used in parallel. A system can be used where methods and devices are tailored to perform compression and decompression of the semantically meaningful data fields of floating-point numbers after first partitioning further at least one of said data fields into two or a plurality of sub-fields to increase the degree of value locality and improve compressibility of floating-point values.

Methods, devices and systems for semantic-value data compression and decompression

A method of operating a multi-core processor. In one embodiment, each processor core is provided with its own private cache and the device comprises or has access to a common memory, and the method comprises executing a processing thread on a selected first processor core, and implementing a normal access mode for executing an operation within a processing thread and comprising allocating sole responsibility for writing data to given blocks of said common memory, to respective processor cores. The method further comprises implementing a speculative execution mode switchable to override said normal access mode. This speculative execution mode comprises, upon identification of said operation within said processing thread, transferring responsibility for performing said operation to a plurality of second processor cores, and optionally performing said operation on the first processor core as well.

Multi-core memory model and speculative mode processor management

In one embodiment, a computer cache is extended with structures that can (1) establish the frequency by which distinct values occur in the cache and use that information to (2) compress values in caches into dense codes using a plurality of statistical-based compression techniques and (3) decompress densely coded values to realize caches that can store information densely that can be retrieved with low overhead.

Growing community of inventors

Torslanda, Sweden

Per Stenström