基于逻辑区间热度的NAND闪存垃圾回收算法

doi:10.11772/j.issn.1001-9081.2017.04.1149

计算机应用 ›› 2017, Vol. 37 ›› Issue (4): 1149-1152.DOI: 10.11772/j.issn.1001-9081.2017.04.1149

基于逻辑区间热度的NAND闪存垃圾回收算法

雷兵兵, 严华

四川大学电子信息学院, 成都 610065

收稿日期:2016-09-20 修回日期:2016-12-23 出版日期:2017-04-10 发布日期:2017-04-19
通讯作者: 雷兵兵
作者简介:雷兵兵(1989-),男,湖北荆门人,硕士研究生,主要研究方向:智能控制;严华(1971-),男,四川渠县人,教授,博士,主要研究方向:模式识别、智能控制。
基金资助:
国家自然科学基金资助项目（61172181）。

Garbage collection algorithm for NAND flash memory based on logical region heat

LEI Bingbing, YAN Hua

College of Electronics and Information Engineering, Sichuan University, Chengdu Sichuan 610065, China

Received:2016-09-20 Revised:2016-12-23 Online:2017-04-10 Published:2017-04-19
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61172181).

摘要/Abstract

摘要： 针对现有的NAND闪存垃圾回收算法中回收性能不高，磨损均衡效果差，并且算法内存开销大的问题，提出了一种基于逻辑区间热度的垃圾回收算法。该算法重新定义了热度计算公式，把连续逻辑地址的NAND内存定义为一个热度区间，以逻辑区间的热度来代替逻辑页的热度，并将不同热度的数据分开存储到不同擦除次数的闪存块上，有效地实现了数据冷热分离，并且节约了内存空间。同时，算法还构造了一种新的回收代价函数来选择回收块，在考虑回收效率的同时，还兼顾了磨损均衡的问题。实验结果表明，该算法与性能优异的FaGC算法相比，总的擦除次数减少了11%，总的拷贝次数减少了13%，擦次数最大差值减少了42%，内存消耗能减少了75%。因此，该算法有利于增加闪存可用空间，改善闪存系统的读写性能，延长闪存使用寿命。

关键词: NAND闪存, 磨损均衡, 垃圾回收, 逻辑区间, 回收块

Abstract: To solve the problems of low collection performance, poor wear leveling effect, and high memory overhead in the existing NAND flash memory garbage collection algorithms, a new garbage collection algorithm based on logical region heat was proposed. The heat calculation formula was redefined, the NAND memory of continuous logical address was defined as a heat range which was used to replace the heat of logical page, then the data with different heat was separated into the corresponding flash blocks with different erase counts. The cold and hot data were effectively separated,and the memory space was also saved. Meanwhile, a new collection cost function was constructed to improve the collection efficiency and wear leveling effect. The experimental results showed that compared with the excellent File-aware Garbage Collection (FaGC) algorithm, the total number of erase operations was reduced by 11%, the total number of copy operations was reduced by 13%, the maximum difference of erase counts was reduced by 42%, and the memory consumption was reduced by 75%. Therefore, the available flash memory space can be increased, the read and write performance of flash memory can be improved, and the flash memory life can be also extended by using the proposed algorithm.

Key words: NAND flash memory, wear leveling, garbage collection, logical region, collection block

中图分类号:

TP316.2

雷兵兵, 严华. 基于逻辑区间热度的NAND闪存垃圾回收算法[J]. 计算机应用, 2017, 37(4): 1149-1152.

LEI Bingbing, YAN Hua. Garbage collection algorithm for NAND flash memory based on logical region heat[J]. Journal of Computer Applications, 2017, 37(4): 1149-1152.

参考文献

[1] LEE S, KIM J. Effective lifetime-aware dynamic throttling for NAND flash-based SSDs[J]. IEEE Transactions on Computers, 2016, 65(4):1075-1089.
[2] CHANG Y, CHANG Y, CHEN J, et al. On trading wear-leveling with heal-leveling[C]//DAC 2014: Proceedings of the 51st Annual Design Automation Conference. New York: ACM, 2014:1-6.
[3] LEE J, KIM Y, SHIPMAN G M, et al. Preemptible I/O scheduling of garbage collection for solid state drives[J]. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 2013, 32(2):247-260.
[4] LAM K Y, ZHU C J, CHANG Y H, et al. Garbage collection of multi-version indexed data on flash memory[J]. Journal of Systems Architecture, 2014, 60(8):630-643.
[5] KIM S H, CHOI J H, KWAK J W. HaWL: hidden cold block-aware wear leveling using bit-set threshold for NAND flash memory[J]. IEICE Transactions on Information and Systems, 2016, E99-D(4):1242-1245.
[6] WU M, ZWAENEPOEL W. eNVy: a non-volatile main memory storage system[C]//ASPLOS VI: Proceedings of the Sixth International Conference on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 1994:86-97.
[7] KAWAGUCHI A, NISHIOKA S, MOTODA H A. Flash memory based file system[C]//Proceedings of the USENIX 1995 Technical Conference. Berkeley: USENIX Association, 1995:155-164.
[8] CHIANG M L, CHANG R C. Cleaning policies inmobile computers using flash memory[J]. Journal of Systems and Software, 1999, 48(3):213-231.
[9] YAN H, YAO Q. An efficient file-aware garbage collection algorithm for NAND flash based consumer electronics[J]. IEEE Transactions on Consumer Electronics, 2014, 60(4):623-627.
[10] 陈金忠, 姚念民, 蔡绍滨, 等. 基于页面写相关的闪存转换层策略[J]. 通信学报, 2013, 34(6):76-84.(CHEN J Z, YAO N M, CAI S B, et al. Page write-related scheme for flash translation layer[J]. Journal on Communications, 2013, 34(6):76-84.)
[11] CHANG L-P, KUO T-K. Efficient management for large-scale flash memory storage systems with resource conservation[J]. ACM Transactions on Storage, 2005, 1(4):381-418.
[12] KIM H, SHIN D. Clustered page-level mapping for flash memory based storage devices[J]. IEEE Transactions on Consumer Electronics, 2015, 61(1):47-55.
[13] LIN M, CHEN S. Efficient and intelligent garbage collection policy for NAND flash-based consumer electronics[J]. IEEE Transactions on Consumer Electronics, 2013, 59(3):538-543.

基于逻辑区间热度的NAND闪存垃圾回收算法

Garbage collection algorithm for NAND flash memory based on logical region heat

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

[1]	张震, 付印金, 胡谷雨. 基于布隆过滤器的新型混合内存架构磨损均衡策略[J]. 计算机应用, 2018, 38(8): 2230-2235.
[2]	方才华, 刘景宁, 童薇, 高阳, 雷霞, 蒋瑜. 全程优化的固态硬盘垃圾回收方法[J]. 计算机应用, 2017, 37(5): 1257-1262.
[3]	王晋阳, 严华. 基于逻辑页冷热分离的NAND闪存磨损均衡算法[J]. 计算机应用, 2016, 36(5): 1430-1433.
[4]	谌宁，覃征. 基于嵌入式Java虚拟机的垃圾回收算法[J]. 计算机应用, 2005, 25(01): 218-219.