Static Wear Leveling

articleissues
article=y
context=December 2007
technical=June 2008
copyedit=June 2008Applications of NAND flash memory have now grown much beyond its original design goals. For instance, Intel proposed the Robson solution by using flash memory as the cache of hard disks and Microsoft proposed a fast booting service for Windows Vista by Microsoft. Such a development imposes harsh challenges on the reliability property of flash memory. It is even worse for the endurance of flash memory. The reliability problem becomes even more challenging, especially when low-cost flash-memory designs gain their momentum in the market. For example, the endurance of a block of MLC flash memory is only 10,000 erase counts or even lower, compared to the 100,000 erase counts of SLC flash memory. Static wear leveling helps maintain crucial reliability while limiting impacts on performance and cost.

Overview

Consider a typical system architecture of flash-memory-based file systems as shown in the following figure. A Memory Technology Device (MTD) driver is to provide primitive functions, such as read, write, and erase over flash memory. A Flash Translation Layer driver is needed in the system for address translation and garbage collection, and FTL and NFTL are its popular implementations. A typical Flash Translation Layer driver consists of an Allocator and a Cleaner. The Allocator handles any translation of Logical Block Addresses (LBA) and their Physical Block Addresses (PBA). Different approaches have different address translation mechanisms, e.g.,FTL and NFTL . The Cleaner is to do garbage collection to reclaim pages of invalid data. Since garbage collection is done in the unit of a block, valid data in any pages of a block must be copied to other free pages when the block is to be erased. One important implementation issue for flash-memory management is wear leveling,which is to evenly distribute the number of erasing for each block (because of the limitation on the number of erasing for blocks) so that the SW Leveler is to distribute block erases over blocks evenly.The motivation of static wear leveling is to prevent any cold data from staying at any block for a long period oftime. It is to minimize the maximum erase-count difference of any two blocks so that the lifetime of flash memoryis extended. In order to minimize the integration overhead, consider a modular design for static wear leveling is very important .

Static Wear Leveler

Let the Static Wear Leveler (SW Leveler) be associated with a Block Erasing Table (BET) to remember which block has been erasedin a selected period of time. The SW Leveler is activated by some system parameters for the needs of static wear leveling. When the SW Leveler is running, it either resets the BET or picks up a block that has not been erased so far (based on the BET information) and triggers the Cleaner to do garbage collection on the block. The selection procedure of a block must be done in an efficient way within a bounded amount of time. Note that the BET must be updated whenever a block is erased. It could be done by a triggering action to the SW Leveler. The design of the BET must be scalable because of the rapid increasing of flash-memory capacity and the limited RAM space on a controller. Whenever a block is recycled by garbage collection, any modification to the address translation is done as the original design of a Flash Translation Layer driver. The implementation of the SW Leveler could be a thread or a procedure triggered by a timer or the Allocator/Cleaner based on some preset conditions.

The SW Leveler is invoked by the Cleaner to update the BET whenever any block is erased by the Cleaner in garbage collection when staticwear leveling is needed. We can use two variables to keep track of the total number of block erases done since the BET is reset and the number of 1’s in the BET. If the ratio of the two tracked number is too high, the SW Leveler is triggered to move cold data from their original place by reguesting the Cleaner to reclaim those blocks whose corresponding bit in the Block Erasing Table is 0.

Block Erasing Table

The purpose of the Block Erasing Table (BET) is to remember which block has been erased in a pre-determinedtime frame, referred to as the resetting interval, so as to locate blocks of cold data. A BET is a bit array, in whicheach bit corresponds to a set of 2^k contiguous blocks where k is an integer that is larger or equal to 0. Whenever ablock is erased by the Cleaner, the SW Leveler is triggered to set the corresponding bit as 1.

External links

* [http://www.onfi.org/index.html Open NAND Flash Interface Working Group]
* [http://newslab.csie.ntu.edu.tw/~flash/index.php?SelectedItem=AcademicResearches&SelectedGroup=AcademicResearches Flash-Memory Research Group]
* [http://aplawrence.com/Makwana/nonvolmem.html A Nonvolatile Memory Overview]
* [http://www.pma-show.com/2006/corporate/sandisk_review/001_sandisk_flash_memory_facility.html SanDisk Flash Memory Plant]
* [http://www2.dac.com/data2/44th/44acceptedpapers.nsf/0c4c09c6ffa905c487256b7b007afb72/bb644b782710bd63872572a000470a4e/$FILE/13_1.PDF An Efficient StaticWear Leveling Design to Enhance the Endurance of Flash-Memory Storage Systems]
* [http://www.micron.com/products/nand/definingnand What is NAND Flash]
* [http://www.micron.com/products/nand/usingnand NAND Flash Applications]

References

* [http://news.bbc.co.uk/2/hi/technology/3939333.stm Digital Memories Survive Extremes]
* [http://www.letsgodigital.org/en/flash_memory_cards.html Flash memory database]