Tracking the least frequently erased blocks in non-volatile memory systems

• US 7,096,313 B1
• Filed: 10/28/2002
• Issued: 08/22/2006
• Est. Priority Date: 10/28/2002
• Status: Expired due to Term

• 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): Vital, Pierre M.
• Application Number:
  US10/281,824
• Time in Patent Office: 1,394 Days
• Field of Search: 365/185.29, 365/185.33, 365/230.03, 711/103, 711/165
• 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

Abstract

Methods and apparatus for performing wear leveling in a non-volatile memory system are disclosed. According to one aspect of the present invention, one method for processing elements included in a non-volatile memory of a memory system includes obtaining erase counts associated with elements and grouping a number of the elements into a first set. Each element has an associated erase count that substantially indicates a number of times the element has been erased. Grouping the number of elements into the first set includes selecting elements included in the plurality of elements which have the lowest associated erase counts of the erase counts associated with the plurality of elements. The method also includes storing the erase counts associated with the first set in a memory component substantially within a table.

Claims

1. A method for processing elements included in a non-volatile memory of a memory system, each element having an associated erase count, the method comprising:

identifying a first set of erased elements, wherein the erased elements included in the first set of erased elements are less worn than erased elements not included in the first set of erased elements, by identifying a number of erased elements for which the associated erase counts are relatively low and grouping the identified erased elements into the first set;

placing entries associated with the first set of elements into a data structure;

sorting the entries within the data structure; and

identifying a first element within the first set of elements using the sorted entries, wherein the first element is less worn than other elements included in the first set of elements;

determining when a second element not included in the first set is to be erased;

removing the first element from the first set when it is determined that the second element is to be erased;

copying one of contents of the second element and new contents to replace the contents of the second element into the first element;

erasing the contents from the second element; and

adding the second element to the first set.

2. The method of claim 1, wherein the step of identifying the first set of elements comprises:

obtaining erase counts associated with a plurality of elements, the plurality of elements including erased elements and elements containing data, wherein each element included in the plurality of elements has an associated erase count, the associated erase count of each element being arranged to indicate a number of times the element has been erased; and

defining a first set of erased elements by selecting erased elements having the lowest associated erase counts relative to the erase counts associated with the plurality of elements;

and wherein the placing step comprises;

storing the erase counts associated with the first set in a memory component substantially within a table, wherein the memory component is associated with the memory system.

3. The method of claim 1 wherein the step of defining a first set of erased elements includes:

comparing the erase counts associated with the plurality of erased elements; and

identifying a predetermined number of erased elements having the lowest associated erase counts of the erase counts.

4. The method of claim 1 wherein the sorting step comprises:

sorting the erased elements in the first set of erased elements according to the erase count associated with each erased element in the first set.

5. The method of claim 4 wherein sorting the elements in the first set of erased elements includes sorting the erase counts within the table.

6. The method of claim 4 wherein the step of identifying the first element comprises:

identifying an element having the lowest erase count associated with the first set of erased elements.

7. The method of claim 1 wherein the non-volatile memory is flash memory.

8. The method of claim 7 wherein the plurality of elements are blocks, and the first set of erased elements is a set of least frequently erased blocks.

9. The method of claim 8 wherein the first set of erased elements includes spare blocks.

10. The method of claim 8 wherein obtaining the erase counts includes obtaining the erase counts from an erase count block.

11. The method of claim 8 wherein the flash memory is NAND flash memory.

12. The method of claim 1 wherein each element has an associated erase count, and identifying the first set of elements includes:

identifying a number of erased elements for which the associated erase counts are relatively low; and

grouping the number of erased elements for which the associated erase counts are relatively low into the first set.

13. The method of claim 12 wherein the entries include the associated erase counts of the elements in the first set.

14. The method of claim 1 wherein removing the first element from the first set includes removing an entry associated with the first element from the data structure, and adding the second element to the first set includes placing an entry associated with the first set of elements into a data structure.

15. The method of claim 14 further including:

resorting the entries within the data structure; and

identifying a third element within the first set of elements using the sorted entries, wherein the third element is less worn than other elements included in the first set of elements.

16. The method of claim 1 wherein the elements each include a section that is arranged to contain data, and wherein the section included in each of the elements included in the first set of elements is substantially empty.

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

18. A flash memory system, comprising:

an array of non-volatile memory cells, arranged into a plurality of physical blocks;

system memory, comprising non-volatile memory for storing at least one data structure comprised of a plurality of entries, the entries including erase counts of physical blocks of the array; and

memory controller circuitry, coupled to the array and the system memory, and programmed to perform a plurality of operations comprising;

identifying a first set of erased physical blocks, wherein the erased physical blocks included in the first set of erased physical blocks are less worn than erased physical blocks not included in the first set of erased physical blocks, by identifying a number of erased physical blocks for which the associated erase counts stored in the system memory are relatively low and grouping the identified erased physical blocks into the first set;

placing entries associated with the first set of physical blocks into a first data structure;

sorting the entries within the first data structure;

identifying a first physical block within the first set of physical blocks using the sorted entries, wherein the first physical block is less worn than other physical blocks included in the first set of physical blocks;

determining when a second physical block not included in the first set is to be erased;

removing the first physical block from the first set when it is determined that the second physical block is to be erased;

copying one of contents of the second physical block and new contents to replace the contents of the second physical block into the first physical block;

erasing the contents from the second physical block; and

adding the second physical block to the first set.

19. The system of claim 18, wherein the memory controller circuitry comprises:

code devices for storing program instructions corresponding to the plurality of operations; and

a processor for executing the software code devices.

20. The system of claim 19, wherein the code devices are arranged according to a system architecture comprising:

a system manager module, including an erase count block management submodule corresponding to the plurality of operations.

21. The system of claim 18, wherein the array and the memory controller circuitry are arranged into a flash memory device, and further comprising:

a host interface, for interfacing the flash memory device to a host system.

22. The system of claim 18, further comprising:

a host interface, for interfacing the array to a system bus;

wherein the memory controller circuitry is arranged into a host processor coupled to the system bus.

23. The system of claim 18, wherein the operation of removing the first physical block from the first set includes removing an entry associated with the first physical block from the first data structure, and adding the second physical block to the first set includes placing an entry associated with the first set of physical blocks into the first data structure.

24. The system of claim 23, wherein the plurality of operations further comprises:

resorting the entries within the first data structure; and

identifying a third physical block within the first set of physical blocks using the sorted entries, wherein the third physical block is less worn than other physical blocks included in the first set of physical blocks.