BACKGROUND

Description of the Related Art

To improve memory access efficiency, many processors employ a memory hierarchy, whereby a processor includes one or more caches to store a subset of data stored in main memory. The criterion for which subset of data from the main memory is stored in the cache can vary depending on the processor design, but typically prioritizes the caching of data that has recently been accessed. In addition, some processors employ one or more prefetchers that predict data that is likely to be accessed by the processor in the near future, and copies that data from main memory to the one or more caches. In order to move new data into the one or more caches, the processor selects previously stored data for eviction based on a specified replacement scheme, but conventional replacement schemes can result in undesirably low memory access efficiency.

BRIEF DESCRIPTION OF THE DRAWINGS

The present disclosure may be better understood, and its numerous features and advantages made apparent to those skilled in the art by referencing the accompanying drawings. The use of the same reference symbols in different drawings indicates similar or identical items.

FIG. 1 is a block diagram of a processing system that applies a transfer policy to a portion of a cache based on access metrics for different test regions of the cache in accordance with some embodiments.

FIG. 2 is an example of the processing system of FIG. 1 employing different transfer policies in different test regions of the cache in accordance with some embodiments.

FIG. 3 is an example of the processing system of FIG. 1 employing different transfer policies in different test regions of the cache in accordance with some embodiments. FIG. 4 is a diagram illustrating an example of the processing system of FIG. 1 changing the transfer policy at the non-test region of the cache based on access metrics for test regions of the cache in accordance with some embodiments.

FIG. 5 is a flow diagram of a method of applying a transfer policy to a portion of a cache based on access metrics for different test regions of the cache in accordance with some embodiments.

DETAILED DESCRIPTION

FIGs. 1 -5 illustrate techniques for applying a transfer policy to a portion of a cache based on access metrics for different test regions of the cache, wherein each test region applies a different transfer policy for data in cache entries that were stored in response to a prefetch requests but were not the subject of demand requests (referred to as "unused prefetches" or "unused prefetched data"). One test region applies a transfer policy under which unused prefetches are transferred to a higher level cache in a cache hierarchy upon eviction from the test region of the cache. The other test region applies a transfer policy under which unused prefetches are replaced without being transferred to a higher level cache (or are transferred to the higher level cache but stored as invalid data) upon eviction from the test region of the cache. By selecting a cache transfer policy for the non-test portion of the cache based on access metrics for the different test regions, the cache dynamically changes the transfer policy to the more efficient policy for the pattern of instructions currently executing at a processor.

To illustrate via an example, in some embodiments the cache has two test regions and a non-test region, whereby all the regions are employed by the cache to store data in response to demand requests from a processor and in response to prefetch requests from a prefetcher. The cache employs different transfer policies for the different test regions, such that for one of the test regions the cache transfers to a higher level cache evicted cache entries that store unused prefetches. For the other test region, the cache replaces evicted cache entries that store unused prefetches without transferring the data to a higher level cache, or transfers the data to the higher level cache but stores the data as invalid data. The processor monitors access metrics for each of the test regions, such as a cache hit rate, cache miss rate, or a combination thereof. Based on the access metrics, the processor selects the transfer policy for one of the test regions and applies it to the non-test region of the cache. For example, if the cache hit rate is higher for one of the test regions, the processor applies the transfer policy for that test region to the non-test region of the cache, thereby improving the hit rate for the cache overall.

As used herein, the term "transfer policy" refers to how data stored in a cache entry is handled upon eviction from the cache. The transfer policy may require that all unused prefetches are to be transferred to and stored as valid data at a higher level cache upon eviction from the cache. Another transfer policy mandates that all unused prefetches are to be discarded upon eviction from the cache. In some embodiments, the prefetch data is discarded by replacing the data at the cache without transferring the data to the higher level cache. In some other embodiments, the prefetch data is discarded by providing the data to the higher level cache but storing the data at the higher level cache with an indicator that the data is invalid, so that the data can be replaced by valid incoming data during cache entry replacement at the higher level cache.

FIG. 1 illustrates a processing system 100 that applies a cache transfer policy for unused prefetches to a portion of a cache based on access metrics for different test regions of the cache in accordance with some embodiments. The processing system 100 is generally configured to execute sets of instructions organized in the form of computer programs in order to carry out tasks on behalf of an electronic device. Accordingly, the processing system 100 may be used in any of a variety of electronic devices, such as a desktop or laptop computer, server, smartphone, tablet, game console, and the like. To facilitate execution of instructions, the processing system 100 includes a processor 101 and memory 130. The processor 101 includes a processor core 102, a cache controller 105, an L2 cache 1 10, and an L3 cache 120. In some

embodiments, each of the modules of the processor 101 are formed on the same semiconductor die to form at least a portion of a processor core 102, and the memory 130 is formed on a different semiconductor die and connected to the processor 101 via one or more busses or signal lines. In some embodiments, at least a portion of the memory 130 is formed on the same semiconductor die as modules of the processor 101 .

The L2 cache 1 10, L3 cache 120 and the memory 130 are each memory devices generally configured to store data, and therefore may be random access memory (RAM) memory modules, non-volatile memory devices (e.g., flash memory), and the like. As described further herein, the L2 cache 1 10, L3 cache 120 and the memory 130 form a memory hierarchy for the processing system 100. In addition, the memory hierarchy of the processing system 100 may include other memory modules, such as additional caches not illustrated at FIG. 1 . The processor core 102 includes an instruction pipeline having, for example, a fetch stage to fetch instructions, a decode stage to decode each fetched instruction into one or more operations, execution stages to execute the operations, and a retire stage to retire instructions whose operations have completed execution. One set of operations generated based on the instructions are referred to herein as memory access instructions, and are requests to load data (load operations) from the memory hierarchy of the processing system 100, and requests to store data at the memory hierarchy of the processing system 100. Memory access requests generated by the processor core 102 represent requests to load or store data that are being used or are known to be needed by an executing program, and are referred to herein as demand requests.

The cache controller 105 is a module generally configured to manage the memory hierarchy of the processing system 100 by moving data between the L2 cache 1 10, the L3 cache 120, and the memory 130. In particular, the L2 cache 1 10 and L3 cache 120 are memory devices, each of which includes a plurality of entries, whereby each entry is associated with one or more addresses of the memory 130. In response to a memory access request, the cache controller 105 reviews the data stored at one or more entries of the L2 cache 1 10 to determine if any of the entries stores data associated with the memory address targeted by the memory access request. If so, the cache controller 105 indicates a cache hit and satisfies the memory access request at the identified entry, either by storing data at the entry (in the case of a store operation) or by providing the data at the identified entry to the processor core 102 (in the case of a load operation). If data associated with the memory address is not stored at an entry of the L2 cache 1 10, the cache controller 105 indicates a cache miss and issues a request to the L3 cache 120. In response to the memory access request, the cache controller 105 (or, in some embodiments, a separate cache controller) reviews the data stored at one or more entries of the L3 cache 120 to determine if any of the entries stores data associated with the memory address targeted by the memory access request. If so, the cache controller 105 indicates a cache hit and satisfies the memory access request at the identified entry, either by storing data at the entry (in the case of a store operation) or by providing the data at the identified entry to the L2 cache 1 10, from which it is subsequently provided to the processor core 102 (in the case of a load operation). If data associated with the memory address is not stored in an entry of the L3 cache 120, the cache controller 105 indicates a cache miss and issues a request to the memory 130 for the data at the memory address. Upon receipt of the data from the memory 130, the cache controller 105 stores the data at an entry of the L3 cache 120, from which it is subsequently transferred to the L2 cache 1 10, which in turn provides the data to the processor core 102, thus satisfying the memory access request.

To support improved memory access efficiency, the processor 101 includes a prefetcher 106 that monitors demand requests issued to the cache controller 105 to identify patterns and predict, based on the identified patterns, memory addresses that will be the target of demand requests by the processor core 102 in the near future. The prefetcher 106 issues to the cache controller 105 memory access requests, referred to herein as prefetch requests, targeting the identified memory addresses. The cache controller 105 treats a prefetch request similar to a demand request by first identifying if data associated with the memory address targeted by the prefetch request is already stored at an entry of the L2 cache 1 10 and, if not already stored, requesting the data from the L3 cache 120 or the memory 130 and storing the data at an entry of the L2 cache 1 10.

In some embodiments, each entry of the L2 cache 1 10 and L3 cache 120 is associated with a subset of memory addresses and only data associated with that subset is permitted to be stored at the entry. For example, in some embodiments the cache is an N-way set associative cache having M sets and each of the M sets including N entries. Each of the M sets is assigned a different subset of memory addresses, such that the cache controller 105 only stores data at an entry if the data is associated with a memory address in the entry's assigned subset. When all entries of a set store data (referred to herein as "valid data") that may be the target of a memory access, the set is referred to herein as full. Further, when the cache controller 105 receives data that is to be stored at a full set, it selects one of the entries of the set to evict (that is, to remove from the set) and replace with the received data. When an entry is evicted from the L2 cache 1 10, it may be transferred to the L3 cache 120, or it may be replaced without first being transferred to the L3 cache 120. The scheme that the cache controller 105 uses to select the entry for transfer or for replacement without transfer is referred to as the transfer policy for the L2 cache 1 10.

To facilitate more efficient transfer of evicted cache entries, the transfer policy for the L2 cache 1 10 may be based at least in part on whether the data stored at the cache entries was stored in response to a prefetch request but was not the subject of a demand request. Under one transfer policy, unused prefetches in the L2 cache 1 10 will be transferred to the L3 cache 120 with a valid status upon eviction from the L2 cache 1 10. Under a different transfer policy, unused prefetches in the L2 cache 1 10 are transferred to the L3 cache 120 with a status indicating that the data is invalid, and therefore is eligible to be discarded. Under yet another transfer policy, unused prefetches in the L2 cache 1 10 will be replaced without being transferred to the L3 cache 120 upon eviction from the L2 cache 1 10. Typically, data that was transferred to the L2 cache 1 10 in response to a prefetch request was previously transferred or copied from the L3 cache 120. In some embodiments, the L3 cache 120 is not inclusive of the L2 cache 1 10 such at least some of the cache entries stored in the L2 cache 1 10 are not also stored at the L3 cache 120. Transferring unused prefetched data to the L3 cache 120 upon its eviction from the L2 cache 1 10 where the L3 cache 120 is not inclusive of the L2 cache 1 10 may require the eviction of other valid data from the L3 cache 120, for example, if the set in the L3 cache 120 into which the unused prefetched data is assigned is full, and resulting in less efficient processing of memory requests. By optionally employing a transfer policy that transfers unused prefetched data to the L3 cache 120 with an invalid status or, alternatively, that replaces unused prefetched data upon its eviction from the L2 cache 1 10 without transferring the unused prefetched data to the L3 cache 120, more efficient processing of memory requests may be achieved. By contrast, in a conventional cache management system, unused prefetched data is transferred to the L3 cache 120 upon its eviction from the L2 cache 1 10 with a valid status, thereby potentially evicting more useful data (e.g., data that is more likely to be accessed than the unused prefetch data), reducing memory access efficiency.

In some embodiments, the cache controller 105 applies different transfer policies to different regions of the cache 1 10, wherein each region includes a plurality of entries. In at least one embodiment, each region only varies as to its transfer policy. Thus, the entries of a region may be used for any set, and different regions may include different entries of the same set.

In the depicted example of FIG. 1 , the cache 1 10 includes three regions: test regions 1 15 and 1 16 and non-test region 1 18. In addition, the cache controller 105 stores transfer policies 1 1 1 and 1 12 that differ in at least one aspect, such as whether unused prefetched data is transferred to the L3 cache 120 upon eviction from the L2 cache 1 10 with a valid status or an invalid status or, alternatively, is replaced without being transferred to the L3 cache 120. Thus, in the example of FIG. 1 , the transfer policy 1 1 1 mandates that upon eviction from the L2 cache 1 10, all or a portion of the unused prefetched data is transferred to the L3 cache 120 with a valid status, as is any non-prefetch request data. As used herein, a non-prefetch request refers to a memory access that is not a prefetch request targeted to the cache level to which the transfer policy is applied. Examples of non-prefetch requests include demand requests, memory access requests generated in response to instruction cache misses, hardware page table walk requests, speculative memory access requests generated by the processor core 102 (e.g., memory access requests generated during speculative execution of instructions after a branch instruction), and prefetch requests generated at other cache levels.

In contrast, the transfer policy 1 12 mandates that upon eviction from the L2 cache 1 10 all or a portion of the unused prefetched data is transferred to the L3 cache 120 with an invalid status or, alternatively, is replaced without being transferred to the L3 cache 120, whereas non-prefetch request data is transferred to the L3 cache 120 upon eviction from the L2 cache 1 10. The transfer policy 1 1 1 may therefore be more efficient for memory access patterns that more frequently access prefetched data, and the transfer policy 1 12 may be more efficient for memory access patterns that access prefetched data with less frequency. However, the memory access pattern for the processor core 102 may vary over time, such that the cache 1 10 operates more efficiently under different transfer policies at different times.

Accordingly, for the non-test region 1 18, the cache controller 105 selects between the transfer policies 1 1 1 and 1 12 depending on performance characteristics of the test regions 1 15 and 1 16.

To illustrate, the processor 101 includes a performance monitor 104 that monitors and records performance characteristics, such as cache hit rate, cache miss rate, and the like, for each of the test regions 1 15 and 1 16. Based on one or more of the performance characteristics, or a combination thereof, of the test regions 1 15 and 1 16, the cache controller selects one of the transfer policies 1 1 1 and 1 12 and applies it to the non-test region 1 18. For example, if the cache hit rate for the test region 1 15 is higher than the cache hit rate for the test region 1 16, the cache controller 105 selects the transfer policy for the test region 1 15 (e.g., transfer policy 1 1 1 ) and applies it to the non-test region 1 18. In some embodiments, the non-test region 1 18 includes the majority of the entries of the cache 1 10. Thus, by selecting the transfer policy for the non-test region 1 18 as the more efficient transfer policy, as indicated by the performance of the test regions 1 15 and 1 16, the cache controller 105 enhances the overall efficiency of the cache 1 10. Further, as the performance characteristics of the test regions 1 15 and 1 16 change over time, the cache controller changes the transfer policy to the policy that is more efficient for a given set of performance characteristics. FIG. 2 illustrates an example of the cache controller 105 applying different transfer policies to the test regions 1 15 and 1 16 of the L2 cache 1 10 of FIG. 1 in accordance with some embodiments. In the depicted example, each of the test regions 1 15 and 1 16 includes a plurality of entries, such as entries 240, 241 , 242, and 243 of test region 1 15 and entries 246, 247, 248, and 249 of test region 1 16. Each of the entries includes a data portion (e.g., data portion 244 of entry 240) to store data retrieved from the memory 130— that is, the data used to satisfy memory access requests at the entry. Each entry also includes a transfer field (e.g., transfer field 245 of entry 240) to store an indication of whether the transfer policy being applied to test region 1 15 mandates that the data be transferred to the L3 cache 120 or replaced without being transferred to the L3 cache 120 (or, alternatively, transferred with a status indicating that the data is to be discarded) upon eviction from the test region 1 15 of the L2 cache 1 10.

For the example of FIG. 2, it is assumed the cache controller 105 applies a transfer policy to the test region 1 15 wherein unused prefetch requests are replaced without first being transferred to the L3 cache 120 upon eviction from the test region 1 15 of the L2 cache 1 10, whereas demand requests are transferred to the L3 cache 120 upon eviction from the test region 1 15 of the L2 cache 1 10. In the example of FIG. 2, test region 1 15 of the L2 cache 1 10 is populated with data associated with prefetch requests 250 and 252, respectively, and data associated with demand requests 251 and 253, respectively.

As described above, the cache controller 105 applies different transfer policies to the different test regions 1 15 and 1 16. By measuring the performance

characteristics for each test region, the cache controller 105 identifies the more efficient transfer policy for a recent memory access pattern of the processor core 102, and applies the more efficient transfer policy to the non-test region 1 18, thereby improving overall cache efficiency. In some embodiments, instead of mandating replacement without transfer to the

L3 cache 120 (or, alternatively, transfer to the L3 cache 120 with a status indicating that the data is to be discarded) for all unused data associated with prefetch requests, the transfer policy mandates replacement without transfer to the L3 cache 120 for a portion of the unused data associated with prefetch requests. For example, for the test region 1 15, the cache controller 105 applies a transfer policy pursuant to which only a percentage of entries associated with prefetch requests will be replaced without first being transferred to the L3 cache 120.

In contrast to the transfer policy applied to the test region 1 15, the transfer policy applied to the test region 1 16 mandates transfer with a valid status to the L3 cache 120 for each entry upon eviction from the L2 cache 1 10, without regard to whether the entry is associated with a demand request or a prefetch request. In the example of FIG. 2, test region 1 16 is populated with data associated with prefetch requests 256 and 258, respectively, and data associated with demand requests 257 and 259, respectively. In response to eviction of an entry of the test region 1 16, the cache controller 105 applies a transfer policy to require that the entry be transferred to the L3 cache 120, whether the data is associated with a demand request or a prefetch request. Thus, the different transfer policies applied to the different test regions 1 15 and 1 16 vary in one or more of several aspects, including whether all, some, or none of the entries associated with prefetch requests be replaced without first transferring to the L3 cache 120 upon eviction from the L2 cache 1 10. Further, in some embodiments the cache 1 10 includes more than two test regions, with different transfer policies applied to each test region, thereby giving the cache controller a wide range of possible transfer policies to apply to the non-test region 1 18.

FIG. 3 illustrates an example of a cache controller 305 applying different transfer policies to different test regions of an L2 cache 310. In the example of FIG. 3, the cache controller 305 applies transfer policy 31 1 to test region 315 of the L2 cache 310, and applies transfer policy 312 to test region 316 of the L2 cache 310. Transfer policy 31 1 mandates that upon eviction from the L2 cache 310, all entries are to be transferred to the L3 cache 320, without regard to whether the entries are associated with prefetch requests or demand requests. In the example of FIG. 3, incoming data 341 is received into a set containing prefetch data 345 in test region 315 of the L2 cache 310, necessitating the eviction of prefetch data 345. Cache controller 305 applies transfer policy 31 1 to test region 315, and therefore transfers prefetch data 345 to the L3 cache 320 before replacing it with incoming data 341 .

By contrast, incoming data 342 is received into a set containing prefetch data 346 in test region 316 of the L2 cache 310, necessitating the eviction of prefetch data 346. Cache controller 305 applies transfer policy 312 to test region 316, and therefore discards the prefetch data 346 without being transferring it to the L3 cache 320.

FIG. 4 illustrates a diagram 400 depicting an example of the relative

performance of the different test regions 1 15 and 1 16 changing over time in accordance with some embodiments. The diagram 400 includes an X-axis 450 representing time and a Y-axis 451 representing cache hit rate. The diagram 400 depicts a curve 452 representing the cache hit rate for the test region 1 16 over time and a curve 453 representing the cache hit rate for the test region 1 15.

In the example illustrated by the diagram 400, prior to a time 455 the cache hit rate for the test region 1 15 is greater than the cache hit rate for the test region 1 16. Accordingly, prior to time 455 the cache controller 105 applies the transfer policy for the test region 1 15 to the non-test region 1 18. At time 455, the relationship between the cache hit rates for the test regions 1 15 and 1 16 changes, such that the cache hit rate for the test region 1 16 is greater than the cache hit rate for the test region 1 15. In response, the cache controller 105 changes the transfer policy for the non-test region 1 18 to match the transfer policy for the test region 1 16. At a later time 456, the relationship between the cache hit rates for the test regions 1 15 and 1 16 again changes, such that the cache hit rate for the test region 1 15 is again greater than the cache hit rate for the test region 1 16. In response, the cache controller 105 changes the transfer policy for the non-test region 1 18 to match the transfer policy for the test region 1 15. Thus, the cache controller 105 changes the transfer policy applied to the non-test region 1 18 based on changes in the relative performance of the test regions 1 15 and 1 16.

FIG. 5 is a flow diagram of a method 500 of selecting a transfer policy for a non- test region of a cache based on performance characteristics of different test regions of the cache in accordance with some embodiments. For purposes of description, the method 500 is described with respect to an example implementation at the processing system 100 of FIG. 1 . At block 502, the cache controller 105 applies the different transfer policies 1 1 1 and 1 12 to the different test regions 1 15 and 1 16 of the cache 1 10. Thus, for example, the cache controller 105 applies the transfer policy 1 1 1 to the test region 1 15 and the transfer policy 1 12 to the test region 1 16. At block 504, the performance monitor 104 monitors and records performance characteristics for the different test regions 1 15 and 1 16, such as cache hit rate, cache miss rate, a weighted sum of cache hit rate and cache miss rate, and the like.

At block 506, the cache controller 105 compares the performance

characteristics for each of the test regions 1 15 and 1 16 and based on the comparison selects one of the transfer polices 1 1 1 and 1 12. For example, the cache controller 105 selects the transfer policy that is applied to the test region that has a higher performance as indicated by the performance characteristics. At block 508, the cache controller 105 applies the selected transfer policy to the non-test region 1 18 of the cache 1 10. That is, the cache controller designates cache entries either for transfer or replacement without prior transfer upon eviction at the non-test region 1 18 in keeping with the requirements of the selected transfer policy. At block 510, the cache controller 105 uses the transfer or replacement designations to either transfer or discard the prefetch data stored at the non-test region 1 18 of the L2 cache 1 10 in accordance with a replacement policy non-test region 1 18 of the L2 cache 1 10. The method flow returns to block 504, reflecting that the cache controller 105 continues to monitor the performance of the test regions 1 15 and 1 16 and based on the performance adjusts the transfer policy applied to the non-test region 1 18.

In some embodiments, certain aspects of the techniques described above may implemented by one or more processors of a processing system executing software. The software comprises one or more sets of executable instructions stored or otherwise tangibly embodied on a non-transitory computer readable storage medium. The software includes the instructions and certain data that, when executed by the one or more processors, manipulate the one or more processors to perform one or more aspects of the techniques described above. The non-transitory computer readable storage medium may include, for example, a magnetic or optical disk storage device, solid state storage devices such as Flash memory, a cache, random access memory (RAM) or other non-volatile memory device or devices, and the like. The executable instructions stored on the non-transitory computer readable storage medium may be in source code, assembly language code, object code, or other instruction format that is interpreted or otherwise executable by one or more processors.

A computer readable storage medium may include any storage medium, or combination of storage media, accessible by a computer system during use to provide instructions and/or data to the computer system. Such storage media includes, but is not limited to, optical media (e.g., compact disc (CD), digital versatile disc (DVD), Blu-Ray disc), magnetic media (e.g., floppy disc, magnetic tape, or magnetic hard drive), volatile memory (e.g., random access memory (RAM) or cache), non-volatile memory (e.g., read-only memory (ROM) or Flash memory), or microelectromechanical systems (MEMS)-based storage media. The computer readable storage medium may be embedded in the computing system (e.g., system RAM or ROM), fixedly attached to the computing system (e.g., a magnetic hard drive), removably attached to the computing system (e.g., an optical disc or Universal Serial Bus (USB)-based Flash memory), or coupled to the computer system via a wired or wireless network (e.g., network accessible storage (NAS)).

Note that not all of the activities or elements described above in the general description are required, that a portion of a specific activity or device may not be required, and that one or more further activities may be performed, or elements included, in addition to those described. Still further, the order in which activities are listed are not necessarily the order in which they are performed. Also, the concepts have been described with reference to specific embodiments. However, one of ordinary skill in the art appreciates that various modifications and changes can be made without departing from the scope of the present disclosure as set forth in the claims below. Accordingly, the specification and figures are to be regarded in an illustrative rather than a restrictive sense, and all such modifications are intended to be included within the scope of the present disclosure.

Benefits, other advantages, and solutions to problems have been described above with regard to specific embodiments. However, the benefits, advantages, solutions to problems, and any feature(s) that may cause any benefit, advantage, or solution to occur or become more pronounced are not to be construed as a critical, required, or essential feature of any or all the claims. Moreover, the particular embodiments disclosed above are illustrative only, as the disclosed subject matter may be modified and practiced in different but equivalent manners apparent to those skilled in the art having the benefit of the teachings herein. No limitations are intended to the details of construction or design herein shown, other than as described in the claims below. It is therefore evident that the particular embodiments disclosed above may be altered or modified and all such variations are considered within the scope of the disclosed subject matter. Accordingly, the protection sought herein is as set forth in the claims below.