STOCHASTIC BLOCK ALLOCATION FOR IMPROVED WEAR LEVELING

• US 20120265922A1
• Filed: 04/14/2011
• Published: 10/18/2012
• Est. Priority Date: 04/14/2011
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Post, Daniel J., Wakrat, Nir J.
• Granted Patent: US 8,762,625 B2
• Time in Patent Office: Days
• 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
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 7/588 Random number generators, i.e. based on natural stochastic processes
• CPC Class Codes: G11C 16/349 Arrangements for evaluating degradation, retention or wearout, e.g. by counting erase cycles

Abstract

Systems and methods are disclosed for stochastic block allocation for improved wear leveling for a system having non-volatile memory (“NVM”). The system can probabilistically allocate a block or super block for wear leveling based on statistics associated with the block or super block. In some embodiments, the system can select a set of blocks or super blocks based on a pre-determined threshold of a number of cycles (e.g., erase cycles and/or write cycles). The block or super block can then be selected from the set of super blocks. In other embodiments, the system can use a fully stochastic approach by selecting a block or super block based on a biased random variable. The biased random variable may be generated based in part on the number of cycles associated with each block or super block of the NVM.

Claims

1. A method for super block allocation of a plurality of super blocks of a non-volatile memory (“

NVM”

) for wear leveling, the method comprising;

selecting a set of super blocks from the plurality of super blocks that satisfy a pre-determined threshold of a total distribution of the number of cycles of the plurality of super blocks;

allocating a super block of the set of super blocks for wear leveling, wherein the super block is stochastically selected from the set of super blocks; and

performing wear leveling on the NVM using the allocated super block.

2. The method of claim 1, wherein the plurality of super blocks comprises the free super blocks of the NVM.

3. The method of claim 1, wherein the number of cycles is at least one of a number of erase cycles or a number of write cycles.

4. The method of claim 1, wherein the determining the set of super blocks further comprises:

determining that a lower-cycled super block needs to be allocated for wear leveling; and

selecting the set of super blocks, wherein each super block of the set of super blocks has a number of cycles that is one of lower than or equal to the pre-determined threshold.

5. The method of claim 4, wherein at least one super block of the set of super blocks is a lowest-cycled super block.

6. The method of claim 4, wherein each super block of the set of super blocks has a number of cycles that is in a pre-determined percentile of the total distribution of the number of cycles of the plurality of super blocks, wherein the pre-determined percentile is selected based on at least one statistical parameter of the total distribution.

7. The method of claim 1, wherein the determining the set of super blocks further comprises:

determining that a higher-cycled super block needs to be allocated for wear leveling; and

selecting the set of super blocks, wherein each super block of the set of super blocks has a number of cycles that is one of greater than or equal to the pre-determined threshold.

8. The method of claim 7, wherein one super block of the set of super blocks is a highest-cycled super block.

9. The method of claim 7, wherein each super block of the set of super blocks has a number of cycles that is in a pre-determined percentile of the total distribution of the number of cycles of the plurality of super blocks, wherein the pre-determined percentile is selected based on at least one statistical parameter of the total distribution.

10. The method of claim 1, wherein the allocating further comprises allocating the super block of the set of super blocks based on at least one statistical parameter.

11. The method of claim 10, wherein the at least one statistical parameter is at least one of the mean of the total distribution of the number of cycles of the plurality of super blocks and the median of the total distribution of the number of cycles of the plurality of super blocks.

12. The method of claim 1, wherein the allocating the super block further comprises allocating a random super block from the set of super blocks.

13. A memory interface for accessing a non-volatile memory (“

NVM”

) having a plurality of blocks, wherein each block is associated with a number of cycles, the memory interface comprising;

a bus controller operative to communicate with the NVM; and

control circuitry operative to;

determine that a block needs to be allocated;

generate a biased random variable based at least in part on the number of cycles associated with each block of the plurality of blocks of the NVM; and

allocate a block from the plurality of blocks based at least on the biased random variable.

14. The memory interface of claim 13, wherein the number of cycles is at least one of a number of erase cycles or a number of write cycles.

15. The memory interface of claim 13, wherein the control circuitry is further operative to direct the bus controller to perform wear leveling on the NVM using the allocated block.

16. The memory interface of claim 13, wherein the control circuitry is further operative to assign a plurality of weights to the plurality of blocks, wherein each weight of the plurality of weights is assigned to a block based on the number of cycles associated with the block.

17. The memory interface of claim 16, wherein the plurality of weights have lower or higher values as the number of cycles corresponding to the plurality of blocks increases.

18. The memory interface of claim 16, wherein the control circuitry is further operative:

generate a sum of the plurality of weights; and

select the biased random variable based on the sum of the plurality of weights.

19. The memory interface of claim 18, wherein the control circuitry is further operative to:

subtract the sum of the plurality of weights by one to generate an upper range value;

select the biased random variable with a range between zero and the upper range value.

20. The memory interface of claim 18, wherein the control circuitry is further operative to:

for a block of the plurality of blocks, compare the weight assigned to the block to the biased random variable;

determine whether the biased random variable is less than the weight assigned to the block;

in response to determining that the biased random variable is less than the weight assigned to the block, allocate the block for wear leveling.

21. The memory interface of claim 20, wherein in response to determining that the biased random variable is greater than or equal to the weight assigned to the block, the control circuitry is further operative to:

update the biased random variable by subtracting the weight assigned to the block from the biased random variable; and

select another block of the plurality of blocks for comparison to the updated random variable.

22. A system comprising:

a non-volatile memory (“

NVM”

) comprising a plurality of super blocks;

a bus controller operative to communicate with the NVM; and

control circuitry operative to;

determine whether a lower-cycled block needs to be allocated for wear leveling;

in response to determining that a lower-cycled super block needs to be allocated for wear leveling, select a set of super blocks, wherein each super block of the set of super blocks has a number of cycles that is within a pre-determined range of the number of cycles of a lowest-cycled block of the plurality of super blocks; and

allocate a super block of the set of super blocks for wear leveling, wherein the super block is stochastically selected from the set of super blocks.

23. The system of claim 22, wherein the number of cycles is at least one of a number of erase cycles or a number of write cycles.

24. The system of claim 22, wherein the set of super blocks comprises free super blocks.

25. The system of claim 22, wherein the control circuitry is operative to direct the bus controller to perform wear leveling on the NVM using the allocated super block.

26. The system of claim 22, wherein the pre-determined range has a lower end equal to the number of cycles of the lowest-cycled block, and an upper end equal to a pre-determined percentile of a total distribution of a number of cycles of the plurality of super blocks.

27. The system of claim 22, wherein in response to determining that a higher-cycled block needs to be allocated for wear leveling, the control circuitry is operative to:

select a set of super blocks, wherein each super block of the set of super blocks has a number of cycles that is within a pre-determined range of the number of cycles of a highest-cycled block of the plurality of super blocks; and

allocate a super block of the set of super blocks for wear leveling.

28. The system of claim 27, wherein the pre-determined range has a lower end equal to a pre-determined percentile of a total distribution of a number of cycles of the plurality of super blocks, and an upper end equal to the number of cycles of the highest-cycled super block.