Implementation of a pseudo-LRU algorithm in a partitioned cache
AssigneeInternational Business Machines Corporation
InventorsWen-Tzer Thomas Chen, Peichun Peter Liu, Kevin C. Stelzer
Life of this patent
Estimating the term…
Abstract
The present invention provides for a plurality of partitioned ways of an associative cache. A pseudo-least recently used binary tree is provided, as is a way partition binary tree, and signals are derived from the way partition binary tree as a function of a mapped partition. Signals from the way partition binary tree and the pseudo-least recently used binary tree are combined. A cache line replacement signal is employable to select one way of a partition as a function of the pseudo-least recently used binary tree and the signals derived from the way partition binary tree.
Claims20
A method for employing a cache with partitions, comprising:
- receiving a cache address request;
- determining if there is a cache address miss;
- generating an address comparison match value if there is a cache address miss;
- generating a decision node control value as a function of the partition;
- retrieving a pseudo-least recently used binary tree;
- combining the decision node control value and the pseudo-least recently used binary tree;
- and
- selecting at least one way of the partitioned cache as a function of the combination.
A method for setting partitions of ways in a cache, comprising:
- partitioning a plurality of ways of a cache;
- assigning address ranges to a plurality of address range comparators as a function of the partition;
- creating a way partition binary tree as a function of an output of the address range comparator;
- and
- determining a cache line for replacement within a way correlating as a function of the way partition binary tree.
A system for employing an associative cache, comprising:
- a plurality of partitioned ways of the associative cache;
- a pseudo-least recently used binary tree;
- a way partition binary tree;
- and
- a cache line replacement signal employable for selecting one way of the partition as a function of the pseudo-least recently used binary tree and the way partition binary tree.
A computer program product for employing a cache with partitions, the computer program product having a computer-readable medium with a computer program embodied thereon, the computer program comprising:
- computer code for receiving a cache address request;
- computer code for determining if there is a cache address miss;
- computer code for generating an address comparison match value if there is a cache address miss;
- computer code for generating a decision node control value as a function of the partition;
- computer code for retrieving a pseudo-least recently used binary tree;
- computer code for combining the decision node control value and the pseudo-least recently used binary tree;
- and
- computer code for selecting at least one way of the partitioned cache as a function of the combination.
A processor for employing a partitioned cache, the processor including a computer program comprising:
- computer code for receiving a cache address request;
- computer code for determining if there is a cache address miss;
- computer code for generating an address comparison match value if there is a cache address miss;
- computer code for generating a decision node control value as a function of the partition;
- computer code for retrieving a pseudo-least recently used binary tree;
- computer code for combining the decision node control value and the pseudo-least recently used binary tree;
- and
- computer code for selecting at least one way of the partitioned cache as a function of the combination.
Dependencies are inferred from the claim text.