Hybrid cache memory and method for reducing latency in the same

A method for controlling a cache comprising receiving a request for data and determining whether the requested data is present in a first portion of the cache, a second portion of cache, or not in the cache. If the requested data is not located in the MRU portion of the cache, moving the data into the first portion of the cache.

TECHNICAL FIELD

This relates to semiconductor memory devices and more particularly to hybrid cache memory devices and methods for reducing latency (e.g., average latency) in hybrid cache memory devices.

BACKGROUND

Modern processors generally employ main memory to be used in connection with a processor for program and data storage. To speed up the access of main memory, cache memory may be inserted between main memory and the processor to store frequently accessed data and codes. Cache memory generally operates faster than main memory so requests for data from cache memory are generally completed more quickly. Cache memory can be implemented using different types of semiconductor memory. Cache memory may be located close to or on the same chip as the associated processor.

DETAILED DESCRIPTION

Cache memory is a type of memory that is used in connection with processors (e.g., central processing units (CPU), accelerated processing units (APU), and/or graphics processing units (GPU)) to reduce memory access latency and to address bandwidth pressures associated with main memory. Cache memory generally comprises a data array and a tag array. The data array stores data for use by the processor and the tag array stores address and other status information (e.g., if the data has been changed or not) for the data stored in the data array. In some embodiments, the cache may also maintain replacement information to manage the cache during different operations (e.g., if a cache miss occurs and the relevant portion of cache is full). Cache may be located close to or on the same chip as the associated processor. Caches can be implemented using a variety of circuits based on various semiconductor technologies. For example, cache memory may be implemented using static random access memory (SRAM) circuits based on complementary metal oxide semiconductor (CMOS) technology. SRAM memory cells may consist of six transistors (e.g., a pair of cross-coupled inverters and two access devices). SRAM memory devices are relatively fast compared to alternative memory technologies and are therefore commonly used over alternative technologies. However, SRAM memory devices may be relatively large compared to alternative memory circuits and technologies and therefore, they occupy more space than possible alternative memory technologies.

In certain embodiments, it may be desirable to include a relatively large amount of cache in a processing system. If such a cache were composed of SRAM memory, that cache might occupy an unacceptable amount of space within the processing system. Accordingly, an alternative memory technology may be considered. The alternative memory technology may be one that has a smaller cell size than the SRAM memory cells, such as a magnetic random access memory (MRAM) or a spin-transfer torque MRAM (STT-MRAM). MRAM and STT-MRAM are generally smaller than SRAM but can be slower than SRAM. For example, an STT-MRAM cell may be structured to only include a single transistor and a magnetic tunnel junction (MTJ) instead of the six transistors that typically make up an SRAM call. MRAM is non-volatile and typically consumes less power in standby mode in comparison with SRAM. But, MRAM does have its disadvantages. For example, due to the relatively small resistivity difference between different logic states, it may be more difficult to sense the correct data value from an MRAM cell, resulting in a longer latency.

To mitigate the tradeoff between size and speed for cache design, a hybrid approach may be utilized in which a portion of the data array of the cache is implemented using one type of memory cell (e.g., faster SRAM cells) and another portion of the cache is implemented using another type of memory cell (e.g., smaller MRAM cells). By combining two different memory technologies, memory density and latency can both be improved.

To obtain acceptable average latency, in some embodiments, the hybrid cache may be designed such that the majority of accesses to the hybrid cache are to the portion of the hybrid cache implemented with the fast memory technology (e.g., SRAM).

In operation, most of the cache accesses are directed to the most recently used (MRU) data in the system. Accordingly, in some embodiments, the MRU data may be maintained in SRAM (e.g., always available for access in SRAM). This type of policy may involve swapping data between e.g., SRAM and MRAM during operation so that the most recently used data is stored in the faster SRAM portion.

FIG. 1is a schematic diagram illustrating an example of a hybrid cache memory in accordance with some embodiments.FIG. 1illustrates a cache100which includes a plurality of cache sets, including cache set10. Although multiple cache sets are illustrated, for the purposes of illustration, only one cache set10will be discussed with reference to the embodiment illustrated inFIG. 1. The cache set may include a plurality of ways12,14,16and each way12,14,16may include a corresponding block of data12A,14A,16A. As illustrated, the plurality of ways (n) may be identified as way_0, way_1 . . . way_n−1. Each block12A,14A,16A may include a plurality of memory cells for storing data.

The cache100may also be in communication with a processor20configured to communicate with the cache100and hardware logic22configured to control the operation of the cache100. In particular, as described herein, requests for data may be made from the processor20and the movement of data within the cache may be controlled by the hardware logic22.

As illustrated inFIG. 1, the cache set10includes one SRAM way12and a plurality of MRAM ways (way_1-Way_N−1)14,16. SRAM way12includes block12A. MRAM way14includes block14A. MRAM way16includes block16A. In operation data in individual memory cells within a block14A,16A can be addressed and accessed individually. However, data may be copied or moved by block to take advantage of spatial locality.

As discussed above, in operation, most of the cache accesses are directed to the most recently used (MRU) data in the system. However, to take further advantage of the hybrid cache100and further reduce average latency, it may be desirable to increase the number of cache accesses directed to the faster portion of the cache—the SRAM12. Accordingly, in some embodiments, the MRU data may be maintained in SRAM (e.g., always available for access in SRAM). As illustrated inFIG. 1, the MRU portion of the cache100is block12A within the SRAM way12. Accordingly, to increase the number of cache accesses to the SRAM12, the policy may involve swapping data between e.g., an SRAM portion of the cache12and an MRAM portion of the cache14,16during operation. By implementing a policy where the MRU block12A of data is moved to SRAM, the average latency of the cache100can be reduced. To achieve this, data may be read from the SRAM portion of memory12into a buffer11via operation15and from the MRAM portion of memory14,16into buffer13via operation17. Then via operations18and19the data locations can be switched or altered.

In some embodiments, in operation, there are five possible scenarios when an access for data is issued by a processor, (e.g., processor20:The requested data is already in the MRU portion (e.g., block12A) of the SRAM way12;The requested data is not located in the hybrid cache100and there are empty blocks (e.g.,12A,14A, and/or16A in the cache sets10;The requested data is not located in the hybrid cache100and all of the blocks12A,14A,16A in the cache set10are filled with data;The requested data is in the least recently used (LRU) portion of the cache100; orThe requested data is in the cache100and is not located in the MRU portion12A or the LRU portion of the cache100.

In some embodiments, each of these five scenarios may be addressed with a corresponding procedure.

If the requested data is already in the MRU portion (e.g., block12A) of the SRAM12, the procedure accesses the data from the MRU portion of the cache100and does not move any data between different portions of the cache100or other non-cache memory. In some embodiments, this procedure may be executed in about 80% of the data access requests.

If the requested data is not located in the hybrid cache100and there are empty blocks12A,14A,16A in the cache set10, the procedure may proceed in one of two ways. If the MRU block12A is empty, the data is loaded into the MRU block12A. Additionally, the pointer identifying the LRU block (e.g.,16A) remains unchanged. However, if the MRU block12A already contains data, the existing data is moved to buffer11and then to the current LRU block (e.g.,16A) and the pointer for the LRU block is updated (e.g., incremented) such that it points to a new block of data. The MRU block12A is then updated with the requested data.

If the requested data is not located in the hybrid cache100and all of the blocks12A,14A,16A in the cache set10are filled with data, the procedure proceeds by writing any data in LRU block back to a non-volatile main memory (e.g., if there are changes) and moving the existing data in the MRU block12A to the current LRU block. The pointer for the LRU block is updated (e.g., incremented) such that it points to a new block of data and the MRU block12A is then updated with the requested data.

If the requested data is in the LRU portion of the cache100, the procedure proceeds by swapping the data in the existing MRU block12A with the data in the current LRU block and then updating (e.g., incrementing) the pointer corresponding to the LRU block.

If the requested data is in the cache100and not located in the MRU portion or the LRU portion of the cache100, the procedure proceeds by swapping the data in the MRU block12A with the requested data in the non MRU, non LRU block. In this situation, the pointer for the LRU block is not updated.

FIG. 2is a flow chart illustrating the operation of a hybrid cache in accordance with some embodiments. The embodiment inFIG. 2is merely an example of the operation of the hybrid cache. In some embodiments, the operation may be implemented in hardware via e.g., a finite state machine. While this embodiment addresses all five operating scenarios discussed above, other embodiments, may achieve similar results in different manners (e.g., by reordering the steps of the illustrated process) or by selecting an entirely different process. The example ofFIG. 2is not limited to any specific hardware implementation and is applicable to many hardware arrangements. The example is described below while referencing the hardware example ofFIG. 1for ease of visualization. Additionally, in some embodiments, the operations described herein may be skipped, additional operations may be added and/or the order of operations may be changed.

Initially, in operation202, the system (e.g., the system illustrated inFIG. 1) requests data. In operation204, the system determines whether the requested data is present in the cache100. If the data is in the cache100, the process continues with operation208where the system determines whether the requested data is in the MRU block (e.g.,12A). If the data is present in the MRU block12A, the system retrieves the requested data from the MRU block12A in operation212.

If the requested data is not in the MRU block12A, the system, in operation214, determines whether the requested data is in the LRU block16A. If the data is in the LRU block16A, the system swaps the data in the MRU block and the LRU block in operation216. Then the pointer for the LRU block is incremented in operation218and the data is retrieved from the MRU block12A in operation212.

If the requested data is not in the LRU block16A, the requested data in the target block (i.e., the block where the data is located) is swapped with the data from the MRU block12A in operation210and the target data is retrieved from the MRU block12A in operation212.

If operation204determines the requested data is not in the cache100, the process continues with operation220where the system determines whether there are any empty cache blocks. If there are empty cache blocks, the system determines whether the MRU block12A is empty. If the MRU block12A is empty, the system moves the target data to the MRU block in operation224and then retrieves the requested data from the MRU block in operation212. If the MRU block12A is not empty, the system moves the data in the MRU block12A to the LRU block16A in operation226and then moves the target data to the MRU block in operation228. In operation218, the pointer for the LRU block is incremented and, in operation212, the requested data is retrieved from the the MRU block12A.

If the system determined there were no empty cache blocks in operation220then, in operation230, the system determines whether the data in the LRU block16A is dirty (i.e., whether it is changed relative to what is stored in the main memory of the system). If the LRU data is not dirty, the system continues to operation232whether the data in the MRU block12A is moved to the LRU block16A. If the LRU block was dirty, the LRU data is written back to the main memory in operation236before performing operation232. Next, in operation234, the target data is moved to the MRU block12A and the pointer for the LRU block is incremented in operation218. In operation212, the requested data is retrieved from the MRU block12A. As should be appreciated, the process for loading data into the cache may be handled in different manners. For example, the example discussed above with respect toFIG. 1describes an alternative embodiment for loading data, not already in the cache100, into the cache100. While the embodiment inFIG. 2is described with reference to blocks12A and16A, it should be readily understood that the process may be performed in connection with any combination of blocks (e.g.,12A and14A).

FIG. 3is a table illustrating an example of the operation of a hybrid cache in accordance with some embodiments. The embodiment illustrated inFIG. 3is of an eight way (way_0, way_1, way_2, way_3, way_4, way_5, way_6, way_7) cache with a single cache set10. Each row of the table indicates a data request by the system. The data request is for the data in the first column (Reference). The second column describes which of the five conditions the requests corresponds to (hit/miss). The next eight columns correspond to ways of data (e.g., way_0, way_1, . . . way_n−1). As illustrated, the first of the eight columns corresponds to the MRU (M) way_0 (or a block (e.g.,12A) within the way) and the remaining seven ways or blocks correspond to the remaining ways in the cache set10(way_1, way_2, way_3, way_4, way_5, way_6, way_7). The shaded cell (way_1 in the first row, way_2 in the second row, etc) in the diagram corresponds to the LRU (L) block and as can be readily seen, the location of the LRU changes as a function of the LRU pointer which may be updated based on certain requests (described in more detail below). The last column describes the changes that occur to the cache set10based on the data request.

In the first row ofFIG. 3(below the headings), a request for data A is made. Since the cache set (way_0, way_1, way_2, way_3, way_4, way_5, way_6, way_7) is empty, because this is the beginning of the process, data A is loaded into the MRU block from main memory. In the next row (2), a request for data B is made. As discussed above, in certain embodiments, it may be desirable to consistently retrieve the requested data from the MRU block. Since the MRU block (way_0) does not include data B, the data A in MRU block (way_0) is moved to the block currently identified as the LRU block (way_1) so the data B can be loaded into the MRU block (way_0). A new LRU block (way_2) is identified by incrementing an LRU block pointer to the next block (LRU++). In the next two rows (3, 4) the same operation performed in row 2 is performed but with respect to data C and D respectively. The operations in rows 1-4 are referred to a “miss with empty way” because the requested data is not in the MRU block (way_0) and there are empty ways in the cache to load new data. In the fifth row (5), a request for data C is made. Since data C is not in the MRU block (way_0), but it is located in a non-LRU block (way_1) within the cache, this operation is referred to as a “hit to non-LRU). The data C in the non-LRU block (way_3) is swapped with the data D in the MRU block(way_0). Since the operation does not involve the LRU block (way_4), the LRU block pointer remains unchanged. The operation in row six (6) is similar to the operation in row five because the data A is in a non-LRU block. Accordingly, the data A in way_1) is swapped with data C In way_0. In rows seven, eight, and nine (7, 8, 9), a request for data (E, F, G) is made and the data is not in the cache (e.g., because it has not been used recently). This is similar to the data requests illustrated in rows 1, 2, 3, and 4. In this case, the data in the MRU block (way_0) is moved to the LRU block (way_4, way_5, way_6) and the LRU block pointer is incremented to the next block (way_5, way_6, way_7). Row ten (10) illustrates a similar operation to rows five and six discussed above in that the requested data is in a non-LRU block.

Row eleven (11) illustrates a similar operation to rows 1, 2, 3, 4, 7, 8, and 9 discussed above because the requested data H is not in the cache and there is still one empty way (way_7). Accordingly, data E from the MRU (way_0) is moved to the LRU block (way_7) and the LRU block pointer is incremented back to the first non-MRU block (way_1).

Beginning with row twelve (12) the cache set is full (i.e., there is data in all of the ways. In row twelve (12) a request for data A is made. Since data A is in a non-LRU block of the cache, the data in the MRU block (way_0) is swapped with data A in way_4. It is also worth noting that even though the LRU block pointer is pointing to the block way_1, the actual LRU data is in hightlighted block way_2. However, the process cannot determine that this is the case and so it continues to treat the data in block way_1 as the LRU data.

In rows thirteen and fourteen (13, 14), a request for data I, J is made and the data does not exist in cache which is full. This is simply referred to as a “miss.” In this instance, the data C, B in the LRU block are removed from the cache since it is considered the oldest data in the cache. Then the data A, I in the MRU block (way_0) is moved to the LRU block (way_1, way_2) and the LRU block pointer is incremented to point to the next block (way_2, way_3). Finally, the requested data I, J, is loaded into the MRU block (way_0).

In row fifteen (15), the requested data D is located in the LRU block. In this case, the requested data D in the LRU block (way_3) is swapped with the data J in the MRU block (way_0). The LRU block pointer is incremented to the next block (way_4).

Row sixteen (16) illustrates an operation that is similar to the operation in row twelve because the requested data is in a non-LRU block. As described above, the data A in the requested block (way_1) is swapped with the data D in the MRU block (way_0).

The operation in row seventeen (17) is similar to the operation in rows thirteen and fourteen. In this instance, the data H in the LRU block is removed from the cache since it is considered the oldest data in the cache. Then the data A in the MRU block (way_0) is moved to the LRU block (way_4) and the LRU block pointer is incremented to point to the next block (way_5). Finally, the requested data B is loaded into the MRU block (way_0).

Rows eighteen and nineteen (18, 19) illustrate an operation that is similar to the operation in row twelve because the requested data is in a non-LRU block. As described above, the data I, A in the requested block (way_2, way_4) is swapped with the data B, I in the MRU block (way_0).

The operation in row twenty is similar to the operation in row fifteen. The requested data G in the LRU block (way_5) is swapped with the data A in the MRU block (way_0). The LRU block pointer is incremented to the next block (way_6).

FIG. 4is a table illustrating another example of the operation of a hybrid cache in accordance with some embodiments. The embodiment illustrated inFIG. 4is of a four way (way_0, way_1, way_2, way_3) cache set. As inFIG. 3, inFIG. 4, each row indicates a data request by the system. The data request is for the data in the first column (Reference). The second column (hit/miss) describes which of the five conditions the requests corresponds to. The next four columns (way_0, way_1, way_2, way_3) correspond to ways or blocks of data. As illustrated, the first of the four columns corresponds to the MRU (M) way or block and the remaining three blocks correspond to the remaining blocks in the cache set10. The shaded cell in the diagram (way_1 in the first row, way_2 in the second row, etc) corresponds to the LRU block and as can be readily seen, the location of the LRU changes when the pointer is updated. The last column (notes) describes the changes that occur to the cache set10based on the data request.

The operation illustrated inFIG. 4is similar to the operation illustrated inFIG. 3. In row one (1) ofFIG. 4, the cache is empty. Accordingly, when a request for data A is made, data A is loaded into the MRU block (way_0). In row 2, a request for data B is made. Since data B is not in the cache, data A is moved to the LRU block (way_1) and the LRU block pointer is incremented to way_2. Then data B is loaded to the MRU block (way_0). In row 3, a request for data C is made. Since data C is not in the cache, data B is moved to the LRU block (way_2) and the LRU block pointer is incremented to way_3. Then data C is loaded to the MRU block (way_0). In row 4, a request for data D is made. Since data D is not in the cache, data C is moved to the LRU block (way_3) and the LRU block pointer is incremented to way_1. Then data D is loaded to the MRU block (way_0). After the request in row 4, the cache is full of data. In row 5, a request for data C is made. Since data C is in the cache and in a non-LRU block (way_3), the data in way_3 is swapped with the data in the MRU block (way_0). In row 6, a request for data A is made. Since data A is in the cache and in the LRU block (way_1), the data in way_1 is swapped with the data in the MRU block (way_0) and the LRU block pointer is incremented to way_2.

In row 7, a request for data E is made. Since data E is not in the cache, data A is moved to the LRU block (way_2) and the LRU block pointer is incremented to way_3. Then data E is loaded to the MRU block (way_0). In row 8, a request for data F is made. Since data F is not in the cache, data E is moved to the LRU block (way_3) and the LRU block pointer is incremented to way_1. Then data F is loaded to the MRU block (way_0). In row 9, a request for data G is made. Since data G is not in the cache, data F is moved to the LRU block (way_1) and the LRU block pointer is incremented to way_2. Then data E is loaded to the MRU block (way_0).

In row 10, a request for data E is made. Since data E is in the cache and in a non-LRU block (way_3) (similar to the situation in row 5), the data in way_3 is swapped with the data in the MRU block (way_0).

In row 11, a request for data H is made. Since data H is not in the cache, data E is moved to the LRU block (way_2) and the LRU block pointer is incremented to way_3. Then data H is loaded to the MRU block (way_0). In row 12, a request for data A is made. Since data A is not in the cache, data H is moved to the LRU block (way_3) and the LRU block pointer is incremented to way_1. Then data A is loaded to the MRU block (way_0). In row 13, a request for data I is made. Since data I is not in the cache, data A is moved to the LRU block (way_1) and the LRU block pointer is incremented to way_2. Then data I is loaded to the MRU block (way_0). In row 14, a request for data J is made. Since data J is not in the cache, data I is moved to the LRU block (way_2) and the LRU block pointer is incremented to way_3. Then data J is loaded to the MRU block (way_0).

In row 15, a request for data H is made. Since data H is in the cache and in the LRU block (way_3), the data in way_3 is swapped with the data in the MRU block (way_0) and the LRU block pointer is incremented to way_1. In row 16, a request for data I is made. Since data I is in the cache and in a non-LRU block (way_2) (similar to the situation in row 5), the data in way_2 is swapped with the data in the MRU block (way_0).

In row 17, a request for data B is made. Since data B is not in the cache, data I is moved to the LRU block (way_1) and the LRU block pointer is incremented to way_2. Then data B is loaded to the MRU block (way_0). In row 18, a request for data I is made. Since data I is in the cache and in a non-LRU block (way_1), the data in way_1 is swapped with the data in the MRU block (way_0). In row 19, a request for data B is made. Since data B is in the cache and in a non-LRU block (way_1), the data in way_1 is swapped with the data in the MRU block (way_0). In row 20, a request for data H is made. Since data H is in the cache and in the LRU block (way_2), the data in way_2 is swapped with the data in the MRU block (way_0) and the LRU block pointer is incremented to way_3.

As discussed above and illustrated inFIG. 4, these various situations cause the cache to operate in a particular fashion as described in the “notes” column ofFIG. 4and more generally with respect toFIG. 2.

Some embodiments described herein may include a method for controlling a cache comprising receiving a request for data and determining whether the requested data is present in a first portion of the cache, a second portion of the cache, or not in the cache. If the requested data is not located in the first portion of the cache, the requested data is moved into the first portion of the cache.

Some embodiments described herein may include a hardware implemented finite state machine comprising: a digital logic circuit, which, when operating, causes the hardware implemented finite state machine to perform logical operations. The operations include receiving a request for data; determining whether the requested data is present in a most recently used (MRU) portion of a cache. If the requested data is not located in the MRU portion of the cache, data is swapped between the MRU portion of the cache and a portion of the cache where the requested data is located.

Some embodiments described herein may include a semiconductor memory device comprising a processor and a first portion of cache comprising at least one block of data storage and implemented using static random access memory (SRAM). The semiconductor memory device further comprises a second portion of cache comprising a plurality of blocks of data storage and implemented using magnetic random access memory (MRAM). A most recently used (MRU) portion of the cache located is within the first portion of cache, and the semiconductor memory device includes hardware implemented logic configured to receive a request for data from the processor and move data to the MRU portion of the cache if the requested data is not located in the MRU portion of the cache.