A Garbage Collection Algorithm For NAND Flash Memory Based On Page Merged Updating

NAND Flash memory has advantages of non-volatile, high performance, lowpower consumption, small size, light weight and anti-vibration. In the storage device ofconsumer, enterprise, industry and military, NAND Flash has been used widely. Thestructure of NAND Flash is page, block. Its smallest unit for writing is page, and forerasing is block. Before writing, the block must be erased which is time-consuming,energy-consuming operation. In order to improve performance, the storage which basedon NAND Flash write data out-of-place. But this method will make some data invalid.Garbage Collection will collect the invalid data and erase the block, so that there will beenough free-block for writing.According to the development trend of NAND Flash, which is the capacity ofsingle page is increasing, but the P/E cycle is reducing and analyzing the existingGarbage Collection algorithm, we proposed an Efficient Garbage Collection Algorithmbased on Page Merged Updating (EGCbPMU). The main work and contribution of thedissertation is as follows:(1) Studied the key technologies of NAND Flash memory, analyzed therelationship systematically of Garbage Collection, Write Amplification, Wear Leveling,Over-Provisioning, Flash Translation Layer.(2) Designed the mechanism which takes the free page ratio as garbage collectionstarting condition. Taking into account the load of the system, Reduce the overheadgarbage when ensure the writing performance.(3) Proposed the algorithm merging page according the data similarity whenupdating. And structured the garbage collection mechanism of preparative collectingblock in order to reduce consideration. Implemented the algorithm on the basis of thesimulation, the result is that the algorithm reduced the block erasing and improved theWear Leveling.Finally, verified the algorithm on the SSD platform which based on FPGA.EGCbPMU is better on improving writing performance, reducing the valid pagemigration and block erasing, improving the Wear Leveling at the expense of consumemore RAM memory.