제자리 덮어쓰기가 불가능하고 블록의 지움 횟수가 제한되는 낸드 플래시 메모리를 저장매체로 사용하기 위해서 지움 횟수 평준화를 지원하는 다양한 가비지 컬렉션 정책들이 연구되고 있다. 기존정책들은 지움 횟수 평준화를 지원하기 위해 가비지 컬렉션이 수행될 때마다 전체 블록에 대해 지움 대상블록을 선정하기 위한 클리닉 지표를 구하는 연산을 수행하여야 하고 이 연산들은 시스템의 성능을 저하시킨다. 본 논문에서 제안하는 가비지 컬렉션 정책은 지움 횟수의 분산(variance)과 블록들의 최대 지움횟수에 따라 변경되는 임계값을 이용하여 전체 블록에 대한 클리닉 지표를 구하는 연산을 수행하지 않으면서 지움 횟수 평준화를 제공한다. 가비지 컬렉션 시 분산이 임계값 보다 작을 때는 Greedy 정책을 이용하여 지움 비용을 최소화하고, 분산이 임계값 보다 클 때는 최대 지움 횟수를 가진 블록을 지움 대상에서 제외하여 지움 횟수를 평준화한다. 본 논문에서 제안하는 방법으로 가비지 컬렉션을 수행하였을 때, 블록들의 지움 횟수가 지움 횟수 상한에 가까워질수록 블록들의 지움 횟수 표준 편차가 0에 근접하며, 기존의 지움 횟수 평준화를 지원하는 알고리즘과 비교하여 두 배 이상 빠른 가비지 컬렉션 속도를 보였다.
In order to utilize NAND flash memory as storage media which does not allow update-in-place and limits the number of block erase count, various garbage collection policies supporting wear-leveling have been investigated. Conventional garbage collection policies require cleaning-index calculation for the entire blocks to choose a block to be garbage-collected to support wear-leveling whenever a garbage collection is required, which results in performance degradation of system. This paper proposes a garbage collection policy which supports wear-leveling using a threshold value, which is in fact a variance of erase counts and by the maximum erase count of all blocks, without calculating the cleaning-index. During garbage collection, the erase cost is minimized by using the Greedy Policy if the variance is less than the threshold value. It achieves wear-leveling by excluding the block with the largest erase count from erase target blocks if the variance is larger than threshold value. The proposed scheme shows that a standard deviation approaches to zero as the erase count of blocks approaches to its upper limit and the measured speed of garbage collection is two times faster than the conventional schemes.
