Back to results
US 12,675,312 B2Granted
Pseudo-random way selection
AssigneeTexas Instruments Incorporated
InventorsAbhijeet Ashok Chachad, David Matthew Thompson
Life of this patent
Estimating the term…
Abstract
A method includes receiving a first request to allocate a line in an N-way set associative cache and, in response to a cache coherence state of a way indicating that a cache line stored in the way is invalid, allocating the way for the first request. The method also includes, in response to no ways in the set having a cache coherence state indicating that the cache line stored in the way is invalid, randomly selecting one of the ways in the set. The method also includes, in response to a cache coherence state of the selected way indicating that another request is not pending for the selected way, allocating the selected way for the first request.
Claims20
A method, comprising:
- receiving a first request to allocate a line in an N-way set associative cache;
- in response to a cache coherence state of a way in the N-way set associative cache indicating that a cache line stored in the way is invalid, allocating the way for the first request;
- and
- in response to no ways in the N-way set associative cache having a cache coherence state indicating that the cache line stored in the way is invalid, pseudo-randomly selecting one of the ways in the N-way set associative cache;
- determining whether a cache coherence state of the pseudo-randomly selected way indicates that another request is not pending for the pseudo-randomly selected way in response to pseudo-randomly selecting the one of the ways;
- and
- allocating the pseudo-randomly selected way for the first request in response to determining that the cache coherence state of the pseudo-randomly selected way indicates that another request is not pending for the pseudo-randomly selected way.
4 more elements
A level two (L2) cache subsystem, comprising:
- a L2 cache configured as an N-way set associative cache;
- and
- a L2 controller configured to:
- receive a first request to allocate a line in the L2 cache;
- determine whether a cache coherence state of a way in the N-way set associative cache indicates that a cache line stored in the way is invalid;
- allocate the way for the first request in response to determining that the cache coherence state of the way indicates that the cache line stored in the way is invalid;
- pseudo-randomly select one of the ways in the N-way set associative cache in response to determining that no ways in the N-way set associative cache have a cache coherence state indicating that the cache line stored in the way is invalid;
- determine whether a cache coherence state of the pseudo-randomly selected way indicates that another request is not pending allocation for the pseudo-randomly selected way;
- and
- allocate the pseudo-randomly selected way for the first request in response to determining that the cache coherence state of the pseudo-randomly selected way indicates that another request is not pending for the pseudo-randomly selected way.
7 more elements
A system, comprising:
- a cache that includes lines arranged in a set of ways;
- a memory configured to store a respective value for each of the lines of the cache, wherein the value for each line includes a first portion and a second portion, and wherein the first portion indicates a modified state, an exclusive state, or a shared state of the line, and the first portion and the second portion collectively indicate an invalid state or a pending state of the line;
- and
- a controller coupled to the cache and the memory and configured to:
- receive a request associated with the set of ways of the cache;
- determine whether any line of the lines has the invalid state based on the values for the lines stored in the memory;
- allocate a first line of the lines to the request in response to determining the first line of the lines has the invalid state based on the value for the first line;
- pseudo-randomly select one of the lines in response to determining that none of the lines has the invalid state based on the values for the lines stored in the memory;
- determine whether the pseudo-randomly selected line does not have the pending state based on the value for the pseudo-randomly selected line in response to pseudo-randomly selecting the one of the lines;
- and
- allocate the pseudo-randomly selected line to the request in response to determining that the pseudo-randomly selected line does not have the pending state.
8 more elements
Dependencies are inferred from the claim text.