Wear leveling method and controller using the same

• US 8,046,526 B2
• Filed: 01/29/2008
• Issued: 10/25/2011
• Est. Priority Date: 09/27/2007
• Status: Active Grant

• Current Assignee: Phison Electronics Corporation
• Original Assignee: Phison Electronics Corporation
• Inventors: Yeh, Chih-Kang
• Primary Examiner(s): SONG, HUA JASMINE
• Application Number:
  US12/021,885
• Publication Number:
  US 20090089485A1
• Time in Patent Office: 1,365 Days
• Field of Search: 711/103, 711/156, 711/159, 711/E12.001, 365/185.29, 365/185.33, 365/230.03
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7211 Wear leveling

Abstract

A wear leveling method for a non-volatile memory is provided. The non-volatile memory is substantially divided into a plurality of blocks, and these blocks are grouped into at least a data area, a spare area, a substitute area, and a temporary area. The wear leveling method includes selecting blocks from the spare area according to different purposes and executing a wear leveling procedure.

Claims

1. A wear leveling method for a non-volatile memory, wherein the non-volatile memory is substantially divided into a plurality of blocks, and the blocks are grouped into at least a data area, a spare area, a substitute area, and a temporary area, the wear leveling method comprising:

(a) determining the blocks to be selected from the spare area is used for the substitute area or the temporary area;

(b) selecting the blocks from the spare area according to a result determined by the step (a), wherein the blocks in the substitute area used for substituting blocks in the data area and the blocks in the temporary area used for storing data of small quantity; and

(c) executing a wear leveling procedure,

wherein step (b) comprises;

determining a hot area in the spare area in order to identify at least one block having relatively higher erase count in the spare area; and

when a first block is selected from the spare area to be used in the substitute area, moving the first block to the substitute area if the erase count of the first block is lower than or equal to the sum of the erase count of the block in the hot area and a first threshold, and moving one of the at least one block in the hot area to the substitute area and identifying the first block as a block in the hot area if the erase count of the first block is greater than the sum of the erase count of the block in the hot area and the first threshold.

2. The wear leveling method according to claim 1, wherein step (b) further comprises:

selecting a second block to be used in the temporary area from the spare area, wherein the second block is a block having relatively lower erase count in the spare area.

3. The wear leveling method according to claim 1, wherein the wear leveling procedure comprises moving one of the at least one block in the hot area to the data area, and at the same time, moving a third block in the data area to the spare area and identifying the third block as a block in the hot area, wherein the third block is a block having relatively lower erase count in the data area.

4. The wear leveling method according to claim 1 further comprising:

adding 1 to a counting value when the erase count of the block in the hot area is greater than the sum of the intermediate value of a maximum erase count and a minimum erase count among the erase counts of the blocks and a second threshold; and

executing step (c) and resetting the counting value when the counting value is greater than a third threshold.

5. The wear leveling method according to claim 1 further comprising:

adding 1 to a counting value when executing a write or erase command; and

executing step (c) and resetting the counting value when the counting value is greater than a third threshold.

6. The wear leveling method according to claim 1 further comprising:

executing step (c) when the erase count of the block in the hot area is greater than the sum of the intermediate value of a maximum erase count and a minimum erase count among the erase counts of the blocks and a fourth threshold.

7. The wear leveling method according to claim 1 further comprising:

executing step (c) randomly.

8. The wear leveling method according to claim 1 further comprising establishing at least one data block erase count table, one spare block erase count table, one substitute block erase count table, and one temporary block erase count table corresponding to at least one zone in the data area for respectively recording the erase counts of blocks in the data area, the spare area, the substitute area, and the temporary area.

9. The wear leveling method according to claim 8, wherein the step of establishing the data block erase count table is to establish the data block erase count table corresponding to a logical-physical mapping table, wherein the data block erase count table respectively records the erase counts of blocks in the data area corresponding to the logical-physical mapping table.

10. The wear leveling method according to claim 8 further comprising storing the data block erase count table, the spare block erase count table, the substitute block erase count table, and the temporary block erase count table into a system area which further groups the blocks.

11. The wear leveling method according to claim 8 further comprising increasing the erase count of a block while erasing or writing data into the block.

12. The wear leveling method according to claim 8 further comprising scanning the data block erase count table and recording a block having the lowest erase count while erasing or writing data into a block.

13. The wear leveling method according to claim 8 further comprising updating at least one of the data block erase count table, the spare block erase count table, the substitute block erase count table, and the temporary block erase count table while updating blocks in the spare area.

14. The wear leveling method according to claim 1 further comprising executing a normal write command issued by a host to complete step (c).

15. A controller, suitable for a storage device, wherein a non-volatile memory of the storage device is substantially divided into a plurality of blocks, and the blocks are grouped into at least a data area, a spare area, a substitute area, and a temporary area, the controller comprising:

a microprocessor unit is configured for controlling a whole operation of the controller;

a buffer memory is electrically connected to the microprocessor unit and configured for temporarily storing data;

a non-volatile memory interface is electrically connected to the microprocessor unit and configured for accessing the non-volatile memory; and

a memory management module is electrically connected to the microprocessor unit and configured for managing the non-volatile memory,

wherein the memory management module determines the blocks to be selected from the spare area is used for the substitute area or the temporary area, selects the blocks from the spare area according to a determined result and exchanges a block in the spare area with a block in the data area,

wherein the blocks in the substitute area used for substituting blocks in the data area and the blocks in the temporary area used for storing data of small quantity,

wherein the memory management module further determines a hot area in the spare area in order to identify at least one block having relatively higher erase count in the spare area, and

when a first block is selected from the spare area to be used in the substitute area, the memory management module moves the first block to the substitute area if the erase count of the first block is lower than or equal to the sum of the erase count of the block in the hot area and a first threshold, and the memory management module moves one of the at least one block in the hot area to the substitute area and identifying the first block as a block in the hot area if the erase count of the first block is greater than the sum of the erase count of the block in the hot area and the first threshold.

16. The controller according to claim 15, wherein the memory management module selects a second block to be used in the temporary area from the spare area and the second block is a block having relatively lower erase count in the spare area.

17. The controller according to claim 15, wherein for exchanging the block in the spare area with the block in the data area, the memory management module moves one of the at least one block in the hot area to the data area, and moves a third block in the data area to the spare area and identifying the third block as a block in the hot area, wherein the third block is a block having relatively lower erase count in the data area.

18. The controller according to claim 15, wherein the memory management module further adds 1 to a counting value when the erase count of the block in the hot area is greater than the sum of the intermediate value of a maximum erase count and a minimum erase count among the erase counts of the blocks and a second threshold, and exchanges the block in the spare area with the block in the data area and resets the counting value when the counting value is greater than a third threshold.

19. The controller according to claim 15, wherein the memory management module further adds 1 to a counting value when executing a write or erase command, and exchanges the block in the spare area with the block in the data area and resets the counting value when the counting value is greater than a third threshold.

20. The controller according to claim 15, wherein the memory management module exchanges the block in the spare area with the block in the data area when the erase count of the block in the hot area is greater than the sum of the intermediate value of a maximum erase count and a minimum erase count among the erase counts of the blocks and a fourth threshold.

21. The controller according to claim 15, wherein the memory management module randomly exchanges the block in the spare area with the block in the data area.

22. The controller according to claim 15, wherein the memory management module further establishes at least one data block erase count table, one spare block erase count table, one substitute block erase count table, and one temporary block erase count table corresponding to at least one zone in the data area for respectively recording the erase counts of blocks in the data area, the spare area, the substitute area, and the temporary area.

23. The controller according to claim 22, wherein the memory management module establishes the data block erase count table corresponding to a logical-physical mapping table, wherein the data block erase count table respectively records the erase counts of blocks in the data area corresponding to the logical-physical mapping table.

24. The controller according to claim 22, wherein the memory management module further stores the data block erase count table, the spare block erase count table, the substitute block erase count table, and the temporary block erase count table into a system area which further groups the blocks.

25. The controller according to claim 22, wherein the memory management module increases the erase count of a block while erasing or writing data into the block.

26. The controller according to claim 22, wherein the memory management module further scans the data block erase count table and records a block having the lowest erase count while erasing or writing data into a block.

27. The controller according to claim 22, wherein the memory management module further updates at least one of the data block erase count table, the spare block erase count table, the substitute block erase count table, and the temporary block erase count table while updating blocks in the spare area.

28. The controller according to claim 15, wherein the memory management module further executes a normal write command issued by a host to exchange the block in the spare area with the block in the data area.

29. The controller according to claim 15, wherein the non-volatile memory is a SLC NAND flash memory or a MLC NAND flash memory.

30. A wear leveling method for a non-volatile memory, wherein the non-volatile memory is substantially divided into a plurality of blocks, and the blocks are grouped into at least a data area, a spare area, and a substitute area, the wear leveling method comprising

(a) determining a hot area in the spare area in order to identify at least one block having relatively higher erase count in the spare area;

(b) selecting a first block from the spare area to be used in the substitute area by using the sum of the erase count of the block in the hot area and a first threshold as a selection condition; and

(c) executing a wear leveling procedure,

wherein the wear leveling procedure comprises moving one of the at least one block in the hot area to the data area, and at the same time, moving a third block in the data area to the spare area and identifying the third block as a block in the hot area, wherein the third block is a block having relatively lower erase count in the data area.

31. The wear leveling method according to claim 30, wherein the selection condition comprises:

moving the first block to the substitute area if the erase count of the first block is lower than or equal to the sum of the erase count of the block in the hot area and the first threshold, and moving one of the at least one block in the hot area to the substitute area and identifying the first block as a block in the hot area if the erase count of the first block is greater than the sum of the erase count of the block in the hot area and the first threshold.

32. The wear leveling method according to claim 30 further comprising:

adding 1 to a counting value when the erase count of the block in the hot area is greater than the sum of the intermediate value of a maximum erase count and a minimum erase count among the erase counts of the blocks and a second threshold; and

executing step (c) and resetting the counting value when the counting value is greater than a third threshold.

33. The wear leveling method according to claim 30 further comprising:

adding 1 to the counting value when executing a write or erase command; and

executing step (c) and resetting the counting value when the counting value is greater than the third threshold.

34. The wear leveling method according to claim 30 further comprising:

executing step (c) when the erase count of the block in the hot area is greater than the sum of the intermediate value of a maximum erase count and a minimum erase count among the erase counts of the blocks and a fourth threshold.

35. A controller, suitable for a storage device, wherein a non-volatile memory of the storage device is substantially divided into a plurality of blocks, and the blocks are grouped into at least a data area, a spare area, and a substitute area, the controller comprising:

a microprocessor unit is configured for controlling a whole operation of the controller;

a buffer memory is electrically connected to the microprocessor unit and configured for temporarily storing data;

a non-volatile memory interface is electrically connected to the microprocessor unit and configured for accessing the non-volatile memory; and

a memory management module is electrically connected to the microprocessor unit and configured for managing the non-volatile memory,

wherein the memory management module determines a hot area in the spare area in order to identify at least one block having relatively higher erase count in the spare area, selects a first block from the spare area to be used in the substitute area by using the sum of the erase count of the block in the hot area and a first threshold as a selection condition, and exchanges a block in the spare area with a block in the data area.

36. The controller according to claim 35, wherein the selection condition comprises:

moving the first block to the substitute area if the erase count of the first block is lower than or equal to the sum of the erase count of the block in the hot area and the first threshold, and moving one of the at least one block in the hot area to the substitute area and identifying the first block as a block in the hot area if the erase count of the first block is greater than the sum of the erase count of the block in the hot area and the first threshold.

37. The controller according to claim 35, wherein for exchanging the block in the spare area with the block in the data area, the memory management module moves one of the at least one block in the hot area to the data area, and moves a third block in the data area to the spare area and identifying the third block as a block in the hot area, wherein the third block is a block having relatively lower erase count in the data area.

38. The controller according to claim 35, wherein the memory management module further adds 1 to a counting value when the erase count of the block in the hot area is greater than the sum of the intermediate value of a maximum erase count and a minimum erase count among the erase counts of the blocks and a second threshold, and exchanges the block in the spare area with the block in the data area and resets the counting value when the counting value is greater than a third threshold.

39. The controller according to claim 35, wherein the memory management module further adds 1 to the counting value when executing a write or erase command, and exchanges the block in the spare area with the block in the data area resets the counting value when the counting value is greater than the third threshold.

40. The controller according to claim 35, wherein the memory management module exchanges the block in the spare area with the block in the data area when the erase count of the block in the hot area is greater than the sum of the intermediate value of a maximum erase count and a minimum erase count among the erase counts of the blocks and a fourth threshold.

41. A wear leveling method for a non-volatile memory, wherein the non-volatile memory is substantially divided into a plurality of blocks, and the blocks are grouped into at least a data area, a spare area, and a substitute area, the wear leveling method comprising:

(a) determining a hot area in the spare area in order to identify at least one block having relatively higher erase count in the spare area;

(b) selecting a first block from the spare area to be used in the substitute area;

(c) using the comparison between the erase count of the hot area and a predetermined value as a counting condition; and

(d) executing a wear leveling procedure when a counting value is greater than a third threshold,

wherein the counting condition comprises;

adding 1 to the counting value when the erase count of the block in the hot area is greater than the sum of the predetermined value and a second threshold.

42. The wear leveling method according to claim 41, wherein the predetermined value is the intermediate value of a maximum erase count and a minimum erase count among the erase counts of the blocks.

43. The wear leveling method according to claim 41, wherein the wear leveling procedure comprises moving one of the at least one block in the hot area to the data area, and at the same time, moving a third block in the data area to the spare area and identifying the third block as a block in the hot area, wherein the third block is a block having relatively lower erase count in the data area.

44. The wear leveling method according to claim 41 further comprising establishing at least one data block erase count table, one spare block erase count table, one substitute block erase count table, and one temporary block erase count table corresponding to at least one zone in the data area for respectively recording the erase counts of blocks in the data area, the spare area, the substitute area, and the temporary area.

45. The wear leveling method according to claim 41 further comprising executing a normal write command issued by a host to complete the wear leveling procedure.