Patent ID: 12229408

DETAILED DESCRIPTION

Embodiments provide a memory system and a read method for improving read performance.

In general, according to an embodiment, a memory system includes a nonvolatile memory and a controller. The controller is configured to determine a first predicted read address as a subsequent read address following an input read address from which data is to be read, based on the input read address and a preset write sequence rule, determine a second predicted read address as the subsequent read address, based on the input read address and a read sequence history, select one of read addresses including the first and second predicted read addresses as a target read address, and read data from the target read address of the nonvolatile memory.

Hereinafter, an embodiment will be described with reference to drawings. The following description illustrates devices and methods for embodying the technical idea of the embodiment, and the technical ideas of the embodiment are not limited to the structure, shape, arrangement, and materials of the elements described below. Modifications that may be easily conceived by those skilled in the art are naturally included in the scope of the disclosure. In order to make the description clearer, in the drawings, the size, thickness, planar dimension, and shape of each element may be changed from the actual embodiment and schematically represented. A plurality of drawings may include elements having different dimensional relationships and ratios to each other. In some drawings, corresponding elements may be denoted by the same reference numerals, and duplicate description may be omitted. Some elements may be given a plurality of names, but these examples of names are merely examples, and it is not denied that these elements are given other names. In addition, it is not denied that other names may be given to the elements which are not given a plurality of names. In the following description, “connection” may include not only direct connection but also connection via other elements.

Hereinafter, the present embodiment will be described in detail with reference to drawings.

FIG.1is a block diagram illustrating an example of an information processing system1including a memory system4according to an embodiment and a host2connectable to the memory system4. The memory system4is a storage device configured to write data to a nonvolatile storage medium, or read data from the nonvolatile storage medium. The memory system4is, for example, a solid state drive (SSD), a universal flash storage (UFS) device, or a memory card. The nonvolatile storage media include, for example, NAND flash memory, NOR flash memory, magneto-resistive random access memory (MRAM), phase change random access memory (PRAM), resistive random access memory (ReRAM), ferroelectric random access memory (FeRAM), and the like. Hereinafter, the memory system4including a NAND memory12as a nonvolatile storage medium will be described.

The host2is an information processing device as an external device that accesses the memory system4. The host2may be a server (storage server) that stores a large amount of various kinds of data in the memory system4. The host2may be a personal computer. The memory system4may be an SSD for business use incorporated in a server such as a data center. The memory system4may be an SSD for personal use incorporated in a personal computer.

The memory system4includes a controller10, the NAND memory12, and a dynamic random access memory (DRAM)14. The memory system4may be used as a main storage for the host2. The memory system4may be built in the host2or may be provided outside the host2and connected to the host2via a cable or network.

The controller10writes data to the NAND memory12or reads data from the NAND memory12according to a request transmitted from the host2. The controller10may be configured with a circuit such as system on a chip (SoC).

The DRAM14is an example of a “volatile memory”. The DRAM14is, for example, a double data rate3low voltage (DDR3L) standard DRAM. The DRAM14operates as a buffer memory that stores data that is supplied from the host2to the memory system4and is being written or is not yet written to the NAND memory12, or data that is read from the NAND memory12and is being transferred or is not yet transferred to the host2. The DRAM14includes an area for storing an address mapping table for defining association between a logical address for the address specified by the host2and a physical address of the NAND memory12, an area for storing the requests received from the host2, an area (referred to as a write buffer) for storing the data that is being written or not yet write to the NAND memory12, and an area (referred to as a read buffer) for storing the data that is being transferred or not yet transferred to the host2after being read from the NAND memory12.

The DRAM14as the volatile memory may be provided inside the controller10instead of being provided outside the controller10. As the volatile memory, instead of the DRAM14, a static random access memory (SRAM) that enables faster access may be used.

The NAND memory12includes a plurality of NAND chips. Each NAND chip includes a memory cell array including a plurality of memory cells disposed in a matrix. The memory cell array may be a two-dimensional memory cell array in which a plurality of memory cells are disposed in a plane, or a three-dimensional memory cell array in which a plurality of memory cells are disposed three-dimensionally. The memory cell array of each NAND chip includes a plurality of blocks. Each block is connected to common word lines.

The controller10includes a CPU20, a host interface (host I/F) circuit22, a NAND interface (NAND I/F) circuit24and a DRAM interface (DRAM I/F) circuit26. The CPU20, the host I/F circuit22, the NAND I/F circuit24, and the DRAM I/F circuit26are connected to a bus line28.

The CPU20executes firmware stored in, for example, the NAND memory12to perform various functions. Various functions are, for example, the execution of host requests transmitted by the host2. Host requests include, for example, host read requests and host write requests.

The host I/F circuit22is electrically connected to the host2, the NAND I/F circuit24is electrically connected to the NAND memory12, and the DRAM I/F circuit26is electrically connected to the DRAM14.

The host I/F circuit22complies with one or more standards such as small computer system interface (SCSI), serial attached SCSI (SAS), AT attachment (ATA), serial ATA (SATA), PCI Express (PCIe™), Ethernet™, Fibre Channel™, NVM Express (NVMe™), Universal Serial Bus (USB™), universal asynchronous receiver/transmitter (UART™), and the like.

The NAND I/F circuit24complies with one or more standards such as Toggle DDR and Open NAND Flash Interface (ONFI).

FIG.2is a functional block diagram illustrating an example of functions of the CPU20. The CPU20includes an address prediction unit32, a read request generation unit34, and a read data output unit36. The address prediction unit32, the read request generation unit34, and the read data output unit36are implemented by the CPU20executing the firmware stored in the NAND memory12.

The DRAM14includes a read address memory40, a write address memory42, and a read buffer44. The read address memory40and write address memory42are connected to the address prediction unit32. The read address memory40is connected to the read request generation unit34. The read buffer44is connected to the read data output unit36.

The read address memory40stores a plurality of read addresses (may be referred to as read sequence history) transmitted from the read request generation unit34.

The write address memory42stores write order data representing the order of writing write data to a plurality of NAND chips of the NAND memory12. The memory system4stores preset write order data so that write data is written to the plurality of NAND chips in a specific order during writing. The write order data is set in accordance with the design specifications of the memory system4. For example, the write order data represents ascending order of a chip1, a chip2, a chip3, . . . , a chip N, descending order of the chip N, the chip (N−1), . . . , the chip2, the chip1, or discrete order of the chip1, the chip3, the chip5, . . . , the chip2, the chip4, . . . , the chip (N−2).

The read address stored in the read address memory40and the write order data stored in the write address memory42are written to the NAND memory12and made nonvolatile when the power of the memory system4is shut down. The read address and write order data written in the NAND memory12are loaded to the DRAM14after the power of the memory system4is turned on.

When the host2transmits a host read request to the memory system4and the host I/F circuit22receives the host read request, the CPU20converts a logical address for the address specified in the host read request into a physical address by using the address mapping table. The physical address (hereinafter, referred to as an input address) is input to the address prediction unit32, the read request generation unit34, and the read data output unit36. An example of the logical address is an address in unit of a plurality of consecutive addresses specified by the host2. The physical address represents a physical storage location in the NAND memory12.

The address prediction unit32determines two predicted addresses from the input address according to two prediction methods based on the read address stored in the read address memory40and the write order data stored in the write address memory42.

The address prediction unit32uses the input address and the predicted address to calculate a hit ratio indicating whether or not the prediction for the predicted address is correct. The address prediction unit32transmits the predicted address and hit ratio to the read request generation unit34and the read data output unit36.

The read request generation unit34generates a read request based on the input address, the predicted address, and the hit ratio. The read request generation unit34transmits the generated read request to the NAND I/F circuit24and also transmits the read address for the generated read request to the read address memory40. The read address memory40stores a plurality of read addresses for a plurality of read requests transmitted to the NAND memory12in order of transmission.

The storage capacity of the read address memory40is predetermined and fixed. When the free storage capacity of the read address memory40becomes 0, the oldest read address is overwritten with a new read address.

The NAND I/F circuit24transmits a read request to the NAND memory12. The NAND I/F circuit24receives read data from the NAND memory12in response to the read request. The read data from the NAND memory12is written to the read buffer44.

The read data output unit36reads read data from the read buffer44and transmits the read data to the host I/F circuit22. The host I/F circuit22transmits the read data to the host2.

FIG.3is a diagram illustrating an example of the read address memory40. The physical address of the NAND memory12includes a chip number identifying a NAND chip, a block number identifying a block, and a word line address identifying a word line. The read address may also include a chip number, a block number, and a word line address.

The read address memory40stores chip numbers and read addresses including word line addresses. The number of word lines is very large compared to the number of blocks. For that reason, when predicting a read address, a word line address is important, but a block number is relatively not important. In order to reduce the size of data to be stored, the read address memory40does not store block numbers.

The address prediction unit32determines a predicted address from an input address according to a chip number and a change pattern of a word line address. When determining the predicted address, the address prediction unit32assumes that a block number is the same as the block number at a previous read request.

Further, in order to save storage capacity, the read address memory40does not store a word line address itself, but stores a word line address as a difference from the word line address for the previous read request. In this case, for example, the word line address itself of a first entry in the read address memory may be stored.

FIG.4is a block diagram illustrating an example of operations of the address prediction unit32, the read request generation unit34, and the read data output unit36.

The address prediction unit32includes a delay device50, a first predicted address determination unit52a, a second predicted address determination unit52b, a first selector54, a first hit ratio calculation unit56a, a second hit ratio calculation unit56b, delay devices58aand58b, and a hit ratio comparison unit60.

The delay device50stores the input address for one read request. When the input address for the next read request is input to the delay device50while the input address for the one read request is stored in the delay device50, the delay device50stores the input address for the next read request in place of the input address for the one read request. The input address for an n-th (n is a positive integer) read request is input to the first hit ratio calculation unit56aand the second hit ratio calculation unit56b. When the input address for an n-th read request is input to the delay device50, the input address for an (n−1)th read request is input to the first predicted address determination unit52aand the second predicted address determination unit52b.

The first predicted address determination unit52ais connected to the write address memory42. The first predicted address determination unit52adetermines a first predicted address based on the (n+1)th read request based on an n-th input address and the write order data. For example, when the write order data indicates writing data to different chips in ascending order of the chip1, the chip2, the chip3, . . . , and chip N, and the input address indicates a word line address1of the chip1, the first predicted address indicates a word line address1of the chip2.

The first predicted address determination unit52atransmits the first predicted address to a first input terminal54aof the first selector54and the first hit ratio calculation unit56a.

The second predicted address determination unit52bis connected to the read address memory40. The second predicted address determination unit52bdynamically predicts an address during a read operation according to a change pattern of the read address. For example, the second predicted address determination unit52bincludes a memory that stores a plurality of input addresses for a plurality of the most recent read requests (for example, four times). The second predicted address determination unit52bdetermines a second predicted address based on the (n+1)th read request based on the change pattern of the input address for an (n−3)th read request, the input address for an (n−2)th read request, the input address for an (n−1)th read request, and the input address for the n-th read request. For example, the second predicted address determination unit52bsubsequently compares the change pattern of four input addresses for the (n−3)th to n-th read requests with an address group that is stored in the read address memory40and includes four read addresses. For example, as shown inFIG.3, when n is index=12, the second predicted address determination unit52bdetermines whether an address group102having a change pattern matching the change pattern of four input addresses whose indexes=9 to 12 exists in the read address memory40. If any, the second predicted address determination unit52bsets a read address104with index=13, which follows the address group102, as the second predicted address.

The second predicted address determination unit52btransmits the second predicted address to a second input terminal54bof the first selector54and the second hit ratio calculation unit56b.

The first hit ratio calculation unit56auses the input address and the first predicted address to calculate a first hit ratio r1of the first predicted address. The first hit ratio calculation unit56acompares the input address and the first predicted address, and determines whether or not the input address and the first predicted address match (prediction is correct). The first hit ratio calculation unit56aincludes a memory that stores a plurality of the most recent determination results (for example, four times). The first hit ratio r1is the average value of the plurality of determination results, and indicates the ratio that prediction of the first predicted address is correct to the plurality of determination results. The first hit ratio r1may be calculated by (the number of correctly predicted read requests)/(the total number of read requests). Instead of the calculation, the hit ratio may be obtained from the number of consecutive read requests for which the read prediction is correct. For example, when the input address and the first predicted address match, the determination result may be set to 100%, when the input address and the first predicted address do not match, the determination result may be set to 0%, and when the prediction of the four consecutive read requests is correct, the first hit ratio may be set to 100%.

The first hit ratio r1is input to the hit ratio comparison unit60and the read data output unit36via the delay device58a. The delay device58astores the first hit ratio r1of the first predicted address based on one read request. When the first hit ratio r1of the first predicted address based on the one read request is stored in the delay device58a, if the first hit ratio r1of the first predicted address based on the next read request is input to the delay device58a, the delay device58astores the first hit ratio r1of the first predicted address based on the next read request in place of the first hit ratio r1of the first predicted address based on the one read request.

The second hit ratio calculation unit56buses the input address and the second predicted address to calculate a second hit ratio r2of the second predicted address. The second hit ratio calculation unit56bcompares the input address and the second predicted address, and determines whether or not the input address and the second predicted address match (prediction is correct). The second hit ratio calculation unit56bincludes a memory that stores a plurality of the most recent determination results (for example, four times). The second hit ratio r2is the average value of the plurality of determination results, and indicates the ratio that prediction of the second predicted address is correct to the plurality of determination results. The second hit ratio r2may be calculated by (the number of correctly predicted read requests)/(the total number of read requests). Instead of the calculation, the hit ratio may be obtained from the number of consecutive read requests for which the read prediction is correct. For example, when the input address and the second predicted address match, the determination result may be 100%, when the input address and the second predicted address do not match, the determination result may be 0%, and when the prediction of the four consecutive read requests is correct, the second hit ratio may be 100%.

The second hit ratio r2is input to the hit ratio comparison unit60and the read data output unit36via the delay device58b. The delay device58bstores the second hit ratio r2of the second predicted address based on one read request. When the second hit ratio r2of the second predicted address based on the one read request is stored in the delay device58b, if the second hit ratio r2of the second predicted address based on the next read request is input to the delay device58b, the delay device58bstores the second hit ratio r2of the second predicted address based on the next read request in place of the second hit ratio r2of the second predicted address based on the one read request.

The hit ratio comparison unit60compares the first hit ratio r1and the second hit ratio r2. The hit ratio comparison unit60outputs a selection signal corresponding to the comparison result to the first selector54. When the first hit ratio r1is higher than the second hit ratio r2, the hit ratio comparison unit60causes the first selector54to select the first input terminal54a. When the first hit ratio r1is not higher than the second hit ratio r2, the hit ratio comparison unit60causes the first selector54to select the second input terminal54b. The first selector54outputs an output signal according to the input selection signal. The output signal of the first selector54is transmitted to the read request generation unit34and the read data output unit36.

The read request generation unit34includes a first read request generation unit34aand a second read request generation unit34b.

The read buffer44includes a first read buffer44aand a second read buffer44b.

The input address is further input to the first read request generation unit34a. The first read request generation unit34auses the input address to generate a first read request, and transmits the first read request to the NAND I/F circuit24based on the signal from the read data output unit36. The first read request is issued after receiving the input address. Reading in response to the first read request is executed after receiving the input address, and is also referred to as normal read.

The NAND I/F circuit24transmits the first read request to the NAND memory12. The read data read from the NAND memory12in response to the first read request is written to the first read buffer44a.

A predicted address (first predicted address or second predicted address) output from the first selector54is input to the second read request generation unit34b. The second read request generation unit34buses the predicted address to generate a second read request, and transmits the second read request to the NAND I/F circuit24based on the signal from the read data output unit36. The second read request is issued before the input address is received. The read in response to the second read request is executed before the input address is received, which is also referred to as read-ahead.

The NAND I/F circuit24transmits the second read request to the NAND memory12. The read data read from the NAND memory12in response to the second read request is written to the second read buffer44b.

The read data output unit36includes a second selector70, a third selector72, an address comparison unit74, and a read-ahead possibility determination unit76. The read data stored in the first read buffer44a is transmitted to a first input terminal70aof the second selector70and a first input terminal72aof the third selector72. The read data stored in the second read buffer44bis transmitted to a second input terminal70bof the second selector70.

The input address and one of the first predicted address and the second predicted address output from the first selector54are input to the address comparison unit74. The address comparison unit74determines whether or not the input address matches the one of the first predicted address and the second predicted address. The address comparison unit74transmits a comparison signal representing the determination result to the second selector70and the first read request generation unit34a.

The second selector70selects the first input terminal70aand the second input terminal70bin response to the comparison signal. The second selector70selects the second input terminal70baccording to a comparison signal indicating that the input address matches the first predicted address or the second predicted address. The second selector70selects the first input terminal70aaccording to a comparison signal indicating that the input address is not equal to the first predicted address or the second predicted address.

The first hit ratio r1output from the delay device58aand the second hit ratio r2output from the delay device58bare input to the read-ahead possibility determination unit76. A read-ahead threshold value th is also input to the read-ahead possibility determination unit76. The read-ahead possibility determination unit76determines whether or not read-ahead is to be carried out by determining whether or not the maximum value (that is, the greater one) of the first hit ratio r1and the second hit ratio r2is equal to or greater than the read-ahead threshold value th. The read-ahead possibility determination unit76transmits a possible/not possible signal indicating the determination result to the third selector72, the first read request generation unit34a, and the second read request generation unit34b.

The third selector72selects the first input terminal72aor a second input terminal72baccording to the possible/not possible signal. The third selector72selects the second input terminal72bin response to a possible/not possible signal indicating that the larger one of the first hit ratio r1and the second hit ratio r2is equal to or greater than the read-ahead threshold value th (read-ahead is enabled). The third selector72selects the first input terminal72ain response to a possible/not possible signal indicating that the larger one of the first hit ratio r1and the second hit ratio r2is less than the read-ahead threshold value th (read-ahead is not possible).

When the possible/not possible signal indicates that read-ahead is not possible, or when the possible/not possible signal indicates that read-ahead is possible and the predicted address does not match the input address, the first read request generation unit34atransmits the first read request to the NAND I/F circuit24. When the possible/not possible signal indicates that read-ahead is possible, the second read request generation unit34btransmits the second read request to the NAND I/F circuit24.

FIG.5is a flowchart illustrating an example of processing of the controller10.

The processing inFIG.5is started before the CPU20transmits the input address to the address prediction unit32, the read request generation unit34, and the read data output unit36. It is assumed that the input address is the input address for the (n+1)th read request.

The first predicted address determination unit52adetermines a read address (a first predicted address) for the (n+1)th read request (S104) based on the input address for the n-th read request stored in the delay device50and the write order designated by the write order data stored in the write address memory42.

Based on the input address for the n-th read request and the read address stored in the read address memory40, the second predicted address determination unit52bdetermines a read address (second predicted address) based on the (n+1)th the read request (S106).

The first hit ratio calculation unit56acalculates the first hit ratio r1by using the input address when the (n+1)th read request is received, and the first predicted address based on the n-th read request. Similarly, the second hit ratio calculation unit56bcalculates the second hit ratio r2by using the input address when the (n+1)th read request is received, and the second predicted address based on the n-th read request.

The read-ahead possibility determination unit76compares a greater one of the hit ratio r1transmitted from the delay device58aand the hit ratio r2transmitted from the delay device58bwith the read-ahead threshold value th to determine whether or not read-ahead is to be carried out (S108). Specifically, the read-ahead possibility determination unit76determines whether or not the greater one of the first hit ratio r1and the second hit ratio r2is greater than the read-ahead threshold value th. The read-ahead possibility determination unit76transmits a possible/not possible signal representing the determination result to the third selector72.

When the greater one of the first hit ratio r1and the second hit ratio r2is greater than the read-ahead threshold value th (YES in S108), the third selector72selects the second input terminal72b(S112). When the greater one of the first hit ratio r1and the second hit ratio r2is not greater than the read-ahead threshold value th (NO in S108), the third selector72selects the first input terminal72a(S114).

After the processing of S112, the hit ratio comparison unit60determines whether or not the first hit ratio r1is greater than the second hit ratio r2(S116). A determination signal representing the determination result is input to the first selector54. The first selector54selects an input terminal based on the determination signal.

When the first hit ratio r1is greater than the second hit ratio r2(YES in S116), the first selector54selects the first input terminal54a(S118). When the first hit ratio r1is not greater than the second hit ratio r2(NO in S116), the first selector54selects the second input terminal54b(S122). As a result, the first predicted address or the second predicted address is input to the second read request generation unit34band the address comparison unit74via the first selector54.

After the processing of S118or S122, the second read request generation unit34buses the first predicted address or the second predicted address to generate a second read request (S124).

The second read request is transmitted to the NAND I/F circuit24. The NAND I/F circuit24transmits the second read request to the NAND memory12. The NAND memory12executes read-ahead based on the predicted address based on the second read request. The read data read by the read-ahead is transmitted from the NAND memory12to the NAND I/F circuit24. The read data is written to the second read buffer44b.

When the (n+1)th input address is input to the address prediction unit32, the address comparison unit74determines whether or not the (n+1)th predicted address used in the read-ahead matches the (n+1)th input address (S126). When the predicted address matches the input address, it may be determined that the read-ahead is successful. When the predicted address does not match the input address, it is possible to determine that the read-ahead is not successful. When it is determined that the read-ahead is not successful, normal read using the input address needs to be executed.

The address comparison unit74transmits the determination signal to the read request generation unit34aand the second selector70. The second selector70selects an input terminal based on the determination signal.

When the (n+1)th predicted address matches the (n+1)th input address (YES in S126), the second selector70selects the second input terminal70b(S128). When the (n+1)th predicted address is not equal to the (n+1)th input address (NO in S126), the second selector70selects the first input terminal70a(S132).

After the processing of S128, the read data output unit36reads the read data from the second read buffer44band outputs the read data via the second input terminal70bof the second selector70and the second input terminal72bof the third selector72(S134). The read data output from the read data output unit36is transmitted to the host2via the host I/F circuit22.

The first hit ratio calculation unit56acalculates (updates) the first hit ratio r1based on the (n+1)th input address and the (n+1)th first predicted address (S136). The second hit ratio calculation unit56bcalculates (updates) the second hit ratio r2based on the (n+1)th input address and the (n+1)th second predicted address (S138). This completes the processing for one input address.

After the processing of S114or S132, the first read request generation unit34auses the input address to generate a first read request (S142).

The first read request is transmitted to the NAND I/F circuit24. The NAND I/F circuit24transmits the first read request to the NAND memory12. The NAND memory12executes normal read based on the input address for the first read request. The read data read by the normal read is transmitted from the NAND memory12to the NAND I/F circuit24. The read data is written to the first read buffer44a.

The read data output unit36reads read data from the first read buffer44aand outputs the read data via the first input terminal72aof the third selector72(S144). The read data output from the read data output unit36is transmitted to the host2via the host I/F circuit22.

After the processing of S144, the processing of S136is executed.

FIG.6is a block diagram illustrating an example of the address prediction unit32and the read data output unit36when executing a normal read operation without executing a read-ahead operation.FIG.6shows the states of the address prediction unit32and the read data output unit36after execution of the processing of S114, S142, and S144in the flowchart ofFIG.5. That is, the read-ahead possibility determination unit76outputs a possible/not possible signal indicating that read-ahead is not possible. The third selector72selects the first input terminal72aaccording to this possible/not possible signal. The first read request generation unit34agenerates a first read request according to this possible/not possible signal. The read data read from the NAND memory12in response to the first read request is written to the first read buffer44a. The read data read from the first read buffer44ais output via the third selector72(first input terminal72a).

FIG.7is a block diagram illustrating an example of the address prediction unit32and the read data output unit36when executing a read-ahead operation.FIG.7shows the states of the address prediction unit32and the read data output unit36after execution of the processing of S112, S118(or S122), S124, S128, and S134in the flowchart ofFIG.5. That is, the read-ahead possibility determination unit76outputs a possible/not possible signal indicating the possibility of read-ahead. The third selector72selects the second input terminal72baccording to this possible/not possible signal. The second read request generation unit34bgenerates a second read request in response to this possible/not possible signal. The read data read from the NAND memory12in response to the second read request is written to the second read buffer44b. The address comparison unit74outputs a comparison signal indicating that the input address matches the predicted address. The second selector70selects the second input terminal70baccording to this comparison signal. The read data read from the second read buffer44bis output via the second selector70(second input terminal70b) and the third selector72(second input terminal72b).

FIG.8is a block diagram illustrating an example of the address prediction unit32and the read data output unit36when normal read is executed after a read-ahead operation does not succeed.FIG.8shows the states of the address prediction unit32and the read data output unit36after execution of the processing of S112, S118(or S122), S124, S132, S142, and S144in the flowchart ofFIG.5. That is, the read-ahead possibility determination unit76outputs a possible/not possible signal indicating the possibility of read-ahead. The third selector72selects the second input terminal72baccording to this possible/not possible signal. The address comparison unit74outputs a comparison signal indicating that the input address and the predicted address do not match. The second selector70selects the first input terminal70aaccording to this comparison signal. The first read request generation unit34agenerates a first read request according to this comparison signal. The read data read from the NAND memory12in response to the first read request is written to the first read buffer44a. The read data read from the first read buffer44ais output via the second selector70(first input terminal70a) and the third selector72(second input terminal72b).

According to the above embodiment, the first predicted address is determined based on the input address and the write order data, and the second predicted address is determined based on the input address and the read addresses for the plurality of the most recent read requests. The first hit ratio is calculated that indicates how much the first predicted address matches the input address. The second hit ratio is calculated that indicates how much the second predicted address matches the input address.

When the greater one of the first hit ratio and the second hit ratio is equal to or greater than the threshold value, a read-ahead operation is executed before the input address is received. A read-ahead request is generated by using a predicted address with a high hit ratio. Therefore, when reading in a case where the read address changes in an order different from the order in which write data is written, since read-ahead is executed by using the second predicted address predicted by using the read address, the read-ahead is highly likely to succeed. Therefore, read performance is improved.

When the read-ahead is not successful, a normal read operation is executed, and therefore the data specified by the input address may be read.

When the greater one of the first hit ratio and the second hit ratio is less than the threshold value, read-ahead is highly likely not to succeed, a read-ahead operation is not executed, and a normal read operation is executed. As a result, the possibility of an unnecessary read-ahead operation being executed is low, and the read performance is improved.

A modification example will be described. The number of predicted addresses is not limited to two, and may be three or more. For example, during a write operation, some write data may be written according to write order data, but the rest of the write addresses may be written without in compliance with the write order data. In this case, the DRAM14includes a second write address memory. The address prediction unit32includes a third predicted address determination unit in parallel with the first predicted address determination unit52aand the second predicted address determination unit52b, a third hit ratio calculation unit in parallel with the first hit ratio calculation unit56aand a second hit ratio calculation unit56b, and a third delay device in parallel with the delay devices58aand58b. A second write address of the write data written not in compliance with the write order data is stored in the second write address memory. The third predicted address determination unit may compare a change pattern of a plurality of input addresses for a plurality of the most recent read requests with a write address group including a plurality of second write addresses to determine a third predicted address.

The address input to the address prediction unit32is described as a physical address, but may be predicted as a logical address.

The read address referred to when the second predicted address determination unit52bdetermines the second predicted address is stored in the read address memory40. A large number of read addresses need to be stored in the read address memory40in order to improve the accuracy of prediction. If the second predicted address determination unit52bis configured to use a time-series data learning algorithm to determine the second predicted addresses, the number of read addresses stored in the read address memory40can be reduced compared to the embodiment. Alternatively, when storing the same number of read addresses, the modification example improves the hit ratio of the second predicted address compared to the embodiment.

An example of obtaining the first hit ratio r1and the second hit ratio r2by a simple average for a certain period is described, but an example of obtaining by an average value of average values for a plurality of periods, an example of calculating by an arithmetic average, and an example of obtaining by a recursive average may be adopted.

While certain embodiments have been described, these embodiments have been presented by way of example only, and are not intended to limit the scope of the disclosure. Indeed, the novel embodiments described herein may be embodied in a variety of other forms; furthermore, various omissions, substitutions, and changes in the form of the embodiments described herein may be made without departing from the spirit of the disclosure. The accompanying claims and their equivalents are intended to cover such forms or modifications as would fall within the scope and spirit of the disclosure.