Cost-conscious pre-emptive cache line displacement and relocation mechanisms
AssigneeInternational Business Machines Corporation
InventorsAlper Buyuktosunoglu, Zhigang Hu, Jude A. Rivers, John T. Robinson, Xiaowei Shen, Vijayalakshmi Srinivasan
Life of this patent
Estimating the term…
Abstract
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.
Claims21
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 2n−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.
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 2n−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.
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 2n−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.
Dependencies are inferred from the claim text.