System and method for prediction of multiple read commands directed to non-sequential data

• US 10,649,776 B2
• Filed: 12/19/2018
• Issued: 05/12/2020
• Est. Priority Date: 06/29/2018
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Navon, Ariel, Sharon, Eran, Alrod, Idan
• Primary Examiner(s): Shyu, Jing-Yih
• Application Number:
  US16/226,021
• Publication Number:
  US 20200004540A1
• Time in Patent Office: 510 Days
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 2212/1021 Hit rate improvement
• CPC Class Codes: G06F 2212/1024 Latency reduction
• CPC Class Codes: G06F 2212/6024 History based prefetching
• CPC Class Codes: G06F 2212/7203 Temporary buffering, e.g. using volatile buffer or dedicated buffer blocks
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0683 Plurality of storage devices
• CPC Class Codes: G06F 9/355 Indexed addressing
• CPC Class Codes: G06F 9/3832 Value prediction for operands; operand history buffers
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

Systems and methods for predicting read commands and pre-fetching data when a memory device is receiving random read commands to non-sequentially addressed data locations are disclosed. A limited length search sequence of prior read commands is generated and that search sequence is then converted into an index value in a predetermined set of index values. A history pattern match table having entries indexed to that predetermined set of index values contains a plurality of read commands that have previously followed the search sequence represented by the index value. The index value is obtained via application of a many-to-one algorithm to the search sequence. The index value obtained from the search sequence may be used to find, and pre-fetch data for, a plurality of next read commands in the table that previously followed a search sequence having that index value.

Claims

1. A memory device comprising:

a first memory;

a second memory comprising;

a search sequence buffer; and

a prior read command data structure having a plurality of entries representing a read command history of the memory device; and

a controller in communication with the first memory and the second memory, the controller configured to;

receive a current read command comprising read command data including a start logical block address (LBA) and a data length, wherein the start LBA of the current read command is discontiguous with an address range associated with a last read command received prior to the current read command;

generate a search sequence in the search sequence buffer based on at least the current read command, wherein the search sequence comprises the current read command and at least one read command received prior to the current read command;

calculate an index value based on the search sequence;

retrieve, from an entry in the prior read command data structure indexed by the calculated index value, address data for a sequence of historical next read commands with the calculated index value; and

pre-fetch data for the sequence of historical next read commands from the first memory to the second memory based on the retrieved address data.

2. The memory device of claim 1, wherein:

the prior read command data structure comprises only a predetermined number of entries that are each indexed with a respective index value within a predetermined range of index values.

3. The memory device of claim 1, wherein:

the first memory comprises non-volatile memory; and

the second memory comprises volatile memory.

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

5. The memory device of claim 1, wherein the search sequence comprises:

the start LBA of the current read command; and

a respective start LBA. of each of a predetermined number of prior read commands arranged chronologically in order of read command receipt at the controller.

6. The memory device of claim 1, wherein:

the search sequence comprises a list, arranged chronologically by time of read receipt at the controller, of differential logical block address (DLBA) information for the current read command and each other of a predetermined number of prior read commands; and

each DLBA comprises a difference between a start LBA of a respective read command and a start LBA of a last read command received prior to the respective read command.

7. The memory device of claim 1, further comprising a read command counter, wherein the controller, to pre-fetch the data for the sequence of historical next read commands, is further configured to reset the read command counter equal to a number of historical next read commands in the sequence of historical next read commands associated with the search sequence that have been pre-fetched.

8. The memory device of claim 7, wherein the controller is further configured to, responsive to a next read command being received after pre-fetching the sequence of historical next read commands associated with the search sequence:

determine whether the received next read command is directed to pre-fetched data for one of the sequence of historical next read commands associated with the search sequence; and

responsive to the received next read command not being directed to the pre-fetched data, initiate a new pre-fetch operation for a new sequence of historical next read commands associated with a new search sequence.

9. The memory device of claim 8, wherein the controller is further configured to:

responsive to the received next read command being directed to the pre-fetched data, provide the pre-fetched data associated with the received next read command to a host and change a value of the read command counter; and

responsive to the value of the read command counter indicating that all of the pre-fetched data for the sequence of historical next read commands associated with the search sequence have been processed, initiate the new pre-fetch operation for the new sequence of historical next read commands associated with the new search sequence.

10. A method for predicting multiple random read commands, the method comprising:

receiving, at a memory device, a current read command for data located at a starting address discontiguous with an address range associated with a last read command received prior to the current read command;

generating, with a controller of the memory device, a search sequence comprising a predetermined plurality of prior read commands including at least the current read command and the last read command, wherein generating the search sequence comprises storing a start logical block address (LBA) for each of the predetermined plurality of prior read commands, arranged chronologically in order of read command receipt at the controller, in a search sequence buffer in the memory device;

calculating, with the controller, based on the search sequence, an index value within a predetermined range of index values, the calculated index value representative of the search sequence, wherein calculating the index value comprises;

applying a value of the search sequence as input for a many-to-one mapping operation and,

processing a result of the many-to-one mapping operation with a modulo operation having an output limited to index values in the predetermined range of index values;

retrieving, from an entry in a prior read command data structure stored in a first memory of the memory device and indexed by the calculated index value, data representative of a predetermined plurality of historical next read commands associated with the calculated index value; and

pre-fetching data for each of the predetermined plurality of historical next read commands from a second memory of the memory device to the first memory of the memory device based on the retrieved data representative of the predetermined plurality of historical next read commands associated with the calculated index value.

11. The method of claim 10, wherein many-to-one mapping operation comprises a hash function.

12. The method of claim 10, wherein:

generating the search sequence comprises storing a differential logical block address (DLBA) for each of the predetermined plurality of prior read commands, arranged chronologically in order of read command receipt at the controller, in a search sequence buffer in the memory device, wherein each DLBA comprises a difference between a start logical block address (LBA) of a respective read command and a start LBA of a last read command received prior to the respective read command; and

calculating the index value comprises;

applying a value of the search sequence as input for a many-to-one mapping operation; and

processing a result of the many-to-one mapping operation with a modulo operation having an output limited to index values in the predetermined range of index values.

13. The method of claim 12, further comprising the controller, after pre-fetching the data for each of the predetermined plurality of historical next read commands:

receiving a next read command; and

responsive to the next read command not g directed to the pre-fetched data, initiating a new pre-fetch operation for a new predetermined plurality of historical next read commands associated with a new search sequence.

14. The method of claim 13, further comprising the controller:

responsive to the received next read command being directed to the pre-fetched data;

providing the pre-fetched data associated with the received next read command to a host; and

changing a value of a read command counter in the first memory, the read command counter representative of a number of the sequence of historical read commands that have been processed; and

responsive to the value of the read command counter indicating that all of the pre-fetched data for the predetermined plurality of historical next read commands associated with the search sequence has been processed, initiating the new pre-fetch operation for the new predetermined plurality of historical next read commands associated with the new search sequence.

15. The method of claim 10, further comprising the controller:

receiving next read commands; and

responsive to an order of the next read commands not matching an order of the pre-fetched data for the plurality of historical next read commands, initiating a new pre-fetch operation for a new predetermined plurality of historical next read commands.

16. The method of claim 10, further comprising the controller, after pre-fetching the data for each of the predetermined plurality of historical next read commands:

receiving next read commands; and

responsive to at least two consecutive next read commands not matching any of the pre-fetched data;

discarding the pre-fetched data; and

initiating a new pre-fetch operation for a new predetermined plurality of historical next read commands associated with a new search sequence.

17. The method of claim 10, further comprising:

calculating, with the controller, based on the search sequence, a uniqueness value for the search sequence; and

retrieving the data representative of the predetermined plurality of historical next read commands associated with the calculated index value only responsive to the calculated uniqueness value matching a stored uniqueness value in the entry of the prior read command data structure indexed by the calculated index value.

18. The method of claim 17, wherein:

calculating the index value comprises applying a hash function to the search sequence; and

calculating the uniqueness value comprises applying a cyclic redundancy check function to the search sequence.

19. A memory device comprising:

a first memory;

a second memory comprising;

a search sequence buffer; and

a prior read command data structure having a plurality of entries representing a read command history of the memory device;

means for receiving a current read command comprising read command data including a start logical block address (LBA) and a data length, wherein the start LBA of the current read command is discontiguous with an address range associated with a last read command received prior to the current read command;

means for generating a search sequence in the search sequence buffer based on at least the current read command, wherein the search sequence comprises the current read command and at least one read command received prior to the current read command;

means for calculating an index value based on the search sequence;

means for retrieving from an entry of a prior read command data structure indexed by the calculated index value address data for a sequence of historical next read commands with the calculated index value; and

means for pre-fetching data for the sequence of historical next read commands from the first memory to the second memory based on the retrieved address data.