Methods of sketch-based memory management and memory devices utilizing the same
A memory device having a memory array with a plurality of memory addresses 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 of the d rows corresponds to a different one of d hash functions. The controller is also configured to detect an event associated with a first memory address of the plurality of memory addresses and to hash the first memory address with each of the d hash functions to generate a corresponding d sketch locations. The controller is further configured to adjust, for each of the d sketch locations, a stored sketch value by a first amount corresponding to the event.
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 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, and
adjust, for each of the d sketch locations, a stored sketch value by a first amount corresponding to the event,
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 controller is further 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, and
perform, if the threshold value has been reached, a responsive operation at the first memory address.
7. The memory device of claim 6 , wherein the summary metric is one of: a minimum value, a maximum value, a median value, or a mean value.
8. The memory device of claim 6 , 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 8 , wherein the second amount is equal to a lower one of the summary metric and the stored sketch value.
10. The memory device of claim 6 , wherein the responsive operation is one of an error correction operation, a wear leveling operation, and a copy-and-erase operation.
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 first memory address is a first memory cell of the memory array, and wherein the event is a write operation to a second memory cell of the memory array.
13. The memory device of claim 12 , wherein the first amount corresponds to a distance between the first memory cell and the second memory cell.
14. 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 sketch.