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 method of operating a memory device comprising a memory array, comprising:
storing 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,
detecting an event associated with a first memory address of the memory array,
hashing the first memory address with each of the d hash functions to generate a corresponding d sketch locations,
adjusting, for each of the d sketch locations, a stored sketch value by a first amount corresponding to the event,
evaluating a summary statistic, the summary statistic corresponding to the stored sketch value in every one of the d sketch locations to determine if a threshold value has been reached, and
performing, in response to determining that the threshold value has been reached, a responsive operation at the first memory address,
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 method of claim 1 , further comprising:
adjusting, for each of the d sketch locations, the stored sketch value by a second amount corresponding to the responsive operation.
3. The method of claim 1 , wherein the memory array includes a number of memory addresses greater than d×w.
4. The method of claim 1 , wherein the d sketch locations include one location for each of the d rows.
5. The method of claim 1 , wherein each of the d hash functions has a unique hash seed.
6. The method of claim 1 , wherein the summary statistic is a single value corresponding to the stored sketch value in every one of the d sketch locations, and wherein the summary statistic is one of a minimum, a maximum, a median, a mean, a mode, a sum, or a standard deviation.
7. A memory system, comprising:
a host, and
a memory device operably coupled to the host, the 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,
adjust, for each of the d sketch locations, a stored sketch value by a first amount corresponding to the event,
evaluate a summary statistic, the summary statistic corresponding to the stored sketch value in every one of the d sketch locations to determine if a threshold value has been reached, and
perform, in response to determining that the threshold value has been reached, a responsive operation at the first memory address,
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 δ.
8. The memory system of claim 7 , wherein the controller is configured to perform the responsive operation in response to receiving a responsive operation command from the host.
9. The memory system of claim 8 , wherein the host is configured to issue the responsive operation command in response to the determination that a threshold value has been reached.
10. The memory system of claim 7 , wherein the summary statistic is a single value corresponding to the stored sketch value in every one of the d sketch locations, and wherein the summary statistic is one of a minimum, a maximum, a median, a mean, a mode, a sum, or a standard deviation.