Methods of bit-flagged sketch-based memory management and memory devices utilizing the same
View Patent ↗A memory device having a memory array and a controller operably coupled to the memory array is described. The controller is configured to store a sketch comprising d rows and w columns, wherein d and w are positive integers. Each row corresponds to a different one of d hash functions. The controller is also configured to detect an event associated with a memory address and to hash the memory address with each of the d hash functions to generate a corresponding d sketch locations. The controller is further configured, for each of the d sketch locations, to set a detection window flag, if it is not already set, and to adjust a stored sketch value by an amount corresponding to the event. The controller is also configured to evaluate a summary metric corresponding to the stored sketch value in each of the d sketch locations to determine if a threshold value has been reached.
1. A memory device, comprising:
a memory array comprising a plurality of memory addresses, and
a controller operably coupled to the memory array and configured to:
store a sketch comprising d rows and w columns, wherein d and w are positive integers, and wherein each of the d rows corresponds to a different one of d hash functions,
detect, during a detection window, an event associated with a first memory address of the plurality of memory addresses,
hash the first memory address with each of the d hash functions to generate a corresponding d sketch locations,
set, for each of the d sketch locations, a detection window flag, if the detection window flag is not already set,
adjust, for each of the d sketch locations, a stored sketch value by a first amount corresponding to the event, and
evaluate a summary metric corresponding to the stored sketch value in each of the d sketch locations to determine if a threshold value has been reached,
wherein the integer w corresponds to an estimation error factor £ of the sketch according to the equation w=┌e/ε┐, wherein the integer d corresponds to an estimation error probability δ of the sketch according to the equation d=┌ ln 1/δ┐, such that an estimation of the sketch is within the factor ε of a correct value with probability δ.
2. The memory device of claim 1 , further comprising a static random access memory (SRAM), and wherein the controller is configured to store the sketch in the SRAM.
3. The memory device of claim 1 , wherein the plurality of memory addresses includes a number of memory addresses greater than d×w.
4. The memory device of claim 1 , wherein the d sketch locations include one location for each of the d rows.
5. The memory device of claim 1 , wherein each of the d hash functions has a unique hash seed.
6. The memory device of claim 1 , wherein the summary metric is one of: a minimum value, a maximum value, a median value, or a mean value.
7. The memory device of claim 1 , wherein the controller is further configured to:
perform, if the threshold value has been reached, a responsive operation at the first memory address.
8. The memory device of claim 7 , wherein the controller is further configured to:
adjust, for each of the d sketch locations, the stored sketch value by a second amount corresponding to the responsive operation.
9. The memory device of claim 1 , wherein the controller is further configured to:
clear, at the end of the detection window, for each sketch location with an unset detection window flag, the corresponding stored sketch value, and
unset, at the end of the detection window, the detection window flag for each sketch location.
10. The memory device of claim 9 , wherein the controller is further configured to:
begin a new detection window.
11. The memory device of claim 1 , wherein the event is one of: a program operation, an erase operation, a read operation, a disturb event, or an error.
12. The memory device of claim 1 , wherein the sketch is one of: a COUNT sketch, a COUNT-MIN sketch, an AGMS sketch, and a FAST AGMS.