MANAGING METHOD FOR FLASH STORAGE AND STORAGE SYSTEM

Abstract

A managing method for a flash storage includes: sorting a plurality of blocks within the flash storage into precise blocks and imprecise blocks; and managing the sorted blocks as a plurality of free block pools. The management includes performing garbage collection and wear leveling, and the wear leveling is performed based on CEW (Cumulative Effective Wearing), the CEW indicating cumulative cell damage induced by performing a plurality of operations on a specific block. A storage system includes a memory array; and a memory controller sorting a plurality of blocks of the memory array based on error rates, applying erase voltages corresponding to the error rates, respectively, when data stored in the blocks are erased, controlling each of the erase voltages to have a value scaled down from a standard voltage, and performing incremental step pulse programming on one or more of the blocks.

Claims

1. A managing method for a flash storage, the method comprising: sorting a plurality of blocks within the flash storage into precise blocks and imprecise blocks; and managing the sorted blocks as a plurality of free block pools, wherein the management includes performing garbage collection and wear leveling, and wherein the wear leveling is performed based on CEW (Cumulative Effective Wearing), the CEW indicating cumulative cell damage induced by performing a plurality of operations on a specific block.

2. The managing method of claim 1, wherein the management is performed to maintain target numbers of the precise and imprecise blocks while ensuring even block wearing.

3. The managing method of claim 1, wherein deep erase and shallow erase are performed on each of the precise blocks and each of the imprecise blocks, respectively.

4. The managing method of claim 3, wherein a voltage applied during the shallow erase is lower than a voltage applied during the deep erase.

5. The managing method of claim 3, wherein a plurality of voltages are applied to divide the shallow erase into a plurality of steps, the plurality of steps corresponding to a plurality of erase modes, respectively.

6. The managing method of claim 1, wherein the plurality of free block pools corresponds to a plurality of error tolerance levels, respectively, and a free block is selected from a corresponding one of the free block pools meeting an error tolerance requirement.

7. The managing method of claim 6, wherein, when shallow erase or deep erase is performed on the selected block, an erase mode is determined based on a current size of the corresponding one of the free block pools and recent request history.

8. The managing method of claim 1, wherein incremental step pulse programming is performed in a P/E (Program/Erase) cycle.

9. The managing method of claim 8, wherein the incremental step pulse programming is performed on a first block among the imprecise blocks during a first time interval and on a second block among the precise blocks during a second time interval, the first time interval being shorter time interval than the second time interval.

10. The managing method of claim 1, wherein a first block among the precise blocks and a second block among the imprecise blocks are allocated to allow different error rates.

11. The managing method of claim 1, wherein the CEW is obtained based on a first weight of shallow erase and a second weight of deep erase, and wherein the first weight of the shallow erase is different from the second weight of the deep erase.

12. A managing method for a flash storage, the method comprising: sorting a plurality of blocks based on error rates; and applying erase voltages corresponding to the error rates, respectively, when data stored in the blocks are erased, wherein each of the erase voltages is controlled to have a value scaled down from a standard voltage.

13. The managing method of claim 12, wherein the reference voltage is used during deep erase, and each of the erase voltages having the scaled-down value is used during shallow erase.

14. The managing method of claim 12, wherein the sorted blocks are managed as a plurality of free block pools, and wherein when erase is performed, an erase mode is determined based on a current size of a corresponding one of the free block pools and recent request history.

15. The managing method of claim 12, wherein incremental step pulse programming is performed on one or more of the blocks.

16. The managing method of claim 15, wherein the blocks include precise blocks and imprecise blocks, and wherein the incremental step pulse programming is performed on a first block among the imprecise blocks during a first time interval and on a second block among the precise blocks during a second time interval, the first time interval being shorter than the second time interval.

17. A storage system comprising: a memory array; and a memory controller configured to: sort a plurality of blocks of the memory array based on error rates; apply erase voltages corresponding to the error rates, respectively, when data stored in the blocks are erased; control each of the erase voltages to have a value scaled down from a standard voltage; and perform incremental step pulse programming on one or more of the blocks.

18. The storage system of claim 17, wherein the memory controller determines an erase mode based on the error rates.

19. The storage system of claim 17, wherein the memory controller manages the sorted blocks as a plurality of free block pools and determines an erase mode based on a current size of a corresponding one of the free block pools and recent request history, when erase is performed.

20. The storage system of claim 17, wherein the memory controller operates using an application program, the memory controller including the application program, or a file system including the application program.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0014] FIG. 1 is a cross-sectional view illustrating a flash memory cell.

[0015] FIG. 2 illustrates correlations among MPEG frames and error propagation and compression ratios in the MPEG frames.

[0016] FIG. 3 illustrates shallow erase and ISPP (Incremental Step Pulse Programming) in accordance with an embodiment of the present disclosure.

[0017] FIG. 4 illustrates block allocation for each erase mode.

[0018] FIG. 5 illustrates block degradation and effective wearing.

[0019] FIG. 6 schematically illustrates a system in accordance with an embodiment of the present disclosure.

[0020] FIG. 7 illustrates distributions of threshold voltages.

[0021] FIG. 8 illustrates allocation of precise blocks and imprecise blocks in a free block pool.

[0022] FIG. 9 illustrates an example of counter reset.

[0023] FIG. 10 illustrates block migration in a free block pool and a used block pool.

[0024] FIG. 11 illustrates selection of a victim block associated with cumulative effective wearing.

DETAILED DESCRIPTION

[0025] Hereafter, embodiments of the present disclosure will be described in detail with reference to the accompanying drawings such that various embodiments of the present disclosure can be carried out by those skilled in the art to which the present disclosure pertains. Among reference numerals marked on the respective drawings, like reference numerals represent the same components.

[0026] In describing the present disclosure, detailed descriptions for related publicly-known technologies may be omitted in order not to unnecessarily obscure subject matters of the present disclosure.

[0027] The terms such as first and second may be used to describe various components, but the components are not limited by the terms, and the terms are used only to distinguish one component from another component.

[0028] The terms used in this specification will be briefly described as follows.

[0029] ‘Flash storage’ may refer to a storage including a flash memory among nonvolatile memories.

[0030] ‘Memory cell’ or ‘cell’ may refer to one unit element capable of storing binary information therein.

[0031] ‘Flash translation layer’ or ‘FTL’ may refer to middleware for sector-block translation in order to use a block-based flash memory in a sector-based system or application program.

[0032] In the present disclosure, an expression ‘deeply’ in a program operation or erase operation may indicate that a standard voltage or normal voltage which does not cause an error is applied. However, an expression ‘shallowly’ in a program operation or erase operation may indicate that a weak voltage is applied to such an extent to endure or allow a few errors, in order to reduce damage to a memory cell. ‘Shallow’ voltage may be used to indicate a voltage lower than ‘deep’ voltage. Furthermore, it should be noted that various numerical values presented throughout this specification are only used for convenience of description, or used for an experiment or simulation for verifying the effects of the present disclosure, and the technical ideas of the present disclosure are not limited thereto.

Error Tolerance-Aware Block Allocation

[0033] One of aspects of embodiments of the present disclosure relates to a method capable of improving the lifetime of a storage using a flash memory by selectively applying shallow erase to a block having error-tolerant data stored therein. More specifically, a shallow erase technique is adopted to manage blocks having different erase modes. Furthermore, while ISPP (Incremental Step Pulse Programming) is more rapidly and normally performed on a block which has been erased shallowly, data matched with an error tolerance level is allocated to the corresponding block. For example, ISPP may be performed on a first block (e.g., an imprecise block) having been erased shallowly during a first time interval that is shorter than a second time interval during which ISPP is performed on a second block (e.g., a precise block) having been erased deeply. As shown in FIG. 3 which comparatively illustrates applying a shallow erase voltage and a deep erase voltage, the interval between voltage distributions of program states by shallow erase and fine-grained ISSP is narrower than the interval between voltage distributions of program states by deep erase. For reference, in FIG. 3, memory cells each capable of storing 2-bit binary information therein are taken as example for description.

[0034] When a first block of a flash memory is deeply erased, the first block is referred to as a precise block, and when a second block of the flash memory is shallowly erased, the second block is referred to as an imprecise block. Since different levels of erase voltages have been used in the respective blocks, the blocks have different error rates. When a write request is received from a system, a controller or application program which controls an operation of the flash memory, a block which meets the error tolerance of data is allocated. Error-intolerant data should be allocated only to a precise block, while error-tolerant data can be allocated to either a precise block or an imprecise block. Using a precise block may be avoided as much as possible since it is more costly in terms of EW (Effective Wearing). Block allocation is performed for each erase mode according to the precision (e.g., an error tolerance level) of each block in a free block pool. For example, as illustrated in FIG. 4, a first erase mode for a precise block which tolerates no errors (e.g., error tolerance level 0) is represented by erase mode 0, a second erase mode for an imprecise block with a middle error tolerance level (e.g., error tolerance level 1) is represented by erase mode 1, and a third erase mode for an imprecise block which tolerates relatively many errors (e.g., error tolerance level 2) is represented by erase mode 2. FIG. 4 illustrates that the deep erase and the shallow erase divided into two steps correspond the erase modes 0, 1 and 2, respectively. Although will be described below, a shallow erase voltage lower than a deep erase voltage may be scaled down to an extent in order to perform such an erase method.

[0035] Whenever a flash memory cell is erased, a tunnel oxide layer thereof gradually wears. During deep erase and shallow erase, different impacts are applied to the tunnel oxide layer because voltages having different magnitudes are applied during deep erase and shallow erase. In an embodiment, effective wearing (EW) indicates the cell damage that is induced by an erase operation depending on an erase voltage and has a value equal to the erase voltage normalized with a standard erase voltage used in deep erase. When shallow erase and deep erase are represented by EW, the EW of shallow erase may be less than 1 under the supposition that the EW of deep erase is normalized to 1. In consideration of normalization, CEW (Cumulative Effective Wearing) may be calculated as follows. The CEW may indicate cumulative cell damage induced by performing a plurality of operations (e.g., a plurality of erase operations) on a specific block. For example, if a block is deep-erased two times and shallow-erased five times with an EW of 0.5, the CEW of the block is 5.5 (=2×1+5×0.5). That is, deep erase and shallow erase have different weights (e.g., 1 and 0.5), and shallow erases may be divided into a plurality of steps. FIG. 5 illustrates examples in which EWs given to blocks for the respective erase modes 0, 1, and 2 are set to 1, 0.61, and 0.51, respectively.

Erase Mode-Aware Garbage Collection and Wear Leveling

[0036] Hereafter, erase mode-aware garbage collection and wear leveling, which are other features of embodiments of the present disclosure, will be described. In embodiments of the present disclosure, garbage collection and wear leveling schemes are designed to take into account multiple erase modes and different cell damages induced by the erase modes. The schemes jointly manage FBPs (Free Block Pools). That is, the schemes are operated to maintain the required numbers (or target numbers) of precise blocks and imprecise blocks while ensuring even block wearing. In particular, block wearing is evaluated in terms of CEW rather than P/E cycle counts. FIG. 6 illustrates the overview of an AxFTL (Approximate Flash Translation Layer) with functional blocks in accordance with an embodiment of the present disclosure. Suppose that all write requests each are marked with an error tolerance determined by a controller or application. The AxFTL in accordance with the embodiment illustrated in FIG. 6, manages multiples FBPs, one for each error tolerance level, and selects a free block from one of the FBPs which meets the error tolerance requirement. When a block is erased, the erase mode is determined based on the current size of the FPBs and the recent request history to minimize extra erase. Garbage collection and wear leveling are performed based on this determination as well as the CEW of the blocks.

[0037] The system 600 shown in FIG. 6 includes a memory controller 610, a file system 630, and a memory array 650 (e.g., NAND flash memory array). The memory controller 610 may refer to a hardware controller as well as firmware and software controller. In an embodiment, the memory controller 610 may include an internal memory (not shown) storing the AxFTL and a core (not shown) executing the AxFTL. For example, the core may include a micro control unit (MCU) or a central processing unit (CPU). In another embodiment, the AxFTL may be loaded on a dedicated memory (not shown) provided within the core, rather than the internal memory. The AxFTL according to an embodiment of the present disclosure may be implemented as an application program, and the memory controller 610 may operate using the application program. In an embodiment, the memory controller 610 may include the application program. In another embodiment, the file system 630 may include the application program.

Erase Voltage Scaling and Error Modeling

[0038] Hereafter, a method in accordance with an embodiment of the present disclosure, which models the scaling of erase voltage and a long-term impact to data retention error, will be described. Voltage scaling may be performed for shallow erase. Since voltage for shallow erase will be lower than voltage for deep erase, the magnitude of the voltage for shallow erase is scaled to a value of 0 to 1, when the voltage for deep erase is normalized to 1. It may be assumed that the threshold voltage distributions of cell data stored at multi levels statistically follow a Gaussian distribution as illustrated in FIG. 7, even though the threshold voltage distributions are not perfectly symmetric. FIG. 7 illustrates that an error occurs because some tails of the threshold voltage distributions of states S.sub.1 to S.sub.3 overlap each other. It should be noted that FIG. 7 is exaggerated for clear illustration of errors. The voltages marked in FIG. 7 represent reference voltages for a read operation and a voltage for verifying erase. The scaling is subjected to the following process. First, the probability density function of the threshold voltages is calculated. The probability density function is given by:

[00001]$\begin{array}{cc}P\left(v\right)={.Math.}_{k=1}^{K-1}{P}_S\left(S_k\right)\frac{1}{{\sigma }_k\sqrt{2\pi }}\exp \left(\frac{-{\left(v-{\mu }_k\right)}^2}{2{\sigma }_k^2}\right).& \mathrm{Equatoion}1\end{array}$

[0039] In Equation 1, K is the number of states, P.sub.S(S.sub.K) is the probability of state S.sub.K, and μ.sub.k and σ.sub.k are the mean and the standard deviation of state S.sub.K.

[0040] Second, an RBER (Raw Bit Error Rate) is calculated from the calculated probability density function. The error rate indicates that the tails of the probability density functions, which lie outside the reference voltage boundaries, overlap each other in FIG. 7, and RBERp due to program error may be calculated from the probability density function of threshold voltages as expressed by Equation 2 below:

[00002]$\begin{array}{cc}{\mathrm{RBER}}_p={.Math.}_{k=1}^{K-1}\left({\int }_{-\infty }^{V_{S_k}^{\mathrm{read}}}{P}_k\left(v\right)\mathrm{dv}+{\int }_{V_{S_{k+1}}^{\mathrm{read}}}^{\infty }{P}_k\left(v\right)\mathrm{dv}\right).& \mathrm{Equation}2\end{array}$

[0041] Third, when data is retained for a long time, charges stored in the floating gate of a memory cell gradually leak to increase program errors. Thus, this needs to be considered. It is natural that an error occurs due to data retention. The retention error is initially 0, and gradually increases over time. That is, the retention error becomes a function of time. Typically, retention error dominates program error by order of magnitude typically by up to 450 times after the maximum retention time of one year, and the RBER increases approximately 450 times. Specifically, although the retention error is initially zero and gradually increases over time, the worst-case retention error that is about 450 times as great as RBERp may be assumed at all times for conservative error estimation. Thus, the RBER that is the sum of RBERp and the worst-case retention error may be expressed as Equation 3 below:

RBER≈450.Math.RBERp   Equation 3.

[0042] Fourth, as a result of shallow erase that applies a low erase voltage, the verify voltage for verifying erase is shifted to the right by Equation 4 below:

ΔW.sub.v.sub.th=α.sub.c.Math.V.sub.nom.sup.erase.Math.(1−rv.sub.e)   Equation 4.

[0043] In Equation 4, V.sub.nom.sup.erase is the nominal erase voltage, rv.sub.e is the erase voltage scaling factor between 0 and 1, and α.sub.c is a scaling parameter required when the shifted value is numerically scaled. Therefore, the distribution centers μ.sub.k of all the threshold voltages v.sub.th and the reference voltages V.sub.S.sub.k.sup.read should be shifted to the right accordingly to maximize the margins between adjacent states. The shifted distribution centers and the shifted reference voltages are represented by μ.sub.k′ and V.sub.S.sub.k.sup.read′, respectively. Fifth, the distances between the distribution centers μ.sub.k and the reference voltages V.sub.S.sub.k.sup.read are scaled by the same scaling factor rv.sub.e, in order to set the new distribution center as Equation 5 below:

μ.sub.k′=μ.sub.k+(V.sub.S.sub.k.sup.read−μ.sub.k).Math.rv.sub.e   Equation 5.

[0044] On the other hand, the distribution widths of the threshold voltages remain unchanged since the same ISPP step voltage V.sub.p is used, and the width of the threshold voltage is proportional to V.sub.p. The reduced distance between reference voltages and the unchanged width of the threshold voltage result in a higher RBER. Therefore, V.sub.S.sub.k.sup.read may be numerically optimized from Equations 1 and 2 with new μ.sub.k′ to minimize the RBER.

[0045] Sixth, in order to promote convenience when applying the contents of the present disclosure, the RBER is mapped or inversely mapped to UBER (Uncorrectable Bit Error Rate) as expressed by Equation 6 below:

[00003]$\begin{array}{cc}\mathrm{UBER}=\frac{{.Math.}_{i=t+1}^i\left(\begin{array}{c}i\\ j\end{array}\right).Math.{\mathrm{RBER}}^j.Math.{\left(1-\mathrm{RBER}\right)}^{l-j}}{l}.& \mathrm{Equation}6\end{array}$

[0046] In Equation 6, l is the codeword length, and t is the error correction capability of the ECC. The above-described AxFTL model is not only used to determine the scaling factor rv.sub.e, but also used to evaluate the effect of embodiments of the present disclosure.

Specific Example of Error Tolerance-Aware Block Allocation

[0047] To take advantage of varying error tolerance of data, the AxFTL in accordance with an embodiment of the present disclosure performs error tolerance-aware block allocation that maps a free block to a write request based on the error tolerance. The AxFTL in accordance with an embodiment maintains M free block pools (FBPs), FBP.sub.0 through FBP.sub.M−1, grouped by their RBER. Each FBP is a pool of free blocks that are erased by one of M erase modes, resulting in substantially the same RBER as modeled in the above descriptions. Specifically, for m=0, 1, . . . , M−1, FPB.sub.m is a pool of free blocks with a RBER of RBER.sub.blk under a condition of (RBER.sub.m<RBER.sub.blk≤RBER.sub.m+1). Here, RBER.sub.0<RBER.sub.1<. . . <RBER.sub.M are the preset error tolerance boundaries. Among them, FBP.sub.0 is the pool of precise free blocks with virtually zero RBER. That is, FBP.sub.0 is bounded by RBER.sub.0=0 and very small RBER1. FIG. 8 illustrates the architectures of FBPs which are divided by the RBER according to such a principle.

[0048] A write request's UBER tolerance is first converted into the corresponding RBER tolerance, denoted by RBER.sub.app, based on Equation 6. When a write request with a RBER tolerance of RBER.sub.m<RBER.sub.app≤RBER.sub.m+1 is received, this write request is defined as ‘a write request of Mode m’ that demands a free block of erase mode m. To the write request of Mode m, a free block is allocated based on the following priorities.

[0049] 1) If N(FBP.sub.m)>0, where N(FBP.sub.m) is the number of free blocks in FBP.sub.m, a free block is allocated from FBP.sub.m.

[0050] If N(FBP.sub.m)≤N.sub.min after allocation, where N.sub.min is the minimum number of free blocks for garbage collection, garbage collection is invoked for FBP.sub.m.

[0051] 2) If N(FBP.sub.m)=0, a free block from the next available highest FBP is allocated, and garbage collection is invoked for FBP.sub.m.

[0052] 3) If N(FBP.sub.i)=0 for all 0≤i≤m, i.e., if there exists no free block that meets the error tolerance requirement, garbage collection is invoked to replenish FBP.sub.m with a free block, which is then allocated to the data.

[0053] The selection of a block within an FBP can be done by any conventional free block selection criteria. In an embodiment, each FBP keeps its free blocks sorted by CEW, and the one with the lowest CEW located at the head is selected.

[0054] The above-mentioned priority ensures that the most error-prone free block is preferred as long as it does not violate the application's error tolerance, which is the least costly in terms of storage lifetime. ‘Erase-on-demand’ is avoided whenever possible to minimize the performance degradation caused by maintaining multiple FBPs.

Hot and Cold Mode Prediction

[0055] To facilitate the preferred block allocation and avoid the non-preferred block allocation described above, it is desirable to maintain the size of the FBPs so that none of them become prematurely depleted before the storage is full. The AxFTL in accordance with an embodiment of the present disclosure proactively manages the number of free blocks in the FBPs based on the recent request history and the number of remaining free blocks in each FBP. Whenever a block is being erased, the most demanded and the least demanded erase modes are determined. The sufficiency and the deficiency of free blocks in each mode are measured by the ratio between the number of recent write requests and the number of remaining free blocks. Specifically, for Mode m, the ratio is defined as Equation 7 below:

[00004]$\begin{array}{cc}{R}_m=\frac{W_m}{N\left({\mathrm{FBP}}_M\right)-N_{\min }}.& \mathrm{Equation}7\end{array}$

[0056] In Equation 7, W.sub.m is the number of recent write requests of Mode m, and N.sub.min is the minimum number of free blocks for garbage collection.

[0057] The hot mode, m.sub.hot, and the cold mode, m.sub.cold, are the modes that are most demanded and least demanded, respectively, which are defined as Equation 8 below:

m.sub.hot=arg.sub.m max R.sub.m, m.sub.cold=arg.sub.m min R.sub.m   Equation 8.

[0058] In case that the above-described ratios (e.g., R.sub.0 to R.sub.M−1) are equal to one another, the hot and cold modes are selected based on the size of FBPs, which is another indirect measure of demand for write request modes. During garbage collection and wear leveling, which will be described below, m.sub.hot and m.sub.cold are used to determine which erase modes should be used and how the free blocks should move among FBPs.

[0059] To obtain W.sub.m efficiently, the number of write requests of Mode m is counted until the sum of the counters reaches W.sub.max. When the sum of the counters reaches W.sub.max, the counters are reset, and the counter values are used as W.sub.m until the next counter reset. FIG. 9 illustrates how m.sub.hot and m.sub.cold are selected in an example where M=3, W.sub.max=100, and N.sub.min=0. In FIG. 9, at time t.sub.0, three counters are reset. Between t.sub.0 and t.sub.1, 100 writes requests are received, including 20, 50, and 30 requests in Modes 0, 1, and 2, respectively, i.e., W.sub.0=20, W.sub.1=50, and W.sub.2=30. Since W.sub.0+W.sub.1+W.sub.2=W.sub.max, the counters are reset at t.sub.2, and these values are used until the next counter reset. An erase occurs at t.sub.2 before the next count reset, at which the size of three FBPs are 100, 200, and 100, respectively. R.sub.0, R.sub.1, and R.sub.2 are calculated as in Equation 7. As a result, the most demanded write mode is Mode 2 (i.e., m.sub.hot=2), and the least demanded write request mode is Mode 0 (i.e., m.sub.cold=0).

Erase Mode-Aware Garbage Collection

[0060] Garbage collection is invoked to replenish an FBP with a new free block when the number of available free blocks in the FBP falls below a certain threshold. Unlike in conventional FTLs, garbage collection in the AxFTL in accordance with an embodiment of the present disclosure involves the selection of a victim mode in addition to the selection of a victim block because garbage collection is one mechanism to address the possible imbalance between the demand and supply of free blocks in each mode. Specifically, as a result of garbage collection, a block in a less demanded mode should be freed and moved to the most demanded mode.

[0061] According to an embodiment of the present disclosure, Algorithm 1 in Table 1 shows the detailed procedure of the erase mode-aware garbage collection. This procedure is invoked when N(FBP.sub.m)<N.sub.min for any FBP.sub.m due to data allocation, and whenever it is invoked, by definition, m.sub.hot is the mode whose free block is most lacking. First, the mode with the lowest R.sub.m, i.e., m.sub.cold, which indicates the least demand for free blocks, is considered as the victim mode. Subsequently, the mode with the next lowest R.sub.m (lines 2-7) is considered. The used block pool (UBP) B of the considered mode, which is a pool of blocks that have at least one non-free page, is searched to find the block that has the most invalid pages (lines 3-5). Then, the function NUMINVPAGE(x) returns the number of invalid pages in block x, and NUMINVPAGE(NULL) is defined as zero. The selected b.sub.victim is the block that has at least one non-free page in the least demanded mode. If b.sub.victim has any valid pages that have to be preserved, the valid pages are migrated to a precise (Mode 0) block. That is because migration to an imprecise block will introduce additional errors that will accumulate over time and eventually violate the error tolerance of the data (lines 8 and 9). The function NUMVALPAGE(x) returns the number of valid pages in block x. Finally, b.sub.victim is erased in Mode m.sub.hot and moved into FBPm.sub.hot (lines 10 and 11).

[0062] FIG. 10 illustrates an example of garbage collection in which a victim block is selected by the above-described Algorithm 1 and migrated to a free block pool.

TABLE-US-00001 TABLE 1 Algorithm 1: Erase Mode-Aware Garbage Collection  1 b.sub.victim ← NULL  2 for each UBP B sorted by R.sub.m in ascending order do  3  | for each block b ∈ B do  4  |  | if NUMINVPAGE(b.sub.victim) < NUMINVPAGE(b)  |  |  then  5  |  |  | b.sub.victim ← b  6  | if b.sub.victim ≠ NULL then  7  |  | break  8 if NUMVALPAGE(b.sub.victim) > 0 then  9  | MIGRATE(b.sub.victim, Mode 0) 10 ERASE(b.sub.victim, m.sub.hot) 11 Move b.sub.victim into FBP.sub.m.sub.hot

Erase Mode-Aware Wear Leveling

[0063] Static wear leveling prevents uneven wearing among blocks due to cold data sitting in one block for a long time while other blocks undergo many P/E cycles. Similarly to the above-described garbage collection, wear leveling in the AxFTL in accordance with an embodiment of the present disclosure takes different erase modes into account. The wear leveling in the AxFTL in accordance with an embodiment of the present disclosure is another mechanism to balance the demand and supply of free blocks in each mode by moving blocks in a less demanded mode into a more demanded mode.

[0064] Algorithm 2 describes how a potential victim block b.sub.victim is selected for wear leveling. Unlike conventional FTLs, the AxFTL in accordance with an embodiment of the present disclosure should consider not only UBPs but also FBPs to select the victim block. That is because a free block can be unused for a long time if no write request with a matching error tolerance is received. Therefore, as shown in Table 2, the victim block b.sub.victim that has the lowest CEW from all UBPs and FBPs that satisfy N (FBP)≥N.sub.min (lines 1 to 4) is selected. If the difference between the CEW of b.sub.victim and the highest CEW is greater than a threshold ΔCEW.sub.th, wear leveling is invoked for the selected b.sub.victim (lines 5 and 6). FIG. 11 illustrates an example in which a victim block for wear leveling is selected by Algorithm 2 described above.

TABLE-US-00002 TABLE 2 Algorithm 2: Selection of Victim Block for Wear leveling 1 b.sub.victim ← NULL 2 for each block b in all UBPs and FBPs that  N(FBP) ≥ N.sub.min do 3  | if CEW(b) ≤ CEW(b.sub.victim) then 4  |  | b.sub.victim ← b 5 if CEW.sub.max − CEW(b.sub.victim) > ΔCEW.sub.th then 6  | Call Algorithm 3

[0065] Algorithm 3 shows how the erase mode-aware wear leveling is performed for the selected b.sub.victim. The objective of this algorithm is to bring b.sub.victim into the FBP of the most demanded mode so that it can be used soon. If b.sub.victim is not a free block, all valid pages, if any, in the block are migrated to a precise (Mode 0) block to prevent additional errors, erased in Mode m.sub.hot, and moved into FBPm.sub.hot (lines 1 to 5). If b.sub.victim is a free block, it is moved into FBPm.sub.hot with or without re-erase (lines 6 to 10). In case that the erase mode of b.sub.victim greater than m.sub.hot, it is re-erased in Mode m.sub.hot to meet the error tolerance requirement of FBPm.sub.hot (lines 8 and 9). If b.sub.victim is already a free block in FBPm.sub.hot, no action is taken because it is expected to be allocated soon.

TABLE-US-00003 TABLE 3 Algorithm 3: Erase Mode-Aware Wear Leveling  1 if b.sub.victim is not a free block then  2  | if NUMVALPAGE(b.sub.victim) > 0 then  3  |  | MIGRATE(b.sub.victim, Mode 0)  4  | ERASE(b.sub.victim, m.sub.hot)  5  | MOVE b.sub.victim into FBP.sub.m.sub.hot  6 else  7  | if m.sub.victim ≠ m.sub.hot then  8  |  | if m.sub.victim > m.sub.hot then  9  |  |  | ERASE(b.sub.victim, m.sub.hot) 10  |  | MOVE b.sub.victim into FBP.sub.m.sub.hot

[0066] Although various embodiments have been described for illustrative purposes, it will be apparent to those skilled in the art that various changes and modifications may be made without departing from the spirit and scope of the invention as defined in the following claims.