Data merge method for rewritable non-volatile memory storage device and memory control circuit unit

• US 10,810,121 B2
• Filed: 01/04/2019
• Issued: 10/20/2020
• Est. Priority Date: 10/25/2018
• Status: Active Grant

• Current Assignee: Phison Electronics Corporation
• Original Assignee: Phison Electronics Corporation
• Inventors: Chen, Chien-Wen, Lin, Ting-Wei
• Primary Examiner(s): Peyton, Tammara R
• Application Number:
  US16/239,535
• Publication Number:
  US 20200133844A1
• Time in Patent Office: 655 Days
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/0638 Combination of memories, e.g. ROM and RAM such as to permit replacement or supplementing of words in one module by words in another module address formation of the next microinstruction G06F9/26; masking faults in memories by using spares or by reconfiguring G11C29/70
• CPC Class Codes: G06F 12/1045 associated with a data cache
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 2212/1036 Life time enhancement
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/0607 by facilitating the process of upgrading existing storage systems, e.g. for improving compatibility between host and storage device
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

A data merge method for a rewritable non-volatile memory module including a plurality of physical units is provided according to an exemplary embodiment of the disclosure. The method includes: obtaining a first logical distance value between a first physical unit and a second physical unit among the physical units, and the first logical distance value reflects a logical dispersion degree between at least one first logical unit mapped by the first physical unit and at least one second logical unit mapped by the second physical unit; and performing a data merge operation according to the first logical distance value, so as to copy valid from a source node to a recycling node.

Claims

1. A data merge method, for a rewritable non-volatile memory module, wherein the rewritable non-volatile memory module comprises a plurality of physical units, the data merge method comprising:

obtaining a first logical distance value between a first physical unit and a second physical unit among the physical units, wherein the first logical distance value reflects a logical dispersion degree between at least one first logical unit mapped by the first physical unit and at least one second logical unit mapped by the second physical unit; and

performing a data merge operation according to the first logical distance value, so as to copy valid data from a source node among the physical units to a recycling node among the physical units,

wherein the step of obtaining the first logical distance value between the first physical unit and the second physical unit among the physical units comprises;

performing a first calculation on a plurality of first bits corresponding a first table mapping information of the first physical unit and a plurality of second bits corresponding a second table mapping information of the second physical unit to obtain at least one third bit; and

obtaining the first logical distance value according to the at least one third bit.

2. The data merge method according to claim 1, wherein logical-to-physical mapping information of the at least one first logical unit is recorded in at least one first logical-to-physical mapping table, logical-to-physical mapping information of the at least one second logical unit is recorded in at least one second logical-to-physical mapping table, and the first logical distance value further reflects an overlapping degree between the at least one first logical-to-physical mapping table and the at least one second logical-to-physical mapping table.

3. The data merge method according to claim 1, wherein the step of performing the data merge operation according to the first logical distance value comprises:

copying valid data in the first physical unit to the recycling node and copying valid data in the second physical unit to the recycling node if the first logical distance value is not larger than a target distance value; and

copying valid data in the first physical unit to the recycling node and copying valid data in a third physical unit among the physical units to the recycling node if the first logical distance value is larger than the target distance value.

4. The data merge method according to claim 3, further comprising:

obtaining a second logical distance value between the first physical unit and the third physical unit, wherein the target distance value comprises the second logical distance value.

5. The data merge method according to claim 1, wherein

the first table mapping information reflects that logical-to-physical mapping information of the at least one first logical unit is recorded in at least one first logical-to-physical mapping table, and the second table mapping information reflects that logical-to-physical mapping information of the at least one second logical unit is recorded in at least one second logical-to-physical mapping table.

6. The data merge method according to claim 5, wherein the first table mapping information comprises a plurality of first values, the second table mapping information comprises a plurality of second values, and the step of obtaining the first logical distance value according to the first table mapping information and the second table mapping information comprises:

obtaining a N-dimensional distance between the first values and the second values; and

obtaining the first logical distance value according to the N-dimensional distance.

7. A memory storage device, comprising:

a connection interface unit, configured to connect a host system;

a rewritable non-volatile memory module which comprises a plurality of physical units; and

a memory control circuit unit, coupled to the connection interface unit and the rewritable non-volatile memory module,

wherein the memory control circuit unit is configured to obtain a first logical distance value between a first physical unit and a second physical unit among the physical units, wherein the first logical distance value reflects a logical dispersion degree between at least one first logical unit mapped by the first physical unit and at least one second logical unit mapped by the second physical unit, and

the memory control circuit unit is further configured to perform a data merge operation according to the first logical distance value, so as to copy valid data from a source node among the physical units to a recycling node among the physical units,

wherein the operation of obtaining the first logical distance value between the first physical unit and the second physical unit among the physical units by the memory control circuit unit comprises;

performing a first calculation on a plurality of first bits corresponding a first table mapping information of the first physical unit and a plurality of second bits corresponding a second table mapping information of the second physical unit to obtain at least one third bit; and

obtaining the first logical distance value according to the at least one third bit.

8. The memory storage device according to claim 7, wherein logical-to-physical mapping information of the at least one first logical unit is recorded in at least one first logical-to-physical mapping table, logical-to-physical mapping information of the at least one second logical unit is recorded in at least one second logical-to-physical mapping table, and the first logical distance value further reflects an overlapping degree between the at least one first logical-to-physical mapping table and the at least one second logical-to-physical mapping table.

9. The memory storage device according to claim 7, wherein the operation of performing the data merge operation according to the first logical distance value by the memory control circuit unit comprises:

instructing to copy valid data in the first physical unit to the recycling node and copy valid data in the second physical unit to the recycling node if the first logical distance value is not larger than a target distance value; and

instructing to copy valid data in the first physical unit to the recycling node and copy valid data in a third physical unit among the physical units to the recycling node if the first logical distance value is larger than the target distance value.

10. The memory storage device according to claim 9, wherein the memory control circuit unit is further configured to obtain a second logical distance value between the first physical unit and the third physical unit, and the target distance value comprises the second logical distance value.

11. The memory storage device according to claim 7,

wherein the first table mapping information reflects that logical-to-physical mapping information of the at least one first logical unit is recorded in at least one first logical-to-physical mapping table, and the second table mapping information reflects that logical-to-physical mapping information of the at least one second logical unit is recorded in at least one second logical-to-physical mapping table.

12. The memory storage device according to claim 11, wherein the first table mapping information comprises a plurality of first values, the second table mapping information comprises a plurality of second values, and the operation of obtaining the first logical distance value according to the first table mapping information and the second table mapping information by the memory control circuit unit comprises:

obtaining a N-dimensional distance between the first values and the second values; and

obtaining the first logical distance value according to the N-dimensional distance.

13. A memory control circuit unit for controlling a rewritable non-volatile memory module comprising a plurality of physical units, and the memory control circuit unit comprising:

a host interface configured to couple to a host system;

a memory interface, configured to couple to the rewritable non-volatile memory module; and

a memory management circuit, coupled to the host interface and the memory interface,

wherein the memory management circuit is configured to obtain a first logical distance value between a first physical unit and a second physical unit among the physical units, wherein the first logical distance value reflects a logical dispersion degree between at least one first logical unit mapped by the first physical unit and at least one second logical unit mapped by the second physical unit, and

the memory management circuit is further configured to perform a data merge operation according to the first logical distance value, so as to copy valid data from a source node among the physical units to a recycling node among the physical units,

wherein the operation of obtaining the first logical distance value between the first physical unit and the second physical unit among the physical units by the memory management circuit comprises;

performing a first calculation on a plurality of first bits corresponding a first table mapping information of the first physical unit and a plurality of second bits corresponding a second table mapping information of the second physical unit to obtain at least one third bit; and

obtaining the first logical distance value according to the at least one third bit.

14. The memory control circuit unit according to claim 13, wherein logical-to-physical mapping information of the at least one first logical unit is recorded in at least one first logical-to-physical mapping table, logical-to-physical mapping information of the at least one second logical unit is recorded in at least one second logical-to-physical mapping table, and the first logical distance value further reflects an overlapping degree between the at least one first logical-to-physical mapping table and the at least one second logical-to-physical mapping table.

15. The memory control circuit unit according to claim 13, wherein the operation of performing the data merge operation according to the first logical distance value by the memory management circuit comprises:

instructing to copy valid data in the first physical unit to the recycling node and copy valid data in the second physical unit to the recycling node if the first logical distance value is not larger than a target distance value; and

instructing to copy valid data in the first physical unit to the recycling node and copy valid data in a third physical unit among the physical units to the recycling node if the first logical distance value is larger than the target distance value.

16. The memory control circuit unit according to claim 15, wherein the memory management circuit is further configured to obtain a second logical distance value between the first physical unit and the third physical unit, and the target distance value comprises the second logical distance value.

17. The memory control circuit unit according to claim 13,

wherein the first table mapping information reflects that logical-to-physical mapping information of the at least one first logical unit is recorded in at least one first logical-to-physical mapping table, and the second table mapping information reflects that logical-to-physical mapping information of the at least one second logical unit is recorded in at least one second logical-to-physical mapping table.

18. The memory control circuit unit according to claim 17, wherein the first table mapping information comprises a plurality of first values, the second table mapping information comprises a plurality of second values, and the operation of obtaining the first logical distance value according to the first table mapping information and the second table mapping information by the memory management circuit comprises:

obtaining a N-dimensional distance between the first values and the second values; and

obtaining the first logical distance value according to the N-dimensional distance.