基于分组—偏向随机游走的闪存地址映射及磨损均衡算法研究

发布时间：2018-06-13 11:45

本文选题：地址映射 + 磨损均衡　；参考：《西南交通大学》2016年硕士论文

【摘要】：闪存作为一种性能优良的半导体存储芯片,广泛应用于诸如固态硬盘(SSDs)、存储卡(SD cards)等设备。但由于闪存物理介质能承受的擦除次数有限,闪存芯片上共存的高频更新数据(热数据)和低频更新数据(冷数据)会造成其物理介质的不均衡磨损,缩短其使用寿命。本文提出一种基于分组-偏向随机游走的地址映射算法,利用程序访问存储器时体现的局部性和偏向随机游走理论,将冷热数据存储在逻辑上相邻的闪存物理块中,并在此基础上设计和实现了一种闪存转换层控制器。现有的闪存转换层倾向于利用不同的数据结构分别操控地址映射、磨损均衡及垃圾回收过程,与其不同的是,本文设计的闪存转换层控制器通过一个核心数据结构操控并协调这三个过程,从而在消耗一定内存资源的条件下,简化算法的数据结构。本文以磨损均衡效果较为稳定的双池算法和消耗内存较少的BET算法作为参照,从算法应对不同冷热数据比例的能力、磨损均衡效果及内存消耗量三方面与本文提出的算法进行了比较。从算法应对不同比例冷热数据的能力来看,BET只适用于热数据占主导情况,而本文提出的算法与双池算法都适用于冷数据占主导、热数据占主导以及最接近真实冷热数据共存比例的情况。在存储数据的冷热比例最接近真实情况时,本文提出算法的均衡磨损性能与双池算法相当；且在热数据占主导的情况下,本文提出算法的磨损性能优于双池算法；只有在冷数据占主导的情况下,本文提出算法的磨损均衡性能略逊于双池算法。但本文提出算法对内存空间需求较大,针对这一缺陷,本文进一步简化了算法的数据结构,从后续实验结果来看,在算法整体思路不变的情况下,改进后的算法进一步优化了磨损均衡效果,并有效地减少了内存开销。实验证明,本文提出的基于分组-偏向随机游走的闪存地址映射及磨损均衡算法适用范围广,且可在占用较少内存资源的前提下,有效延长闪存存储系统的使用寿命。
[Abstract]:As a semiconductor memory chip with excellent performance, flash memory is widely used in devices such as solid state hard disk (SSD), memory card (SD card) and so on. However, due to the limited erasure times of flash physical media, the coexistence of high frequency update data (thermal data) and low frequency update data (cold data) on flash memory chip will cause uneven wear and tear of physical medium and shorten its service life. In this paper, an address mapping algorithm based on packet-biased random walk is proposed. By using the local and biased random walk theory when the program accesses the memory, the cold and hot data are stored in the logically adjacent flash memory blocks. On this basis, a flash memory conversion layer controller is designed and implemented. The existing flash conversion layer tends to manipulate address mapping, wear balance, and garbage collection processes using different data structures. The flash transfer layer controller designed in this paper controls and coordinates these three processes through a core data structure, which simplifies the data structure of the algorithm under the condition of consuming some memory resources. In this paper, the two-cell algorithm with stable wear equalization effect and the BET algorithm with less memory consumption are taken as the reference, and the ability of the algorithm to deal with different ratios of cold and hot data is discussed. The wear equalization effect and memory consumption are compared with the proposed algorithm. From the view of the ability of the algorithm to deal with different proportions of cold and hot data, BET is only suitable for the dominant situation of thermal data, while the algorithm proposed in this paper and the dual-cell algorithm are both suitable for the dominance of cold data. Thermal data dominated and closest to the coexistence of real hot and cold data. When the ratio of cold and heat stored is the closest to the real situation, the equalization wear performance of the algorithm is equal to that of the two-cell algorithm, and the wear performance of the algorithm is superior to that of the double-cell algorithm when the thermal data is dominant. Only when the cold data is dominant, the wear equalization performance of the proposed algorithm is slightly inferior to that of the dual-cell algorithm. However, this paper proposes that the algorithm needs a large amount of memory space. In view of this defect, this paper further simplifies the data structure of the algorithm. From the results of subsequent experiments, under the condition that the whole idea of the algorithm remains unchanged, The improved algorithm further optimizes the wear equalization effect and effectively reduces the memory overhead. Experimental results show that the proposed flash address mapping and wear equalization algorithm based on grouping bias random walk has a wide range of applications and can effectively prolong the service life of flash memory system on the premise of occupying less memory resources.
【学位授予单位】：西南交通大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP333

【相似文献】