System and method for scaling a historical pattern matching data structure in a memory device

Patent metadata

Field	Value
Publication number	US-10719445-B1
Application number	US-201916288784-A
Country	US
Kind code	B1
Filing date	Feb 28, 2019
Priority date	Feb 28, 2019
Publication date	Jul 21, 2020
Grant date	Jul 21, 2020

Abstract

Systems and methods for permitting flexible use of volatile memory for storing read command prediction data in a memory device, or in a host memory buffer accessible by the memory device, while preserving accuracy in predicting read commands and pre-fetching data are disclosed. The read command prediction data may be in the form of history pattern match table having entries indexed to a search sequence of one or more commands historically preceding the read command in the indexed table entry. A host trigger requesting the limited volatile memory space, a lower power state that is detected, or a memory device-initiated need may trigger generation of and subsequent use of a smaller table for the prediction process while the larger table is released. The memory device may later regenerate the larger table when more space in the volatile memory becomes available.

First claim

We claim:

1. A method for managing pre-fetch prediction information in a memory device, the method comprising:
generating a first prior read command data structure in a memory;
predicting a next read command using the first prior read command data structure based on a current received read command;
in response to a size reduction trigger, generating a second prior read command data structure in the memory based on a portion of content of the first prior read command data structure, wherein the second prior read command data structure is a smaller data structure than the first prior read command data structure; and
after generating the second prior read command data structure, releasing memory space in the memory containing the first prior read command data structure.

2. The method of claim 1 , wherein:
the first prior read command data structure comprises a maximum size corresponding to a first predetermined range of index values; and
the second prior read command data structure comprises a maximum size corresponding a second predetermined range of index values that is smaller than the first predetermined range of index values.

3. The method of claim 2 , further comprising:
after generating the second prior read command data structure:
predicting additional next read commands using the second prior read command data structure; and
updating the second prior read command data structure with actual received read commands.

4. The method of claim 2 , wherein generating the second prior read command data structure comprises copying only a predetermined portion of the first prior read command data structure into a part of the memory of the memory device that differs from a part of the memory containing the first prior read command data structure.

5. The method of claim 4 , wherein the predetermined portion comprises prior read command data from a portion of the first predetermined range of index values equal to a total of the second predetermined range of index values.

6. The method of claim 1 , wherein:
the size reduction trigger comprises a memory device power reduction request; and
generating the second prior read command data structure comprises copying only a predetermined portion of the first prior read command data structure into a persistent memory.

7. The method of claim 6 , further comprising:
after generating the second prior read command data structure:
receiving a power-on trigger; and
in response to receiving the power-on trigger:
copying the second prior read command data structure from the persistent memory to a volatile memory;
predicting next read commands using the second prior read command data structure based on newly received read commands;
updating the second prior read command data structure with the newly received read commands; and
concurrently with updating the second prior read command data structure, regenerating the first prior read command data structure with the newly received read commands.

8. The method of claim 7 , further comprising:
in response to completing regeneration of the first prior read command data structure:
releasing memory space in the memory containing the second prior read command data structure;
predicting a next read command using the first prior read command data structure based on a current received read command;
receiving a second size reduction trigger; and
in response to receiving the second size reduction trigger:
regenerating the second prior read command data structure in the memory of the memory device based on the content of the first prior read command data structure;
releasing memory space in the memory containing the first prior read command data structure after regenerating the second prior read command data structure;
predicting additional next read commands using the second prior read command data structure; and
updating the second prior read command data structure with actual received read commands.

9. The method of claim 1 , wherein generating the first prior read command data structure comprises:
receiving a current read command;
generating an index value, in a first predetermined range of index values, for the current read command based on a search sequence comprising at least a last read command received prior to the current read command; and
storing at least a portion of the current read command in the first prior read command data structure at an entry indexed by the index value.

10. A memory device comprising:
a volatile memory;
a non-volatile memory; and
a controller in communication with the volatile memory and the non-volatile memory, the controller configured to:
receive a read command from a host;
predict a next read command;
pre-fetch data associated with the predicted next read command, using a first data structure stored in the volatile memory based on the received read command; and
in response to a data structure switch trigger:
generate a second data structure in the volatile memory from a portion of content of the first data structure, wherein the second data structure is a smaller data structure than the first data structure;
release memory space in the volatile memory containing the first data structure; and
for subsequently received read commands, predict additional next read commands, and pre-fetch data associated with the predicted additional next read commands, from the second data structure based on the subsequently received read commands.

11. The memory device of claim 10 , wherein the non-volatile memory comprises a substrate formed with a three-dimensional memory structure.

12. The memory device of claim 10 , wherein the controller is further configured to:
in response to an additional data structure switch trigger after generation of the second data structure and release of memory space containing the first data structure:
regenerate the first data structure based on newly received read commands; and
until the first data structure is regenerated to contain a predetermined amount of read command data:
concurrently update the second data structure with the newly received read commands; and
continue to predict additional next read commands and pre-fetch data associated with the predicted additional next read commands only from the second data structure based on the newly received read commands.

13. The memory device of claim 12 , wherein the controller is further configured to:
responsive to the regenerated first data structure containing the predetermined amount of read command data:
release memory space in the non-volatile memory containing the second data structure; and
predict next read commands based on subsequently received read commands only from the first data structure.

14. The memory device of claim 12 , wherein the predetermined amount of read command data comprises a percentage of a maximum space in memory allocated for the first data structure.

15. The memory device of claim 12 , wherein the predetermined amount of read command data comprises a percentage of index values of the first data structure containing read command data.

16. The memory device of claim 10 , wherein:
the first data structure comprises a first table indexed by a first number of index values;
the second data structure comprises a second table indexed by a second number of index values that is less than the first number of index values; and
the portion of content of the first data structure used to generate the second data structure comprises prior read command data in a sequentially numbered group of index values equal to a total of the s

Assignees

• Western Digital Tech Inc

Inventors

• Navon Ariel
• Benisty Shay
• Bazarsky Alex

Classifications

• G06F12/0862 Primary

  with prefetch · CPC title

• G06F12/0804

  with main memory updating (G06F12/0806 takes precedence) · CPC title

• G06F2212/214

  Solid state disk · CPC title

• G06F2212/6024

  History based prefetching · CPC title

• G06F12/0868

  Data transfer between cache memory and other subsystems, e.g. storage devices or host systems · CPC title