System and method for prediction of read commands to non-sequential data
First Claim
1. A method for predicting 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 plurality of prior read commands including at least the current read command and the last read command;
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;
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 historical next read command associated with the calculated index value; and
pre-fetching data from a second memory of the memory device to the first memory of the memory device based on the retrieved data representative of the historical next read command.
7 Assignments
0 Petitions
Accused Products
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 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 prior 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 next read command in the table that previously followed a search sequence having that index.
-
Citations
20 Claims
-
1. A method for predicting 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 plurality of prior read commands including at least the current read command and the last read command; 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; 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 historical next read command associated with the calculated index value; and pre-fetching data from a second memory of the memory device to the first memory of the memory device based on the retrieved data representative of the historical next read command. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A memory device comprising:
-
a first memory; a second memory comprising; a search sequence buffer; and a prior read command data structure, the prior read command data structure having only a predetermined number of entries that are each indexed with a respective index value within a predetermined range of index values; 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, where 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 read command data from a plurality of prior read commands including at least the current read command and the last read command; calculate an index value, based on the search sequence, within the predetermined range of index values; retrieve, from an entry in the prior read command data structure indexed by the calculated index value, data representative of a historical next read command associated with the calculated index value; and pre-fetch data from the first memory to the second memory based on the retrieved data representative of the historical next read command. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19)
-
-
20. A memory device comprising:
-
a first memory; a second memory; means for updating a prior read command data structure of prior next read commands in the second memory by; calculating, from a sequence of read commands preceding a current read command, one of a plurality of predetermined index values; and storing read command data for the current read command in an entry of the prior read command data structure indexed by the one of the plurality of predetermined index values; and means for predicting and pre-fetching data for a next read command by; calculating an index value of the plurality of predetermined index values from a search sequence of prior received read commands; and retrieving read command data from a historical next read command in an entry of the prior read command data structure indexed to the calculated index value.
-
Specification