Methods of sketch-based memory management and memory devices utilizing the same

• US 10,379,757 B2
• Filed: 04/07/2017
• Issued: 08/13/2019
• Est. Priority Date: 04/07/2017
• Status: Active Grant

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Micron Technology, Inc.
• Inventors: Bradshaw, Samuel E.
• Primary Examiner(s): Rones, Charles
• Assistant Examiner(s): Dare, Ryan
• Application Number:
  US15/482,288
• Publication Number:
  US 20180293005A1
• Time in Patent Office: 858 Days
• Field of Search: None
• CPC Class Codes: G06F 11/1048 using arrangements adapted for a specific error detection or correction feature
• CPC Class Codes: G06F 12/0207 with multidimensional access, e.g. row/column, matrix
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0653 Monitoring storage devices or systems
• CPC Class Codes: G06F 3/0673 Single storage device

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.

Claims

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.