The Journal of Korean Institute of Communications and Information Sciences (한국통신학회논문지)

The Korean Institute of Commucations and Information Sciences (한국통신학회)
권호 표지

Design of an Efficient FTL Algorithm for Flash Memory Accesses Using Sector-level Mapping

섹터 매핑 기법을 적용한 효율적인 FTL 알고리듬 설계

  • 윤태현 (서강대학교 전자공학과 CAD & ES 연구실) ;
  • 김광수 (서강미래기술원) ;
  • 황선영 (서강대학교 전자공학과 CAD & ES 연구실)
  • Published : 2009.12.31
Download PDF
⟨ Previous Next ⟩

Abstract

This paper proposes a novel FTL (Flash Translation Layer) algorithm based on sector-level mapping to reduce the number of total erase operations in flash memory accesses. The proposed algorithm can reduce the number of erase operations by utilizing the sector-level mapping table when writing data at flash memory. Sector-level mapping technique reduces flash memory access time and extendsthe life time of the flash memory. In the algorithm, wear-leveling is implemented by selecting victim blocks having the minimal number of erase operations, when empty spaces for write are not available. To evaluate the performance of the proposed FTL algorithm, experiments were performed on several applications, such as MP3 players, MPEG players, web browsers and document editors. The proposed algorithm reduces the number of erase operations by 72.4% and 61.9%, when compared with well-known BAST and FAST algorithms, respectively.

본 논문은 플래쉬 메모리 접근시 erase 횟수를 줄이기 위하여 섹터 매핑 기법을 적용한 FTL (Flash Translation Layer) 알고리듬을 제안한다. 블록 매핑 기법을 적용한 기존의 알고리듬에 비하여 제안한 알고리듬은 섹터 단위의 매핑 테이블을 활용하여 데이터를 억세스하는 섹터 매핑 기법을 사용하여 erase 횟수를 줄임으로써 전체적인 메모리 억세스 시간을 줄이고 플래쉬 메모리의 수명을 연장시킬 수 있다. 제안한 알고리듬에서는 write를 위한 빈 공간이 없을 때 erase 횟수가 가장 적은 블록을 victim 블록으로 선택함으로써 wear-leveling을 구현하였다. 제안한 알고리듬을 검증하기 위하여 MP3 재생기, 동영상 재생기, 웹 브라우저, 문서 편집기의 어플리케이션에 대해 실험을 수행하였다. 제안한 알고리듬을 사용하였을 때 기존의 BAST, FAST 알고리듬과 비교하여 72.4%, 61.9%의 erase 횟수가 감소하였다.

Keywords

References

  1. F. Douglis, R. Caceres, F. Kaashoek, K. Li, B. Marsh, and JA. A. Tauber, “Storage Alternatives for Mobile Computers,” In Proceedings of the 1st Symposium on Operating Systems Design and Implementation (OSDI), 1994
  2. J. Kim, J. Kim, S. Noh, S. Min, and Y. Cho, 'A space-efficient flash translation layer for compact flash systems,' IEEE Transactions on Consumer Electronics, Vol.48, No.2, pp.366-375, May 2002. https://doi.org/10.1109/TCE.2002.1010143
  3. Samsung Electronics, '2G x 8Bit / 4G x 8 Bit / 8G x 8 Bit NAND Flash memory (K9WBG08U1M) Data Sheets,' 2007
  4. E. Gal and S. Toledo, 'Algorithms and data structures for flash memories,' ACM Computing Surveys (CSUR), Vol.37, No.2, pp.138-163, June 2005 https://doi.org/10.1145/1089733.1089735
  5. T. Chung, D. Park, S. Park, D. Lee, S. Lee, and H. Song, 'System software for flash memory: A survey,' IFIP Int. Conf. Embedded and Ubiquitous Computing, Lecture Note in Computer Science (LNCS), Vol.4096, pp.394-404, Springer-Verlag, 2006 https://doi.org/10.1007/11802167_41
  6. S. Lee, D. Park, T. Chung, W. Choi, D. Lee, S. Park, and H. Song, 'A log buffer based flash translation layer using fully associative sector translation,' ACM Transactions on Embedded Computing Systems, Vol.6, No.3, July 2007 https://doi.org/10.1145/1275986.1275990
  7. S. Kwon and T. Chung, 'An efficient and advanced space-management technique for flash memory using reallocation blocks,' IEEE Transactions on Consumer Electronics, Vol.54, No.2, pp.631-638, May 2008 https://doi.org/10.1109/TCE.2008.4560140
  8. S. Lee, D. Shin, Y. Kim, and J. Kim, 'LAST: Locality-aware sector translation for NAND flash memory-based storage systems,' ACM SIGOPS Operating Systems Review, Vol.42, No.6, pp.36-42, Feb. 2008 https://doi.org/10.1145/1453775.1453783