Cost-conscious pre-emptive cache line displacement and relocation mechanisms
View Patent ↗A hardware based method for determining when to migrate cache lines to the cache bank closest to the requesting processor to avoid remote access penalty for future requests. In a preferred embodiment, decay counters are enhanced and used in determining the cost of retaining a line as opposed to replacing it while not losing the data. In one embodiment, a minimization of off-chip communication is sought; this may be particularly useful in a CMP environment.
1. An apparatus comprised of a computer processor configured for executing a computer program stored in computer memory so as to effect cache management, said apparatus comprising:
an arrangement for displacing data from a cache block;
an arrangement for ascertaining a new cache location for displaced data;
wherein said ascertaining arrangement determines the suitability of one or more candidates for a new cache location via at least one of:
determining a cost of re-fetching the displaced data,
determining a likelihood of future reference to the displaced data, and
determining whether a candidate is able to retain the displaced data;
wherein said ascertaining arrangement determines the suitability of one or more candidates for a new cache location via determining a likelihood of future reference to the displaced data; and
wherein said ascertaining arrangement employs a decay counter corresponding to each candidate cache block to determine a likelihood of future reference to the displaced data; and
wherein said ascertaining arrangement employs a residency counter per congruence class to determine a likelihood of future reference to the displaced data; and
wherein the likelihood of future reference to displaced data corresponds to a threshold being reached in the residency counter; and
wherein the residency counter threshold is 2 n−1 , where n represents a count of instances in which a cache block belonging to a corresponding congruence class is displaced before the decay counter reaches a predetermined decay threshold.
2. The apparatus according to claim 1 , wherein said ascertaining arrangement determines the suitability of one or more candidates for a new cache location via all three of:
determining a cost of re-fetching the displaced data,
determining a likelihood of future reference to the displaced data, and
determining whether a candidate is able to retain the displaced data.
3. The apparatus according to claim 1 , wherein said ascertaining arrangement seeks an on-chip peer cache as a suitable candidate for a new cache location.
4. The apparatus according to claim 3 , wherein said ascertaining arrangement seeks a peer L2 cache as a suitable candidate for a new cache location.
5. The apparatus according to claim 1 , wherein said ascertaining arrangement determines the suitability of one or more candidates for a new cache location via determining a cost of re-fetching the displaced data.
6. The apparatus according to claim 5 , wherein said ascertaining arrangement determines the cost of re-fetching based on a state of a candidate cache block.
7. The apparatus according to claim 6 , wherein said ascertaining arrangement estimates that a cost of re-fetching is cost-effective if a candidate cache block is an exclusive copy, or represents the only copy of a shared cache block within a chip.
8. The apparatus according to claim 1 , wherein said ascertaining arrangement determines the suitability of one or more candidates for a new cache location via determining whether a candidate is able to retain the displaced data.
9. The apparatus according to claim 8 , wherein said ascertaining arrangement employs cache block usage data among candidates for a new cache location.
10. The apparatus according to claim 9 , wherein said ascertaining arrangement employs cache block usage data wherein the most recent requester of a candidate cache block is tracked.
11. A method of effecting cache management, said method comprising the steps of:
displacing data from a cache block;
ascertaining a new cache location for displaced data;
said ascertaining arrangement step comprising determining the suitability of one or more candidates for a new cache location via at least one of:
determining a cost of re-fetching the displaced data,
determining a likelihood of future reference to the displaced data, and
determining whether a candidate is able to retain the displaced data;
wherein said ascertaining step comprises determining the suitability of one or more candidates for a new cache location via determining a likelihood of future reference to the displaced data; and
wherein said step of determining a likelihood of future reference comprises employing a decay counter corresponding to each candidate cache block; and
wherein said step of determining a likelihood of future reference further comprises employing a residency counter per congruence class to determine a likelihood of future reference to the displaced data; and
wherein the likelihood of future reference to displaced data corresponds to a threshold being reached in the residency counter; and
wherein the residency counter threshold is 2 n−1 , where n represents a count of instances in which a cache block belonging to a corresponding congruence class is displaced before the decay counter reaches a predetermined decay threshold.
12. The method according to claim 11 , wherein said ascertaining step comprises determining the suitability of one or more candidates for a new cache location via all three of:
determining a cost of re-fetching the displaced data,
determining a likelihood of future reference to the displaced data, and
determining whether a candidate is able to retain the displaced data.
13. The method according to claim 11 , wherein said ascertaining step comprises seeking an on-chip peer cache as a suitable candidate for a new cache location.
14. The method according to claim 13 , wherein said seeking step comprises seeking a peer L2 cache as a suitable candidate for a new cache location.
15. The method according to claim 11 , wherein said ascertaining step comprises determining the suitability of one or more candidates for a new cache location via determining a cost of re-fetching the displaced data.
16. The method according to claim 15 , wherein said step of determining a cost of re-fetching comprises determining the cost of re-fetching based on a state of a candidate cache block.
17. The method according to claim 16 , wherein said step of determining the cost of re-fetching based on a state of a candidate cache block comprises estimating that a cost of re-fetching is cost-effective if a candidate cache block is in an exclusive state or represents the only or last copy of a shared cache block.
18. The method according to claim 11 , wherein said ascertaining step comprises determining the suitability of one or more candidates for a new cache location via determining whether a candidate is able to retain the displaced data.
19. The method according to claim 18 , wherein said step of determining whether a candidate is able to retain the displaced data comprises employing cache block usage data among candidates for a new cache location.
20. The method according to claim 19 , wherein said step of employing cache block usage data comprises tracking the most recent requester of a candidate cache block.
21. A computer program storage device readable by computer processor machine, tangibly embodying a program of instructions executable by the computer processor machine to perform method steps for effecting cache management, said method comprising the steps of:
displacing data from a cache block;
ascertaining a new cache location for displaced data;
said ascertaining arrangement step comprising determining the suitability of one or more candidates for a new cache location via at least one of:
determining a cost of re-fetching the displaced data,
determining a likelihood of future reference to the displaced data, and
determining whether a candidate is able to retain the displaced data;
wherein said ascertaining step comprises determining the suitability of one or more candidates for a new cache location via determining a likelihood of future reference to the displaced data; and
wherein said step of determining a likelihood of future reference comprises employing a decay counter corresponding to each candidate cache block; and
wherein said step of determining a likelihood of future reference further comprises employing a residency counter per congruence class to determine a likelihood of future reference to the displaced data; and
wherein the likelihood of future reference to displaced data corresponds to a threshold being reached in the residency counter; and
wherein the residency counter threshold is 2 n−1 , where n represents a count of instances in which a cache block belonging to a corresponding congruence class is displaced before the decay counter reaches a predetermined decay threshold.