SSD address table cache management based on probability distribution
Aspects of a storage device including a cache having a logical-to-physical (L2P) mapping table, a scratchpad buffer, and a controller are provided to optimize cache storage of L2P mapping information. A controller receives a random pattern of logical addresses and identifies each logical address within one of multiple probability distributions. Based on a frequency of occurrence of each logical address, the controller stores a control page including the logical address within either a partition of the L2P mapping table which is associated with the corresponding probability distribution, or in the scratchpad buffer. The frequency of occurrence of each logical address is determined based on whether the logical address is within one or more standard deviations from a mean of each probability distribution. As a result, frequently occurring control pages are stored in cache, while infrequently occurring control pages are stored in the scratchpad buffer.
1. A storage device, comprising:
a cache configured to store a plurality of global address table (GAT) pages;
a scratchpad buffer separate from the cache;
a controller configured to receive a random pattern of logical addresses; and
the controller configured to, in response to a miss in the cache, for one of the logical addresses of the random pattern, store a GAT page including the one of the logical addresses in the cache or the scratchpad buffer;
wherein the controller is configured to store the GAT page in a partition of the cache, in response to determining, within a probability distribution, that the one of the logical addresses is within one standard deviation from a mean associated with the probability distribution; and
wherein the controller is configured to store the GAT page in the scratchpad buffer in response to determining, within the probability distribution, that the one of the logical addresses is outside of the one standard deviation from the mean.
2. The storage device of claim 1 , wherein the controller is further configured to identify a second one of the logical addresses of the random pattern within a second probability distribution, and to store a second GAT page including the second one of the logical addresses within a second partition of the cache, the second partition being associated with the second probability distribution.
3. The storage device of claim 2 , wherein the controller is further configured to identify the second one of the logical addresses as being within the second probability distribution in response to the second one of the logical addresses being outside the probability distribution.
4. The storage device of claim 2 ,
wherein the controller is further configured to increase a temperature associated with the probability distribution in response to the one of the logical addresses being within the probability distribution, and
wherein the controller is further configured to decrease the temperature associated with the probability distribution in response to the second one of the logical addresses being identified as being within the second probability distribution.
5. The storage device of claim 1 , wherein the controller is further configured to identify a second one of the logical addresses of the random pattern outside the probability distribution, and to store a second GAT page including the second one of the logical addresses within the scratchpad buffer.
6. The storage device of claim 1 ,
wherein the controller is further configured to store the GAT page in the partition or the scratchpad buffer based on whether the cache is full in response to the one of the logical addresses being within two standard deviations from the mean but not within the one standard deviation from the mean; and
wherein the controller is further configured to store the GAT page in the scratchpad buffer in response to the one of the logical addresses being within at least three standard deviations from the mean but not within the two standard deviations from the mean.
7. The storage device of claim 1 , wherein the controller is further configured to dynamically change a size of the partition based on a range of the probability distribution.
8. The storage device of claim 1 , wherein the controller is further configured to identify a state of the probability distribution as corresponding to one of an inactive state, a ramping state, or an active state.
9. The storage device of claim 8 ,
wherein the controller is further configured to transition the state from the ramping state to the active state in response to a number of logical addresses having been identified as being within the probability distribution; and
wherein the controller is further configured to transition the state from the active state to the inactive state in response to a temperature associated with the probability distribution having decreased below a threshold.
10. A storage device, comprising:
a cache configured to store a plurality of GAT pages;
a scratchpad buffer separate from the cache; and
a controller configured to receive a random pattern of logical addresses;
the controller configured to, in response to a first miss in the cache, for a first logical address of the logical addresses of the random pattern, store a first GAT page including the first logical address in the cache;
the controller configured to, in response to a second miss in the cache, for a second logical address of the logical addresses of the random pattern, store a second GAT page including the second logical address in the cache or the scratchpad buffer;
wherein the controller is configured to store the first GAT page in a first partition of the cache in response to determining, within a first probability distribution, that the first logical address is within one first standard deviation from a first mean associated with the first probability distribution;
wherein the controller is configured to store the second GAT page in a second partition of the cache in response to determining, within a second probability distribution, that the second logical address is within one second standard deviation from a second mean associated with the second probability distribution; and
wherein the controller is configured to store the second GAT page in the scratchpad buffer in response to determining, within the second probability distribution, that the second logical address is outside of the one second standard deviation from the second mean.
11. The storage device of claim 10 ,
wherein the controller is further configured to increase a temperature associated with the first probability distribution in response to the first logical address being within the first probability distribution, and
wherein the controller is further configured to decrease the temperature associated with the first probability distribution in response to the second logical address being within the second probability distribution.
12. The storage device of claim 10 , wherein the controller is further configured to identify a third one of the logical addresses of the random pattern outside the first probability distribution and the second probability distribution, and to store a third GAT page including the third one of the logical addresses within the scratchpad buffer.
13. The storage device of claim 10 , wherein the controller is further configured to dynamically change a first size of the first partition based on a first range of the first probability distribution and to dynamically change a second size of the second partition based on a second range of the second probability distribution.
14. The storage device of claim 10 , wherein the controller is further configured to identify a state of each of the first probability distribution and the second probability distribution as corresponding to one of an inactive state, a ramping state, or an active state.
15. A storage device, comprising:
a cache configured to store a plurality of global address table (GAT) pages;
a scratchpad buffer separate from the cache; and
a controller configured to receive a random pattern of logical addresses;
the controller configured to, in response to a first miss in the cache for a first logical address of the logical addresses of the random pattern, store a first GAT page including the first logical address in the cache or the scratchpad buffer;
the controller configured to, in response to a second miss in the cache for a second logical address of the logical addresses of the random pattern, store a second GAT page including the second logical address in the cache or the scratchpad buffer;
the controller configured to, in response to a third miss in the cache, for a third logical address of the logical addresses of the random pattern, store a third GAT page including the third logical address in the scratchpad buffer;
wherein the controller is configured to store the first GAT page in a first partition of the cache in response to determining, within a first probability distribution, that the first logical address is within one first standard deviation from a first mean associated with the first probability distribution;
wherein the controller is configured to store the second GAT page in a second partition of the cache in response to determining, within a second probability distribution, that the second logical address is within one second standard deviation from a second mean associated with the second probability distribution; and
wherein the controller is configured to store the first GAT page in the scratchpad buffer in response to determining, within the first probability distribution, that the first logical address is outside of the one first standard deviation from the first mean;
wherein the controller is configured to store the second GAT page in the scratchpad buffer in response to determining, within the second probability distribution, that the second logical address is outside of the one second standard deviation from the second mean; and
wherein the controller is configured to store the third GAT page in the scratchpad buffer in response to determining that the third logical address is outside of the first probability distribution and the second probability distribution.
16. The storage device of claim 15 ,
wherein the controller is further configured to increase a temperature associated with the first probability distribution in response to the first logical address being within the first probability distribution, and
wherein the controller is further configured to decrease the temperature associated with the first probability distribution in response to the second logical address being within the second probability distribution and in response to the third logical address being outside the first probability distribution and the second probability distribution.
17. The storage device of claim 15 , wherein the controller is further configured to dynamically change a first size of the first partition based on a first range of the first probability distribution and to dynamically change a second size of the second partition based on a second range of the second probability distribution.