CN118369652A - Priority-based cache line fitting in a compressed memory system for a processor-based system - Google Patents

Abstract

A compressed memory system of a processor-based system includes a memory partitioning circuit for partitioning a memory region into data regions having different priority levels. The system also includes a cache line selection circuit for selecting a first cache line from the high priority data region and a second cache line from the low priority data region. The system also includes a compression circuit to compress the cache line to obtain a first compressed cache line and a second compressed cache line. The system also includes a cache line encapsulation circuit to encapsulate the compressed cache line such that the first compressed cache line is written to a first predetermined portion of a candidate compressed cache line and the second cache line or a portion of the second compressed cache line is written to a second predetermined portion of the candidate compressed cache line. The first predetermined portion is larger than the second predetermined portion.

Description

Priority-based cache line fitting in compressed memory systems for processor-based systems

Priority application

This application claims priority to U.S. patent application serial number 17/572,471, filed on January 10, 2022, entitled “PRIORITY-BASED CACHE-LINE FITTING IN COMPPRESSED MEMORY SYSTEMS OF PROCESSOR-BASED SYSTEMS,” which is incorporated herein by reference in its entirety.

This application also claims priority to U.S. patent application serial number 17/572,472, filed on January 10, 2022, entitled “PRIORITY-BASED CACHE-LINE FITTING IN COMPPRESSED MEMORY SYSTEMS OF PROCESSOR-BASED SYSTEMS,” which is incorporated herein by reference in its entirety.

Technical Field

The disclosed embodiments relate generally to memory systems, and in particular to priority-based cache line fitting in a compressed memory system of a processor-based system.

Background technique

As applications executed by conventional processor-based systems increase in size and complexity, memory bandwidth can become a constraint on system performance. Although available memory bandwidth can be increased by using wider memory communication channels, this approach may incur penalties in terms of increased cost and/or additional area required for memory on an integrated circuit (IC). One way to increase memory bandwidth in a processor-based system without increasing the width of the memory communication channel is by using data compression. A data compression system can be employed in a processor-based system to store data in a compressed format, thereby increasing effective storage capacity without increasing physical storage capacity. In this regard, some conventional data compression systems provide a compression engine to compress data to be written to the main system memory. After performing compression, the compression engine writes the compressed data to the system memory together with metadata that maps the virtual address of the compressed data to a physical address in the system memory where the compressed data is actually stored. However, because metadata is used for address mapping, memory access incurs additional reads and writes, which negatively affects system performance. For example, accessing a particular cache line in memory may require accessing metadata in memory and an additional layer of address calculation to determine the location of the compressed cache line in memory corresponding to the particular cache line. This increases the complexity, cost, and latency of processor-based systems that employ storage capacity compression.

Summary of the invention

Therefore, there is a need for systems, methods, and techniques that minimize the overhead of conventional compression systems. The techniques described herein can be used to remove metadata for most cache lines and thus improve the average performance of cache line accesses.

In one aspect, a method for compressing data in a compressed memory system of a processor-based system is provided. The method includes: dividing a storage area into a plurality of data areas, each data area being associated with a corresponding priority level. The method also includes: (i) selecting a first cache line from a first data area of the plurality of data areas, and (ii) selecting a second cache line from a second data area of the plurality of data areas. The first data area has a higher priority level than the second data area. The method also includes: (i) compressing the first cache line to obtain a first compressed cache line, and (ii) compressing the second cache line to obtain a second compressed cache line. Based on determining that the first cache line is compressible, the method includes: (i) writing the first compressed cache line to a first predetermined portion of a candidate compressed cache line, and (ii) writing the second cache line or a second portion of the second compressed cache line to a second predetermined portion of the candidate compressed cache line. The first predetermined portion is larger than the second predetermined portion.

In some implementations, the method further includes: setting an overflow pointer in the candidate compressed cache line based on determining that (i) the first cache line is incompressible, (ii) the second cache line is incompressible, or (iii) the second compressed cache line does not fit within a second predetermined portion of the candidate compressed cache line. The overflow pointer points to an overflow block in a plurality of overflow blocks based on a compression ratio of the second cache line or a size of the second compressed cache line. Each overflow block in the plurality of overflow blocks has a different size.

In some specific implementations, the method also includes: receiving a read request for the first cache line or the second cache line; and in response to receiving the read request: retrieving data from an overflow block in the plurality of overflow blocks according to the overflow pointer based on determining that the overflow pointer is set.

In some specific implementations, the method also includes: based on determining that the first cache line is compressible: setting a first compression rate control bit in the candidate compressed cache line; and based on determining that the first cache line is incompressible: writing a first portion of the first cache line to the candidate compressed cache line; writing a remaining portion of the first cache line to an overflow block; resetting the first compression rate control bit in the candidate compressed cache line; and setting an overflow pointer in the candidate compressed cache line to point to the overflow block.

In some specific implementations, the method also includes: in response to receiving a read request for the first cache line: based on determining that the first compression rate control bit is set: retrieving the first cache line from a candidate compressed cache line; and based on determining that the first compression rate control bit is reset: retrieving a first portion of the first cache line from the candidate compressed cache line; and retrieving a second portion of the first cache line from an overflow block based on an overflow pointer.

In some specific implementations, the method also includes: based on determining that the first cache line is incompressible: writing the second cache line or the second compressed cache line to the overflow block based on whether the second cache line is compressible; and resetting the second compression rate control bit in the candidate compressed cache line to indicate whether the second cache line is incompressible.

In some implementations, the method further includes: in response to receiving a read request for the second cache line: retrieving the second cache line or the second compressed cache line from the overflow block based on the second compression rate control bit.

In some specific implementations, the method also includes: in response to receiving a cache line write request for the first cache line: compressing the first cache line to obtain a first updated cache line having a first size; writing the first updated cache line to the candidate compressed cache line based on a determination that the first size is equal to or less than a first predetermined size of the candidate compressed cache line; performing a read-modify-write operation on the candidate compressed cache line based on the first updated cache line based on a determination that the first size is greater than the first predetermined size and equal to or less than a second predetermined size of the candidate compressed cache line; and performing a read-modify-write operation on the candidate compressed cache line based on the first updated cache line and performing a read-modify-write operation on an overflow block of a plurality of overflow blocks based on a determination that the first size is greater than the second predetermined size of the candidate compressed cache line.

In some implementations, the first predetermined size is half the size of the candidate compressed cache line.

In some specific implementations, the method also includes: when writing the second cache line or the second portion of the second compressed cache line to the second predetermined portion of the candidate compressed cache line, writing an end bit index in the candidate compressed cache line to indicate where the second cache line or the second portion of the second compressed cache line is written within the candidate compressed cache line; and calculating the second predetermined size based on the end bit index in the candidate compressed cache line.

In some specific implementations, the method also includes: in response to receiving a cache line write request for a second cache line: compressing the second cache line to obtain a second updated cache line having a second size; based on determining that the sum of the second size and the size of the first compressed cache line is less than a first predetermined size of the candidate compressed cache line, performing a read-modify-write operation to write the second updated cache line to the candidate compressed cache line; and based on determining that the sum of the second size and the size of the first compressed cache line is not less than the first predetermined size of the candidate compressed cache line, (i) performing a first read-modify-write operation to write a first portion of the second updated cache line to the candidate compressed cache line, and (ii) performing a second read-modify-write operation to write a remaining portion of the second updated cache line to the overflow block pointed to by the overflow pointer.

In some specific implementations, the method also includes: in response to receiving a cache line write request for the first cache line or the second cache line: compressing the first cache line or the second cache line to obtain an updated compressed cache line with an updated size; and based on determining that the updated size cannot fit within the overflow block pointed to by the overflow pointer, releasing the overflow pointer and updating the overflow pointer to point to a new overflow block among the multiple overflow blocks.

In some implementations, the first compressed cache line, the second compressed cache line, and the candidate compressed cache line have equal sizes.

In some implementations, the first data region and the second data region are of equal size.

In some implementations, the second predetermined portion is less than half the size of the candidate compressed cache line.

In some implementations, the first compressed cache line and the second compressed cache line are written to the candidate compressed cache line in opposite directions. The first compressed cache line and the second compressed cache line are separated by one or more bytes.

On the other hand, a compressed memory system of a processor-based system is provided. The compressed memory system includes a memory partitioning circuit configured to partition a storage area into a plurality of data areas. Each data area is associated with a corresponding priority level. The compressed memory system also includes a cache line selection circuit configured to: (i) select a first cache line from a first data area of the plurality of data areas, and (ii) select a second cache line from a second data area of the plurality of data areas. The first data area has a higher priority level than the second data area. The compressed memory system also includes a compression circuit configured to: (i) compress the first cache line to obtain a first compressed cache line, and (ii) compress the second cache line to obtain a second compressed cache line. The compressed memory system also includes a cache line packing circuit configured to: based on determining that the first cache line is compressible: (i) write the first compressed cache line to a first predetermined portion of a candidate compressed cache line, and (ii) write the second cache line or the second portion of the second compressed cache line to a second predetermined portion of the candidate compressed cache line. The first predetermined portion is greater than the second predetermined portion.

In some implementations, the cache line packing circuit is further configured to: in response to determining that (i) the first cache line is incompressible, (ii) the second cache line is incompressible, or (iii) the second compressed cache line does not fit within a second predetermined portion of the candidate compressed cache line, set an overflow pointer in the candidate compressed cache line. In response to a compression ratio of the second cache line or a size of the second compressed cache line, the overflow pointer points to one of a plurality of overflow blocks, and each of the plurality of overflow blocks has a different size.

In some specific implementations, the cache line packing circuit is also configured to: receive a read request for the first cache line or the second cache line; and in response to receiving the read request: retrieve data from an overflow block in the plurality of overflow blocks according to the overflow pointer based on determining that the overflow pointer is set.

In some specific implementations, the cache line packing circuit is also configured to: based on determining that the first cache line is compressible: set a first compression rate control bit in the candidate compressed cache line; and based on determining that the first cache line is incompressible: write a first portion of the first cache line to the candidate compressed cache line; write the remaining portion of the first cache line to an overflow block; reset the first compression rate control bit in the candidate compressed cache line; and set an overflow pointer in the candidate compressed cache line to point to the overflow block.

In some specific implementations, the cache line packing circuit is also configured to: in response to receiving a read request for the first cache line: based on determining that the first compression rate control bit is set: retrieve the first cache line from a candidate compressed cache line; and based on determining that the first compression rate control bit is reset: retrieve a first portion of the first cache line from the candidate compressed cache line; and retrieve a second portion of the first cache line from the overflow block based on the overflow pointer.

In some specific implementations, the cache line packing circuit is further configured to: based on determining that the first cache line is incompressible: write the second cache line or the second compressed cache line to the overflow block based on whether the second cache line is compressible; and reset the second compression rate control bit in the candidate compressed cache line to indicate whether the second cache line is incompressible.

In some implementations, the cache line packing circuit is further configured to: in response to receiving a read request for the second cache line: retrieve the second cache line or the second compressed cache line from the overflow block based on the second compression rate control bit.

In some specific implementations, the cache line packing circuit is also configured to: in response to receiving a cache line write request for a first cache line: compress the first cache line to obtain a first updated cache line having a first size; write the first updated cache line to the candidate compressed cache line based on a determination that the first size is equal to or less than a first predetermined size of the candidate compressed cache line; perform a read-modify-write operation on the candidate compressed cache line based on the first updated cache line based on a determination that the first size is greater than the first predetermined size and equal to or less than a second predetermined size of the candidate compressed cache line; and perform a read-modify-write operation on the candidate compressed cache line based on the first updated cache line and perform a read-modify-write operation on an overflow block among a plurality of overflow blocks based on a determination that the first size is greater than the second predetermined size of the candidate compressed cache line.

In some implementations, the first predetermined size is half the size of the candidate compressed cache line.

In some specific implementations, the cache line packing circuit is also configured to: when writing the second cache line or the second portion of the second compressed cache line to the second predetermined portion of the candidate compressed cache line, write an end bit index in the candidate compressed cache line to indicate where the second cache line or the second portion of the second compressed cache line is written within the candidate compressed cache line; and calculate the second predetermined size based on the end bit index in the candidate compressed cache line.

In some specific implementations, the cache line packing circuit is further configured to: in response to receiving a cache line write request for a second cache line: compress the second cache line to obtain a second updated cache line having a second size; based on determining that the sum of the second size and the size of the first compressed cache line is less than a first predetermined size of the candidate compressed cache line, perform a read-modify-write operation to write the second updated cache line to the candidate compressed cache line; and based on determining that the sum of the second size and the size of the first compressed cache line is not less than the first predetermined size of the candidate compressed cache line, (i) perform a first read-modify-write operation to write a first portion of the second updated cache line to the candidate compressed cache line, and (ii) perform a second read-modify-write operation to write a remaining portion of the second updated cache line to the overflow block pointed to by the overflow pointer.

In some specific implementations, the cache line packing circuit is also configured to: in response to receiving a cache line write request for the first cache line or the second cache line: compress the first cache line or the second cache line to obtain an updated compressed cache line with an updated size; and based on determining that the updated size cannot fit within the overflow block pointed to by the overflow pointer, release the overflow pointer and update the overflow pointer to point to a new overflow block among the multiple overflow blocks.

In some implementations, the first compressed cache line, the second compressed cache line, and the candidate compressed cache line have equal sizes.

In some implementations, the first data region and the second data region are of equal size.

In some implementations, the second predetermined portion is less than half the size of the candidate compressed cache line.

In some implementations, the cache line packing circuit is further configured to write the first compressed cache line and the second compressed cache line to the candidate compressed cache line in opposite directions. The first compressed cache line and the second compressed cache line are separated by one or more bytes.

On the other hand, a compressed memory system of a processor-based system is provided. The compressed memory system includes a storage area, which includes a plurality of cache lines. Each cache line has a priority level among a plurality of priority levels. The compressed memory system also includes a compressed storage area, which includes a plurality of compressed cache lines. Each compressed cache line includes a first group of data bits, which is configured to keep a portion of a first cache line or a portion of a compressed first cache line in a first direction, and the first cache line has a first priority level. Each compressed cache line also includes a second group of data bits, which is configured to keep a portion of a second cache line or a portion of a compressed second cache line in a second direction opposite to the first direction, and the second cache line has a second priority level lower than the first priority level. The first group of data bits includes a greater number of bits than the second group of data bits.

In some specific implementations, the compressed memory system also includes an overflow storage area, the overflow storage area includes a plurality of overflow bins. Each overflow bin is configured to hold a different number of bytes. Each compressed cache line also includes a set of overflow pointer bits, the set of overflow pointer bits being configured to hold a pointer to one of the plurality of overflow bins.

In some implementations, each compressed cache line further includes: a first control bit indicating a compression rate of the first cache line; and a second control bit indicating a compression rate of the second cache line.

In some embodiments, the compressed memory system further comprises an overflow storage area, the overflow storage area comprising a plurality of overflow bins, wherein each overflow bin is configured to hold a different number of bytes. Each compressed cache line further comprises a set of bits, the set of bits being configured to hold the size of one of the plurality of overflow bins.

In some implementations, each compressed cache line also includes an end bit index indicating an end of the second set of data bits.

In some implementations, each overflow bin is configured to hold bits of the first cache line and/or bits of the second cache line or a compressed second cache line in a first direction.

In some implementations, the first set of data bits and the second set of data bits are separated by one or more bytes.

In some implementations, each cache line and each compressed cache line have the same size.

In some implementations, when the compressed first cache line or the compressed second cache line does not fit in the compressed cache line, each compressed cache line further includes a set of overflow pointer bits configured to hold a pointer to an overflow bin of the plurality of overflow bins. The overflow bin is configured to hold bits of the first cache line, the compressed first cache line, the second cache line, and/or the compressed second cache line.

In some implementations, the second set of data bits is further configured to hold a plurality of control bits that indicate an overflow in the compressed cache line and an end of the second set of data bits.

In another aspect, a non-transitory computer-readable medium is provided. The non-transitory computer-readable medium stores computer-executable instructions thereon, which, when executed by a processor, cause the processor to perform any of the methods described herein.

Various embodiments of systems, methods, and devices within the scope of the appended claims each have several aspects, no single one of which is solely responsible for the attributes described herein. Without limiting the scope of the appended claims, after considering this disclosure, and in particular after considering the section entitled "Detailed Description of the Invention," it will be understood how aspects of the various embodiments can be used to achieve higher throughput in a storage device of a memory device.

BRIEF DESCRIPTION OF THE DRAWINGS

In order that the present disclosure may be understood in more detail, a more specific description may be given with reference to the features of various embodiments, some of which are illustrated in the accompanying drawings. However, the accompanying drawings only illustrate the more relevant features of the present disclosure and are therefore not to be considered limiting, as the description may allow for other effective features.

1 is a diagram of an example system with a cache line compression/decompression hardware engine according to some implementations.

FIG. 2A is a schematic diagram of a compressed memory system 200 according to some implementations.

2B is a sequence diagram illustrating a method for reading a cache line using the compressed memory system shown in FIG. 2A , according to some implementations.

2C is a sequence diagram illustrating a method for writing a cache line using the compressed memory system shown in FIG. 2A , according to some implementations.

3 is a schematic diagram of a packaging scheme for a compressed memory system according to some implementations.

4-9 illustrate example compressed row layouts according to some implementations.

10 illustrates a flow chart of an example method for reading a high priority cache line according to some implementations.

11 illustrates a flow chart of an example method for reading a low priority cache line according to some implementations.

12 illustrates a flow chart of an example method for writing a high priority cache line according to some implementations.

13 illustrates a flow chart of an example method for writing a low priority cache line according to some implementations.

14 is a block diagram of an example compressed memory system of a processor-based system according to some implementations.

According to conventional practice, the various features shown in the drawings may not be drawn to scale. Accordingly, for clarity, the sizes of the various features may be arbitrarily enlarged or reduced. In addition, some of the drawings in the drawings may not depict all components in the components of a given system, method or device. Ultimately, similar reference numerals can be used throughout the specification and the drawings to indicate similar features.

Detailed ways

Numerous details are described herein to provide a thorough understanding of the example implementations shown in the accompanying drawings. However, some embodiments may be practiced without many of the specific details, and the scope of the claims is limited only by those features and aspects specifically recited in the claims. In addition, well-known methods, components, and circuits are not described in detail so as not to unnecessarily obscure the more relevant aspects of the implementations described herein.

FIG. 1 is a schematic diagram of an example system 100 having a cache line compression/decompression hardware engine 110 according to some implementations. System 100 includes a chip 102, which in turn includes a processor 104, a level 2 (L2) cache or L2 tightly coupled memory (TCM) 106, and a compression/decompression hardware engine 110. Processor 104 includes a memory management unit (MMU), a data cache, and an instruction cache. The data cache and the instruction cache constitute a level 1 (L1) cache. L2 cache or L2 TCM 106 includes an L2 control and an L2 cache tag or status module 108. The system also includes a memory controller 114 for accessing a main external memory (e.g., a double data rate dynamic random access memory (DRAM), sometimes referred to as DDR). Although not shown in FIG. 1, some implementations may include conventional peripherals, other storage devices, a peripheral component interconnect (PCI) express interface, a direct memory access (DMA) controller, and/or an integrated memory controller (IMC). Some implementations may include two or more processors or processor blocks, and/or a shared level 3 (L3) cache for storing cache data used by any one of the processor blocks or shared between each of the processor blocks. Some implementations include an internal system bus that allows each of the processor blocks to access the shared L3 cache and/or other shared resources including a memory controller 114. The processor-based system 100 is configured to store cache data in an uncompressed form in a cache entry in a cache memory. The cache entry may be a cache line. For example, the cache memory may be an L2 cache memory (e.g., L2 cache 106). The cache memory may be dedicated to a processor core in the processor 104 or shared between multiple processor cores. The processor-based system 100 includes a system memory 112, which includes a compressed data area configured to store data in a compressed form in a memory entry (which may be a memory line). For example, the system memory 112 may include a double data rate (DDR) static random access memory (SRAM). Processor 104 is configured to access system memory 112 during read and write operations to execute software instructions and to perform other processor operations.

FIG. 2A is a schematic diagram of a compressed memory system 200 according to some specific implementations. The compressed memory system is configured to compress cache data from cache entries evicted from the cache memory, and read metadata for accessing physical addresses in the compression system memory to write the compressed cache data. Providing the ability to store compressed data in a compressed data area (e.g., blocks 202, 204, 206) increases the storage capacity of the processor-based system 100, exceeding the physical memory size of the system memory 112. In some specific implementations, the processor 104 uses virtual addressing. Perform virtual to physical address conversion to effectively address the compressed data area without knowing the compression system and the compressed size of the compressed data area. In this regard, a compression or decompression engine 212 is provided in the compressed memory system 200 to compress uncompressed data to be written in the compressed data area from the processor 104, and decompress the compressed data received from the compressed data area to provide such data to the processor 104 in an uncompressed form. The compression or decompression engine 212 may include compression circuitry configured to compress data from the processor 104 to be written into the compressed data area. For example, as shown in FIG1 , the compression circuitry may be configured to compress a 64-byte (64B) data word into a 48-byte (48B) compressed data word, a 32-byte (32B) compressed data word, or a 16-byte (16B) compressed data word, which may be stored in corresponding storage blocks 202 (64B), 204 (48B), 206 (32B), and 204 (16B), each of which has a size smaller than each of the entire memory entries of the system memory 112. If the uncompressed data from the processor 104 cannot be compressed down to the next smaller size storage block 125 configured for the compressed memory system 102, such uncompressed data is stored uncompressed over the entire width of one of the memory entries. For example, one of the memory entries may be 64B wide and may therefore store a 64B memory block, such as memory block 202 (64B). Compression or decompression engine 212 also includes decompression circuitry configured to decompress compressed data from the compressed data area to be provided to processor 104.

However, in order to provide faster memory access without the need for compression and decompression, a cache memory 214 (e.g., L2 cache 106) is provided. The cache entries in the cache memory 214 are configured to store cache data in an uncompressed form. Each of the cache entries may have the same width as each of the memory entries for performing efficient memory read and write operations. The cache entries are accessed by corresponding virtual address ("VA") tags (e.g., tags stored in the L2 cache tags 108) because, as discussed above, the compressed memory system 200 provides the processor 104 with more addressable memory space than the physical address space provided in the compressed data area. When the processor 104 issues a memory read request for a memory read operation, the virtual address of the memory read request is used to search the cache memory 214 to determine whether the virtual address matches one of the virtual address tags of the cache entry. If so, a cache hit occurs, and the cache data in the hit cache entry in the cache entry is returned to the processor 104 without the need to decompress the cache data. However, because the number of cache entries is less than the number of memory entries, a cache miss may occur if cache data for a memory read request is not contained in cache memory 214 .

Therefore, continuing to refer to FIG. 2A, in response to a cache miss, the cache memory 214 is configured to provide the virtual address of the memory read request to the compression circuit to retrieve data from the compressed data area. In this regard, the compression circuit may first query the metadata cache containing metadata cache entries, each of which contains metadata indexed by the virtual address. The metadata cache is accessed faster than the compressed data area. Metadata is data, such as a pointer, used to access a physical address (PA) in the compressed data area to access a memory entry containing compressed data of the virtual address. If the metadata cache contains metadata for the memory read request, the compression circuit uses the metadata to access the correct memory entry in the memory entry in the compressed data area to provide the corresponding compressed data area to the decompression circuit. If the metadata cache does not contain metadata for the memory read request, the compression circuit provides the virtual address for the memory read request to the metadata circuit 210, which contains metadata in the corresponding metadata entries for all virtual address spaces in the processor-based system 100. Therefore, the metadata circuit 210 can be linearly addressed by the virtual address of the memory read request. The metadata is used for a memory read request to access a correct one of the memory entries in the compressed data region to provide the corresponding compressed data region to the decompression circuitry.

2, the decompression circuit receives the compressed data region in response to the memory read request. The decompression circuit decompresses the compressed data region into uncompressed data, and then can provide the uncompressed data to the processor 104. The uncompressed data is also stored in the cache memory 214. However, if the cache memory 214 does not have an available cache entry in the cache entries, the cache memory 214 can evict one of the existing cache entries to the compressed data region to make room to store the uncompressed data.

To this end, the cache memory 214 first sends the virtual address and uncompressed cache data of the evicted cache entry to the compression circuit. The compression circuit receives the virtual address and uncompressed cache data of the evicted cache entry. The compression circuit initiates a metadata read operation on the metadata cache to obtain metadata associated with the virtual address. During, before, or after the metadata read operation, the compression circuit compresses the uncompressed cache data into compressed data to be stored in the compressed data area. If the metadata read operation on the metadata cache results in a cache miss, the metadata cache issues a metadata read operation to the metadata circuit 210 in the system memory 112 to obtain the metadata associated with the virtual address. The metadata cache is then suspended. Because access to the compressed data area can take much longer than the processor 104 can issue a memory access operation, the uncompressed data received from the processor 104 for subsequent memory write requests can be buffered in the memory request buffer.

After the metadata is returned from the compressed data area to update the metadata cache, the metadata cache provides the metadata as metadata to the compression circuit. The compression circuit determines whether the new compressed size of the compressed data area fits into the same storage block size in the compressed data area as the data previously used to store the virtual address of the evicted cache entry. For example, the processor 104 may have updated the cache data in the evicted cache entry because it was last stored in the compressed data area. If a new storage block is needed to store the compressed data area of the evicted cache entry, the compression circuit recycles the pointer to the current storage block in the compressed memory system 200 associated with the virtual address of the evicted cache entry to one of the free memory lists (e.g., list 216 of free 64B blocks, list 218 of free 48B blocks, list 220 of free 32B blocks, and list 222 of free 16B blocks) of pointers to available storage blocks in the compressed data area. The compression circuit then obtains a pointer from one of the free memory lists to a new available memory block of the desired memory block size in the compressed data region to store the compressed data region of the evicted cache entry. The compression circuit then stores the compressed data region of the evicted cache entry in a memory block in the compressed data region associated with the virtual address of the evicted cache entry determined from the metadata.

If a new memory block is assigned to the virtual address of the evicted cache entry, metadata in the metadata cache entry corresponding to the virtual address tag in the virtual address tag of the evicted cache entry is updated based on the pointer to the new memory block. Then, the metadata cache updates metadata in the metadata entry corresponding to the virtual address in the metadata cache based on the pointer to the new memory block 125.

Because metadata of metadata circuit 210 is stored in system memory 112, metadata circuit 210 may consume an excessive amount of system memory 112, thereby negatively affecting system performance. Therefore, it is desirable to minimize the amount of system memory 112 required to store metadata while still providing effective data compression. In this regard, some specific implementations of compressed memory system 200 reduce metadata size. The techniques described herein may be used to:

2A shows uncompressed data indexed linearly by metadata according to some implementations. An uncompressed cache line is represented by 3 bytes of metadata, and the metadata points to a compressed block (e.g., blocks 202, 204, and 206) of size 16 bytes, 32 bytes, 48 bytes, or 64 bytes. In some implementations, if the entire uncompressed line is 0, the metadata circuit 210 marks it as not pointing to any compressed block. In some implementations, the compressed memory system 200 includes a register file 208 that holds base pointers for blocks 202, 204, and 206, and the metadata circuit 210 provides an offset from the base pointer for the block.

FIG. 2B is a sequence diagram illustrating a method for reading cache lines using the compressed memory system shown in FIG. 2A according to some specific implementations. After an L2 cache miss, the read address of the external memory is sent to the compression or decompression engine 212, which retrieves the cached L2 metadata (if it is available). If the metadata is not available in the cache, the metadata is read from the external memory (e.g., DDR). Based on the metadata, the compressed data is taken out from the external memory from the block of the compressed data area. The compressed data is then decompressed by the decompression circuit, and the uncompressed data is returned to the processor. Using this method, a 0 cache line (e.g., 64 bytes of 0) requires one read, and other cache lines require two reads, i.e., one read for the metadata and one read for the compressed block.

FIG. 2C is a sequence diagram illustrating a method for writing cache lines using the compressed memory system shown in FIG. 2A according to some specific implementations. After an L2 cache miss, the uncompressed data is sent to the compression or decompression engine 212, and the compression circuit compresses the data to a new size. Similar to FIG. 2B, if the metadata is not available in the metadata cache, the metadata is retrieved from the external memory. If the metadata is available in the metadata cache, the metadata is retrieved from the metadata cache. Depending on the size of the compressed data, a new index for the new size can be retrieved from a free list (e.g., one of lists 216, 218, 220, 222), and the compressed data is written to the compressed data area. In some cases, the old index can be recycled and the metadata is updated in the external memory. Using this method, for cache line writes, depending on the size of the compressed block, if the cache line is all 0, the write requires a read-modify-write for the metadata, and other cache lines require a read-modify-write for the metadata and a write or a read-modify-write for the compressed data.

FIG. 3 is a schematic diagram of a packaging scheme 300 for a compressed memory system according to some specific implementations, which helps avoid the additional reading and writing of metadata described above. FIG. 3 shows a storage area (e.g., compressed data candidate) divided into a high priority portion 302 and a low priority portion 304 of equal size. In practice, the storage area can be divided into any number of partitions with different priority levels, and/or the partitions can have unequal amounts of data. A high priority cache line and a low priority cache line are selected and compressed to fit in a compressed cache line 306. In the case where the compressed high cache line and the low cache line do not fit in a compressed cache line, an overflow pointer is retained in the compressed line, which points to an overflow block (e.g., an overflow bin 308, 310, or 312, each bin having a different size). In order to avoid read-modify-write, some specific implementations use multiple overflow blocks (e.g., an overflow bin holds 32 bytes of data, an overflow bin 310 holds 64 bytes of data, and an overflow bin 312 holds 96 bytes of data). To improve write performance of high priority rows, the compressed low priority rows only occupy the lower half of the compressed rows.

4 to 9 illustrate example compressed row layouts according to some specific implementations. These examples are provided for illustration purposes and should not be interpreted to mean that the layout or organization is limited to these examples. Referring to FIG. 4 , a compressed row (CL) 400 may include: (i) an HP 402 indicating compressed data for a high priority cache line; (ii) an LP 404 indicating compressed data for a low priority cache line; (iii) an HP 406 which is a flag indicating whether the high priority cache line is compressed. For example, 1 indicates compression and 0 indicates uncompressed; (iv) an LPC 408 which is a flag indicating whether the low priority cache line is compressed. For example, 1 indicates compression and 0 indicates uncompressed; (v) an OFB 410 indicating the overflow bin size. For example, 0 indicates 32 bytes, 1 indicates 64 bytes, 2 indicates 96 bytes, and 3 indicates no overflow; (vi) OFP 412 indicating an overflow pointer index; and/or (vii) LPE 414 indicating a low priority end bit index, which indicates where the low priority compressed data ends. This information can be used to extend the high priority cache line on the write path. The value can be between 11 and 255. 0 may mean that there is no remaining space for HP to expand. A specific implementation may use any number of these fields. In some specific implementations, high priority compression or decompression starts from the HPC bit toward the OFP, as indicated by arrow 416. In some specific implementations, low priority compression or decompression starts from the OFP toward where the LPE points (as indicated by arrow 418), and if it has an overflow, it continues from right to left in the overflow area (as indicated by arrow 420). According to some specific implementations, area 420 of the CL is not used by the CL, and/or the HP 402 and LP 404 are separated by a gap 422. 4, 32 bytes are dedicated to HP, and 32 bytes are usable by HP/LP, and there are 31 control bits, including OFP 412, LPE 414, OFB 410, and LPC 408. According to some implementations, the compressed rows may have slightly different layouts depending on the HP and LP compression sizes, as further described below with reference to Figures 5 to 10. For example, the number of control bits may be reduced (e.g., because there is no overflow, OFP is not needed, and these bits are consumed by LP).

5 shows an example compressed row layout 500 when HP is less than 256 bits and the low priority row fits in the CL according to some implementations. According to some implementations, HPC is set to 1, OFB is set to 0x11, and LPC is set to 1. There are only 11 control bits (as opposed to 31 bits in FIG. 4 ).

6 shows an example compressed row layout 600 when both HP and LP fit in one CL and HP is greater than 255 bits according to some implementations. According to some implementations, HPC is set to 1, OFB is set to 0x11, and LPC is set to 1. In this example, HP has been extended into the lower half of the CL.

7 shows an example compressed row layout 700 when HP is less than 256 bits and LP has overflow according to some implementations. According to some implementations, HPC is set to 1, OFB is any value between 0x0 and 0x2, and LPC is set to 1 or 0, and OFP points to overflow block 424.

8 shows an example compressed row layout 800 when HP is greater than 255 bits but less than 480 bits and LP has overflow according to some implementations. According to some implementations, HPC is set to 1, OFB is set to a value between 0 and 2, LPC is 1 or 0, and OFP points to overflow block 426.

9 shows an example compressed row layout 900 when HP is equal to 512 bits (uncompressible) and LP has overflow according to some implementations. According to some implementations, HPC is set to 0, OFB is set to a value between 0 and 2, LPC is set to 0 or 1, and OFP points to overflow block 428. Overflow block 428 includes the remaining 32 bits of HP 430, gap 432, and LP 404.

Example read/write overhead and statistics

For cache line reads, high priority cache lines and low priority cache lines in a compressed cache line fit requires one read, and other cache lines require two reads, one for the compressed line and one for the overflow block. For cache line writes, compressed high priority cache lines fit at 255 bits require one write, compressed high priority cache lines fit at 256 bits to 480 bits require one read-modify-write, and other incompressible high priority cache lines (>480 bits) require one read-modify-write for the compressed line and one read-modify-write for the overflow block; low priority cache lines in a compressed line fit require one read-modify-write, and low priority cache lines not fit in a compressed line require one read-modify-write for the compressed line and one read-modify-write for the overflow block.

The following table shows example cache line read/write costs and statistics for modem data (50017075 bytes of compression candidate data).

According to the statistical values, 84.7% of high-priority cache lines require only one read/one write for cache line read/write. On the basis of the above, an additional 11% of high-priority cache lines require one read/one read-modify-write for cache line read/write. Only 4.3% of high-priority cache lines require two reads/two read-modify-writes for cache line read/write. 78.6% of low-priority cache lines require one read/one read-modify-write for cache line read/write. 21.4% of low-priority cache lines require two reads/two read-modify-writes for cache line read/write.

In Figures 10 to 13 described below, memory reads and writes are indicated by patterns within rectangular boxes, and all other operations (except for receiving an initial block of a read request or a write request) are shown without any patterns. In addition, operations predicted to be high probability are shown in solid lines (i.e., solid arrows indicate paths with high probability), and other paths are shown as dashed or dotted arrows. The probability of a path is based on the data distribution of a particular data set (e.g., modem data).

10 shows a flow chart of an example method 1000 for reading a high priority cache line according to some implementations. The method 1000 includes receiving (1002) a request for a HP read, and reading (1004) the CL. The method also includes determining (1006) whether the HPC is equal to 1. If the HPC is 1, the HP is decompressed. If the HPC is not 1, the overflow block pointed to by the OFP is read (1010) and 480 bits are copied (1012) from the compressed line and 32 bits are copied from the OFP block.

FIG. 11 illustrates a flow chart of an example method 1100 for reading a low priority cache line according to some implementations. The method 1100 includes receiving 1102 a request for a LP read, and reading 1104 CL. The method also includes determining 1106 whether OFB is set to 3 (hexadecimal value 0x11). If OFB is set to 3, LP is decompressed 1108 from bit 11 to the LPE bit. If OFB is not set to 3, OFP is read 1110 and bits of LPE from bit 32 to CL are decompressed and bits from the overflow block pointed to by OFP are added 1112.

FIG. 12 shows a flow chart of an example method 1200 for writing a high priority cache line according to some specific implementations. The method includes receiving (1202) an HP write request and compressing (1204) the HP line to the HPSZ bit. The method also includes determining (1206) whether the HPSZ is less than 256 bits. If the HPSZ is less than 256 bits, HPC is set to 1 and 32 bytes of HP are written (1210). The path through blocks 1202, 1204, 1206, and 1210 forms a short path and results in fast write access to the high priority cache line. If the HPSZ is not less than 256 bits, CL is read (1208). It is then determined (1212) whether the HPSZ is less than 511-LPE. If so, CL is updated with HP (1214) and HPC is set to 1, and CL is written (1216). If the HPSZ is not less than 511-LPE, it is further determined (1218) whether the OFP is set (or whether the CL has an OFP). If the OFP exists, the OFP is read (1220). If the OFP does not exist, the LP content is read and the OFP is released (1222). In addition, it is determined (1224) whether the HP is compressible (1224). If the HP is compressible, a new OFP block (1232) with a bit size greater than LPSZ-(480-HPSZ) is obtained, the new OFP with LP is updated (1234), and the CL is filled with HP and the HPC is set to 1 (1236). If the HP is not compressible, a new OFP block (1226) with a bit size greater than LPSZ+32 is obtained, the 32-bit HP overflow is copied and the new OFP is updated with LP (1228), and the CL is filled with HP and the HPC is set to 0 (1230). Subsequently, the OFP is written (1238) and the CL is written (1240).

13 illustrates a flow chart of an example method 1300 for writing a low priority cache line according to some implementations. The method 1300 includes receiving (1302) an LP write request and compressing the line to LPSZ bits and setting LPC to 1 (1304). The method also includes determining (1306) whether LPSZ is greater than 480 bits. If LPSZ is greater than 480 bits, LPSZ is set to 512 (to indicate no compression) and LPS is set to 0 (1308). If LPSZ is not greater than 480 bits, the compressed line is read (1310). It is further determined (1312) whether HPC is set to 0. If HPC is set to 0, the OFP line is read (1314). It is further determined whether the current block is greater than LPSZ plus 32. If so, the OFP is updated (1324). If the current block is not larger than LPSZ plus 32, a new OFP block with a bit size larger than LPSZ+32 is obtained (1318), the 32-bit HP is copied and the new OFP is updated (1320), and the old OFP is pushed into the free list (1322). Subsequently, the OFP is written (1326), the compression line is updated for the OFP, OFB, and LPC (1328), and the CL is written (1330). If HPC is not equal to 0 (block 1312), it is further determined (1332) whether the OFP is not set to 0xFF. If not, the OFL is released (1334). If the OFP is set to 0xFF, the HP is decompressed (1336) to find the HP end bit. It is further determined (1338) whether the HP exceeds 32 bytes. If so, LPSPACE is set to the HP end bit -11. If not, LPSPACE is set to 256-11. In either case, it is further determined (1344) whether LPSZ is less than LPSPACE. If so, the LP is packed (1346) into the CL, the compressed row is updated (1348) for (OFP set to 0x11, LPC, and LPE), and the CL is written (1350). If LPSZ is not less than LPSPACE, an OFP block of bit size greater than LPSZ-LPSPACE-20 is obtained (1352), the LP is packed (1354) into the OFP and CL, the CL is updated (1356) for (OFP, OFB, LPC, and LPE), the CL is written (1358), and the OFP is written (1360).

FIG. 14 is a block diagram of an example of a compressed memory system 1400 of a processor-based system according to some specific implementations. System 1400 includes a memory partitioning circuit 1402 configured to partition a storage area into a plurality of data areas. Each data area is associated with a corresponding priority level. The storage area includes compressed data candidates and may include data and/or instructions. For example, a software image may be linked to different parts. Each part may have a different address range. The memory partitioning circuit 1402 may be configured to distinguish different data areas based on address ranges. In FIG. 3 , according to some specific implementations, the storage area is shown as being divided into a high priority hole 302 and a low priority hole 304. Although only two holes or priority levels are shown in FIG. 3 , more than two holes (sometimes referred to as data areas) and/or more than two priority levels may be used in some specific implementations.

The compressed memory system 1400 also includes a cache line selection circuit 1404, which is configured to: (i) select a first cache line from a first data area of the plurality of data areas, and (ii) select a second cache line from a second data area of the plurality of data areas. For example, the address of the cache line can be used by the cache line selection circuit 1404 to determine whether the cache line belongs to the first data area or the second data area. Based on the determination, the cache line selection circuit 1404 can select the first cache line and the second cache line. The first data area has a higher priority level than the second data area. For example, in FIG. 3, a cache line from the high priority hole 302 and a cache line from the low priority hole 304 are selected to form a compressed cache line 306.

The compressed memory system 1400 also includes a compression circuit 1406 configured to: (i) compress the first cache line to obtain a first compressed cache line, and (ii) compress the second cache line to obtain a second compressed cache line. According to some specific implementations, examples of compression circuits are described above with reference to Figures 1, 2A, 2B, and 2C.

The compressed memory system 1400 also includes a cache line packing circuit 1408, which is configured to: based on determining that the first cache line is compressible, (i) write the first compressed cache line to a first predetermined portion of the candidate compressed cache line, and (ii) write the second cache line or the second portion of the second compressed cache line to a second predetermined portion of the candidate compressed cache line. The first predetermined portion is larger than the second predetermined portion. For example, FIG. 5 shows a high priority cache line that is compressed and written to HP 402 indicating the first predetermined portion. FIG. 5 also shows a low priority cache line that is compressed and written to LP 404 (the second predetermined portion). In some specific implementations, the first predetermined portion and the second predetermined portion may correspond to two different portions of the compressed cache line. The first predetermined portion is first filled with high priority compressed data, and then the second predetermined portion is filled with low priority data. The high priority data can overflow into the second predetermined portion, but the low priority data cannot overflow into the first predetermined portion. In some implementations, the second predetermined portion includes control bits and the first predetermined portion does not include control bits. In some implementations, the compressed data is written in different directions (eg, toward the intersection of the two portions).

In some implementations, the cache line packing circuit 1408 is further configured to: set an overflow pointer (e.g., OFP 412 in FIG. 4 ) in the candidate compressed cache line based on determining that (i) the first cache line is incompressible, (ii) the second cache line is incompressible, or (iii) the second compressed cache line does not fit within a second predetermined portion of the candidate compressed cache line. The overflow pointer points to an overflow block (e.g., one of the overflow bins 308 , 310 , or 312 ) in a plurality of overflow blocks based on a compression ratio of the second cache line or a size of the second compressed cache line. Each overflow block in the plurality of overflow blocks has a different size. For example, the overflow bins 308 , 310 , and 312 hold data of different sizes. In some implementations, the cache line packing circuit 1408 is further configured to: receive a read request for the first cache line or the second cache line; and in response to receiving the read request: retrieve data from an overflow block in the plurality of overflow blocks based on the overflow pointer based on determining that the overflow pointer is set. According to some implementations, examples of overflow blocks and overflow logic are described above with reference to Figures 3, 4, 7, 8, and 9. According to some implementations, example methods for reading are described above with reference to Figures 10 and 11.

In some implementations, the cache line packing circuit 1408 is further configured to: in accordance with determining that the first cache line is compressible: set a first compression rate control bit (e.g., HPC 406) in the candidate compressed cache line; and in accordance with determining that the first cache line is not compressible: write a first portion of the first cache line to the candidate compressed cache line; write the remaining portion of the first cache line to the overflow block; reset the first compression rate control bit in the candidate compressed cache line; and set an overflow pointer in the candidate compressed cache line to point to the overflow block. In accordance with some implementations, an example is described above with reference to FIG. 9. In some implementations, the cache line packing circuit 1408 is further configured to: in response to receiving a read request for the first cache line: in accordance with determining that the first compression rate control bit is set: retrieve the first cache line from the candidate compressed cache line; and in accordance with determining that the first compression rate control bit is reset: retrieve a first portion of the first cache line from the candidate compressed cache line; and retrieve a second portion of the first cache line from the overflow block based on the overflow pointer. In some implementations, the cache line packing circuit 1408 is further configured to: based on determining that the first cache line is incompressible: based on whether the second cache line is compressible, write the second cache line or the second compressed cache line to the overflow block; and reset the second compression rate control bit (e.g., LPC 408) in the candidate compressed cache line to indicate whether the second cache line is incompressible. In some implementations, the cache line packing circuit 1408 is further configured to: in response to receiving a read request for the second cache line: retrieve the second cache line or the second compressed cache line from the overflow block based on the second compression rate control bit. According to some implementations, the above describes an example method for reading a high priority cache line and a low priority cache line with reference to Figures 10 and 11, respectively.

In some implementations, the cache line packing circuit 1408 is further configured to: in response to receiving a cache line write request for a first cache line: compress the first cache line (e.g., using the compression circuit 1406) to obtain a first updated cache line having a first size; write the first updated cache line to the candidate compressed cache line based on a determination that the first size is equal to or less than a first predetermined size of the candidate compressed cache line; perform a read-modify-write operation on the candidate compressed cache line based on the first updated cache line based on a determination that the first size is greater than the first predetermined size and equal to or less than a second predetermined size of the candidate compressed cache line; and perform a read-modify-write operation on the candidate compressed cache line based on the first updated cache line and perform a read-modify-write operation on an overflow block of the plurality of overflow blocks based on a determination that the first size is greater than the second predetermined size of the candidate compressed cache line. In some implementations, the first predetermined size is half the size of the candidate compressed cache line. In some specific implementations, the cache line packing circuit 1408 is also configured to: when writing the second cache line or the second portion of the second compressed cache line to the second predetermined portion of the candidate compressed cache line, write an end bit index (e.g., LPE414) in the candidate compressed cache line to indicate where the second cache line or the second portion of the second compressed cache line is written within the candidate compressed cache line; and calculate the second predetermined size based on the end bit index in the candidate compressed cache line.

In some implementations, the cache line packing circuit 1408 is further configured to: in response to receiving a cache line write request for a second cache line: compress the second cache line to obtain a second updated cache line having a second size; based on determining that the sum of the second size and the size of the first compressed cache line is less than a first predetermined size of the candidate compressed cache line, perform a read-modify-write operation to write the second updated cache line to the candidate compressed cache line; and based on determining that the sum of the second size and the size of the first compressed cache line is not less than the first predetermined size of the candidate compressed cache line, (i) perform a first read-modify-write operation to write a first portion of the second updated cache line to the candidate compressed cache line, and (ii) perform a second read-modify-write operation to write a remaining portion of the second updated cache line to the overflow block pointed to by the overflow pointer. In some implementations, for high priority cache lines, there is no control bit to indicate where the HP ends. In this case, the system decompresses the HP portion to determine this information. In some implementations, this is not a true decompression, but rather the end is determined by scanning the HP through the compressed bits (a process very similar to decompression). Some implementations reserve bits 8 to 9 to indicate the end of the HP, just like the LP side.

In some implementations, the cache line packing circuit 1408 is further configured to: in response to receiving a cache line write request for the first cache line or the second cache line: compress the first cache line or the second cache line to obtain an updated compressed cache line with an updated size; and based on determining that the updated size cannot fit within the overflow block pointed to by the overflow pointer, release the overflow pointer and update the overflow pointer to point to a new overflow block in the plurality of overflow blocks. According to some implementations, examples for operating the free list are described above with reference to FIGS. 12 and 13.

In some implementations, the first compressed cache line, the second compressed cache line, and the candidate compressed cache line have equal sizes. For example, in Figure 3, each cache line from regions 302, 304 and compressed cache line 306 has 64 bytes.

In some implementations, the first data region and the second data region have equal sizes. For example, in Figure 3, regions 302 and 304 have equal sizes (eg, the regions have equal numbers of cache lines).

In some implementations, the second predetermined portion is less than half the size of the candidate compressed cache line.According to some implementations, examples of layouts are described above with reference to FIGS.

In some implementations, the cache line packing circuit 1408 is further configured to write the first compressed cache line and the second compressed cache line to the candidate compressed cache line in opposite directions. The first compressed cache line and the second compressed cache line are separated by one or more bytes.

On the other hand, a compressed memory system of a processor-based system is provided. The compressed memory system includes a storage area, which includes a plurality of cache lines. For example, FIG. 3 shows two storage areas 302 and 304. Each cache line has a priority level in a plurality of priority levels. For example, the cache line in area 302 has a higher priority than the cache line in area 304. The compressed memory system also includes a compressed storage area (e.g., an area including compressed cache line 306), which includes a plurality of compressed cache lines. Each compressed cache line includes a first group of data bits, which is configured to keep a portion of a first cache line or a portion of a compressed first cache line in a first direction, and the first cache line has a first priority level. For example, according to some specific implementations, the layout shown in FIG. 4 shows a compressed cache line of HP 402 including bits for storing high priority cache lines. Each compressed cache line also includes a second set of data bits that are configured to hold a portion of a second cache line or a compressed portion of a second cache line in a second direction opposite to the first direction, the second cache line having a second priority level lower than the first priority level. For example, according to some specific implementations, the layout shown in FIG. 4 shows a compressed cache line including an LP 404 for storing bits for low priority cache lines. The first set of data bits includes a greater number of bits than the second set of data bits. HP 402 stores compressed bits in a direction opposite to LP 404. The layout in FIG. 4 shows that bits for high priority cache lines can occupy HP 402 and region 420, while bits for low priority cache lines can occupy only LP 404, which is smaller in size than HP 402.

In some specific implementations, the compressed memory system also includes an overflow storage area, which includes multiple overflow bins (e.g., overflow block 426). Each overflow bin is configured to keep different numbers of bytes. For example, overflow blocks 308, 310 and 312 each include different numbers of bytes. Each compressed cache line also includes a set of overflow pointer bits (e.g., OFP 412), which is configured to keep a pointer to an overflow bin in the multiple overflow bins.

In some implementations, each compressed cache line further includes: a first control bit (eg, HPC 406) indicating a compression rate for the first cache line; and a second control bit (eg, LPC 408) indicating a compression rate for the second cache line.

In some implementations, the compressed memory system further includes an overflow storage area, the overflow storage area including a plurality of overflow bins. Each overflow bin is configured to hold a different number of bytes. Each compressed cache line further includes a set of bits (e.g., OFB 410) configured to hold the size of one of the plurality of overflow bins.

In some implementations, each compressed cache line also includes an end bit index (eg, LPE 414) indicating the end of the second set of data bits.

In some implementations, each overflow bin is configured to hold bits of the first cache line and/or bits of the second cache line or the compressed second cache line in a first direction. For example, as shown in FIG. 4 , overflow bin 420 holds bits in the same direction as HP 402 .

In some implementations, the first set of data bits and the second set of data bits are separated by one or more bytes. For example, in FIG. 4 , HP 402 and LP 404 are separated by gap 422 .

In some implementations, each cache line and each compressed cache line have the same size. For example, in Figure 3, each cache line 302 and 304, each compressed cache line 306 includes 64 bytes.

In some specific implementations, when the compressed first cache line or the compressed second cache line does not fit in the compressed cache line, each compressed cache line also includes a set of overflow pointer bits, which are configured to keep a pointer to an overflow bin in the multiple overflow bins. The overflow bin is configured to keep the first cache line, the compressed first cache line, the second cache line and/or the compressed second cache line. In other words, as shown in Figures 5 and 6, OFP 412 is optional and is used only when there is an overflow. When both compressed cache lines fit in the compressed cache line, the OFP bit is not used.

In some implementations, the second set of data bits is further configured to hold a plurality of control bits that indicate an overflow in the compressed cache line (eg, OFP 412, OFB 410) and the end of the second set of data bits (eg, LPE 414).

It will be understood that although the terms "first", "second", etc. may be used herein to describe various elements, these elements should not be limited by these terms. These terms are only used to distinguish one element from another.

The terms used herein are only for the purpose of describing specific embodiments and are not intended to limit the claims. As used in the description of the embodiments and the description of the appended claims, the singular forms of "one", "a kind of" and "the" are intended to include plural forms unless the context clearly indicates otherwise. It will also be understood that the term "and/or" as used herein refers to and encompasses any and all possible combinations of one or more of the associated listed items. It will be further understood that the terms "include" and/or "comprising" when used in this specification specify the presence of stated features, wholes, steps, operations, elements and/or components, but do not exclude the presence or addition of one or more other features, wholes, steps, operations, elements, components and/or their groups.

As used herein, the term “if” may be interpreted to mean “when” or “at” or “in response to determining” or “upon determining” or “in response to detecting” the stated antecedent condition is true, depending on the context. Similarly, the phrase “if it is determined that [the stated antecedent condition is true]” or “if [the stated antecedent condition is true]” or “when [the stated antecedent condition is true]” may be interpreted to mean “upon determining” or “in response to determining” or “upon determining” or “upon detecting” or “in response to detecting” the stated antecedent condition is true, depending on the context.

For the purpose of explanation, the foregoing description has been described with reference to specific implementations. However, the above illustrative discussion is not intended to be exhaustive or to limit the claims to the precise forms disclosed. In view of the above teachings, many modifications and variations are possible. Specific implementations are selected and described in order to best explain the operating principles and practical applications, thereby enabling others skilled in the art to implement.

Claims (34)

1. A method for compressing data in a compressed memory system of a processor-based system, the method comprising:

Dividing the storage area into a plurality of data areas, each data area being associated with a respective priority level;

(i) Selecting a first cache line from a first data region of the plurality of data regions, and (ii) selecting a second cache line from a second data region of the plurality of data regions, wherein the first data region has a higher priority level than the second data region;

(i) Compressing the first cache line to obtain a first compressed cache line, and (ii) compressing the second cache line to obtain a second compressed cache line; and

In accordance with a determination that the first cache line is compressible:

(i) Writing the first compressed cache line to a first predetermined portion of a candidate compressed cache line, and (ii) writing the second cache line or a second portion of the second compressed cache line to a second predetermined portion of the candidate compressed cache line, wherein the first predetermined portion is greater than the second predetermined portion.

2. The method of claim 1, the method further comprising:

In accordance with a determination that (i) the first cache line is incompressible, (ii) the second cache line is incompressible, or (iii) the second compressed cache line is not fit within the second predetermined portion of the candidate compressed cache line, an overflow pointer is set in the candidate compressed cache line, wherein the overflow pointer points to one of a plurality of overflow blocks, and wherein each of the plurality of overflow blocks has a different size, in accordance with a compression rate of the second cache line or a size of the second compressed cache line.

3. The method of claim 2, the method further comprising:

receiving a read request for the first cache line or the second cache line; and

In response to receiving the read request:

in accordance with a determination that the overflow pointer is set, data is retrieved from an overflow block of the plurality of overflow blocks in accordance with the overflow pointer.

4. The method of claim 1, the method further comprising:

In accordance with a determination that the first cache line is compressible:

setting a first compression rate control bit in the candidate compressed cache line; and

In accordance with a determination that the first cache line is incompressible:

writing a first portion of the first cache line to the candidate compressed cache line;

Writing the remainder of the first cache line to an overflow block;

Resetting the first compression rate control bit in the candidate compressed cache line; and

An overflow pointer is set in the candidate compressed cache line to point to the overflow block.

5. The method of claim 4, the method further comprising:

In response to receiving a read request for the first cache line:

in accordance with a determination that the first compression ratio control bit is set:

Retrieving the first cache line from the candidate compressed cache line; and

In accordance with a determination that the first compression ratio control bit is reset:

Retrieving the first portion of the first cache line from the candidate compressed cache line; and

The second portion of the first cache line is retrieved from the overflow block based on the overflow pointer.

6. The method of claim 4, the method further comprising:

In accordance with a determination that the first cache line is incompressible:

writing the second cache line or the second compressed cache line to the overflow block according to whether the second cache line is compressible; and

A second compression rate control bit in the candidate compressed cache line is reset to indicate whether the second cache line is incompressible.

7. The method of claim 6, the method further comprising:

In response to receiving a read request for the second cache line:

The second cache line or the second compressed cache line is retrieved from the overflow block based on the second compression rate control bit.

8. The method of claim 2, the method further comprising:

in response to receiving a cache line write request for the first cache line:

compressing the first cache line to obtain a first updated cache line of a first size;

in accordance with a determination that the first size is equal to or less than a first predetermined size of the candidate compressed cache line, writing the first updated cache line to the candidate compressed cache line;

Performing a read-modify-write operation on the candidate compressed cache line based on the first updated cache line in accordance with determining that the first size is greater than the first predetermined size and equal to or less than a second predetermined size of the candidate compressed cache line; and

In accordance with a determination that the first size is greater than the second predetermined size of the candidate compressed cache line, a read-modify-write operation is performed on the candidate compressed cache line and a read-modify-write operation is performed on an overflow block of the plurality of overflow blocks based on the first updated cache line.

9. The method of claim 8, wherein the first predetermined size is half a size of the candidate compressed cache line.

10. The method of claim 8, the method further comprising:

Writing an end bit index in the candidate compressed cache line to indicate where the second cache line or the second portion of the second compressed cache line is written within the candidate compressed cache line when writing the second cache line or the second portion of the second compressed cache line to the second predetermined portion of the candidate compressed cache line; and

The second predetermined size is calculated based on the end bit index in the candidate compressed cache line.

11. The method of claim 2, the method further comprising:

in response to receiving a cache line write request for the second cache line:

compressing the second cache line to obtain a second updated cache line of a second size;

In accordance with a determination that a sum of the second size and the size of the first compressed cache line is less than a first predetermined size of the candidate compressed cache line, performing a read-modify-write operation to write the second updated cache line to the candidate compressed cache line; and

In accordance with a determination that the sum of the second size and the size of the first compressed cache line is not less than the first predetermined size of the candidate compressed cache line, (i) performing a first read-modify-write operation to write a first portion of the second updated cache line to the candidate compressed cache line, and (ii) performing a second read-modify-write operation to write a remaining portion of the second updated cache line to an overflow block pointed to by the overflow pointer.

12. The method of claim 2, the method further comprising:

in response to receiving a cache line write request to the first cache line or the second cache line:

compressing the first cache line or the second cache line to obtain an updated compressed cache line having an updated size; and

In accordance with a determination that the updated size cannot fit within the overflow block pointed to by the overflow pointer, the overflow pointer is released and updated to point to a new overflow block of the plurality of overflow blocks.

13. The method of claim 1, wherein the first compressed cache line, the second compressed cache line, and the candidate compressed cache line are of equal size.

14. The method of claim 1, wherein the first data region and the second data region are of equal size.

15. The method of claim 1, wherein the second predetermined portion is less than half a size of the candidate compressed cache line.

16. The method of claim 1, wherein the first compressed cache line and the second compressed cache line are written to the candidate compressed cache line in opposite directions, and wherein the first compressed cache line and the second compressed cache line are separated by one or more bytes.

17. A compressed memory system of a processor-based system, the compressed memory system comprising:

a memory partitioning circuit configured to partition a storage area into a plurality of data areas, each data area being associated with a respective priority level;

a cache line selection circuit configured to: (i) Selecting a first cache line from a first data region of the plurality of data regions, and (ii) selecting a second cache line from a second data region of the plurality of data regions, wherein the first data region has a higher priority level than the second data region;

a compression circuit configured to: (i) Compressing the first cache line to obtain a first compressed cache line, and (ii) compressing the second cache line to obtain a second compressed cache line; and

A cache line encapsulation circuit configured to:

In accordance with a determination that the first cache line is compressible:

(i) Writing the first compressed cache line to a candidate compressed cache

A first predetermined portion of a cache line, and (ii) writing a second portion of the second cache line or the second compressed cache line to a second predetermined portion of the candidate compressed cache line, wherein the first predetermined portion is greater than the second predetermined portion.

18. The compressed memory system of claim 17, wherein the cache line packaging circuitry is further configured to:

In accordance with a determination that (i) the first cache line is incompressible, (ii) the second cache line is incompressible, or (iii) the second compressed cache line is not fit within the second predetermined portion of the candidate compressed cache line:

setting an overflow pointer in the candidate compressed cache line, wherein the overflow pointer points to one of the plurality of overflow blocks according to a compression rate of the second cache line or a size of the second compressed cache line, and wherein each of the plurality of overflow blocks has a different size.

19. The compressed memory system of claim 18, wherein the cache line packaging circuitry is further configured to:

receiving a read request for the first cache line or the second cache line; and

In response to receiving the read request:

in accordance with a determination that the overflow pointer is set, data is retrieved from an overflow block of the plurality of overflow blocks in accordance with the overflow pointer.

20. The compressed memory system of claim 17, wherein the cache line packaging circuitry is further configured to:

In accordance with a determination that the first cache line is compressible:

setting a first compression rate control bit in the candidate compressed cache line; and

In accordance with a determination that the first cache line is incompressible:

writing a first portion of the first cache line to the candidate compressed cache line;

Writing the remainder of the first cache line to an overflow block;

Resetting the first compression rate control bit in the candidate compressed cache line; and

An overflow pointer is set in the candidate compressed cache line to point to the overflow block.

21. The compressed memory system of claim 20, wherein the cache line packaging circuitry is further configured to:

In response to receiving a read request for the first cache line:

in accordance with a determination that the first compression ratio control bit is set:

Retrieving the first cache line from the candidate compressed cache line; and

In accordance with a determination that the first compression ratio control bit is reset:

Retrieving the first portion of the first cache line from the candidate compressed cache line; and

The second portion of the first cache line is retrieved from the overflow block based on the overflow pointer.

22. The compressed memory system of claim 21, wherein the cache line packaging circuitry is further configured to:

In accordance with a determination that the first cache line is incompressible:

writing the second cache line or the second compressed cache line to the overflow block according to whether the second cache line is compressible; and

A second compression rate control bit in the candidate compressed cache line is reset to indicate whether the second cache line is incompressible.

23. The compressed memory system of claim 22, wherein the cache line packaging circuitry is further configured to:

In response to receiving a read request for the second cache line:

The second cache line or the second compressed cache line is retrieved from the overflow block based on the second compression rate control bit.

24. The compressed memory system of claim 18, wherein the cache line packaging circuitry is further configured to:

in response to receiving a cache line write request for the first cache line:

compressing the first cache line to obtain a first updated cache line of a first size;

in accordance with a determination that the first size is equal to or less than a first predetermined size of the candidate compressed cache line, writing the first updated cache line to the candidate compressed cache line;

Performing a read-modify-write operation on the candidate compressed cache line based on the first updated cache line in accordance with determining that the first size is greater than the first predetermined size and equal to or less than a second predetermined size of the candidate compressed cache line; and

In accordance with a determination that the first size is greater than the second predetermined size of the candidate compressed cache line, a read-modify-write operation is performed on the candidate compressed cache line and a read-modify-write operation is performed on an overflow block of the plurality of overflow blocks based on the first updated cache line.

25. The compressed memory system of claim 24, wherein the first predetermined size is half the size of the candidate compressed cache line.

26. The compressed memory system of claim 24, wherein the cache line packaging circuitry is further configured to:

Writing an end bit index in the candidate compressed cache line to indicate where the second cache line or the second portion of the second compressed cache line is written within the candidate compressed cache line when writing the second cache line or the second portion of the second compressed cache line to the second predetermined portion of the candidate compressed cache line; and

The second predetermined size is calculated based on the end bit index in the candidate compressed cache line.

27. The compressed memory system of claim 18, wherein the cache line packaging circuitry is further configured to:

in response to receiving a cache line write request for the second cache line:

compressing the second cache line to obtain a second updated cache line of a second size;

In accordance with a determination that a sum of the second size and the size of the first compressed cache line is less than a first predetermined size of the candidate compressed cache line, performing a read-modify-write operation to write the second updated cache line to the candidate compressed cache line; and

In accordance with a determination that the sum of the second size and the size of the first compressed cache line is not less than the first predetermined size of the candidate compressed cache line, (i) performing a first read-modify-write operation to write a first portion of the second updated cache line to the candidate compressed cache line, and (ii) performing a second read-modify-write operation to write a remaining portion of the second updated cache line to the overflow block pointed to by the overflow pointer.

28. The compressed memory system of claim 18, wherein the cache line packaging circuitry is further configured to:

in response to receiving a cache line write request to the first cache line or the second cache line:

compressing the first cache line or the second cache line to obtain an updated compressed cache line having an updated size; and

In accordance with a determination that the updated size cannot fit within the overflow block pointed to by the overflow pointer, the overflow pointer is released and updated to point to a new overflow block of the plurality of overflow blocks.

29. The compressed memory system of claim 17, wherein the first compressed cache line, the second compressed cache line, and the candidate compressed cache line are of equal size.

30. The compressed memory system of claim 17, wherein the first data region and the second data region are of equal size.

31. The compressed memory system of claim 17, wherein the second predetermined portion is less than half a size of the candidate compressed cache line.

32. The compressed memory system of claim 17, wherein the cache line packaging circuitry is further configured to:

the first compressed cache line and the second compressed cache line are written to the candidate compressed cache line in opposite directions, wherein the first compressed cache line and the second compressed cache line are separated by one or more bytes.

33. A non-transitory computer-readable medium having stored thereon computer-executable instructions that, when executed by a processor, cause the processor to:

Dividing the storage area into a plurality of data areas, each data area being associated with a respective priority level;

(i) Selecting a first cache line from a first data region of the plurality of data regions, and (ii) selecting a second cache line from a second data region of the plurality of data regions, wherein the first data region has a higher priority level than the second data region;

(i) Compressing the first cache line to obtain a first compressed cache line, and (ii) compressing the second cache line to obtain a second compressed cache line; and

In accordance with a determination that the first cache line is compressible:

(i) Writing the first compressed cache line to a first predetermined portion of a candidate compressed cache line, and (ii) writing the second cache line or a second portion of the second compressed cache line to a second predetermined portion of the candidate compressed cache line, wherein the first predetermined portion is greater than the second predetermined portion.

34. The non-transitory computer-readable medium of claim 33 having stored thereon computer-executable instructions that, when executed by a processor, further cause the processor to:

In accordance with a determination that (i) the first cache line is incompressible, (ii) the second cache line is incompressible, or (iii) the second compressed cache line is not fit within the second predetermined portion of the candidate compressed cache line:

setting an overflow pointer in the candidate compressed cache line, wherein the overflow pointer points to one of the plurality of overflow blocks according to a compression rate of the second cache line or a size of the second compressed cache line, and wherein each of the plurality of overflow blocks has a different size.