Method of flash memory management

• US 7,409,490 B2
• Filed: 04/15/2006
• Issued: 08/05/2008
• Est. Priority Date: 04/15/2006
• Status: Expired due to Fees

• Current Assignee: Yi Chun Liu
• Original Assignee: Yi Chun Liu
• Inventors: Liu, Yi-Chun
• Primary Examiner(s): Bragdon; Reginald G.
• Assistant Examiner(s): Dinh; Ngoc V
• Application Number:
  US11/279,889
• Publication Number:
  US 20070245064A1
• Time in Patent Office: 843 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
• CPC Class Codes: G11C 16/349 Arrangements for evaluating degradation, retention or wearout, e.g. by counting erase cycles
• CPC Class Codes: G11C 16/3495 Circuits or methods to detect or delay wearout of nonvolatile EPROM or EEPROM memory devices, e.g. by counting numbers of erase or reprogram cycles, by using multiple memory areas serially or cyclically
• CPC Class Codes: G11C 29/76 using address translation or modifications

Abstract

A wear-leveling method for managing flash memory is provided, including an access process to consult a translation table when accessing a data block in the data region, and a reconstruction process to reconstruct the translation table when powering on the flash memory. The translation table is defined to include a plurality of entries, and each entry includes a physical address field and an enduring counter field. The logical address of a data block is used as input to map to the entry in the translation table. The access process, further including a read process and an erase/program process, maps the logical address to the physical address, and uses the enduring counter to determine whether an update is required to avoid the disturbance. The reconstruct process uses the information stored in the spare data region to reconstruct the translation table for the access process to consult during flash memory accesses.

Claims

1. A wear-leveling method for managing flash memory, said flash memory having a data region and a spare region, said spare region further storing a logical address and an enduring counter (EC) for a data block in said data region, said wear-leveling method using a translation table, and a wear-leveling algorithm comprising the following steps of:

reconstructing said translation table when said flash memory is powered on;

determining whether an operation is a read operation or an erase/program operation;

proceeding to a read process if the operation is a read operation;

otherwise, proceeding to an erase/program process if the operation is an erase/program operation; and

waiting for a next operation and returning to said step of determining whether an operation is a read operation until no further operations;

wherein variables n, p, q, m, x, BaseEC, MaxEC and Reverse are defined and used in said wear-leveling algorithm according to the following definition and rules;

n being a number of data blocks in an access region;

p being a logical address space, and n>

p;

q being a pointer pointing to an unused block;

m being maximum difference in a number of erase/program operations

between data blocks allowable within said access region;

x being a number of bits in an enduring counter field in said translation table, and 2^x>

2×

(m+n), m>

2×

n;

BaseEC being a minimum enduring counter value within said access region;

MaxEC being a maximum enduring counter value within said access region; and

Reverse being a Boolean variable indicating a condition of EC usage.

2. The method as claimed in claim 1, wherein said step of reconstructing said translation table further comprises the steps of:

initializing BaseEC equal to EC value of a first block of said access region, MaxEC equal to EC value of a second block of said access region, and Reverse equal to false;

determining whether BaseEC>

MaxEC;

if so, swapping BaseEC and MaxEC;

repeating the following steps for all the remaining blocks of said access region until all the remaining blocks are processed;

assigning EC of a block to BaseEC if Reverse is true, and said EC of the block meets the condition EC>

2<sup>(x−

1)</sup>Λ

BaseEC>

EC;

assigning EC of the block to MaxEC if Reverse is true, and said EC of the block meets the condition EC<

2<sup>(x−

1)</sup>Λ

MaxEC<

EC;

setting Reverse to true and assigning EC of the block to MaxEC if Reverse is false, BaseEC>

EC, and (BaseEC−

EC)>

(m+n);

assigning EC of the block to BaseEC if Reverse is false, BaseEC>

EC, and (BaseEC−

EC)<

=(m+n);

setting Reverse to true and assigning EC of the block to BaseEC if Reverse is false, EC>

MaxEC, and (EC−

MaxEC)>

(m+n); and

assigning EC of the block to MaxEC if Reverse is false, EC>

MaxEC, and (EC−

MaxEC)<

=(m+n).

3. The method as claimed in claim 1, wherein said read process further comprises the following steps of:

finding a physical address in said translation table corresponding to said logical address;

using said physical address to find data in said flash memory; and

returning said data to said read operation.

4. The method as claimed in claim 1, wherein said erase/program process further comprises the following steps of:

incrementing MaxEC and q, respectively;

determining whether q>

=n;

if so, assigning p to q;

writing the data to be programmed and MaxEC to an empty block pointed to by q;

reading original data not to be programmed in original data block according to said logical address, writing said original data to said empty block and marking the block as used;

erasing said original data and marking said original data block empty, and updating said translation table;

determining whether a value of the EC of said original data block is BaseEC;

if so, setting BaseEC to a next minimum EC value in said access region which is greater than or equal to original BaseEC;

determining whether (MaxEC−

BaseEC)>

(m−

2*n);

if not, ending said erase/program process;

incrementing MaxEC and q, respectively;

determining whether q>

=n;

if so, assigning p to q;

reading data in the block having EC value equal to BaseEC, writing the data and MaxEC to an empty block pointed to by q and marking the block as used, erasing said block having EC value equal to BaseEC and marking the erased block as empty, and updating said translation table; and

setting BaseEC to a next minimum EC value in said access region which is greater than or equal to original BaseEC.