Method and apparatus for flash memory wear-leveling using logical groups

• US 7,797,481 B2
• Filed: 06/29/2007
• Issued: 09/14/2010
• Est. Priority Date: 06/14/2007
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Cheon, Won-Moon, Park, Chan-Ik, Lee, Yang-Sup
• Primary Examiner(s): Bragdon; Reginald G
• Assistant Examiner(s): Sadler; Nathan
• Application Number:
  US11/771,531
• Publication Number:
  US 20080313505A1
• Time in Patent Office: 1,173 Days
• Field of Search: None
• 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

A memory system and corresponding method of wear-leveling are provided, the system including a controller, a random access memory in signal communication with the controller, and another memory in signal communication with the controller, the other memory comprising a plurality of groups, each group comprising a plurality of first erase units or blocks and a plurality of second blocks, wherein the controller exchanges a first block from a group with a second block in response to at least one block erase count within the group; and the method including receiving a command having a logical address, converting the logical address into a logical block number, determining a group number for a group that includes the converted logical block number, and checking whether group information comprising block erase counts for the group is loaded into random access memory, and if not, loading the group information into random access memory.

Claims

1. A method of wear-leveling a memory device, the method comprising:

grouping a first region of the device into a plurality of logical groups each comprising a plurality of logical block numbers;

checking whether logical group information comprising block erase counts for logical block numbers in a logical group is loaded into random access memory (“

RAM”

), and if not, loading the logical group information into RAM;

calculating a group erase count for the logical group from the block erase counts in RAM wherein the calculated group erase count is one of a minimum, maximum or average of all of the block erase counts for the logical block numbers currently in the logical group;

receiving a command having a logical address;

converting the logical address into a logical block number;

determining a logical group number for a current logical group that includes the converted logical block number; and

checking whether an accumulated number of merge operations is greater than a predetermined number, and if so, selecting a logical block number currently classified as a data block number and having a minimum block erase count from another logical group having a minimum group erase count, and swapping the selected logical block number from the other logical group into the current logical group in exchange for a logical block number currently classified as a free block number and having a maximum block erase count.

2. A method as defined in claim 1 wherein the command is a write command, further comprising checking whether a log block for the same logical block number already exists, and if so, copying write data to the associated log block.

3. A method as defined in claim 1 wherein the command is a write command, further comprising:

checking if a free block is available, and if none are free, performing a merge operation to free a block; and

copying write data to the free block.

4. A method as defined in claim 1, further comprising determining a physical block address corresponding to the logical block number.

5. A method as defined in claim 1 wherein the command is a read command, further comprising:

reading a mapping table entry associated with requested data, and if it indicates that a log block contains the requested data, returning the requested data from the log block; and

if the mapping table entry associated with the requested data indicates that the latest data is in the data block, reading the data block itself and returning the requested data from the data block.

6. A method as defined in claim 1, further comprising:

checking whether the variance between an erase count for a free block and an erase count for a data block in a group is greater than a predetermined variance, and if so, swapping the free block with the data block.

7. A method as defined in claim 6, further comprising calculating a group erase count whenever a free block is used.

8. A method as defined in claim 6 wherein the erase count for the free block is a maximum erase count for all free blocks, and the erase count for the data block is a minimum erase count for all data blocks in the group.

9. A method as defined in claim 8 wherein the erase count for the group is a minimum erase count for all groups.

10. A method as defined in claim 1, the memory device comprising at least one of DRAM, PRAM, MRAM, FRAM, EEPROM, or Flash Memory.

11. A method as defined in claim 1, further comprising checking whether the accumulated number of merge operations is greater than a predetermined number, and if so, calculating group erase counts for each of a plurality of groups.

12. A method as defined in claim 1, further comprising address translating a logical block number to a physically addressable memory block as data is written to or read from the memory block.

13. A method as defined in claim 12 wherein the physically addressable memory blocks comprise non-volatile memory.

14. A method as defined in claim 1 wherein the logical block numbers are initially interleaved among the logical groups.

15. A method of wear-leveling a memory device, the method comprising:

dividing a first region of the device into a plurality of logical groups wherein each logical group comprises a plurality of logical erase units or logical blocks;

calculating a group erase count for each logical group in response to at least one block erase count from the logical group, wherein the calculated group erase count for a logical group is a minimum, maximum or average of all of the block erase counts in said logical group; and

replacing a logical block in one logical group in response to a comparison of the calculated group erase counts when an accumulated number of merge operations is greater than a predetermined number, wherein a logical block having a maximum block erase count is swapped out for a logical block having a minimum block erase count from a logical group having a minimum group erase count,

wherein a logical block currently classified as a free block and having a maximum block erase count is swapped out for a logical block currently classified as a data block and having a minimum block erase count.

16. A method as defined in claim 15 wherein the blocks are interleaved among the plurality of logical groups.

17. A method as defined in claim 15, further comprising performing a merge operation to free a block, wherein the step of replacing a block is performed when a number of merge operations reaches a threshold.

18. A method as defined in claim 17 wherein the step of performing a merge operation is performed when there are no free blocks remaining.

19. A method as defined in claim 15, further comprising defining a second region comprising free blocks within the memory.

20. A method as defined in claim 19 wherein the first region is a data region and the second region is a log or free region.

21. A method as defined in claim 19, further comprising:

defining a meta region within the memory; and

exchanging a block from the second region with a block from the meta region having a different block erase count.

22. A method as defined in claim 19, further comprising calculating a group erase count for each group, wherein exchanging a block from the second region with a block having a different block erase count is responsive to all of the calculated group erase counts.

23. A method as defined in claim 15, further comprising accumulating a block erase count for at least one of said plurality of blocks in each group.

24. A method as defined in claim 15 wherein calculating a group erase count comprises loading block erase count information for blocks of one group at a time into random access memory (“

RAM”

), and calculating a group erase count for the loaded group.

25. A method as defined in claim 15, further comprising defining a reserved region within the memory for storing blocks reserved for replacing defective blocks.

26. A method as defined in claim 15, further comprising defining a meta region within the memory for storing at least one of erase counts for all blocks or mapping information indicative of mapping blocks to physical block addresses.

27. A method as defined in claim 15, further comprising reserving a spare area in each block for storing an erase count of the block.

28. A method as defined in claim 15 wherein each block comprises a plurality of read/write units or pages.

29. A method as defined in claim 15, further comprising accumulating a block erase count for each of said plurality of blocks in each group.

30. A method as defined in claim 15 wherein said block erase count corresponds to the total number of erasures for a block.

31. A wear-leveling memory system comprising:

a controller;

a random access memory (“

RAM”

) in signal communication with the controller; and

another memory in signal communication with the controller, the other memory comprising a plurality of logical groups, each logical group comprising a plurality of first logical erase units or logical blocks and a plurality of second logical blocks,

wherein the controller is disposed for exchanging a first logical block from a logical group with a second logical block in response to at least one block erase count within the logical group by calculating a group erase count for each logical group in response to at least one block erase count from the logical group where the group erase count is a minimum, maximum or average of all the block erase counts in the logical group, and replacing a logical block in the logical group in response to a comparison of the calculated group erase counts when an accumulated number of merge operations is greater than a predetermined number where a logical block having a maximum block erase count is swapped out for a logical block having a minimum block erase count from a logical group having a minimum group erase count,

wherein a logical block currently classified as a free block and having a maximum block erase count is swapped out for a logical block currently classified as a data block and having a minimum block erase count.

32. A system as defined in claim 31 wherein the RAM size is sufficient to store all block erase counts for one group at a time, but insufficient to store all block erase counts for all groups at once.

33. A system as defined in claim 31 wherein the first blocks comprise data blocks and the second blocks comprise free blocks.

34. A system as defined in claim 31 wherein the first blocks comprise meta blocks and the second blocks comprise free blocks.

35. A system as defined in claim 31, the other memory further comprising blocks defining at least one of erase counts or physical address mapping information for the first blocks.

36. A system as defined in claim 31, the first blocks each comprising a data portion and a spare portion, the spare portion for defining at least one of erase counts or physical address mapping information for the first blocks.

37. A system as defined in claim 31 wherein the controller comprises program control steps stored in the other memory.

38. A system as defined in claim 31, further comprising a read-only memory (“

ROM”

) in signal communication with the controller, wherein the controller comprises program control steps stored in the ROM.

39. A system as defined in claim 31 wherein the pluralities of first logical block numbers are arranged in an interleaved order among the initialized logical groups.