Method for Evicting Data from Memory

Abstract

Provided is a resource manager. The resource manager may be a memory manager which is configured to determine a plurality of eviction rankings, wherein each of the plurality of eviction rankings assigns a position within the eviction ranking to each of a plurality of eviction candidates based on at least one eviction criterion. The memory manager may then select one of said eviction candidates by applying a voting algorithm to the plurality of eviction rankings and cause the selected eviction candidate to be evicted.

Claims

1. A memory manager, the memory manager being configured to: determine a plurality of eviction rankings, wherein each of the plurality of eviction rankings ranks a plurality of eviction candidates based on at least one eviction criterion; select one of said eviction candidates by applying a voting algorithm to the plurality of eviction rankings; and cause the selected eviction candidate to be evicted.

2. The memory manager of claim 1, wherein, by ranking, each of the plurality of eviction rankings assigns a position within the eviction ranking to each of the plurality of eviction candidates.

3. The memory manager of claim 1, wherein the voting algorithm determines the most favored eviction candidates across multiple eviction rankings by aggregating measures of favorability derived from the multiple eviction rankings.

4. The memory manager of claim 1, the memory manager being further configured to: determine the plurality of eviction rankings in parallel.

5. The memory manager of claim 1, the memory manager being further configured to: reapply the voting algorithm to a subset of the plurality of eviction rankings if a tie occurs between candidates, most favored for eviction by the voting algorithm; or apply another voting algorithm to the plurality of eviction rankings if a tie occurs between candidates that are most favored for eviction by the previously applied voting algorithm.

6. The memory manager of claim 5, the memory manager being further configured to: randomly select one of the eviction candidates between which a tie has occurred, if reapplying the voting algorithm or applying the other voting algorithm does not favor one of the candidates previously most favored for eviction by the voting algorithm.

7. The memory manager of claim 1, wherein the eviction candidates are memory blocks.

8. A method of managing a memory, comprising: determining a first eviction ranking which ranks a plurality of eviction candidates based on at least one first eviction criterion; determining a second eviction ranking which ranks the plurality of eviction candidates based on at least one second eviction criterion; determining a first eviction candidate based on the first eviction ranking and the second eviction ranking, by applying a voting algorithm to the first and second eviction rankings; and evicting the first eviction candidate.

9. The method of claim 8, wherein evicting the first eviction candidate involves replacing first data stored in the first eviction candidate with second data.

10. The method of claim 8, wherein the eviction candidates are memory blocks.

11. The method of managing a memory according to claim 10, wherein the first and second eviction rankings assign to each block of the memory a position in the first eviction ranking and the second eviction ranking, respectively.

12. The method of managing a memory according to claim 11, wherein a memory block to which a lowest position in the first eviction ranking and/or a lowest position in the second eviction ranking is assigned, is excluded from being determined as the first memory block.

13. The method of managing a memory according to claim 10, wherein determining the first memory block for eviction based on the first eviction ranking and the second eviction ranking comprises assigning a third value to the first memory block; wherein the third value is an output of a function which takes a first value assigned to a first position of the first memory block in the first eviction ranking and a second value assigned to a second position of the first memory block in the second eviction ranking as inputs.

14. The method of managing a memory according to claim 13, wherein the third value is used to establish a voting result and the first memory block is a memory block to which is assigned a highest position in the voting result.

15. The method of managing a memory according to claim 13, wherein determining the first memory block for eviction based on the first eviction ranking and the second eviction ranking further comprises assigning a sixth value to a second memory block; wherein the sixth value is an output of the function which takes a fourth value assigned to a fourth position of the second memory block in the first eviction ranking and a fifth value assigned to a fifth position of the second memory block in the second eviction ranking as inputs; wherein, if the sixth value equals the third value, one of the first and second eviction rankings is disregarded for determining the first memory block for eviction.

16. The method of managing a memory according to claim 13, wherein the third value is a linear combination of the first value and the second value.

17. The method of managing a memory according to claim 13, further comprising: monitoring the eviction decisions for favoritism and adapting the function if favoritism is detected.

18. The method of managing a memory according to claim 10, further comprising: determining a third eviction ranking which ranks the plurality of memory blocks based on at least one third eviction criterion; determining a preliminary voting result based on the first eviction ranking, the second eviction ranking and the third eviction ranking; and detecting a tie regarding the first memory block and a second memory block, based on the preliminary voting result.

19. The method of managing a memory according to claim 10, further comprising: determining a fourth eviction ranking which ranks the plurality of memory blocks based on the at least one first eviction criterion; determining a fifth eviction ranking which ranks the plurality of memory blocks based on the at least one second eviction criterion; selecting a third memory block for eviction based on the fourth eviction ranking and the fifth eviction ranking; and replacing third data stored in the third memory block with fourth data.

20. The method of managing a memory according to claim 10, wherein the memory is a cache; and the method further comprises: detecting a cache miss in regard to the second data; and determining that the cache is full.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0040] The foregoing aspects and many of the attendant advantages will become more readily appreciated as the same becomes better understood by reference to the following description of embodiments, when taken in conjunction with the accompanying drawings, wherein like reference numerals refer to like parts throughout the various views, unless otherwise specified. In this regard, it is noted that although the described embodiments relate to memory management, other resources than memories (e.g., processors, processor cores, bandwidth, etc.) are also contemplated.

[0041] FIG. 1 illustrates a process of determining eviction rankings and determining a first memory block for eviction based on the eviction rankings;

[0042] FIG. 2 illustrates resolving ties in the process of FIG. 1;

[0043] FIG. 3 shows a memory and a memory manager;

[0044] FIG. 4 shows a flow chart of the process;

[0045] FIG. 5 to FIG. 7 show further examples of procedures for resolving a tie; and

[0046] FIG. 8a and FIG. 8b illustrate detecting favoritism.

[0047] Notably, the drawings are not drawn to scale and unless otherwise indicated, they are merely intended to conceptually illustrate the structures and procedures described herein.

DESCRIPTION OF EMBODIMENTS

[0048] FIG. 1 shows memory 10 which comprises memory blocks A, B, C and D. Memory 10 may contain more or less memory blocks than memory blocks A, B, C and D shown in FIG. 1, but the remainder of this description is written as if memory 10 contained only memory blocks A, B, C and D, i.e., as if memory 10 was divided into memory blocks A, B, C and D. When all blocks A, B, C and D of memory 10 contain valid data, storing data that is not yet contained in (or by the nature of its content affiliated with) one of memory blocks A, B, C and D, is preceded by execution of a memory management process that decides which one of memory blocks A, B, C or D is to be evicted.

[0049] Execution of the memory management process by memory manager 12 is triggered by decision request 14. Decision request 14 causes ranking unit 16 of memory manager 12 to generate multiple eviction rankings 18 and 20. Eviction ranking 18 is generated by ranking module 22. Ranking module 22 comprises (or has access to) one or more eviction criteria 24. The one or more eviction criteria 24 and optionally one or more rules relating to the one or more eviction criteria 24 define a specific eviction policy.

[0050] Eviction ranking 20 is generated by ranking module 26 which can be operated in parallel with ranking module 22. Ranking module 26 also comprises (or operates in accordance with) one or more eviction criteria 28 and optionally one or more rules relating to the one or more eviction criteria 28. The one or more eviction criteria 28 and optionally one or more rules define a specific eviction policy which differs from the eviction policy followed by ranking module 22. Ranking modules 22 and 26 thus operate on (the same) set of eviction candidates (i.e., memory blocks A, B, C and D of memory 10) but differ in regard to the eviction policies they follow. As indicated in FIG. 1, ranking unit 16 may contain further ranking modules (not shown) each of which is unique in view of the eviction policy that it follows.

[0051] Each of eviction rankings 18 and 20 assigns a position to each of memory blocks A, B, C and D. The positions assigned to memory blocks A, B, C and D reflect which one of memory blocks A, B, C and D is to be evicted first, which one of memory blocks A, B, C and D is to be evicted second, etc. In other words, eviction rankings 18 and 20 are reflective of a preference with which each of memory blocks A, B, C and D is to be evicted or maintained under the applied eviction policies. Hence, although eviction rankings 18 and 20 may (depending on the applied eviction policies) both assign the same positions to memory blocks A, B, C and D, eviction rankings 18 and 20 can generally be expected to order the same eviction candidates in different ways.

[0052] For example, each of eviction rankings 18 and 20 may be based on one eviction policy selected from the group consisting of Least Recently Used (LRU) and Least Frequently Used (LFU). If memory 10 is employed in a multi-core environment that has multiple memories (caches) that possibly contain (in part) the same data and a sparse directory, each of eviction rankings 18 and 20 may be based on one eviction policy selected from the group consisting of Least Recently Used (LRU), Least Frequently Used (LFU), Least Number of Sharers (LNS) and Shortest Distance First (SDF). However, the present disclosure is not limited to said eviction policies.

[0053] In the present example, eviction ranking 18 would, if being the only one of eviction rankings 18 and 20 that is relied on, suggest evicting memory block C. Eviction ranking 20 would, if being the only one of eviction rankings 18 and 20 that is relied on, suggest evicting memory block A. To determine which one of memory blocks A, B, C and D is to be evicted, the memory manager 12 contains a voting unit 30 which processes the eviction rankings 18 and 20. Voting unit 30 translates positions assigned to a memory block to numerical values V.sub.i (with i identifying the eviction policy) and aggregates the numerical values (for example, by summing them up: Σ.sub.i=0.sup.nV.sub.i, with n being the number of eviction policies that are available or taken into account). For instance, voting unit 30 may assign: [0054] a “1” and a “4” to memory block A, as memory block A is at the lowest position in eviction ranking 18 and at the highest position in eviction ranking 20, and add both numerical values which results in a “5” for memory block A. [0055] two times a “2” to memory block B, as memory block B is immediately above the lowest position in eviction ranking 18 and immediately above the lowest position in eviction ranking 20, and add both numerical values which results in a “4” for memory block B. [0056] a “4” and a “1” to memory block C, as memory block C is at the highest position in eviction ranking 18 and at the lowest position in eviction ranking 20, and add both numerical values which results in a “5” for memory block C. [0057] two times a “3” to memory block D, as memory block D is immediately below the highest position in eviction ranking 18 and immediately below the highest position in eviction ranking 20, and add both numerical values which results in a “6” for memory block D.

[0058] By reordering memory blocks A, B, C and D from highest aggregated value to lowest aggregated value, a voting result 32 (which may be a full eviction ranking as shown in FIG. 1, but may also be a partial eviction ranking or only memory block D) may be established and memory block D (to which the highest position in the voting result 32 is assigned) may be returned by memory manager 12 in decision response 34 which causes memory block D to be evicted. Notably, the above described voting algorithm which applies a linear function to numerical values assigned to the positions is but one example and shall not be construed as limiting, because the described concept lends itself not only to various adaptions of the function but also to fundamentally different voting algorithms.

[0059] For example, the voting algorithm may be adapted by assigning weights a, to eviction rankings 18 and 20, and the numerical values assigned to the positions may be multiplied with the weights before being summed up: Σ.sub.i=0.sup.nα.sub.iV.sub.i. Furthermore, instead of or in addition to multiplying the numerical values with weights, one or more of the numerical values V.sub.i may be replaced with v.sub.i.sup.j with j≠1: Σ.sub.i=0.sup.nV.sub.i.sup.j or Σ.sub.i=0.sup.nα.sub.iV.sub.i.sup.j. Moreover, instead of considering all positions, only N positions (for example, the N highest positions) may be taken into account (with N being an integer that is smaller than the number of eviction candidates). Furthermore, certain eviction candidates may be flagged as “not-to-evict” because they achieved a relatively low position in one or more of eviction rankings 18 and 20 (such as memory block A and memory block C in the depicted example).

[0060] As illustrated in FIG. 1, applying a voting algorithm to eviction rankings 18 and 20 may result in a tie regarding two or more of memory blocks A, B, C and D. If there is no tie regarding the top position, as in the example depicted in FIG. 1, tie resolution may not be required. But if a tie must be resolved, tie resolution may be performed as will be explained with reference to FIG. 2. There, if a need for tie resolution is detected at decision block 36, it is determined at decision block 38 whether a policy agnostic or a policy dependent tie resolution is to be performed.

[0061] If it is decided at decision block 38 that a policy agnostic tie resolution is to be performed, action block 40 is invoked which randomly selects one of (or orders) the eviction candidates involved in the tie or settles the tie based on memory transaction states or memory types. Memory transaction states (which may be related to a coherence protocol) may indicate whether a memory block can be readily evicted (which is the case if, for example, the memory block is in a stable state) or whether a waiting time is required before the memory block can be evicted (which is the case, for example, if the memory block is in a transition state). Ties may also be resolved based on memory types (SRAM, DRAM, etc.) as they may have different write-back times. Both memory transaction states and memory types may not be limited to tie-resolution and may (also) be used as an eviction criterion.

[0062] If it is decided at decision block 38 that a policy dependent tie resolution is to be performed, action block 42 is invoked which causes voting unit 30 to disregard one of eviction rankings 18 and 20. Another option would be to cause ranking unit 16 to provide additional (or modified) eviction rankings (not shown). For instance, ranking unit 16 may comprise M ranking modules (including ranking modules 22 and 26), each of which applies a different eviction policy to the same set of eviction candidates. If only a subset of the available ranking units is active, additional ranking modules may be activated at request. Likewise, ranking modules may be temporarily inactivated at request. In other words, ranking unit 16 may be provided with a plurality of ranking modules (including ranking modules 22 and 26) which can be activated and deactivated at run time, meaning that a deactivated ranking module does either not provide an eviction ranking or, that the eviction ranking of a deactivated ranking module is disregarded by the voting unit 30. Moreover, ranking modules 22 and 26 may allow for the modification of the underlying eviction polices at run time.

[0063] As schematically illustrated in FIG. 3, memory manager 12 may be connected to system 44 which comprises memory 10. System 44 may further comprise one or more processor cores (no shown) and one or more further memories. If an entity within system 44 (such as a processor core) to which memory 10 is assigned requests data that is not stored in memory 10, it may be decided to add said data to memory 10 to avoid future memory misses. If memory 10 is full, decision request 14 may be made. In case that one of memory managers 12 or 12′ receives decision requests 14 for different memories, all information required by memory manager 12 or 12′ may be provided by system 44 through decision request 14.

[0064] For example, decision request 14 may comprise a list of eviction candidates, the eviction policies to be used and the parameters of each eviction candidate that are to be evaluated in accordance with the eviction policies. In case that memory manager 12 or 12′ receives decision requests 14 only for memory 10, the information required by memory manager 12 or 12′ may already be available in memory manager 12 or 12′ or received (in total or part) through decision request 14. If system 44 comprises a plurality of instances of memory 10, each one may be provided with a dedicated memory manager or multiple instances may share a single memory manager.

[0065] FIG. 4 shows a flow chart of some basic steps performed by memory manager 12. At step 46, memory manager 12 determines eviction ranking 18 which ranks the plurality of memory blocks A, B, C and D based on eviction criterion 24. At step 48, memory manager 12 determines eviction ranking 20 which ranks the plurality of memory blocks A, B, C and D based on eviction criterion 28. Notably, steps 46 and 48 may be performed concurrently. At step 50, memory manager 12 determines memory block D for eviction based on eviction ranking 18 and eviction ranking 20. At step 52, data stored in memory block D is replaced.

[0066] FIG. 5 shows an example where a voting on eviction rankings 18, 20 and 54 results in a tie regarding the top position in voting result 56. As shown in FIG. 5, this tie may be resolved by disregarding eviction ranking 54. FIG. 6 shows another example where a voting on eviction rankings 18 and 58 results in a tie regarding the top position in voting result 60. As shown in FIG. 6, this tie may be resolved by randomly ordering memory blocks C and D involved in the tie. FIG. 7 shows an alternative tie resolution where eviction ranking 18 is disregarded to resolve the tie, leading to result 60′.

[0067] FIG. 8a and FIG. 8b illustrate a series of ranking and voting steps performed on memory blocks A, B, C and D which exhibit favoritism which reveals itself in that a substantially static series of voting results 32, 66, 72, 78, 32 and 84 is determined from eviction rankings 18, 20, 62, 64, 68, 70, 74, 76, 18, 20, 80 and 82. In response, an additional ranking module may be activated, one of ranking modules 22, 26 may be deactivated, or the voting algorithm may be adapted as described above.

REFERENCE SIGNS LIST

[0068] 10 memory [0069] 12 memory manager [0070] 12′ memory manager [0071] 14 decision request [0072] 16 ranking unit [0073] 18 eviction ranking [0074] 20 eviction ranking [0075] 22 ranking module [0076] 24 eviction criterion [0077] 26 ranking module [0078] 28 eviction criterion [0079] 30 voting unit [0080] 32 voting result [0081] 34 decision response [0082] 36 decision block (“tie resolution?”) [0083] 38 decision block (“policy agnostic tie resolution?”) [0084] 40 action block [0085] 42 action block [0086] 44 system [0087] 46 process step [0088] 48 process step [0089] 50 process step [0090] 52 process step [0091] 54 eviction ranking [0092] 56 voting result [0093] 58 eviction ranking [0094] 60 voting result [0095] 60′ result [0096] 62 eviction ranking [0097] 64 eviction ranking [0098] 66 voting result [0099] 68 eviction ranking [0100] 70 eviction ranking [0101] 72 voting result [0102] 74 eviction ranking [0103] 76 eviction ranking [0104] 78 voting result [0105] 80 eviction ranking [0106] 82 eviction ranking [0107] 84 voting result [0108] A memory block [0109] B memory block [0110] C memory block [0111] D memory block [0112] E memory block