The Research On Address Mapping And Wear Leveling Algorithms Of Flash Memory Based On Grouping And Biased Random Walk

Flash memory is a high performance semiconductor memory chip, which is widely used in equipment like solid-state drives (SSDs) and memory card (SD cards). The hardware of flash memory could only bear a limited number of erase operation, and the coexistence of frequently updated data (called hot data) and seldom updated data (called cold data) causes uneven wear in flash memory’s physical medium, which would shorten its lifespan.This paper put forward an address mapping algorithm based on grouping and biased random walk, which uses the principle of locality and biased random walk theory to store hot and cold data in logically adjacent blocks. Then on the basis, it designs and implements a flash translation layer. Different from existing designs of flash translation layer which tends to use different data structures to handle address mapping, wear leveling and garbage collecting process respectively, the design of flash translation layer controller in this paper controls and coordinates these three processes through a core data structure. As the result, the data structures maintained by the algorithm are simplified with an acceptable consumption of internal storage.Using dual pool algorithm and BET algorithm as comparison, the algorithm proposed in this paper is valued from the ability to deal with different proportion of hot and cold data, wear leveling effect and internal storage consumption. From the aspect of dealing with different proportion of hot and cold data, BET algorithm is just suitable for the hot-data-dominated situation, while dual pool algorithm and the proposed algorithm in this paper are applicable to hot-data-dominated situation, cold-data-dominated situation and the closest situation to the real coexistence proportion of cold and hot data. When the proportion of cold and hot data is closest to the real situation, the proposed algorithm and dual pool algorithm have equal wear leveling performances. And under the hot-data-dominated situation, the proposed algorithm outperforms dual pool algorithm. Only under the cold-data-dominated situation, the proposed algorithm performs slightly inferior than dual pool algorithm. Yet the demand for internal storage of the proposed algorithm is relatively large, in order to remedy this defect, this paper further simplifies data structures maintained by the proposed algorithm. The follow-up shows that the wear leveling effect is improved and the internal storage consumption is effectively reduced when the overall idea is unchanged.A series of experiment shows that the proposed address mapping and wear leveling algorithm based on grouping and biased random walk can effectively prolong the lifespan of flash memory storage system with an acceptable internal storage consumption, and its application range is extensive.