Wear Leveling for Non-Volatile Memories: Maintenance of Experience Count and Passive Techniques

• US 20120191927A1
• Filed: 03/29/2012
• Published: 07/26/2012
• Est. Priority Date: 01/05/2009
• Status: Abandoned Application

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Gorobets, Sergey Anatolievich, So, Bum Suck, Zilberman, Eugene
• Application Number:
  US13/433,584
• Publication Number:
  US 20120191927A1
• Time in Patent Office: Days
• US Class Current: 711/156
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7208 Multiple device management, e.g. distributing data over multiple flash devices
• CPC Class Codes: G06F 2212/7211 Wear leveling

Abstract

Wear leveling techniques for re-programmable non-volatile memory systems, such as a flash EEPROM system, are described. One set of techniques uses “passive” arrangements, where, when a blocks are selected for writing, blocks with relatively low experience count are selected. This can be done by ordering the list of available free blocks based on experience count, with the “coldest” blocks placed at the front of the list, or by searching the free blocks to find a block that is “cold enough”. In another, complementary set of techniques, usable for more standard wear leveling operations as well as for “passive” techniques and other applications where the experience count is needed, the experience count of a block or meta-block is maintained as a block'"'"'s attribute along its address in the data management structures, such as address tables.

Claims

1. A method of operating a non-volatile memory system including a memory circuit having a plurality of non-volatile memory cells formed into a plurality of multi-cell erase blocks and control circuitry managing the storage of data on the memory circuit, the method including:

selecting blocks to be written with data content from a list of free blocks;

returning blocks whose data content is obsolete to a pool of free blocks, where the list of free blocks formed from members of the pool of free blocks;

maintaining an experience count for each of the blocks; and

ordering the list of free blocks in increasing order of the blocks'"'"' experience count, where when selecting a block from the list of free blocks, the selection is made from the beginning of the list of free blocks according to the ordering.

2. The method of claim 1, wherein the memory circuit is formed of a plurality of sub-arrays each having a plurality of blocks and the control circuitry forms multi-block logical structures spanning a corresponding number of sub-arrays, the multi-block logical structures being maintained in the list of free blocks.

3. The method of claim 1, wherein the memory circuit is formed of a plurality of sub-arrays each having a plurality of blocks and said ordering includes independently ordering the list of free blocks in each sub-array in increasing order of experience count, wherein said selecting blocks includes selecting multiple blocks, one each from a corresponding number of sub-arrays, and forming the multiple blocks into a composite logical structure;

and wherein said returning blocks includes dissolving the composite logical structure.

4. The method of claim 1, wherein the memory circuit is formed of a binary memory section and a multi-state memory section and said ordering is only performed for the multi-state section of the memory.

5. The method of claim 1, wherein the memory system maintains the experience counts of the blocks as an attribute of the corresponding block that is associated with the block'"'"'s address.

6. The method of claim 1, wherein said selection is for a block in which to store user data.

7. The method of claim 6, wherein the user data is relocated from another location on the memory circuit.

8. The method of claim 1, wherein said selection is for a block in which to store system data.

9. The method of claim 1, wherein the list of free blocks is formed from less than all of the free blocks in the pool of free blocks.

10. The method of claim 1, wherein the list of free blocks is formed from all of the free blocks in the pool of free blocks.

11. The method of claim 1, wherein the experience count is the number of erase cycles experienced.

12. A non-volatile memory system, including

a memory circuit having a plurality of non-volatile memory cells formed into a plurality of multi-cell erase blocks;

and

control circuitry managing the storage of data on the memory circuit, wherein the control circuit maintains an experience count for each of the blocks, and where the control circuitry selects blocks to be written with data content from a list of free blocks, returns blocks whose data content is obsolete to a pool of free blocks, where the list of free blocks formed from members of the pool of free blocks, and orders the list of free blocks in increasing order of the blocks'"'"' experience count, where when selecting a block from the list of free blocks, the selection is made from the list of free blocks according to the ordering.

14. The non-volatile memory system claim of 12, wherein the memory circuit is formed of a plurality of sub-arrays each having a plurality of blocks and the control circuitry independently orders the list of free blocks in each sub-array in increasing order of experience count and selects multiple blocks, each from a corresponding number of sub-arrays, and forming the multiple blocks into a composite logical structure;

and wherein said returning blocks includes dissolving the composite logical structure.

15. The non-volatile memory system claim of 12, wherein the memory circuit is formed of a binary memory section and a multi-state memory section and said ordering is only performed for the multi-state section of the memory.

16. The non-volatile memory system claim of 12, wherein the memory system maintains the experience count of the blocks as an attribute of the corresponding block that is associated with the block'"'"'s address.

17. The non-volatile memory system claim of 12, wherein said selection is for a block in which to store user data.

18. The non-volatile memory system of claim of 17, wherein the user data is relocated from another location on the memory circuit.

19. The non-volatile memory system of claim 12, wherein said selection is for a block in which to store system data.

13. The non-volatile memory system of 12, wherein the memory circuit is formed of a plurality of sub-arrays each having a plurality of blocks and the control circuitry forms multi-block logical structures spanning a corresponding number of sub-arrays, the multi-block logical structures being maintained in the list of free blocks.

20. The non-volatile memory system of 12, wherein the list of free blocks is formed from less than all of the free blocks in the pool of free blocks.

21. The non-volatile memory system of 12, wherein the list of free blocks is formed from all of the free blocks in the pool of free blocks.

22. The non-volatile memory system of 12, wherein the experience count is the number of erase cycles experienced.

23. A method of operating a non-volatile memory system including a memory circuit having a plurality of non-volatile memory cells formed into a plurality of blocks, the block being a multi-cell unit of erase, and control circuitry managing the storage of data on the memory circuit, the method including:

selecting blocks to be written with data content from a list of free blocks;

returning blocks whose data content is obsolete to a pool of free blocks, where the list of free blocks formed from members of the pool of free blocks; and

for the plurality of blocks, maintaining a corresponding experience count, wherein said selecting blocks from a list of free blocks comprises;

searching the list of free blocks to determine a first block having an experience count that is relatively low with respect to others of the blocks; and

in response to determining the first block having a relatively low experience count, discontinuing the searching and selecting the first block.

24. The method of claim 23, wherein said searching the list of free blocks includes individually comparing the corresponding experience count of the blocks in the list of free blocks against a value dependent upon an average experience count for a population of said blocks.

25. The method of claim 24, wherein the average experience count is the average experience count for the blocks on the list of free blocks.

26. The method of claim 24, wherein the average experience count is the average experience count for the blocks on the memory circuit.

27. The method of claim 24, wherein the value dependent upon an average experience count is the average experience count minus a predetermined number.

28. The method of claim 24, wherein the memory circuit is formed of a plurality of sub-arrays each having a plurality of blocks and an independent list of free blocks;

wherein said selecting blocks includes selecting a plurality of blocks from a corresponding plurality of sub-arrays and forming the plurality of blocks into a composite logical structure;

wherein said returning blocks includes dissolving the composite logical structure; and

the individually comparing is performed independently in each sub-array.

29. The method of claim 24, wherein the memory circuit is formed a binary memory section and a multi-state memory section and said individually comparing the corresponding count of the blocks in the list of free blocks and determining a first block in response thereto is only performed for the multi-state section of the memory.

30. The method of claim 23, wherein in response to not finding a block having an experience count that is relatively low based upon a predetermined criteria, selecting the block from the list of free blocks with the lowest experience count of the blocks searched.

31. The method of claim 23, wherein the memory circuit is formed of a plurality of sub-arrays each having a plurality of blocks and the control circuitry forms multi-block logical structures spanning a corresponding number of sub-arrays, the multi-block logical structures being maintained in the list of free blocks.

32. The method of claim 23, wherein the memory system maintains the experience count of the blocks as an attribute of the corresponding block that is associated with the block'"'"'s address.

33. The method of claim 23, wherein said selection is for a block in which to store user data.

34. The method of claim 33, wherein the user data is relocated from another location on the memory circuit.

35. The method of claim 23, wherein said selection is for a block in which to store system data.

36. The method of claim 23, wherein the list of free blocks is formed from less than all of the free blocks in the pool of free blocks.

37. The method of claim 23, wherein the list of free blocks is formed from all of the free blocks in the pool of free blocks.

38. The method of claim 23, wherein the experience count is the number of erase cycles experienced.

39. A non-volatile memory system including

a memory circuit having a plurality of non-volatile memory cells formed into a plurality of blocks, the block being a multi-cell unit of erase;

and

control circuitry managing the storage of data on the memory circuit, where the control circuitry selects blocks to be written with data content from a list of free blocks, returns blocks whose data content is obsolete to a pool of free blocks, where the list of free blocks formed from members of the pool of free blocks; and

for the plurality of blocks, maintaining a corresponding experience count, wherein said selecting blocks from a list of free blocks comprises;

searching the list of free blocks to determine a first block having an experience count that is relatively low with respect to others of the blocks; and

in response to determining the first block having a relatively low experience count, discontinuing the searching and selecting the first block.

40. The non-volatile memory system of claim 39, wherein said searching the list of free blocks includes individually comparing the corresponding experience count of the blocks in the list of free blocks against a value dependent upon an average experience count for a population of said blocks.

41. The non-volatile memory system of claim 40, wherein the average experience count is the average experience count for the blocks on the list of free blocks.

42. The non-volatile memory system of claim 40, wherein the average experience count is the average experience count for the blocks on the memory circuit.

43. The non-volatile memory system of claim 40, wherein the value dependent upon an average experience count is the average experience count minus a predetermined number.

44. The non-volatile memory system of claim 40, wherein the memory circuit is formed of a plurality of sub-arrays each having a plurality of blocks and an independent list of free blocks;

wherein said selecting blocks includes selecting a plurality of blocks from a corresponding plurality of sub-arrays and forming the plurality of blocks into a composite logical structure;

wherein said returning blocks includes dissolving the composite logical structure; and

the individually comparing is performed independently in each sub-array.

45. The non-volatile memory system of claim 40, wherein the memory circuit is formed a binary memory section and a multi-state memory section and said individually comparing the corresponding count of the blocks in the list of free blocks and determining a first block in response thereto is only performed for the multi-state section of the memory.

46. The non-volatile memory system of claim 39, wherein in response to not finding a block having an experience count that is relatively low based upon a predetermined criteria, selecting the block from the list of free blocks with the lowest experience count of the blocks searched.

47. The non-volatile memory system of claim 39, wherein the memory circuit is formed of a plurality of sub-arrays each having a plurality of blocks and the control circuitry forms multi-block logical structures spanning a corresponding number of sub-arrays, the multi-block logical structures being maintained in the list of free blocks.

48. The non-volatile memory system of claim 39, wherein the memory system maintains the experience count of the blocks as an attribute of the corresponding block that is associated with the block'"'"'s address.

49. The non-volatile memory system of claim 39, wherein said selection is for a block in which to store user data.

50. The non-volatile memory system of claim 49, wherein the user data is relocated from another location on the memory circuit.

51. The non-volatile memory system of claim 39, wherein said selection is for a block in which to store system data.

52. The non-volatile memory system of 39, wherein the list of free blocks is formed from less than all of the free blocks in the pool of free blocks.

53. The non-volatile memory system of 39, wherein the list of free blocks is formed from all of the free blocks in the pool of free blocks.

54. The non-volatile memory system of 39, wherein the experience count is the number of erase cycles experienced.