METHODS FOR MIGRATING DATA TO AVOID READ DISTURBANCE AND APPARATUSES USING THE SAME

Abstract

A method for migrating data to avoid read disturbance is introduced to contain the following steps: obtaining first read counts corresponding to physical blocks from a first read-count table; obtaining second read counts corresponding to the physical blocks from a second read-count table; subtracting each first read count from one corresponding second read count to generate third read counts; finding a singular physical-block from physical blocks according to the third read counts; performing a test read on data of the i.sup.th physical page of the singular physical-block; determining whether the data of the i.sup.th physical page of the singular physical block has passed the test read; and if so, moving or copying data of the i.sup.th physical page and at least one neighboring physical-page of the singular physical block to an available physical-block.

Claims

1. A method for migrating data to avoid read disturbance, comprising: obtaining a plurality of first read counts corresponding to a plurality of physical blocks from a first read-count table, wherein each first read count indicates a total number of reads of one corresponding physical block in a time period between a first moment and a second moment; obtaining a plurality of second read counts corresponding to the physical blocks from a second read-count table, wherein each second read count indicates a total number of reads of one corresponding physical block in a time period between the second moment and a third moment; subtracting each first read count from one corresponding second read count to generate a plurality of third read counts; finding a singular physical-block from the physical blocks according to the third read counts; performing a test read on data of the i.sup.th physical page of the singular physical-block, wherein i is an integer that is greater than or equal to 0; determining whether the data of the i.sup.th physical page of the singular physical-block has passed the test read; and when the data of the i.sup.th physical page of the singular physical-block has not passed the test read, moving or copying data of the i.sup.th physical page and at least one neighboring physical-page of the singular physical-block to an available physical-block.

2. The method of claim 1, wherein the third read count corresponding to the singular physical-block exceeds a predefined threshold.

3. The method of claim 1, wherein the third read count corresponding to the singular physical-block exceeds a predetermined times of an average of all third read counts.

4. The method of claim 1, wherein the data of the i.sup.th physical page is programmed on a first wordline, the neighboring physical-page is programmed on a second wordline and the first wordline is next to the second wordline.

5. The method of claim 1, wherein the i.sup.th physical page and at least one neighboring physical-page contains the (i1).sup.th physical page to the (i+1).sup.th physical page.

6. The method of claim 1, wherein the i.sup.th physical page and at least one neighboring physical-page contains the (i2).sup.th physical page to the (i+2).sup.th physical page.

7. The method of claim 1, wherein the step for performing a test read on data of the i.sup.th physical page of the singular physical-block comprises: directing an access interface to read the data from the i.sup.th physical page of the singular physical-block and send the data to an ECC (Error Check-and-Correction) unit, the step for determining whether the data of the i.sup.th physical page of the singular physical-block has passed the test read comprises: obtaining a result from the ECC unit; and determining whether the data of the i.sup.th physical page of the singular physical-block has passed the test read according to the result.

8. The method of claim 7, wherein the result indicates an erroneous extent of the data of the i.sup.th physical page of the singular physical-block.

9. The method of claim 8, wherein the result indicates an error level of the data of the i.sup.th physical page of the singular physical-block, the step for determining whether the data of the i.sup.th physical page of the singular physical-block has passed the test read according to the result comprises: determining whether the error level of the data of the i.sup.th physical page of the singular physical-block reaches a predefined level or worse, and the data of the i.sup.th physical page of the singular physical-block has not passed the test read when the error level of the data of the i.sup.th physical page of the singular physical-block reaches the predefined level or worse.

10. The method of claim 8, wherein the result indicates error bits of the data of the physical page of the singular physical-block, the step for determining whether the data of the i.sup.th physical page of the singular physical block has passed the test read according to the result comprises: determining whether the error bits of the data of the i.sup.th physical page of the singular physical-block exceeds a predefined threshold, and the data of the i.sup.th physical page of the singular physical block has not passed the test read when the error bits of the data of the i.sup.th physical page of the singular physical-block exceeds the predefined threshold.

11. An apparatus for migrating data to avoid read disturbance, comprising: a volatile memory storing a first read-count table and a second read-count table; an access interface coupled to a storage unit comprising a plurality of physical blocks; and a processing unit, coupled to the access interface, obtaining a plurality of first read counts corresponding to the physical blocks from the first read-count table, wherein each first read count indicates a total number of reads of one corresponding physical block in a time period between a first moment and a second moment; obtaining a plurality of second read counts corresponding to the physical blocks from the second read-count table, wherein each second read count indicates a total number of reads of one corresponding physical block in a time period between the second moment and a third moment; subtracting each first read count from one corresponding second read count to generate a plurality of third read counts; finding a singular physical-block from the physical blocks according to the third read counts; performing a test read on data of the i.sup.th physical page of the singular physical-block, wherein i is an integer that is greater than or equal to 0; determining whether the data of the i.sup.th physical page of the singular physical block has passed the test read; and when the data of the i.sup.th physical page of the singular physical block has not passed the test read, directing the access interface to move or copy data of the i.sup.th physical page and at least one neighboring physical-page of the singular physical block to an available physical-block.

12. The apparatus of claim 11, wherein the third read count corresponding to the singular physical-block exceeds a predefined threshold.

13. The apparatus of claim 11, wherein the third read count corresponding to the singular physical-block exceeds a predetermined times of an average of all third read counts.

14. The apparatus of claim 11, wherein the data of the i.sup.th physical page is programmed on a first wordline, the neighboring physical-page is programmed on a second wordline and the first wordline is next to the second wordline.

15. The apparatus of claim 11, wherein the i.sup.th physical page and at least one neighboring physical-page contains the (i1).sup.th physical page to the (i+1).sup.th physical page.

16. The apparatus of claim 11, wherein the i.sup.th physical page and at least one neighboring physical-page contains the (i2).sup.th physical page to the (i+2).sup.th physical page.

17. The apparatus of claim 11, comprising: an ECC (Error Check-and-Correction) unit, wherein the processing unit directs the access interface to read the data from the physical page of the singular physical-block and send the data to the ECC unit; obtains a result from the ECC unit; and determines whether the data of the i.sup.th physical page of the singular physical block has passed the test read according to the result.

18. The apparatus of claim 17, wherein the result indicates an erroneous extent of the data of the i.sup.th physical page of the singular physical-block.

19. The apparatus of claim 18, wherein the result indicates an error level of the data of the i.sup.th physical page of the singular physical-block and the processing unit determines whether the error level of the data of the i.sup.th physical page of the singular physical-block reaches a predefined level or worse; and determines that the data of the i.sup.th physical page of the singular physical block has not passed the test read when the error level of the data of the i.sup.th physical page of the singular physical-block reaches the predefined level or worse.

20. The apparatus of claim 18, wherein the result indicates error bits of the data of the i.sup.th physical page of the singular physical-block, and the processing unit determines whether the error bits of the data of the i.sup.th physical page of the singular physical-block exceeds a predefined threshold and determines that the data of the i.sup.th physical page of the singular physical block has not passed the test read when the error bits of the data of the i.sup.th physical page of the singular physical-block exceeds the predefined threshold.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0009] The present invention can be fully understood by reading the subsequent detailed description and examples with references made to the accompanying drawings, wherein:

[0010] FIG. 1 is the system architecture of a flash memory according to an embodiment of the invention.

[0011] FIG. 2 is a schematic diagram illustrating interfaces to storage units of a flash storage according to an embodiment of the invention.

[0012] FIG. 3 is a schematic diagram depicting connections between one access sub-interface and multiple storage sub-units according to an embodiment of the invention.

[0013] FIGS. 4 and 5 are schematic diagrams illustrating projections of data of a read-count table to physical blocks according to an embodiment of the invention.

[0014] FIG. 6 is a flowchart illustrating a method for migrating data to avoid read disturbance according to an embodiment of the invention.

DETAILED DESCRIPTION

[0015] The following description is of the best-contemplated mode of carrying out the invention. This description is made for the purpose of illustrating the general principles of the invention and should not be taken in a limiting sense. The scope of the invention is best determined by reference to the appended claims.

[0016] The present invention will be described with respect to particular embodiments and with reference to certain drawings, but the invention is not limited thereto and is only limited by the claims. It will be further understood that the terms comprises, comprising, includes and/or including, when used herein, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof.

[0017] Use of ordinal terms such as first, second, third, etc., in the claims to modify a claim element does not by itself connote any priority, precedence, or order of one claim element over another or the temporal order in which acts of a method are performed, but are used merely as labels to distinguish one claim element having a certain name from another element having the same name (but for use of the ordinal term) to distinguish the claim elements.

[0018] FIG. 1 is the system architecture of a flash memory according to an embodiment of the invention. The system architecture 10 of the flash memory contains a processing unit 110 configured to write data into a designated address of a storage unit 180, and read data from a designated address thereof. Specifically, the processing unit 110 writes data into a designated address of the storage unit 180 through an access interface 170 and reads data from a designated address thereof through the same interface 170. The processing unit 110 can be implemented in numerous ways, such as with dedicated hardware, or with general-purpose hardware (e.g., a single processor, multiple processors or graphics processing units capable of parallel computations, etc.) that is programmed using microcode or software instructions to perform the functions recited herein. The processing unit 110 fetches instructions from a FIFO (First-In-First-Output) buffer and directs the access interface 170 according to the fetched instructions. The processing unit 110 may contain one or more ALUs (Arithmetic and Logic Units) and bit shifters. The ALU is responsible for performing Boolean operations (such as AND, OR, NOT, NAND, NOR, XOR, XNOR etc.) and also for performing integer addition and subtraction. The bit shifter is responsible for bitwise shifts and rotations. The system architecture 10 uses several electrical signals for coordinating commands and data transfer between the processing unit 110 and the storage unit 180, including data lines, a clock signal and control lines. The data lines are employed to transfer commands, addresses and data to be written and read. The control lines are utilized to issue control signals, such as CE (Chip Enable), ALE (Address Latch Enable), CLE (Command Latch Enable), WE (Write Enable), etc. The access interface 170 may communicate with the storage unit 180 using an SDR (Single Data Rate) protocol or a DDR (Double Data Rate) protocol, such as ONFI (open NAND flash interface), DDR toggle, or others. The processing unit 110 may communicate with the host device 160 through an access interface 150 using a standard protocol, such as USB (Universal Serial Bus), ATA (Advanced Technology Attachment), SATA (Serial ATA), PCI-E (Peripheral Component Interconnect Express) or others.

[0019] The storage unit 180 may contain multiple storage sub-units and each storage sub-unit may be practiced in a single die and use a respective access sub-interface to communicate with the processing unit 110. FIG. 2 is a schematic diagram illustrating interfaces to storage units of a flash storage according to an embodiment of the invention. The flash memory 10 may contain j+1 access sub-interfaces 170_0 to 170_j, where the access sub-interfaces may be referred to as channels, and each access sub-interface connects to i+1 storage sub-units. That is, i+1 storage sub-units may share the same access sub-interface. For example, assume that the flash memory contains 4 channels (j=3) and each channel connects to 4 storage sub-units (i=3): The flash memory 10 has 16 storage sub-units 180_0_0 to 180_j_i in total. The processing unit 110 may direct one of the access sub-interfaces 170_0 to 170_j to program data into the designated storage sub-unit. Each storage sub-unit has an independent CE control signal. That is, it is required to enable a corresponding CE control signal when attempting to perform data programming into a designated storage sub-unit via an associated access sub-interface. It is apparent that any number of channels may be provided in the flash memory 10, and each channel may be associated with any number of storage sub-units, and the invention should not be limited thereto. FIG. 3 is a schematic diagram depicting connections between one access sub-interface and multiple storage sub-units according to an embodiment of the invention. The processing unit 110, through the access sub-interface 170_0, may use independent CE control signals 320_0_0 to 320_0_i to select one of the connected storage sub-units 180_0_0 and 180_0_i, and then program data into the designated location of the selected storage sub-unit via the shared data line 310_0.

[0020] FIGS. 4 and 5 are schematic diagrams illustrating projections of data of a read-count table to physical blocks according to an embodiment of the invention. Memory cells of the storage unit 180 may be segmented into m physical blocks, each physical block may contain n physical pages and data of each physical page may be programmed on p wordline(s). The storage unit 180 may contain 512 physical blocks, each physical block may contain 256 physical pages and data of each physical page may be programmed on one wordline. For example, the storage sub-unit 180_0_0 at least contains the 0.sup.th physical block BL0, the 0.sup.th physical block BL0 at least contains 256 wordlines WL0 to WL255 and each wordline stores data of one page. The system architecture 10 of the flash memory contains a volatile memory 120 to store necessary data in execution, such as variables, data tables, data abstracts, etc.

[0021] Refer to FIG. 4. In some embodiments, the volatile memory 120 stores a read-count table 400 containing m cells and each cell records the total number of reads of a physical block since the last erase. For example, the read-count table 400 contains 512 cells 400_0 to 400_511 and the 0.sup.th cell 400_0 records the total number of reads of the physical block BL0 since the last erase. When a physical block is erased, the value of the corresponding cell is renewed to 0. After a successful booting, the processing unit 110 reads the read-count table 400 from the storage unit 180 through the access interface 170 and stores the read-count table 400 in the volatile memory 120. The read-count table 400 of the volatile memory 120 is updated after data is read from the storage unit 180. Before a system shutdown, the processing unit 110 programs the read-count table 400 of the volatile memory 120 into the storage unit 180 through the access interface 170.

[0022] Refer to FIG. 5. In some other embodiments, the volatile memory 120 may additionally store read-count tables 510 and 530. The read-count table 510 contains m cells and each cell records the total number of reads of a physical block in a period of time between t.sub.0 and t.sub.1. The read-count table 530 contains m cells and each cell records the total number of reads of a physical block in a period of time between t.sub.1 and t.sub.2. For example, the read-count table 510 contains 512 cells 510_0 to 510_511 and the 0.sup.th cell 510_0 records the total number of reads of the physical block BL0 in a period of time between t.sub.0 and t.sub.1. The read-count table 530 contains 512 cells 530_0 to 530_511 and the 0.sup.th cell 530_0 records the total number of reads of the physical block BL0 in a period of time between t.sub.1 and t.sub.2. It should be noted that, since the volatile memory 120 is a scarce resource, the read counts of the read-count tables 400, 510 and 530 are recorded in physical blocks as basic units, rather than in physical pages. Although the embodiments of FIGS. 4 and 5 describe one physical page being programmed into one storage sub-unit, those skilled in the art may realize that one physical page is programmed across multiple storage sub-units and the invention should not be limited thereto.

[0023] FIG. 6 is a flowchart illustrating a method for migrating data to avoid read disturbance according to an embodiment of the invention. The method is performed when the processing unit 110 loads and executes relevant program code. The method is periodically performed, for example, every 10, 20 or 30 minutes. In each iteration, it is attempted to find singular physical-blocks (step S611) and determined whether one or more singular physical-blocks are present (step S613). When one or more singular physical-blocks are present (the Yes path of step S613), it is determined whether read disturbance has happened in the physical pages of the singular physical-block(s) and data of corresponding physical pages affected by the read disturbance is moved/copied to empty pages of an available physical-block (steps S631 to S653). When no singular physical-block is present (the No path of step S613), a predefined time period is counted (step S619). When the predefined time period is reached, the next iteration starts. Refer to FIG. 4. In some embodiments of step S611, the processing unit 110 may determine whether a value (also called a read count) of each cell of the read-count table 400 exceeds a threshold, such as 76800, 51200, 25600 or another value set before leaving the factory. When at least a value of one cell exceeds the threshold, the processing unit 110 determines that the physical blocks associated with the cells are singular physical-blocks. For example, when the value of the cell 400_0 exceeds the threshold, the processing unit 110 determines that the physical block BL0 is a singular physical-block. Refer to FIG. 5. In some other embodiments of step S611, the processing unit 110 subtracts the value (also called the first read count) of the k.sup.th cell of the read-count table 510 from the value (also called the second read count) of the k.sup.th cell of the read-count table 530 and writes the calculated value (also called the third read count) into the k.sup.th cell of a temporary table where k is an arbitrary value between 0 to m1. Subsequently, the processing unit 110 determines whether data disturbance has happened according to the values of the temporary table. In some implementations, it may determine whether any value of the temporary table exceeds a predefined threshold. In some other implementations, it may determine whether any value of the temporary table is far more than an average of all values, for example, whether a value of any cell exceeds a predetermined times (such as, 5 times, 10 times, etc.) of an average of values of all cells. For example, when the value of the 0.sup.th cell of the temporary table exceeds a predefined threshold or a predetermined times of an average of values of all cells, the processing unit 110 determines that the physical block BL0 is a singular physical-block.

[0024] When a singular physical-block is selected (step S631), the variable i is used to control test reads to physical pages of this singular physical-block. Details of test reads to physical pages of the singular physical-block are described as follows: The variable i is initiated as 0 (step S633) and a test read of the 0.sup.th physical page of this singular physical-block is performed (step S635). Subsequently, it is determined whether the 0.sup.th physical page has passed the test read (step S637). In steps S635 and S637, specifically, the processing unit 110 directs the access interface 170 to read the 0.sup.th physical page of this singular physical-block and send the data to the ECC (Error Check-and-Correction) unit 130 and obtains a result that implicitly or explicitly indicates whether the data of the 0.sup.th physical page has passed ECC from the ECC unit 130. The ECC unit 130 may output a message to indicate the erroneous extent of the data of the 0.sup.th physical page of this singular physical-block. The processing unit 110 determines that the data of the 0.sup.th physical page of this singular physical-block has not passed the test read when an error level of the data of the 0.sup.th physical page of this singular physical-block reaches a predefined level or worse, or, when the error bits of the data of the 0.sup.th physical page of this singular physical-block exceeds a predefined threshold. For example, the error level may be a message indicating that the corrected bits of the 0.sup.th physical page of this singular physical-block is high. When the data of the 0.sup.th physical page has passed the test read (the Yes path of step S637), the variable i is increased by one (step S639) and a test read is performed on data of the 1.sup.st (i.e. the next) physical page of this singular physical-block (steps S635 and S637). When the data of the 0.sup.th physical page has not passed the test read (the No path of step S637), the data of the 0.sup.th to the j.sup.th physical pages is moved/copied to empty physical-pages of an available physical-block (step S651), and then, the variable i is set to i+j+1, where j may be a constant of 1 or 2 (step S653). In step S653, specifically, since j is set to 1, the processing unit 110 directs the access interface 170 to move/copy the data of the 0.sup.th to 1.sup.st physical pages of this singular physical-block to empty physical pages of the available physical-block. Since j is set to 2, the processing unit 110 directs the access interface 170 to move/copy the data of the 0.sup.th to 2.sup.nd physical pages of this singular physical-block to empty physical-pages of the available physical-block. It should be understood that, when the data of the 0.sup.th physical page of this singular physical-block has not passed the test read, the processing unit 110 determines that the data of the 1.sup.st physical page of this singular physical-block has a high possibility of being read continuously and excessively to cause data disturbance to happen in the 0.sup.th and 2.sup.nd physical pages of this singular physical-block. If the data of the 1.sup.st physical page is actually read continuously and excessively to cause data disturbance to happen in the 0.sup.th and 2.sup.nd physical pages of this singular physical-block and j is set to 2, the data of the 0.sup.th and 2.sup.nd physical pages affected by the data disturbance can be efficiently moved/copied to the available physical-block once. If the data of the 1.sup.st physical page is not actually read continuously and excessively and j is set to 1, an unnecessary move/copy for the data of the 2.sup.nd physical page is avoided.

[0025] When the variable i is greater than 0, a test read of the i.sup.th physical page of this singular physical-block is performed (step S635). Subsequently, it is determined whether the i.sup.th physical page has passed the test read (step S637). Details of steps S635 and S637 may refer to the aforementioned description and be omitted for brevity. When the data of the i.sup.th physical page has not passed the test read (the No path of step S637), the data of the i-j.sup.th to the i+j.sup.th physical pages is moved/copied to empty physical-pages of the available physical-block (step S651), and then, the variable i is set to i+j+1, where j may be a constant of 1 or 2 (step S653). In step S653, specifically, since j is set to 1, the processing unit 110 directs the access interface 170 to move/copy the data of the (i1).sup.th to (i+1).sup.th physical pages of this singular physical-block to empty physical pages of the available physical-block. Since j is set to 2, the processing unit 110 directs the access interface 170 to move/copy the data of the (i2).sup.th to (i+2).sup.th physical pages of this singular physical-block to empty physical-pages of the available physical-block. It should be noted that each physical block has boundary physical-pages. When ij<0, data of the 0.sup.th to (i+j).sup.th physical pages are moved/copied to empty physical-pages of the available physical-block. When i+j>=n, data of the (ij).sup.th to (n1).sup.th physical pages are moved/copied to empty physical-pages of the available physical-block.

[0026] In each iteration of the test read for a physical page, after the variable i is updated (step S639 or S653), it is determined whether the variable i is greater than or equal to a total number n of physical pages of each physical block (step S615). When the variable i is less than n (the No path of step S615), a test read is performed on data of the (i+1).sup.th or (i+j+1).sup.th (i.e. the next) physical page (steps S635 and S637). When the variable i is greater than or equal to n (the Yes path of step S615), it is determined whether any singular physical-block has not been processed (step S617). When any singular physical-block has not been processed (the Yes path of step S617), the next singular physical-block is selected (step S631). When no singular physical-block needs to be processed (the No path of step S617), the predefined time period is counted (step S619).

[0027] Although the embodiment has been described as having specific elements in FIGS. 1 to 3, it should be noted that additional elements may be included to achieve better performance without departing from the spirit of the invention. While the process flow described in FIG. 6 includes a number of operations that appear to occur in a specific order, it should be apparent that these processes can include more or fewer operations, which can be executed serially or in parallel (e.g., using parallel processors or a multi-threading environment).

[0028] While the invention has been described by way of example and in terms of the preferred embodiments, it should be understood that the invention is not limited to the disclosed embodiments. On the contrary, it is intended to cover various modifications and similar arrangements (as would be apparent to those skilled in the art). Therefore, the scope of the appended claims should be accorded the broadest interpretation so as to encompass all such modifications and similar arrangements.