Cache using pseudo least recently used (PLRU) cache replacement with locking
View Patent ↗A cache stores information in each of a plurality of cache lines. Addressing circuitry receives memory addresses for comparison with multiple ways of stored addresses to determine a hit condition representing a match of a stored address and a received address. A pseudo least recently used (PLRU) tree circuit stores one or more states of a PLRU tree and implements a tree having a plurality of levels beginning with a root and indicates one of a plurality of ways in the cache. Each level has one or more nodes. Multiple nodes within a same level are child nodes to a parent node of an immediately higher level. PLRU update circuitry that is coupled to the addressing circuitry and the PLRU tree circuit receives lock information to lock one or more lines of the cache and prevent a PLRU tree state from selecting a locked line.
1. A cache comprising:
storage circuitry for storing information in each of a plurality of cache lines;
addressing circuitry having an input for receiving memory addresses and comparing received memory addresses with multiple ways of stored addresses to determine a hit condition representing a match of a stored address and a received address;
a pseudo least recently used (PLRU) tree circuit for storing one or more states of a PLRU tree, the PLRU tree having a plurality of levels beginning with a root and which indicates one of a plurality of ways in the cache, each level having one or more nodes, multiple nodes within a same level being child nodes to a parent node of an immediately higher level, wherein, when there is at least one unlocked way of the cache, none of the one or more states of the PLRU tree indicate a locked way; and
PLRU update circuitry coupled to the addressing circuitry and the PLRU tree circuit, the PLRU update circuitry receiving lock information to lock one or more lines of the cache and preventing a PLRU tree state from selecting a locked line, wherein the lock information comprises a way lock bit for each cache line of the cache which indicates whether a corresponding way of the cache is locked or not and a node lock bit corresponding to each node of the PLRU tree which indicates whether a corresponding node of the PLRU tree is locked or not;
wherein, for each allocation of a new cache line when there is at least one unlocked way of the cache, a state of the PLRU tree stored by the PLRU tree circuit indicates a selected replacement way, wherein the selected replacement way indicated by the state of the PLRU tree is directly used as the selected replacement way for the new cache line without further processing of the selected replacement way.
2. The cache of claim 1 wherein the PLRU update circuitry further comprises logic circuitry that locks any parent node when all child nodes of a corresponding parent node are locked in response to the lock information.
3. The cache of claim 2 wherein the PLRU update circuitry locks a root node corresponding to the root of the PLRU tree, thereby locking all of the plurality of ways in the cache.
4. The cache of claim 3 wherein the PLRU update circuitry further comprises default logic which points to a predetermined one of the plurality of ways in the cache when the root node of the PLRU tree is locked by the lock information.
5. The cache of claim 3 wherein the PLRU update circuitry does not select a replacement way to be replaced next when the root node of the PLRU tree is locked by the lock information.
6. The cache of claim 1 wherein the PLRU update circuitry implements a traversal of the PLRU tree structure via a traversal path from the root to a lowest level to identify a replacement way that is not locked by the lock information by using the node lock bit associated with each node in the traversal path.
7. The cache of claim 1 , wherein the PLRU update circuit updates at least one state of the one or more states of the PLRU tree in response to the hit condition determined by the addressing circuitry.
8. A cache comprising:
multi-way cache circuitry for storing a plurality of sets, each of the plurality of sets comprising a plurality of ways and each way comprising tag, status and data fields;
hit detection circuitry coupled to the multi-way cache circuitry for providing a hit signal indicating when the multi-way cache circuitry contains information associated with an address received at an input;
a pseudo least recently used (PLRU) tree circuit for storing one or more states of a PLRU tree, the PLRU tree circuit implementing a tree structure having a plurality of levels beginning with a root and which indicates one of a plurality of ways to be replaced next in the semiconductor cache, each level having one or more nodes, multiple nodes within a same level being child nodes to a parent node of an immediately higher level, wherein, when there is at least one unlocked way of the cache, none of the one or more states of the PLRU tree indicate a locked way; and
PLRU update circuitry coupled to the hit detection circuitry and the PLRU tree circuit, the PLRU update circuitry receiving lock information to lock one or more ways of a cache set and preventing a PLRU tree state from selecting a locked way, wherein the lock information comprises a way lock bit for each cache line of the cache which indicates whether a corresponding way of the cache is locked or not and a node lock bit corresponding to each node of the PLRU tree which indicates whether a corresponding node of the PLRU tree is locked or not;
wherein, for each allocation of a new cache line when there is at least one unlocked way of the cache, a state of the PLRU tree stored by the PLRU tree circuit indicates a selected replacement way, wherein the selected replacement way indicated by the state of the PLRU tree is directly used as the selected replacement way for the new cache line without further processing of the selected replacement way.
9. The cache of claim 8 wherein the PLRU update circuitry determines whether to prevent each of the one or more states of the PLRU tree from selecting a locked way by traversing the tree structure from the root to a lowest level and using the node lock bit associated with each node in the traversal path to perform the determining.
10. The cache of claim 9 wherein the PLRU tree circuit stores the node lock bit associated with each node in the traversal path and a corresponding node state bit for indicating a path direction to a next level node in the traversal path.
11. The cache of claim 9 wherein the PLRU update circuitry further comprises default logic which points to a predetermined one of the plurality of ways to be replaced next in the semiconductor cache when all of the plurality of ways are indicated as locked by the lock information.
12. The cache of claim 9 wherein the PLRU update circuitry does not select a replacement way when the root of the tree structure is locked by the lock information.
13. A method comprising:
providing storage circuitry in a cache for storing information in each of a plurality of cache lines;
providing addressing circuitry having an input for receiving memory addresses and comparing received memory addresses with multiple ways of stored addresses to determine a hit condition representing a match of a stored address and a received address; and
providing a pseudo least recently used (PLRU) tree circuit for storing one or more states of a PLRU tree, the PLRU tree circuit implementing a tree structure having a plurality of levels beginning with a root and which indicate one of a plurality of ways to be replaced next in the cache, each level having one or more nodes, multiple nodes within a same level being child nodes to a parent node of an immediately higher level, wherein, when there is at least one unlocked way of the cache, none of the one or more states of the PLRU tree indicate a locked way; and
coupling PLRU update circuitry to the addressing circuitry and the PLRU tree circuit, the PLRU update circuitry receiving lock information to lock one or more ways of the PLRU tree and preventing a PLRU tree state from selecting a locked line, wherein the lock information comprises a way lock bit for each cache line of the cache which indicates whether a corresponding way of the cache is locked or not and a node lock bit corresponding to each node of the PLRU tree which indicates whether a corresponding node of the PLRU tree is locked or not, and wherein, for each allocation of a new cache line when there is at least one unlocked way of the cache, a state of the PLRU tree stored by the PLRU tree circuit indicates a selected replacement way, wherein the selected replacement way indicated by the state of the PLRU tree is directly used as the selected replacement way for the new cache line without further processing of the selected replacement way.
14. The method of claim 13 further comprising:
providing logic circuitry in the PLRU update circuitry that locks any parent node when all child nodes of a corresponding parent node are locked in response to the lock information.
15. The method of claim 14 further comprising:
locking a root node corresponding to the root of the PLRU tree, thereby locking all of the plurality of ways to be replaced next in the cache.
16. The method of claim 15 further comprising:
either not selecting a replacement way when the root node of the PLRU tree is locked by the lock information or using a default value that points to a predetermined one of the plurality of ways to be replaced next in the cache when the root node of the PLRU tree is locked by the lock information.
17. The method of claim 13 further comprising:
storing a node lock bit and a node state bit for each node of the PLRU tree.
18. The method of claim 13 further comprising:
traversing the PLRU tree structure via a traversal path from the root to a lowest level to identify a replacement way that is not locked by the lock information by using lock information associated with each node in the traversal path.