Efficient Data-Allocation Scheme for Eliminating Garbage Collection During Analysis of Big Graphs Stored in NAND Flash Memory

摘要

A new control scheme for eliminating garbage collection during high-speed analysis of big-graph data stored in NAND flash memory is proposed and evaluated. During big-graph analysis, intermediate results of the analysis are stored in NAND flash memory and updated repeatedly. Under a conventional control scheme, excessive data copying, called "garbage collection," occurs because overwriting data to NAND flash memory is prohibited. Such excessive data copying degrades performance of big-graph analysis. In contrast, under the proposed control scheme, the controller of NAND flash memory writes the intermediate results, which are updated at the same time, to the same block of NAND flash memory, and the excessive data copying is eliminated completely because all the data in the block can be erased at the same time before the intermediate results are updated. As a result, the proposed scheme shortens analysis time by 88 percent and increases analysis speed for big graphs 8.7 times. The proposed scheme can be applied to three-dimensional NAND flash memory and increases analysis speed 9.5 times. Also, the proposed scheme can be applied to an emerging high-density memory such as three-dimensional vertical chain-cell phase-change memory. These results show that the proposed control scheme enables high-speed analysis of big graphs.