Wear-leveling in non-volatile storage systems

• US 6,985,992 B1
• Filed: 10/28/2002
• Issued: 01/10/2006
• Est. Priority Date: 10/28/2002
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Corporation (Western Digital Corporation)
• Inventors: Qawami, Bahman, Sabet-Sharghi, Farshid, Chang, Robert C.
• Primary Examiner(s): Sparks, Donald
• Assistant Examiner(s): FARROKH, HASHEM
• Application Number:
  US10/281,739
• Time in Patent Office: 1,170 Days
• Field of Search: 365/185.01, 365/185.02, 365/185.29, 365/185.33
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/1036 Life time enhancement
• CPC Class Codes: G06F 2212/7211 Wear leveling
• CPC Class Codes: G11C 16/349 Arrangements for evaluating degradation, retention or wearout, e.g. by counting erase cycles

Abstract

Methods and apparatus for performing wear leveling in a non-volatile memory system are disclosed. According to one aspect of the present invention, a method for allocating non-volatile memory that is divided into elements includes grouping the elements into a first group, a second group, and a third group. The first group includes erased elements with relatively low wear and the second group includes erased elements with relatively high wear. The method also includes determining when a first element included in the third group is to be replaced by a second element included in the first group. Contents of the first element are copied into the second element obtained from the first group. The contents are then erased from the first element, and the second element is associated with the third group. Associating the second element with the third group includes substantially disassociating the second element from the first group.

Claims

1. A method for allocating non-volatile memory, the non-volatile memory being substantially divided into elements, the method comprising:

grouping the elements into at least a first group, a second group, and a third group, wherein the first group includes erased elements with relatively low wear and the second group includes erased elements with relatively high wear;

determining when a first element included in the third group is to be replaced by a second element included in the first group;

copying contents associated with the first element into the second element obtained from the first group when it is determined that the first element is to be substantially replaced by the second element;

erasing contents of the first element from the first element; and

associating the second element with the third group, wherein associating the second element with the third group includes disassociating the second element from the first group.

2. The method of claim 1 wherein grouping the elements into the first group, the second group, and the third group includes grouping the elements based on an erase count associated with each element.

3. The method of claim 1 wherein the first element includes an erase count, the method further including:

incrementing the erase count of the first element after erasing the contents of the first element.

4. The method of claim 3 further including:

using the erase count of the first element to determine whether to associate the first element with the first group; and

associating the first element with the first group when the erase count of the first element indicates that the first element is to be associated with the first group, wherein associating the first element with the first group includes disassociating the first element from the third group.

5. The method of claim 3 further including:

using the erase count of the first element to determine whether to associate the first element with the second group; and

associating the first element with the second group when the erase count of the first element indicates that the first element is to be associated with the second group, wherein associating the first element with the second group includes disassociating the first element from the third group.

6. The method of claim 5 wherein the elements in the second group have erase counts, the erase counts in the second group including a lowest erase count, the lowest erase count being associated with a third element included in the elements in the second group, and wherein using the erase count of the first element to determine whether to associate the first element with the second group includes determining when the erase count of the first element is greater than the lowest erase count.

7. The method of claim 6 further including:

associating the third element with the first group when the erase count of the first element indicates that the first element is to be associated with the second group, wherein associating the third element with the first group includes disassociating the third element from the second group.

8. The method of claim 1 wherein the non-volatile memory is a NAND flash memory and the elements are blocks.

9. The method of claim 1 wherein the contents associated with the first element are one of the contents of the first element and new contents arranged to replace at least some of the contents of the first element.

10. A method for allocating non-volatile memory, the non-volatile memory being substantially divided into elements, the method comprising:

grouping the elements into at least a first group, a second group, and a third group, wherein the first group includes erased elements with erase counts that are approximately less than an average erase count and the second group includes erased elements with erase counts that are approximately greater than the average erase count;

determining when a first element included in the third group is to be replaced by a second element included in the second group;

copying contents associated with the first element into the second element obtained from the second group when it is determined that the first element is to be substantially replaced by the second element;

erasing contents of the first element from the first element; and

associating the second element with the third group, wherein associating the second element with the third group includes disassociating the second element from the second group.

11. The method of claim 10 wherein the first element is a static element, and determining when the first element included in the third group is to be replaced by the second element included in the second group includes:

determining when a comparison of an erase count associated with the first element to the average erase count indicates that the first element included in the third group is to be replaced by the second element included in the second group.

12. The method of claim 11 wherein determining when the comparison of the erase count associated with the first element to the average erase count indicates that the first element included in the third group is to be replaced by the second element included in the second group includes determining when the erase count associated with the first element is substantially less than the average erase count.

13. The method of claim 10 further including:

associating the first element with the first group, wherein associating the first element with the first group includes disassociating the first element from the third group.

14. The method of claim 10 wherein the non-volatile memory is a NAND flash memory and the elements are blocks.

15. The method of claim 10 wherein the contents associated with the first element are one of the contents of the first element and substantially new contents arranged to replace at least some of the contents of the first element.

16. A memory management system, the memory management system being arranged to non-volatile memory, the non-volatile memory being substantially divided into elements, the memory management system comprising:

a first manager, the first manager being arranged to group the elements into at least a first group, a second group, and a third group, wherein the first group includes elements with relatively low wear and the second group includes elements with relatively high wear; and

a second manager, the second manager being arranged to determine when a first element included in the third group is to be replaced by a second element included in the first group, the second manager further being arranged to copy contents associated with the first element into the second element obtained from the first group and to erase contents of the first element from the first element, wherein the second manager is still further arranged to associate the second element with the third group and to disassociating the second element from the first group.

17. The memory management system of claim 16 wherein the first manager is arranged to group the elements into the first group, the second group, and the third group by grouping the elements based on an erase count associated with each element.

18. The memory management system of claim 16 wherein the first element includes an erase count and the second manager is further arranged to increment the erase count of the first element after erasing the contents of the first element from the first element.

19. The memory management system of claim 18 wherein the second manager uses the erase count of the first element to determine whether to associate the first element with the first group and associates the first element with the first group when the erase count of the first element indicates that the first element is to be associated with the first group.

20. The memory management system of claim 18 wherein the second manager is still further arranged to use the erase count of the first element to determine whether to associate the first element with the second group and to associate the first element with the second group when the erase count of the first element indicates that the first element is to be associated with the second group.

21. The memory management system of claim 20 wherein the elements in the second group have erase counts, the erase counts in the second group including a lowest erase count, the lowest erase count being associated with a third element included in the elements in the second group, and wherein the second manager is arranged to use the erase count of the first element to determine whether to associate the first element with the second group by determining when the erase count of the first element is greater than the lowest erase count.

22. The memory management system of claim 16 wherein the non-volatile memory is a NAND flash memory and the elements are blocks.

23. The memory management system of claim 16 wherein the contents associated with the first element are one of the contents of the first element and contents arranged to replace at least some of the contents of the first element.

24. A memory management system for allocating non-volatile memory, the non-volatile memory being substantially divided into elements, the memory management system comprising:

a first manager, the first manager being arranged to group the erased elements into at least a first group, a second group, and a third group, wherein the first group includes elements with erase counts that are approximately less than an average erase count and the second group includes erased elements with erase counts that are approximately greater than the average erase count; and

a second manager, the second manager being arranged to determine when a first element included in the third group is to be replaced by a second element included in the second group, the second manager further being arranged to copy contents associated with the first element into the second element obtained from the second group and to erase contents of the first element from the first element, the second manager still further being arranged to associate the second element with the third group and to disassociate the second element from the second group.

25. The memory management system of claim 24 wherein the second manager is arranged to determine when the first element included in the third group is to be replaced by the second element included in the second group by determining when a comparison of an erase count associated with the first element to the average erase count indicates that the first element included in the third group is to be replaced by the second element included in the second group.

26. The memory management system of claim 24 wherein the second manager is arranged to associate the first element with the second group and to disassociate the first element from the third group.

27. The memory management system of claim 24 wherein the non-volatile memory is a NAND flash memory and the elements are blocks.

28. The memory management system of claim 24 wherein the contents associated with the first element are one of the contents of the first element and new contents arranged to replace at least some of the contents of the first element.

29. A method for performing wear leveling in a system which includes a non-volatile memory, the method comprising:

copying one of contents associated with a first storage element and new contents arranged to replace the contents associated with the first storage element into a second storage element, the second storage element having an erase count that is less than an erase count associated with the first storage element, the second storage element being associated with a first data structure, the first data structure being arranged to contain a first set of storage elements;

associating the second storage element with a second data structure, the second data structure being arranged to contain a second set of storage elements, wherein associating the second storage element with the second data structure includes disassociating the second storage element from the first data structure;

erasing the contents associated with the first storage element from the first storage element;

determining when to associate the first storage element with the first data structure;

associating the first storage element with the first data structure when it is determined that the first storage element is to be associated with the first data structure, wherein associating the first storage element with the first data structure includes disassociating the first storage element from the second data structure; and

associating the first storage element with a third data structure when it is determined that the first storage element is not to be associated with the first data structure, the third data structure being arranged to contain a third set of storage elements.

30. The method of claim 29 further including:

determining an average erase count associated with the storage elements, wherein erase counts associated with the storage elements included in the first set of storage elements are substantially lower than the average erase count, erase counts associated with the storage elements included in the third set of storage elements are substantially higher than the average erase count.

31. The method of claim 29 further including:

incrementing the erase count of the first storage element after the contents of the first storage element are erased.

32. The method of claim 31 wherein determining when to associate the first storage element with the first data structure includes:

comparing the erase count of the first storage element to erase counts of storage elements associated with the third set of storage elements.

33. The method of claim 32 wherein when it is determined that the erase count of the first storage element is less than erase counts of storage elements associated with the third set of storage elements, it is determined that the first storage element is to be associated with the first data structure.

34. The method of claim 32 wherein when it is determined that the erase count of the first storage element is greater than at least one erase count of storage elements associated with the third set of storage elements, it is determined that the first storage element is not to be associated with the first data structure.

35. The method of claim 34 wherein associating the first storage element with the third data structure includes:

obtaining a third storage element, the third storage element being associated with the third set of storage elements, the third element having an erase count that is less than the erase count of the first storage element; and

associating the third storage element with the first data structure, wherein associating the third storage element with the first data structure includes disassociating the third storage element from the third data structure.

36. The method of claim 29 further including:

obtaining the first storage element from the second data structure.

37. The method of claim 29 wherein the non-volatile memory is a NAND flash memory.

38. A method for performing wear leveling in a system which includes a non-volatile memory, the method comprising:

copying at least one of contents associated with a first storage element and new contents arranged to replaced the contents associated with the first storage element into a second storage element, the second storage element having an erase count that is greater than an erase count associated with the first storage element, the second storage element being associated with a first data structure, the first data structure being arranged to contain a first set of storage elements;

associating the second storage element with a second data structure, the second data structure being arranged to contain a second set of storage elements, wherein associating the second storage element with the first data structure includes disassociating the second storage element from the first data structure;

erasing the contents associated with the first storage element from the first storage element;

associating the first storage element with a third data structure, the third data structure being arranged to contain a third set of storage elements;

obtaining a third storage element from the third data structure; and

associating the third storage element with the first data structure, wherein associating the third storage element with the first data structure includes disassociating the third storage element from the third data structure.

39. The method of claim 38 wherein the first set of storage elements includes storage elements which each have an erase count that is greater than an average erase count and the third set of storage elements includes storage elements which each have an erase count that is less than the average erase count, and wherein the contents associated with the first storage element are substantially static.

40. The method of claim 38 further including:

comparing the erase count associated with the first storage element with an average erase count associated with the non-volatile memory; and

determining when the erase count associated with the first storage element is substantially less than the average erase count, wherein copying contents associated with the first storage element into the second storage element occurs when it is determined that the erase count associated with the first storage element is substantially less than the average erase count.

41. The method of claim 38 wherein the non-volatile memory is a NAND flash memory.

42. A memory management system, the memory management system being arranged to manage an allocation of non-volatile storage elements, the memory management system comprising:

means for maintaining a first data structure, the first data structure being associated with storage elements which have each been erased substantially less than a particular amount;

means for maintaining a second data structure, the second data structure being associated with storage elements which have each been erased substantially more than a particular amount;

means for maintaining a third data structure, the third data structure being associated with storage elements which are not associated with the first data structure or the second data structure, wherein at least a plurality of the storage elements associated with the third data structure contain data;

means for determining when a first storage element of the third data structure is to be replaced; and

means for associating a second storage element selected from one of the first data structure and the second data structure with the third data structure when it is determined that the first storage element of the third data structure is to be replaced.

43. The memory management system of claim 42 further including:

means for determining the particular amount, wherein the particular amount is an average erase count associated with storage elements of the first data structure, storage elements of the second data structure, and storage elements of the third data structure.

44. The memory management system of claim 43 further including:

means for maintaining the average erase count.

45. The memory management system of claim 44 further including:

means for initializing the first data structure;

means for initializing the second data structure; and

means for initializing the third data structure.

46. The memory management system of claim 44 further including:

means for moving a third storage element of the storage elements which have each been erased substantially less than a particular amount from the first data structure to the second data structure.

47. The memory management system of claim 44 further including:

means for moving a third storage element of the storage elements which have each been erased substantially more than a particular amount from the second data structure to the first data structure.

48. The memory management system of claim 42 further including:

means for copying one of contents of the first storage element and new contents arranged to replace at least some of the contents associated with the first storage element into the second storage element;

means for erasing the first storage element; and

means for incrementing an erase count associated with the first storage element.

49. The memory management system of claim 44 wherein the storage elements are blocks in the non-volatile memory.

50. The memory management system of claim 49 wherein the non-volatile memory is a NAND flash memory.

51. A memory management system, the memory management system being arranged to manage an allocation of non-volatile storage elements, the memory management system comprising:

code devices for copying one of contents associated with a first storage element and new contents arranged to replace the contents associated with the first storage element into a second storage element, the second storage element having an erase count that is less than an erase count associated with the first storage element, the second storage element being associated with a first data structure, the first data structure being arranged to contain a first set of storage elements;

code device for associating the second storage element with a second data structure, the second data structure being arranged to contain a second set of storage elements, wherein the code devices for associating the second storage element with the first data structure include code devices for disassociating the second storage element from the first data structure;

code devices for erasing the contents associated with the first storage element from the first storage element;

code devices for determining when to associate the first storage element with the first data structure;

code devices for associating the first storage element with the first data structure when it is determined that the first storage element is to be associated with the first data structure, wherein the code devices for associating the first storage element with the first data structure include code devices for disassociating the first storage element from the second data structure;

code devices for associating the first storage element with a third data structure when it is determined that the first storage element is not to be associated with the first data structure, the third data structure being arranged to contain a third set of storage elements;

a memory for storing the code devices; and

a processor arranged to access the code devices.

52. The memory management system of claim 51 further including:

code devices for determining an average erase count associated with the storage elements, wherein erase counts associated with the storage elements included in the first set of storage elements are substantially lower than the average erase count, erase counts associated with the storage elements included in the third set of storage elements are substantially higher than the average erase count.

53. The memory management system of claim 51 further including:

code devices for incrementing the erase count of the first storage element after the contents of the first storage element are erased.

54. The memory management system of claim 53 wherein the code devices for determining when to associate the first storage element with the first data structure include:

code devices for comparing the erase count of the first storage element to erase counts of storage elements associated with the third set of storage elements.

55. The memory management system of claim 54 wherein when it is determined that the erase count of the first storage element is less than erase counts of storage elements associated with the third set of storage elements, it is determined that the first storage element is to be associated with the first data structure.

56. The memory management system of claim 54 wherein when it is determined that the erase count of the first storage element is greater than at least one erase count of storage elements associated with the third set of storage elements, it is determined that the first storage element is not to be associated with the first data structure.

57. The memory management system of claim 56 wherein the code devices for associating the first storage element with the third data structure includes:

code devices for obtaining a third storage element, the third storage element being associated with the third set of storage elements, the third element having an erase count that is less than the erase count of the first storage element; and

code devices for associating the third storage element with the first data structure, wherein the code devices for associating the third storage element with the first data structure include code devices for disassociating the third storage element from the third data structure.

58. The memory management system of claim 51 further including:

code devices for obtaining the first storage element from the second data structure.

59. The memory management system of claim 51 wherein the non-volatile memory is a NAND flash memory.

60. A memory management system, the memory management system being arranged to manage an allocation of non-volatile storage elements, the memory management system comprising:

code devices for copying contents associated with a first storage element into a second storage element, the second storage element having an erase count that is greater than an erase count associated with the first storage element, the second storage element being associated with a first data structure, the first data structure being arranged to contain a first set of storage elements;

code devices for associating the second storage element with a second data structure, the second data structure being arranged to contain a second set of storage elements, wherein the code devices for associating the second storage element with the first data structure include code devices for disassociating the second storage element from the first data structure;

code devices for erasing the contents associated with the first storage element from the first storage element;

code devices for associating the first storage element with a third data structure, the third data structure being arranged to contain a third set of storage elements;

code devices for obtaining a third storage element from the third data structure;

code devices for associating the third storage element with the first data structure, wherein the code devices for associating the third storage element with the first data structure include code devices for disassociating the third storage element from the third data structure;

a storage area for storing the code devices; and

a processor for accessing the code devices.

61. The memory management system of claim 60 wherein the first set of storage elements includes storage elements which each have an erase count that is greater than an average erase count and the third set of storage elements includes storage elements which each have an erase count that is less than the average erase count, and wherein the contents associated with the first storage element are substantially static.

62. The memory management system of claim 60 further including:

code devices for comparing the erase count associated with the first storage element with an average erase count associated with the non-volatile memory; and

code devices for determining when the erase count associated with the first storage element is substantially less than the average erase count, wherein the code devices for copying contents associated with the first storage element include code devices for copying the contents associated with the first storage element into the second storage element when it is determined that the erase count associated with the first storage element is substantially less than the average erase count.

63. The memory management system of claim 60 wherein the non-volatile memory is a NAND flash memory.

64. The memory management system of claim 60 wherein the contents associated with the first element are one of the contents of the first element and substantially new contents arranged to replace at least some of the contents of the first element.