Methods of sketch-based memory management and memory devices utilizing the same
AssigneeMicron Technology, Inc.
InventorSamuel E. Bradshaw
Life of this patent
Estimating the term…
Abstract
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.
Claims14
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 δ.
Dependencies are inferred from the claim text.