Patent ID: 12204454

DETAILED DESCRIPTION OF IMPLEMENTATIONS

In the following description, numerous specific details are set forth to provide a thorough understanding of the methods and mechanisms presented herein. However, one having ordinary skill in the art should recognize that the various implementations may be practiced without these specific details. In some instances, well-known structures, components, signals, computer program instructions, and techniques have not been shown in detail to avoid obscuring the approaches described herein. It will be appreciated that for simplicity and clarity of illustration, elements shown in the figures have not necessarily been drawn to scale. For example, the dimensions of some of the elements may be exaggerated relative to other elements.

Various systems, apparatuses, methods, and computer-readable mediums for employing system probe filter aware last level cache insertion bypassing policies are disclosed herein. In one implementation, a system includes a plurality of nodes, a probe filter, and a last level cache (LLC). The probe filter monitors a rate of recall probes that are generated, and if the rate is greater than a first threshold, then the system initiates a cache partitioning and monitoring phase for the shared cache. Accordingly, the cache is partitioned into two portions. If the hit rate of a first portion is greater than a second threshold, then a second portion will have a non-bypass insertion policy since the cache is useful in this scenario. However, if the hit rate of the first portion is less than or equal to the second threshold, then the second portion will have a bypass insertion policy since the LLC is not useful in this case. This helps to reduce the number of recall probes that are generated when the LLC has a low hit rate.

Referring now toFIG.1, a block diagram of one implementation of a computing system100is shown. In one implementation, computing system100includes at least processing nodes105A-N, input/output (I/O) interfaces120, bus125, memory controller(s)130, and network interface135. In other implementations, computing system100can include other components and/or computing system100can be arranged differently. In one implementation, each processing node105A-N includes one or more general purpose processors, such as central processing units (CPUs). It is noted that a “processing node” can also be referred to as a “core complex” or a “CPU” herein. In some implementations, one or more processing nodes105A-N can include a data parallel processor with a highly parallel architecture. Examples of data parallel processors include graphics processing units (GPUs), digital signal processors (DSPs), and so forth. Each processor core within processing node105A-N includes a cache subsystem with one or more levels of caches. In one implementation, each processing node105A-N includes a cache (e.g., level three (L3) cache) which is shared between multiple processor cores.

Memory controller(s)130are representative of any number and type of memory controllers accessible by processing nodes105A-N. Memory controller(s)130are coupled to any number and type of memory devices (not shown). For example, the type of memory in memory device(s) coupled to memory controller(s)130can include Dynamic Random Access Memory (DRAM), Static Random Access Memory (SRAM), NAND Flash memory, NOR flash memory, Ferroelectric Random Access Memory (FeRAM), or others. I/O interfaces120are representative of any number and type of I/O interfaces (e.g., peripheral component interconnect (PCI) bus, PCI-Extended (PCI-X), PCIE (PCI Express) bus, gigabit Ethernet (GBE) bus, universal serial bus (USB)). Various types of peripheral devices can be coupled to I/O interfaces120. Such peripheral devices include (but are not limited to) displays, keyboards, mice, printers, scanners, joysticks or other types of game controllers, media recording devices, external storage devices, network interface cards, and so forth.

In various implementations, computing system100can be a server, computer, laptop, mobile device, game console, streaming device, wearable device, or any of various other types of computing systems or devices. It is noted that the number of components of computing system100can vary from implementation to implementation. There can be more or fewer of each component than the number shown inFIG.1. It is also noted that computing system100can include other components not shown inFIG.1. Additionally, in other implementations, computing system100can be structured in other ways than shown inFIG.1.

Turning now toFIG.2, a block diagram of one implementation of a processing node200is shown. In one implementation, processing node200includes four processor cores210A-D. In other implementations, processing node200can include other numbers of processor cores. It is noted that a “processing node” can also be referred to as a “core complex” or “CPU” herein. In one implementation, the components of processing node200are included within processing nodes105A-N (ofFIG.1).

Each processor core210A-D includes a cache subsystem for storing data and instructions retrieved from the memory subsystem (not shown). For example, in one implementation, each core210A-D includes a corresponding level one (L1) cache215A-D. Each processor core210A-D can include or be coupled to a corresponding level two (L2) cache220A-D. Additionally, in one implementation, processing node200includes a level three (L3) cache230which is shared by the processor cores210A-D. L3 cache230is coupled to a memory subsystem (not shown) via a fabric (not shown). It is noted that in other implementations, processing node200can include other types of cache subsystems with other numbers of cache and/or with other configurations of the different cache levels.

Referring now toFIG.3, a block diagram of one implementation of a portion of a multi-node system300is shown. In one implementation, system includes multiple processing nodes (not shown). The number of processing nodes per system can vary from implementation to implementation. In one implementation, each processing node is connected to a corresponding coherent master (e.g., coherent master310). As used herein, a “coherent master” is defined as an agent that processes traffic flowing over an interconnect (e.g., bus/fabric320) and manages coherency for a connected node. To manage coherency, a coherent master receives and processes coherency-related messages and probes and generates coherency-related requests and probes.

In one implementation, each processing node is coupled to a coherent slave (e.g., coherent slave330) via a corresponding coherent master and bus/fabric320. Coherent slave330is coupled to a memory controller (not shown) and coherent slave330is also coupled to probe filter335, with probe filter335including entries for cache lines cached in system300for the memory accessible through the corresponding memory controller. As used herein, a “coherent slave” is defined as an agent that manages coherency by processing received requests and probes that target a corresponding memory controller. Additionally, as used herein, a “probe” is defined as a message passed from a coherency point to one or more caches in the computer system to determine if the caches have a copy of a block of data and optionally to indicate the state into which the cache should place the block of data. When coherent slave330receives a memory request targeting its corresponding memory controller, coherent slave330performs a lookup to probe filter335. If the lookup to probe filter335is a hit, a probe is sent to the owner of the cache line targeted by the memory request. Otherwise, if the lookup to probe filter335is a miss, then the memory request is sent to memory without a probe being generated. Depending on the insertion policy of the probe filter335, a new entry might be added to probe filter335when the lookup is a miss.

Turning now toFIG.4, a block diagram of one implementation of a portion of a system on chip (SoC)400is shown. In one implementation, SoC400includes at least cache410, fabric425, memory controller430, and probe filter435. Cache410includes cache memory415and control unit420, with cache410representative of any type of cache. For example, in one implementation, cache410is a level three (L3) cache, and cache410is coupled to a level two (L2) cache (not shown). In other implementations, cache410is other levels of cache in a cache hierarchy. It is noted that cache410can also be referred to herein as a last level cache (LLC).

Cache memory415includes any amount of memory capacity, with the amount of capacity varying according to the implementation. In one implementation, in response to detecting a high stress level for probe filter435, cache memory415is partitioned into portion415A and portion415B, with portion415A smaller than portion415B. In one implementation, a “high stress level” is defined as probe filter435having a recall probe rate which is greater than a threshold. The recall probe rate refers to the number of recall probes that are generated over a given interval, with a recall probe being a message sent from probe filter435to cache410that causes cache410to evict a particular cache line. In other implementations, the “stress level” of probe filter435is determined by the recall probe rate and/or one or more other metrics. It should be understood that while the portions410A-B appear to be contiguous portions of cache410, this is shown merely for ease of illustration. In another implementation, portion410A is a randomly selected number of indices into cache410, with the indices spread throughout cache410in non-contiguous locations. In a further implementation, several partitions can be independently established for various classifications of cache traffic. For example, these classifications can be based on instruction lines, data lines, translation lookaside buffer (TLB) hardware table walker lines, software and hardware prefetchers of various types, traffic from various hardware threads or groups of threads, and so on. Control unit420then considers the hit-rate for a particular classification of cache line when making the decision on whether to apply a bypass or non-bypass insertion policy. Other ways of partitioning cache410into portions410A-B are possible and are contemplated.

In one implementation, control unit420applies a non-bypass insertion policy for portion415A while monitoring the hit rate for portion415A. A non-bypass insertion policy means that at least a portion of the requests that miss in portion415A will be allocated in portion415A. Control unit420monitors the hit rate of portion415A over a given interval of time, and if the hit rate is greater than a threshold, then control unit420applies the non-bypass insertion policy to portion415B. If the hit rate for portion415A is higher than the threshold, this indicates that cache410is useful, and cache lines should be inserted into the remaining portion415B in this case. However, if the hit rate for portion415A is less than or equal to the threshold, then this indicates that cache410is not particularly useful for the given application being executed by SoC400. In this case, control unit420applies a bypass insertion policy for portion415B to cause requests to go to memory instead of being allocated in portion415B. The bypass insertion policy means that any request that misses on a lookup to portion415B will not be allocated in portion415B. The bypass insertion policy helps to reduce cache thrashing as well as reducing the number of recall probes that are generated by probe filter435. As used herein, the term “recall probe” is defined as a message sent from a probe filter to a cache that causes the cache to evict a particular cache line from the cache. It is noted that the bypass insertion policy can be overridden by other mechanisms, such as detecting that a cache line may have further reuse via measuring the hit counts at higher levels of the cache or based on other determinations.

Fabric425is representative of any type of interconnect that connects the various components and/or agents of SoC400together. While fabric425is shown as a single unit, it should be understood that this is merely one way of representing fabric425. In some implementations, fabric425includes multiple components that are spread throughout SoC400, with these multiple components coupled together to allow requests, probes, probe recalls, and other messages to be sent between the various agents. Memory controller430is coupled to probe filter435and a memory (not shown). Requests received by memory controller430that target the corresponding memory will check probe filter435to see if the data is cached by cache410.

In some cases, when a lookup to probe filter435results in a miss, probe filter435evicts an existing entry to make room for a new entry. To evict an existing entry, probe filter435generates a recall probe which is sent to cache410. In a configuration where a given probe filter entry tracks a plurality of cache lines, a recall probe may be a plurality of probes. In response to receiving the recall probe, cache410evicts the corresponding cache line(s) since probe filter435is no longer able to track these particular cache line(s). When probe filter435is sending out frequent recall probes, this can have a negative effect on system performance.

Accordingly, to help prevent this scenario, in one implementation, probe filter435includes counter440to track how many recall probes are generated during a particular interval of time. If the number of recall probes generated during the interval is greater than a threshold, then probe filter435sends a message to control unit420of cache410to partition cache memory415into portion415A-B and to start monitoring the hit rate for portion415A. Otherwise, if the number of recall probes is less than or equal to the given threshold, then cache410can continue with its normal operations. Alternatively, in another implementation, control unit420monitors the number of recall probes that are received and compares the number to a threshold at a given interval.

Referring now toFIG.5, one implementation of a method500for employing a system probe aware last level cache insertion bypassing policy is shown. For purposes of discussion, the steps in this implementation and those ofFIG.6are shown in sequential order. However, it is noted that in various implementations of the described methods, one or more of the elements described are performed concurrently, in a different order than shown, or are omitted entirely. Other additional elements are also performed as desired. Any of the various systems or apparatuses described herein are configured to implement method500.

A probe filter monitors the number of recall probes that are generated over a given interval (block505). Alternatively, in another implementation, a cache controller monitors the number of recall probes that are received over the given interval. Additional metrics other than just the number of probes can be monitored in block505, such as counts of how many probes hit in various levels of caches (e.g., L1, L2, L3), what MOESI state the probes hit, and so on. If the number of recall probes that were generated is greater than a first threshold (conditional block510, “yes” leg), then the probe filter instructs a cache (e.g., last level cache (LLC)) to initiate a monitoring phase (block515). Otherwise, if the number of recall probes over the given interval is less than or equal to the first threshold (conditional block510, “no” leg), then method500returns to block505.

As part of initiating the monitoring phase, the cache is partitioned into a first portion and a second portion (block520). In one implementation, the first portion includes some number of cache indices, with the second portion including the remainder of the cache. In one implementation, the cache indices of the first portion are randomly chosen. In other implementations, other suitable ways of partitioning the cache into the first and second portions can be used.

Next, after block520, the cache monitors the hit rate to the first portion while applying a non-bypass insertion policy to the first portion (block525). In one implementation, the non-bypass insertion policy results in cache lines being allocated for requests that miss in the second portion. In one implementation, the hit rate is calculated in terms of a number of cache hits divided by a total number of requests received by the cache. For example, if the cache receives100requests targeting the first portion and only12of these requests hit in the first portion, then the hit rate is 12%. If the hit rate for the first portion is less than a second threshold (conditional block530, “yes” leg), then the cache applies a bypass insertion policy to the second portion (block535). Applying the bypass insertion policy causes requests to not be allocated in the second portion, which helps to prevent cache thrashing and reduces stress on the probe filter. If the hit rate for the first portion is less than the second threshold, this indicates that the cache is not particularly useful for the current application. It is noted that in another implementation, the cache includes a plurality of monitors for monitoring the hit-rates for many different classifications of cache traffic. The cache then makes its bypass or non-bypass insertion policy decision based on the hit-rate for the particular classification of the targeted cache line. After block535, method500returns to block505. Alternatively, method500can alternate between returning to block525after block535on some iterations and returning to block505after block535on other iterations.

Otherwise, if the hit rate for the first portion is greater than or equal to the second threshold (conditional block530, “yes” leg), then the cache applies a non-bypass insertion policy to the second portion (block540). In this case, the cache is useful, and so the cache can allocate for requests that miss in the second portion. After block540, method500returns to block505. Alternatively, method500can alternate between returning to block525after block540on some iterations and returning to block505after block540on other iterations. It is noted that some amount of hysteresis can be applied to the thresholds of method500to prevent the cache from oscillating between non-bypass insertion policy and bypass insertion policy.

Turning now toFIG.6, one implementation of determining an insertion policy for a portion of a cache is shown. A cache receives an indication of a probe filter stress level (block605). In one implementation, the indication of the probe filter stress level is a measure of a recall probe rate of the probe filter. In other implementations, other metrics of the probe filter stress level are generated and used as indications which are sent to the cache. Also, the cache monitors a hit rate of a first portion of the cache (block610).

Next, the cache determines an insertion policy to apply to a second portion of the cache, where the insertion policy is based on both the probe filter stress level and the hit rate of the first portion of the cache (block615). Then, the insertion policy determined in block615is applied to the second portion of the cache (block620). In one implementation, the cache determines an insertion rate which is based on a combination of the probe filter stress level and the hit rate of the first portion of the cache. For example, in one implementation, the higher the probe filter stress level and the lower the hit rate of the first portion, the higher the insertion rate that is applied to the cache when deciding whether to allocate new cache lines in the second portion of the cache. A higher insertion rate can also be referred to as a relatively less discriminating cache insertion policy. Conversely, the lower the probe filter stress level and the higher the hit rate of the first portion, the lower the insertion rate that is applied to the cache when deciding whether to allocate new cache lines in the second portion of the cache. A lower insertion rate can also be referred to as a relatively more discriminating cache insertion policy. After block620, method600ends. It is noted that method600can be repeated at some interval to update the insertion policy based on changing levels of probe filter stress and changing hit rates for the first portion of the cache.

In various implementations, program instructions of a software application are used to implement the methods and/or mechanisms described herein. For example, program instructions executable by a general or special purpose processor are contemplated. In various implementations, such program instructions are represented by a high level programming language. In other implementations, the program instructions are compiled from a high level programming language to a binary, intermediate, or other form. Alternatively, program instructions are written that describe the behavior or design of hardware. Such program instructions are represented by a high-level programming language, such as C. Alternatively, a hardware design language (HDL) such as Verilog is used. In various implementations, the program instructions are stored on any of a variety of non-transitory computer readable storage mediums. The storage medium is accessible by a computing system during use to provide the program instructions to the computing system for program execution. Generally speaking, such a computing system includes at least one or more memories and one or more processors configured to execute program instructions.

It should be emphasized that the above-described implementations are only non-limiting examples of implementations. Numerous variations and modifications will become apparent to those skilled in the art once the above disclosure is fully appreciated. It is intended that the following claims be interpreted to embrace all such variations and modifications.