Pseudo-random way selection
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.
1 . 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.
2 . The method of claim 1 , further comprising:
servicing the first request without allocating a line in the N-way set associative cache in response to determining that the cache coherence state of the pseudo-randomly selected way indicates that another request is pending for the pseudo-randomly selected way.
3 . The method of claim 2 , wherein servicing the first request without allocating a line in the N-way set associative cache further comprises converting the first request to a non-allocating request and sending the non-allocating request to a memory endpoint identified by the first request.
4 . The method of claim 1 , further comprising:
pseudo-randomly selecting another of the ways in the N-way set associative cache in response to determining that the cache coherence state of the pseudo-randomly selected way indicates that another request is pending for the pseudo-randomly selected way.
5 . The method of claim 4 , further comprising continuing to pseudo-randomly select another of the ways in the N-way set associative cache until the cache coherence state of the pseudo-randomly selected way does not indicate that another request is pending for the pseudo-randomly selected way.
6 . The method of claim 4 , further comprising continuing to pseudo-randomly select another of the ways in the N-way set associative cache until a threshold number of pseudo-random selections have been performed.
7 . The method of claim 1 , wherein allocating the pseudo-randomly selected way for the first request further comprises updating the cache coherence state of the pseudo-randomly selected way to indicate that the first request is pending for the pseudo-randomly selected way and sending the first request to a memory endpoint identified by the first request.
8 . 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.
9 . The L2 cache subsystem of claim 8 , wherein the L2controller is further configured to service the first request without allocating a line in the L2 cache in response to determining that based on the cache coherence state of the pseudo-randomly selected way indicates that another request is pending for the pseudo-randomly selected way.
10 . The L2 cache subsystem of claim 9 , wherein in response to the L2 controller servicing the first request without allocating a line in the L2 cache, the L2 controller is further configured to convert the first request to a non-allocating request and send the non-allocating request to a memory endpoint identified by the first request.
11 . The L2 cache subsystem of claim 8 , wherein the L2 controller is further configured to pseudo-randomly select another of the ways in the N-way set associative cache in response to determining that the cache coherence state of the pseudo-randomly selected way indicates that another request is pending for the pseudo-randomly selected way.
12 . The L2 cache subsystem of claim 11 , wherein the L2 controller is further configured to continue to pseudo-randomly select another of the ways in the N-way set associative cache until the cache coherence state of the pseudo-randomly selected way does not indicate that another request is pending for the pseudo-randomly selected way.
13 . The L2 cache subsystem of claim 11 , wherein the L2 controller is further configured to continue to pseudo-randomly select another of the ways in the N-way set associative cache until a threshold number of pseudo-random selections have been performed.
14 . The L2 cache subsystem of claim 8 , wherein in response to the L 2 controller allocating the pseudo-randomly selected way for the first request, the L2 controller is further configured to update the cache coherence state of the pseudo-randomly selected way to indicate that the first request is pending for the pseudo-randomly selected way and send the first request to a memory endpoint identified by the first request.
15 . 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.
16 . The system of claim 15 , wherein the first portion and the second portion collectively further indicate an available for new allocations state or an unavailable for new allocations state of the line.
17 . The system of claim 16 , wherein the first portion of the value for each line includes a 2-bit value, and wherein the second portion includes a 1-bit value.
18 . The system of claim 17 , wherein the first portion and the second portion of the value for each line collectively indicate the state of the line as:
the invalid state based on the first portion and the second portion collectively being equal to 000;
the pending state based on the first portion and the second portion collectively being equal to 001;
the shared state and the available for new allocations state based on the first portion and the second portion collectively being equal to 010;
the shared state and the unavailable for new allocations state based on the first portion and the second portion collectively being equal to 011;
the exclusive state and the available for new allocations state based on the first portion and the second portion collectively being equal to 100;
the exclusive state and the unavailable for new allocations state based on the first portion and the second portion collectively being equal to 101;
the modified state and the available for new allocations state based on the first portion and the second portion collectively being equal to 110; and
the modified state and the unavailable for new allocations state based on the first portion and the second portion collectively being equal to 111.
19 . The system of claim 15 , wherein the controller is configured to:
in response to determining that none of the lines has the invalid state:
mask a first subset of the lines having the pending state to determine a second subset of the lines that does not have the pending state;
pseudo-randomly select the one of the lines out of the second subset of lines; and
allocate the pseudo-randomly selected line to the request in response to pseudo-randomly selecting the one of the lines out of the second subset of lines.
20 . The system of claim 19 , wherein the controller is configured to:
service the request without allocating a line in the cache to the request in response to determining that the second subset of the lines is empty.