• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

Computer Engineering & Science

Previous Articles     Next Articles

A NAND Flash static wear leveling
mechanism based on weighted heap sort

LIU Yan,XU Jilong,ZHU Lei   

  1. (College of Computer Science and Electronic Engineering,Hunan University,Changsha 410082,China)
  • Received:2018-08-20 Revised:2018-10-15 Online:2019-02-25 Published:2019-02-25

Abstract:

As one of the basic mechanisms of the flash translation layer, the wear leveling mechanism is a software algorithm that is applied to extend the life of the flash disk and improve the reliability of stored data. However, existing wear leveling mechanisms are too aggressive to balance the erasure counts of the entire flash memory and ignore the unnecessary data migration overhead due to the unreasonable selection of victim blocks during wear leveling operations, thereby affecting the overall read and write performance of the solid state disk. To solve this problem, we firstly propose a NAND Flash static wear leveling mechanism based on weighted heap sort, namely WHWL. We introduce a weight calculation method based on page data access frequency and the weight of erase counts of the block, which can effectively improve the hit rate of the target blocks with a small number of erases (cold blocks) and a low frequency of data access (cold data), and avoid redundant data migration operations. Secondly, we also propose a victim block selection algorithm based on weighted heap sort to speed up the selection of victim blocks. Experimental results show that compared with the existing PWL and BET algorithms, using the same mapping mechanism, the WHWL can increase the life span of solid state disks by 1.28 and 5.83 times, and also greatly decrease the number of migrations.
 

Key words: weight, heap sort, NAND Flash, wear leveling