Least recently used ranking in a multi-port cache

An apparatus includes a cache controller circuit and a multi-ported cache memory including a plurality of cache ways. The cache controller circuit is configured to maintain rank values and a threshold value usable to classify the rank values. A given rank value corresponds to a least recently used one of the plurality of cache ways. The cache controller circuit is further configured to receive, in a common access cycle, first and second memory access requests for the cache memory, and, in response to a determination that the first and second memory access requests correspond to respective first and a second cache ways, compare the corresponding rank values for the first and second cache ways to the threshold value. The cache controller circuit is further configured to, based on the comparison, modify the rank value of a selected one of the first and second cache ways.

BACKGROUND

Technical Field

Embodiments described herein are related to the field of integrated circuits, and more particularly to management of multi-port cache memories.

Description of the Related Art

A computer system or integrated circuit (IC), such as a system-on-a-chip (SoC), may include a hierarchal memory system that includes a system memory and one or more levels of cache memories. The system memory typically has a large storage capacity, but also has long access times for retrieving stored information. Lower level cache memories may provide faster access to stored information than higher level caches, but may have a smaller size to provide the decreased access time. Accordingly, higher level cache memories may have a greater size than lower level cache memories, but may require longer access times to retrieve stored information.

A given cache memory may include one or more cache sets, each cache set including a plurality of cache ways. When data fetched from a higher level cache or memory system is to be cached, an address associated with the data may be mapped to a particular cache set using any of the available ways. Cache memories may track use of the cache ways from a most recently used to a least recently used cache way in order to determine which of the plurality of ways stores data that is not being accessed as frequently as the other cache ways. When a cache hit occurs, the cache way associated with the hit is promoted to the most recently used status.

Cache memories that support multiple processors may be implemented with multi-port access capability, allowing the cache to access two or more entries in a single access cycle. If two or more processors make cache requests in a same access cycle, a decision is made to select one of the two access requests as being the most recent. Accordingly, when two or more cache hits occur in a single access cycle considerations must be made in order to update the recent usage of the cache ways.

SUMMARY OF THE EMBODIMENTS

Broadly speaking, a system, an apparatus, and a method are contemplated in which the apparatus includes a cache controller circuit and a multi-ported cache memory including a plurality of cache ways, each including a plurality of entries. The cache controller circuit may be configured to maintain a plurality of rank values and a threshold value usable to classify the plurality of rank values. A given rank value of the plurality of rank values may correspond to a given least recently used cache way of the plurality of cache ways and is used to select a particular cache way when evicting an entry. The cache controller circuit may be further configured to receive, in a common access cycle, first and second memory access requests for the cache memory. In response to a determination that the first memory access request and the second memory access request correspond to a first cache way and a second cache way, respectively, the cache controller circuit may be configured to compare the corresponding rank values for the first and second cache ways to the threshold value. Based on the comparison, the cache controller circuit may be configured to modify the rank value of a selected one of the first and second cache ways.

In a further example, the cache controller circuit may be further configured to increase the rank value of the selected cache way in response to a determination that a base rank value of the selected cache way satisfies the threshold value. In one example, the cache controller circuit may be further configured to decrease the rank value of the unselected one of the first and second cache ways in response to a determination that a base rank of the unselected cache way does not satisfy the threshold value.

In another example, in response to a determination that a base rank value of the unselected cache way satisfies the threshold value, the cache controller circuit may be further configured to store an identifier for the unselected cache way. In an embodiment, the cache controller circuit may be further configured to increase the rank value of the unselected cache way in a subsequent access cycle.

In one example, the subsequent access cycle corresponds to an access cycle during which no memory access requests generate cache hits in cache ways with respective rank values that satisfy the threshold value are received by the cache controller circuit. In a further example, the cache controller circuit is further configured to, in response to a determination that the respective rank values for both the first and second cache ways satisfy the threshold value, select the one of the first cache way or the second cache way based on a comparison of the respective rank values of the first and second cache ways.

While the disclosure is susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that the drawings and detailed description thereto are not intended to limit the disclosure to the particular form illustrated, but on the contrary, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope of the present disclosure as defined by the appended claims. As used throughout this application, the word “may” is used in a permissive sense (i.e., meaning having the potential to), rather than the mandatory sense (i.e., meaning must). Similarly, the words “include,” “including,” and “includes” mean including, but not limited to.

DETAILED DESCRIPTION OF EMBODIMENTS

A cache memory with multiple ways may rank use of the multiple ways from a most recently used (MRU) to a least recently used (LRU) cache way. When an entry in a particular cache way is accessed, then the particular cache way is promoted to the MRU cache way position. If an entry in the current LRU cache way is accessed in a subsequent access cycle, then the LRU cache way is promoted to MRU cache way and the particular cache way is shifted down to the second MRU cache way position. All remaining cache ways are similarly shifted down in ranking with the second LRU cache way being demoted down to the new LRU cache way position. If a cache entry needs to be evicted to make room for recently fetched information, a cache controller circuit uses the tracked usage rankings to determine the current LRU cache way, and evicts a corresponding entry in that cache way. The recently fetched information may then be cached in the evicted entry, and the LRU cache way is promoted to MRU cache way and the remaining cache ways are shifted down in ranking.

Multi-port cache memories may be utilized to support multiple processor circuits (referred to herein as “requestor circuits” or simply “requestors”). Requestors may include one or more general purpose processor cores, as well as processors for graphics, audio, digital signal processing, network processing, and the like. In addition, a multi-threaded core may be capable of issuing two or more cache requests in a same access cycle. A multi-port cache memory with multiple cache ways may use the LRU technique for selecting an entry from a particular cache way for eviction. The present inventors have recognized that a multi-ported cache may present issues with respect to implementing LRU policies. For example, if two cache accesses are made to two different cache ways in a single access cycle, then both of the two cache ways should be promoted since they have just been used. In some cache controller circuits, however, more than one access cycle may be required to complete both promotions. If, however, an accessed cache way is not promoted in a timely manner, then entries in the accessed cache way may be at risk of being evicted if it is ranked in the LRU position before receiving the overdue promotion. To avoid evicting an entry from a recently used cache way, a complex circuit may be utilized to perform the decision making in fewer access cycles. Complex circuits, however, may increase power consumption and/or add die size to the cache controller circuit.

Embodiments of apparatus are disclosed that, in response to two or more cache ways being accessed in a single access cycle, are capable of identifying one of the accessed cache ways that is at a higher risk of being evicted. The disclosed embodiments are capable of performing the identification in a single access cycle and may be implemented without using complex logic circuits. In response to receiving two memory access requests that hit in respective cache ways of a multi-ported cache memory, a disclosed embodiment compares a recent use ranking for each respective cache way to a threshold ranking value. In some embodiments, this threshold ranking value may be used to classify rank values for different cache ways (e.g., establishing a “safe zone” of ways that are at less risk for eviction, and a “danger zone” of ways that are at a higher risk for eviction. If a respective cache way's ranking is above the threshold, then the ranking is not changed. If the respective cache way's ranking is below the threshold, then that cache way's ranking is modified.

A block diagram for an embodiment of a cache subsystem is illustrated inFIG. 1. Cache subsystem100may be included in a computer system such as a desktop computer, laptop computer, smartphone, tablet, wearable device, and the like. In some embodiments, the circuits described herein may be implemented on a system-on-chip (SoC) or other type of integrated circuit. Cache subsystem100includes cache controller circuit101, coupled to cache memory110and requestor circuits120aand120b. Cache memory110includes a plurality of cache ways112a-112h.

Cache memory110is a multi-port cache memory including a plurality of cache ways, each cache way including a plurality of entries, such as entries114a-114c. The entries of cache memory110are implemented using arrangements of memory cells. To support multi-port access, the memory cells are designed to support two or more accesses in a single access cycle. In other embodiments, however, single-port memory cells may be utilized, in which the memory cells have access times that are adequately fast to allow two or more accesses in a single cycle, allowing use of a time-domain multiplexing technique.

As illustrated, cache memory110caches information for use by requestor circuits120aand120b. Requestor circuits120aand120bmay be any suitable processing circuit capable of issuing memory requests, such as general-purpose processor cores, graphics processing cores, and the like. In various embodiments, requestor circuits120aand120bmay or may not be a same type of processing circuit. Requestor circuits120aand120bissue various memory requests that are received by cache controller circuit101. These memory requests include requests to read or write information stored at a particular address in a memory system that is accessible to requestor circuits120aand120b. The stored information may be program instructions to be executed by the corresponding requestor circuit, may be data to be consumed by the corresponding requestor circuit, or a combination thereof.

Cache controller circuit101includes circuitry for receiving these various memory requests. This included circuitry may include combinational and/or sequential logic for performing the disclosed functions. After receiving a given memory request, cache controller circuit101determines if the given memory request is a hit or a miss in cache memory110. If an entry in cache memory110corresponds to the given memory request, then the given memory request is a hit, and information stored in the entry is returned to the requestor circuit that issued the corresponding request. Otherwise, if no cache entry matches the given memory request, then that memory request is a miss and the given memory request is forwarded to a higher-level memory (e.g., a higher-level cache memory or a system memory). When information is returned from the higher-level memory, the returned information is stored in a corresponding entry in a selected one of cache ways112a-112h.

Memory addresses used in the memory requests are mapped to a particular entry in each of cache ways112a-112h. This mapping typically varies between cache ways such that a particular memory address will map to a different entry within each one of cache ways112a-112h. To select an entry in one of cache ways112a-112h, cache controller circuit101determines if a mapped entry in any of cache ways112a-112his available. If none of the mapped entries are available, then cache controller circuit101selects one of the filled entries for eviction. To select one of the cache ways from which to evict an entry, cache controller circuit101is configured to maintain rank values140, wherein a given rank value of rank values140corresponds to a given least recently used cache way of the plurality of cache ways112a-112hand is used to select a particular cache way when evicting an entry. Cache controller circuit101is further configured to maintain threshold value145that is usable to classify rank values140.

As illustrated, when cache controller circuit101receives a memory request that hits an entry in a particular one of cache ways112a-112hin cache memory110, the particular cache way is promoted to the MRU rank, and the other cache ways are demoted accordingly. If, however, cache controller circuit101receives two or more memory requests in a same access cycle, then cache controller circuit101uses a different technique for adjusting rank values140. This different technique utilizes a comparison of rank values of cache ways that are hit by the two or more memory requests to a threshold value. This threshold value is used to identify a cache way with a rank value that puts the cache way at risk of being selected for an eviction operation. Accordingly, cache ways with rank values that satisfy the threshold value may be referred to as “at-risk” cache ways, as they are more at-risk of being evicted sooner than cache ways with rank values that do not satisfy the threshold value.

In this different technique, cache controller circuit101receives, in a common access cycle, memory access requests130aand130bfor cache memory110. As used herein, a “memory access cycle,” or simply “access cycle,” refers to a period of time during which the cache controller circuit receives a memory access request and determines if the memory access request is a hit or a miss, and in the case of a hit, returns the requested data. In various embodiments, a memory access cycle may correspond to one or more clock cycles of a system clock.

In response to a determination that memory access request130aand memory access request130bcorrespond to a first cache way (e.g. cache way112b) and a second cache way (e.g., cache way112h), cache controller circuit101is configured to compare, the corresponding rank values140for the first and second cache ways to threshold value145. For example, a base rank value for cache way112bmay be ‘two,’ corresponding to second MRU, while a base rank value for cache way112his ‘eight,’ corresponding to LRU. If threshold value145is ‘five,’ then the base rank value of cache way112bis below threshold value145(not satisfying the threshold), while the base rank value of cache way112his above threshold value145(satisfying the threshold). Cache way112his selected for promotion based on the base rank value being above threshold value145. Cache controller circuit101, based on the comparison, modifies the rank value of the selected one of the first and second cache ways (cache way112h). More specifically, cache controller circuit101is configured to increase the rank value of cache way112hin response to a determination that the base rank value of cache way112hsatisfies threshold value145. In addition, cache controller circuit101is further configured to decrease the rank value of cache way112bin response to the determination that the base rank of cache way112bdoes not satisfy threshold value145. Further details regarding the modification of rank values140will be disclosed below in regards toFIGS. 3-7.

Use of the threshold value may allow a cache controller circuit to identify an accessed cache way, from a group of two or more accessed cache ways, that has a higher risk of being selected for an eviction operation. By identifying a most at-risk cache way from a group of accessed cache ways, the cache controller circuit can promote the identified cache way to a higher ranking, thereby reducing the risk of this cache way being selected for an eviction operation. Furthermore, to identify and promote the most at-risk cache way from the group, the cache controller circuit may not require complex circuits since the promotion occurs to one cache way in an access cycle.

It is noted that cache subsystem100illustrated inFIG. 1is merely an example. The illustration ofFIG. 1has been simplified to highlight features relevant to this disclosure. Various embodiments may include different configurations of the circuit blocks, including additional circuit blocks such as additional requestor circuits and/or a different number of cache ways in the cache memory.

The processor circuit illustrated inFIG. 1is illustrated with a single set of cache ways. In other embodiments, a processor circuit may include one or more cache memories with more than one set of cache ways. An example of such a processor circuit is shown inFIG. 2.

Moving toFIG. 2, a block diagram of an embodiment of a cache subsystem with multiple cache sets in the cache memory is shown. As illustrated, cache subsystem200includes cache controller circuit201coupled to cache memory210. Cache memory210includes cache sets216aand216b, each including a respective portion of cache ways212a-212p. Each of cache ways212a-212pincludes a respective plurality of entries214(for clarity, only entries214a-214fare shown). Cache controller circuit201receives memory requests230a-230cfrom requestor circuit120aand memory requests230d-230ffrom requestor circuit120b.

Cache controller circuit201, as illustrated, includes circuitry for receiving memory requests230a-230fIn a similar manner as cache controller circuit101inFIG. 1, circuitry included in cache controller circuit201may include combinational and/or sequential logic for performing the disclosed functions. Cache controller circuit201is configured to fulfill memory requests230a-230fusing entries in cache memory210when a particular memory request hits a corresponding entry, or indicate a cache miss if a corresponding entry is not found. Cache memory210, similar to cache memory110, is a multi-ported cache memory including a plurality of cache sets (cache sets216aand216b), each cache set including a plurality of entries. Each memory address used in cache subsystem200is mapped to a respective one of cache sets216aand216b. A given memory address is mapped to each cache way within the respective one cache set in a similar manner as described above for cache memory110.

Cache controller circuit201is configured to, for a particular one of cache sets216aand216b, maintain respective rank values for a plurality of cache ways associated with the particular cache set, wherein a particular rank value is based on a recent use of a corresponding one of the plurality of cache ways. As shown, cache controller circuit201is configured to maintain a respective set of rank values for each of cache sets216aand216b. Rank values240acorresponds to cache set216aand rank values240bcorrespond to cache set216b. In addition, cache controller circuit201is further configured to maintain a threshold value usable to classify the plurality of cache ways associated with the particular cache set. As shown, threshold245asets a threshold value for comparison to rank values240a, and threshold245bsets a threshold value for comparison to rank values240b. In other embodiments, however, a single threshold value may be used for both sets of rank values.

In a common access cycle, cache controller circuit201is further configured to receive first and second memory access requests for memory locations that correspond to entries in respective first and second cache ways of the plurality of cache ways. For example, cache controller circuit201receives memory access request230afrom requestor circuit120aand memory access request230dfrom requestor circuit120bwithin a same access cycle. If both memory accesses result in hits to different cache ways within a same one of cache set216aor216b, then cache controller circuit201may select and promote the rank of one of the hit cache ways. To determine which cache way to select for rank promotion, cache controller circuit201is configured to compare respective base rank values for the first and second cache ways to the threshold value, and increase the rank value of the first cache way in response to a determination that the base rank value of the first cache way satisfies the threshold value.

As an example, cache controller circuit201receives memory access request230afrom requestor circuit120aand memory access request230dfrom requestor circuit120bin a common access cycle. Cache controller circuit201determines that memory access request230ahits an entry in cache way212bin cache set216a, and that memory access request230dhits an entry in cache way212h, also in cache set216a. Since cache controller circuit201has received two memory access requests that hit different ones of cache ways212a-212hwithin the same cache set216a, cache controller circuit201may promote the corresponding rank value of a selected one of the two hit cache ways. Cache controller circuit201determines a base rank value for each of cache ways212band212hfrom rank values240a. These two base rank values are compared to threshold245a.

If neither rank value satisfies threshold245a, then both corresponding cache ways212band212hmay be considered safe from being identified as the least recently used cache way for at least several subsequent access cycles. Cache controller circuit201, therefore, does not promote either rank value. If only one of the two rank values satisfies threshold245a(e.g., the base rank value for cache way212b), then the one rank value that satisfies threshold245amay be the LRU position, or be in jeopardy of being the LRU position within a next few access cycles. As a result, cache controller circuit201promotes the rank value of cache way212bto the MRU position. Other rank values, including the rank value corresponding to cache way212h, are shifted lower to allow the promoted rank value to occupy the MRU position.

If both rank values satisfy threshold245a, then both cache ways212band212hmay be in jeopardy of being in the LRU position. Cache controller circuit201performs a second comparison between the respective rank values for cache ways212band212h. Cache controller circuit201promotes the rank value of the cache way (e.g., cache way212b) that is closer to the LRU position. In some embodiments, the rank value of the unpromoted cache way (cache way212h) may not be promoted until another memory access request hits in cache way212h. In other embodiments, cache controller circuit201is further configured to store, in response to a determination that the base rank of cache way212hsatisfies threshold245aand is greater than the base rank value of cache way212b, an identifier for cache way212hin feedback450a. Feedback450aand450bare storage circuits (e.g., registers, RAM, and the like) used to store an identifier for a cache way that is to be promoted in a subsequent access cycle.

In an embodiment that uses identifiers for unpromoted cache ways, the promotion of the rank value of cache way212hmay occur in a different access cycle when subsequently received memory access requests do not satisfy threshold245a. For example, in a different access cycle, cache controller circuit201receives third and fourth memory access requests (e.g., memory access requests230band230e). If a memory location for memory access request230bcorresponds to an entry in cache way212aof cache set216a, and memory access request230eresults in a hit in cache set216b, then in response to a determination that a base rank value of cache way212adoes not satisfy threshold245a, cache controller circuit201increases the rank value of cache way212h, identified by feedback450a. Since cache way212his closer to the LRU position than cache way212a, the rank value of cache way212his promoted. A rank value of memory access request230eis not considered in this embodiment since it hits in a different cache set.

In the disclosed examples, two memory requests are described as being received in a common access cycle. It is contemplated that the disclosed techniques can be applied to embodiments in which three or more memory requests are received in a common access cycle.

It is noted that the embodiment ofFIG. 2is merely an example to demonstrate the disclosed concepts. In other embodiments, a different combination of circuits may be included. For example, in the illustrated embodiment, although two cache sets are shown, any suitable number of cache sets may be included in the cache memory.

FIGS. 1 and 2depict block diagrams of circuits for managing rankings of cache ways in multi-port cache memories.FIGS. 3-7illustrate various examples of updating rank values for a plurality of cache ways in response to receiving a plurality of memory access requests in a same access cycle.

Turning toFIG. 3, a block diagram of an embodiment of a portion of a cache subsystem, such as cache subsystem100inFIG. 1, is illustrated. Eight cache ways are shown inFIG. 3, cache ways112a-112h. In addition, rank values140are shown at two points in time, t1and t2. Threshold value145is depicted as being set midway in rank values140, with four positions on either side of threshold value145. The example ofFIG. 3demonstrates how a cache controller circuit operates in response to receiving two memory request in a single access cycle and a first request satisfies the threshold value while a second request does not.

At time t1, cache ways112a-112hare ranked from cache way112a(represented as “a” in rank values140) is in the MRU position and cache way112h(represented by “h” in rank values140) is in the LRU position and, therefore, is at risk of being evicted if a cache miss occurs. Rank values140at time t1may also be referred to as base rank values at time t2. It is noted that rank values140may be stored, in various embodiments, in any suitable RAM or register circuit.

At time t2, cache controller circuit101receives two memory access requests. Memory access request330ahits an entry in cache way112c, while memory access request330bhits an entry in cache way112fAs described above, cache controller circuit101, in response to determining that the memory access request330aand memory access request330bhit respective entries in a first cache way and a second cache way, uses threshold value145to select either cache way112cor cache way112f, and modifies the rank value of the selected cache way.

In the illustrated example, cache controller circuit101is configured to increase the rank value of the selected cache way in response to a determination that a base rank value of the selected cache way satisfies the threshold value. As shown, the base rank value of cache way112fsatisfies the threshold by having a less recently used ranking than threshold value145. Cache controller circuit101is further configured to decrease the rank value of the unselected cache way in response to a determination that a base rank of the unselected cache way does not satisfy the threshold value. The base rank value of cache way112cdoes not satisfy the threshold as it has a more recently used ranking than threshold value145. Cache controller circuit101selects and promotes cache way112finto the MRU position. Rank values for all cache ways from the former MRU position (cache way112a) to the position immediately in front of the base rank value of cache way112f(cache way112e) are shifted down by one position. As a result, the rank value of cache way112cis demoted by one position.

It is noted that rank values for cache ways112gand112hdo not change since their respective rank values140were below the base rank value of cache way112fIt is also noted that the rank value of cache way112dmoves from above threshold value145to below threshold value145.

Furthermore, it is noted that the example ofFIG. 3is merely to demonstrate the disclosed concepts. In other embodiments, a different number of cache ways may be included in the cache memory. In addition, more than three memory access requests may be received in a single access cycle in some cases.

Proceeding toFIG. 4, the embodimentFIG. 3is shown for additional points in time. Rank values140are shown at three points in time, starting at time t2fromFIG. 3and proceeding to times t3and t4. The example ofFIG. 4demonstrates how a cache controller circuit operates in response to receiving two memory request in a single access cycle and both requests satisfy the threshold value.

As shown, rank values at time t2form the base rank values for time t3. The threshold value, threshold value145, remains the same as inFIG. 3, set at the midway point between the LRU and MRU positions. At time t3, memory access requests430cand430dare received in a common access cycle. Memory access request430chits an entry in cache way112e, while memory access request430dhits an entry in cache way112g.

To select one of cache way112eor cache way112g, cache controller circuit101is configured, in response to a determination that the respective rank values140for both cache ways112eand112gsatisfy threshold value145, to select the one of cache way112eor cache way112gbased on a comparison of the respective rank values140of cache ways112eand112g. Cache controller circuit101selects the particular one of cache ways112eand112gwith the lowest base rank value140. As shown in the base rank values140at time t2, the base rank value of cache way112g(second LRU) is lower than the base rank value of cache way112e(third LRU). Accordingly, cache controller circuit101selects cache way112gfor promotion, as shown in rank values140at time t3. Cache way112gis promoted to the MRU position. Cache ways112f,112a,112b,112c,112d, and112eare each demoted by one position to open the MRU position for cache way112g.

In the illustrated embodiment, cache controller circuit101is further configured to store an identifier for the unselected cache way112ein response to a determination that the base rank value of cache way112esatisfies threshold value145and is greater than the base rank value of cache way112g. As shown, cache controller circuit101stores an identifier for cache way112ein feedback450. Feedback450, in a similar manner as feedback250aand250binFIG. 2, in various embodiments, may be implemented as a location in a RAM or a register (or portion thereof) within cache subsystem100, or any other suitable storage circuit. Cache controller circuit101is configured to increase the rank value of the unselected cache way112ein a subsequent access cycle. A subsequent access cycle may correspond to an access cycle during which no memory access requests generate cache hits in cache ways with respective rank values that satisfy threshold value145are received by cache controller circuit101. An access cycle in which no memory access request generates a hit to an “at-risk” cache way may be referred to as an “idle access cycle” for rank promotion.

For example, at time t4, cache controller circuit101receives two new memory access requests430eand430f, corresponding to cache ways112aand112g, respectively. Rank values140for both cache ways112aand112gare above threshold value145, and therefore, do not satisfy the threshold value. Cache controller circuit101, therefore, does not select either of cache ways112aand112gfor rank promotion, allowing for an access cycle in which cache controller circuit101can instead select cache way112eas identified in feedback450for promotion. Cache controller circuit101promotes the rank of cache way112eto the MRU position as shown in rank values140at time t4. The identifier of cache way112eis removed from feedback450. In some embodiments, feedback450may be capable of storing identifiers for a plurality of unpromoted cache ways. In such embodiments, if two or more cache ways are identified in feedback450during a given idle access cycle, then cache controller circuit may use the current rank values of the identified cache ways to select the cache way with the lower rank value for promotion.

In a different example, at time t4cache controller circuit receives, instead of memory access requests430eand430f, a single memory access request that hits an entry in cache way112h, the rank value of which satisfies threshold value145. Cache controller circuit101is configured to increase the rank value of cache way112hin response to determining that the base rank value of cache way112his lower than the base rank value of the identified cache way112e. The rank value140of cache way112his promoted to the MRU position and the identifier for cache way112eremains in feedback450.

Moving now toFIG. 5, the embodiment ofFIGS. 3 and 4is shown for three subsequent points in time fromFIG. 4. Rank values140are shown starting at time t4fromFIG. 4and proceeding to times t5and t6. The example ofFIG. 5illustrates how a cache controller circuit operates in response to receiving two memory request in a single access cycle in which one memory access requests hits an entry in the cache way in the LRU position and the other memory access request is a cache miss.

Due to the cache miss of memory access request530h, cache controller circuit101evicts an entry in the cache way with the lowest rank value (the LRU position). Since cache way112his promoted to the MRU position before an eviction is performed for memory access request530h, cache way112havoids eviction and cache way112d, which has just been demoted into the LRU position, is evicted instead. Other circuits (not illustrated inFIGS. 1-5) fetch information related to memory access request530h. Cache controller circuit101fills the evicted entry in cache way112dwith information corresponding to memory access request530h. Furthermore, cache controller circuit101increases the rank value of the filled entry in cache way112dto the MRU position, as shown at time t6.

Turning now toFIG. 6, the embodiment ofFIGS. 3-5is depicted at two additional points in time subsequent toFIG. 5. Rank values140are shown starting at time t6fromFIG. 5and at the subsequent time t7. The example ofFIG. 6demonstrates how a cache controller circuit operates in response to receiving two memory request in a single access cycle that both fail to satisfy the threshold value.

Rank values140, as illustrated at time t6, form base rank values for cache ways112a-112hat time t7. At time t7, cache controller circuit101receives memory access requests630iand630j. Memory access request630ihits an entry in cache way112gand memory access request630jhits an entry in cache way112h. In response to a determination that base rank values of cache ways112gand112hare above threshold value145, cache controller circuit101maintains the rank values of cache ways112gand112h. As shown at time t7, rank value140does not change after receiving the two memory access requests630iand630j. It is noted that cache way112dremains in the MRU position even though both cache ways112gand112hhave been accessed more recently.

In other embodiments, cache controller circuit101, in response to determining that base rank values of cache ways112gand112hare both above threshold value145, may select the particular one of cache ways112gand112hwith the lowest base rank value140. As shown in the base rank values140at time t6, the base rank value of cache way112gis lower than the base rank value of cache way112h, and therefore, the rank value of cache way112gmay be promoted to the MRU position. In various embodiments, the rank value of the unselected cache way112hmay or may not be placed into a feedback register, such as previously described for the example ofFIG. 4.

Proceeding now toFIG. 7, a block diagram of an embodiment of a portion of a cache subsystem with multiple cache sets, such as cache subsystem200inFIG. 2, is illustrated. As previously disclosed, cache memory210includes sixteen cache ways, cache ways212a-212p. Cache ways212a-212hare included in cache set216a, while cache ways212i-212pare included in cache set216b. Two sets of rankings are maintained by cache controller circuit201, rank values240atracks rank values for cache ways212a-212hin cache set216a, while rank values240btracks rank values for cache ways212i-212pin cache set216b. Rank values240aand240bare shown at two points in time, t1and t2. Respective thresholds are depicted for each set of rank values. Threshold245ais shown, in a similar manner as threshold value145inFIGS. 3-6, as being set midway in rank values240a, with four positions on either side of threshold245a. Threshold245bis illustrated as being set closer to the LRU position than the MRU position. The example ofFIG. 7demonstrates how a cache controller circuit operates in response to receiving two memory request in a single access cycle, wherein each memory access request hits an entry in respective different cache sets.

At time t1, rank values240aand240b, as shown, depict base rank values for cache ways212a-212pfor time t2. In a different access cycle at time t2, cache controller circuit201receives memory access requests730aand730b. Memory access request730ahits an entry in cache way212f, which is in cache set216a. Referring to rank values240a, the base rank value of cache way212fis above threshold245a, and therefore, does not satisfy the threshold value. Memory request730bhits an entry in cache way212k, which is in cache set216b. The base rank value for cache way212k, as shown in rank values240b, is below threshold245b, and therefore satisfies the threshold value.

In response to a determination that respective memory locations for memory access requests730aand730bcorrespond to respective entries in different cache ways, each in a different cache set of cache sets216aand216b, cache controller circuit201increases the rank values of both cache ways212fand212k. Since memory access requests730aand730bhit in different cache sets, the rank values for the respective cache ways212fand212kare promoted regardless of the thresholds245aand245b. The threshold values are utilized when two or more memory access requests hit in a same cache set. Since, in the illustrated example ofFIG. 7, memory access requests730aand730bhit in different ones of cache sets216aand216b, cache way212fis promoted to the MRU position in rank values240aand cache way212kis promoted to the MRU position in rank values240b.

If both of memory access requests730aand730bhad hit entries in different cache ways in the same cache set, then cache controller circuit201would use the techniques described above to select one of the hit cache ways for promotion. For example, if memory access request730ahad hit an entry in cache way212jin cache set216b, then cache controller circuit201would use the described techniques to select cache way212jfor promotion to the MRU position. Cache way212k, as well as other cache ways ranked above cache way212k, would be demoted one position to open the MRU position for cache way212j.

It is noted that the examples ofFIGS. 3-7are merely for demonstrating the disclosed techniques for maintaining rank values of cache ways by a cache controller circuit. Although each example limits the number of received memory access requests in a given access cycle to two, it is contemplated that the techniques can be applied to cases in which more than two memory access requests are received in a same access cycle. Furthermore, the number of cache ways and cache sets may differ in other embodiments.

Turning now toFIG. 8, a flow diagram for an embodiment of a method for maintaining rank values of cache ways in a cache memory is shown. Method800may be performed by a cache controller circuit of a cache subsystem, for example, cache controller circuit101inFIG. 1, or cache controller circuit201inFIG. 2. In some embodiments, cache controller circuit101, for example, may access a non-transitory, computer-readable medium having program instructions stored thereon that are executable by a processor to cause cache controller circuit101to perform the operations described in regards toFIG. 8. Referring collectively toFIGS. 1 and 8, method800begins in block801.

At block810, method800includes maintaining, by a cache controller circuit, a set of rank values corresponding to a plurality of cache ways included in a multi-port cache memory. The set of rank values is used to select a particular cache way of the plurality of cache ways when evicting an entry. Cache controller circuit101, as shown, maintains rank values140. Rank values140include a plurality of positions, at least one position for each of cache ways112a-112h. The positions range from a least recently (LRU) position to a most recently used (MRU) position to rank cache ways112a-112hfrom the one that has been accessed most recently to the one that has been accessed least recently. After determining that a memory access request hits an entry in a particular cache way, the particular cache way is promoted to the MRU position. Rank values for other cache ways may be demoted by a position open the MRU position for the particular cache way.

Method800further includes, at block820, receiving, by the cache controller circuit, a plurality of memory access requests in a common access cycle. As shown inFIG. 2, cache controller circuit101may receive multiple memory access requests in a same access cycle. Cache memory110is a multi-port memory, and therefore, is capable of servicing two or more access requests in a single access cycle.

At block830, method800further includes determining, by the cache controller circuit, that respective information corresponding to the plurality of memory access requests is stored in respective ones of the plurality of cache ways. Cache controller circuit101determines, for each received memory access request, if the memory access request hits an entry in cache memory110, and if a hit is determined, which of cache ways112a-112hincludes the hit entry.

Method800also includes, at block840, sorting, by the cache controller circuit, the respective cache ways using a corresponding base rank value, from the set of rank values, for each respective cache way and a threshold value, wherein a given rank value is based on a recent use of a respective one of the plurality of cache ways. In some embodiments, method800includes promoting, by cache controller circuit101, only one rank value in a given access cycle. If the plurality of memory access requests hit in two or more of cache ways112a-112h, then cache controller circuit101selects one cache way for rank promotion. To make a selection, cache controller circuit101compares base rank values for each of the two or more cache ways to threshold value145. Based on this comparison, cache controller circuit101determines if any of the two or more hit cache ways have a base rank value that satisfies threshold value145.

Furthermore, method800, at block850, includes increasing the rank value of a particular one of the respective cache ways in response to a determination that the base rank value of the particular cache way satisfies the threshold value. If a single one of the two or more cache ways satisfies the threshold value, then that single cache way is selected, and the rank value of the selected cache way is promoted into the MRU position. Rank values for other cache ways may be demoted by shifting their respective rank value down by one position to open the MRU position for the selected cache way.

If none of the two or more cache ways have a base rank value that satisfies threshold value145, then none of the base rank values are modified. In other embodiments, one of the two or more cache ways may be selected, as previously described, for promotion. If at least two cache ways of the two or more cache ways have a base rank value that satisfies threshold value145, then the cache way with the lowest base rank value (the least recently used of the hit cache ways) is selected. In some embodiments, the one or more cache ways that satisfy threshold value145, but are not selected, may be indicated by a feedback value, such as feedback450inFIG. 4. In such embodiments, the one or more cache ways indicated by the feedback value may be selected in a subsequent access cycle, such as an access cycle in which no memory access requests are received that hit in cache memory110, or received memory requests hit in a cache way whose base rank value does not satisfy threshold value145. The method ends in block890.

It is noted that method800ofFIG. 8is merely an example. Variations of the disclosed methods are contemplated. For example, the maintaining of block810may occur in parallel with blocks820-850.

FIGS. 1-8illustrate apparatus and methods for a cache controller circuit in a cache subsystem. Cache subsystems, such as those described above, may be used in a variety of computer systems, such as a desktop computer, laptop computer, smartphone, tablet, wearable device, and the like. In some embodiments, the circuits described above may be implemented on a system-on-chip (SoC) or other type of integrated circuit. A block diagram illustrating an embodiment of computer system900that includes the disclosed circuits is illustrated inFIG. 9. As shown, computer system900includes processor complex901, memory circuit902, input/output circuits903, clock generation circuit904, analog/mixed-signal circuits905, and power management unit906. These functional circuits are coupled to each other by communication bus911. In various embodiments, memory circuit902and/or processor complex901may include respective embodiments of cache subsystem100or200.

Processor complex901, in various embodiments, may be representative of a general-purpose processor that performs computational operations. For example, processor complex901may be a central processing unit (CPU) such as a microprocessor, a microcontroller, an application-specific integrated circuit (ASIC), or a field-programmable gate array (FPGA). In some embodiments, processor complex901may correspond to a special purpose processing core, such as a graphics processor, audio processor, or neural processor, while in other embodiments, processor complex901may correspond to a general-purpose processor configured and/or programmed to perform one such function. Processor complex901, in some embodiments, may include a plurality of general and/or special purpose processor cores as well as supporting circuits for managing, e.g., power signals, clock signals, and memory requests. In addition, processor complex901may include one or more levels of cache memory to fulfill memory requests issued by included processor cores.

Memory circuit902, in the illustrated embodiment, includes one or more memory circuits for storing instructions and data to be utilized within computer system900by processor complex901. In various embodiments, memory circuit902may include any suitable type of memory such as a dynamic random-access memory (DRAM), a static random access memory (SRAM), or a non-volatile memory such as a read-only memory (ROM), or flash memory, for example. It is noted that in the embodiment of computer system900, a single memory circuit is depicted. In other embodiments, any suitable number of memory circuits may be employed. In some embodiments, memory circuit902may include a memory controller circuit as well communication circuits for accessing memory circuits external to computer system900, such as a DRAM module, a hard drive or a solid-state drive. In some embodiments, non-volatile storage devices such as hard drives and solid-state drives may provide a non-transitory, computer-readable medium for storing program instructions executable by one or more processors in computer system900, including, for example, one ore more cache controller circuits.

Input/output circuits903may be configured to coordinate data transfer between computer system900and one or more peripheral devices. Such peripheral devices may include, without limitation, storage devices (e.g., magnetic or optical media-based storage devices including hard drives, tape drives, CD drives, DVD drives, etc.), audio processing subsystems, or any other suitable type of peripheral devices. In some embodiments, input/output circuits903may be configured to implement a version of Universal Serial Bus (USB) protocol or IEEE 1394 (Firewire®) protocol.

Input/output circuits903may also be configured to coordinate data transfer between computer system900and one or more devices (e.g., other computing systems or integrated circuits) coupled to computer system900via a network. In one embodiment, input/output circuits903may be configured to perform the data processing necessary to implement an Ethernet (IEEE 802.3) networking standard such as Gigabit Ethernet or 10-Gigabit Ethernet, for example, although it is contemplated that any suitable networking standard may be implemented.

Clock generation circuit904may be configured to enable, configure and manage outputs of one or more clock sources. In various embodiments, the clock sources may be located in analog/mixed-signal circuits905, within clock generation circuit904, in other blocks with computer system900, or come from a source external to computer system900, coupled through one or more I/O pins. In some embodiments, clock generation circuit904may be capable of enabling and disabling (e.g., gating) a selected clock source before it is distributed throughout computer system900. Clock generation circuit904may include registers for selecting an output frequency of a phase-locked loop (PLL), delay-locked loop (DLL), frequency-locked loop (FLL), or other type of circuits capable of adjusting a frequency, duty cycle, or other properties of a clock or timing signal.

Analog/mixed-signal circuits905may include a variety of circuits including, for example, a crystal oscillator, PLL or FLL, and a digital-to-analog converter (DAC) (all not shown) configured to generated signals used by computer system900. In some embodiments, analog/mixed-signal circuits905may also include radio frequency (RF) circuits that may be configured for operation with cellular telephone networks. Analog/mixed-signal circuits905may include one or more circuits capable of generating a reference voltage at a particular voltage level, such as a voltage regulator or band-gap voltage reference.

Power management unit906may be configured to generate a regulated voltage level on a power supply signal for processor complex901, input/output circuits903, memory circuit902, and other circuits in computer system900. In various embodiments, power management unit906may include one or more voltage regulator circuits, such as, e.g., a buck regulator circuit, configured to generate the regulated voltage level based on an external power supply (not shown). In some embodiments any suitable number of regulated voltage levels may be generated. Additionally, power management unit906may include various circuits for managing distribution of one or more power signals to the various circuits in computer system900, including maintaining and adjusting voltage levels of these power signals. Power management unit906may include circuits for monitoring power usage by computer system900, including determining or estimating power usage by particular circuits.

It is noted that the embodiment illustrated inFIG. 9includes one example of a computer system. A limited number of circuit blocks are illustrated for simplicity. In other embodiments, any suitable number and combination of circuit blocks may be included. For example, in other embodiments, security and/or cryptographic circuit blocks may be included.

FIG. 10is a block diagram illustrating an example of a non-transitory computer-readable storage medium that stores circuit design information, according to some embodiments. The embodiment ofFIG. 10may be utilized in a process to design and manufacture integrated circuits, such as, for example, an IC that includes computer system900ofFIG. 9. In the illustrated embodiment, semiconductor fabrication system1020is configured to process the design information1015stored on non-transitory computer-readable storage medium1010and fabricate integrated circuit1030based on the design information1015.

Design information1015may be specified using any of various appropriate computer languages, including hardware description languages such as, without limitation: VHDL, Verilog, SystemC, SystemVerilog, RHDL, M, MyHDL, etc. Design information1015may be usable by semiconductor fabrication system1020to fabricate at least a portion of integrated circuit1030. The format of design information1015may be recognized by at least one semiconductor fabrication system, such as semiconductor fabrication system1020, for example. In some embodiments, design information1015may include a netlist that specifies elements of a cell library, as well as their connectivity. One or more cell libraries used during logic synthesis of circuits included in integrated circuit1030may also be included in design information1015. Such cell libraries may include information indicative of device or transistor level netlists, mask design data, characterization data, and the like, of cells included in the cell library.

Integrated circuit1030may, in various embodiments, include one or more custom macrocells, such as memories, analog or mixed-signal circuits, and the like. In such cases, design information1015may include information related to included macrocells. Such information may include, without limitation, schematics capture database, mask design data, behavioral models, and device or transistor level netlists. As used herein, mask design data may be formatted according to graphic data system (gdsii), or any other suitable format.

In various embodiments, integrated circuit1030is configured to operate according to a circuit design specified by design information1015, which may include performing any of the functionality described herein. For example, integrated circuit1030may include any of various elements shown or described herein. Further, integrated circuit1030may be configured to perform various functions described herein in conjunction with other components. Further, the functionality described herein may be performed by multiple connected integrated circuits.