Improving Hybrid FTL by Fully Exploiting Internal SSD Parallelism with Virtual Blocks

Abstract

Compared with either block or page-mapping Flash Translation Layer (FTL), hybrid-mapping FTL for flash Solid State Disks (SSDs), such as Fully Associative Section Translation (FAST), has relatively high space efficiency because of its smaller mapping table than the latter and higher flexibility than the former. As a result, hybrid-mapping FTL has become the most commonly used scheme in SSDs. But the hybrid-mapping FTL incurs a large number of costly full-merge operations. Thus, a critical challenge to hybrid-mapping FTL is how to reduce the cost of full-merge operations and improve partial merge operations and switch operations. In this article, we propose a novel FTL scheme, called Virtual Block-based Parallel FAST (VBP-FAST), that divides flash area into Virtual Blocks (VBlocks) and Physical Blocks (PBlocks) where VBlocks are used to fully exploit channel-level, die-level, and plane-level parallelism of flash. Leveraging these three levels of parallelism, the cost of full merge in VBP-FAST is significantly reduced from that of FAST. In the meantime, VBP-FAST uses PBlocks to retain the advantages of partial merge and switch operations. Our extensive trace-driven simulation results show that VBP-FAST speeds up FAST by a factor of 5.3--8.4 for random workloads and of 1.7 for sequential workloads with channel-level, die-level, and plane-level parallelism of 8, 2, and 2 (i.e., eight channels, two dies, and two planes).

References

1. Nitin Agrawal, Vijayan Prabhakaran, Ted Wobber, John D. Davis, Mark Manasse, and Rina Panigrahy. 2008. Design Tradeoffs for SSD Performance. In Proceedings of the USENIX Technical Conference. USENIX Association Berkeley, CA. 57--70.
2. A. Ban. Flash file system. United States Patent No. 5,404,485, April 1995.
3. F. Chen, R. Lee, and X. Zhang. 2011. Essential roles of exploiting internal parallelism of flash memory based solid state drives in high-speed data processing. In Proceedings of HPCA’11, San Antonio, TX, 266--277. DOI:http://dx.doe.org/10.1109/HPCA.2011.5749735
4. Zhiguang Chen, Nong Xiao, and Fang Liu. 2012. SAC: Rethinking the cache replacement policy for SSD-based storage systems. In Proceedings of SYSTOR’12. ACM, New York, NY, Article 13 (June 2012). DOI:http://dx.doe.org/10.1145/2367589.2367598
5. H. Cho, D. Shin, and Y. I. Eom. 2009. KAST: K-associative sector translation for NAND flash memory in real-time systems. In Proceedings of DATE’09, Nice, France. Article 5090717 (April 2009), 507--512.
6. T.-S. Chung, D.-J. Park, S. Park, D.-H. Lee, S.-W. Lee, and H.-J. Song. 2006. System software for flash memory: A survey. In Proceedings of the 5th International Conference on Embedded and Ubiquitous Computing (EUC’06), 394--404. DOI:http://dx.doe.org/10.1016/j.physleta.2006.02.043
7. Tae-Sun Chung, Dong-Joo Park, Sangwon Park, Dong-Ho Lee, Sang-Won Lee, and Ha-Joo Song. 2009. A survey of Flash Translation Layer. J. Syst. Architect. 55 (2009), 332--343. DOI:http://dx.doe.org/10.1016/j.sysarc.2009.03.005
8. Aayush Gupta and Youngjae Kim Bhuvan Urgaonkar. 2009. DFTL: A flash translation layer employing demand-based selective caching of page-level address mapping. In Proceedings of ASPLOS’09. ACM, New York, NY, 229--240. DOI:http://dx.doe.org/10.1145/2528521.1508271
9. Yang Hu, Hong Jiang, Dan Feng, et al. 2010. Achieving page-mapping FTL performance at block-mapping FTL cost by hiding address translation. In Proceedings of MSST’ 10, 1--12. DOI:http://dx.doe.org/10.1109/MSST.2010.5496970
10. Yang Hu, Hong Jiang, Dan Feng, et al. 2011. Performance impact and interplay of SSD parallelism through advanced commands, allocation strategy and data granularity. In Proceedings of ICS’11. ACM, New York, NY, 96--107. DOI:http://dx.doe.org/10.1145/1995896.1995912
11. Huazhong University of Science and Technology website. Retrieved May 2012, from http://storage.hust.edu.cn/SSDsim.
12. Ouyang J, Lin S, Jiang S, et al. 2014. SDF: Software-defined flash for web-scale internet storage systems. ASPLOS’14. ACM, New York, NY, 471--484. DOI:http://dx.doe.org/10.1145/2541940.2541959
13. Song Jiang, Lei Zhang, XinHao Yuan, et al. 2011. S-FTL: An efficient address translation for flash memory by exploiting spatial locality. In Proceedings of MSST’11, 12 pages. DOI:http://dx.doe.org/10.1109/MSST.2011.5937215
14. Dawoon Jung, Jeong-UK Kang, Heeseung JO, Jin-Soo Kim, and Joonwon Lee. 2010. Superblock FTL: A superblock-based flash translation layer with a hybrid address translation scheme. ACM Trans. Embed. Comput. Syst. 9, 4, Article 40 (March 2010). DOI:http://dx.doe.org/10.1145/1721695.1721706
15. M. Jung and M. Kandemir. 2012. An evaluation of different page allocation strategies on high-speed SSDs. In Proceedings of Hot Storage. USENIX Association Berkeley, CA, 9 pages.
16. Myoungsoo Jung, Ellis H. Wilson III, and Mahmut Kandemir. 2012. Physically addressed queueing (PAQ): Improving parallelism in solid state disks. In Proceedings of ISCA’12. IEEE Computer Society Washington, DC, 404--415.
17. J. Kim, J. M. Kim, S. H. Noh, S. L. Min, and Y. Cho. 2002. A space-efficient flash translation layer for compact flash systems. IEEE Trans. Consumer Elec. 48, 2 (2002), 366--375. DOI:http://dx.doe.org/10.1109/TCE.2002.1010143
18. Jaehong Kim, Sangwon Seo, Dawoon Jung, et al. 2012. Parameter-aware I/O management for solid state disks (SSDs). IEEE Trans. Comput. 61, 5 (2012), 636--649. DOI:http://dx.doe.org /10.1109/TC.2011.76
19. D. Koo and D. Shin. 2009. Adaptive log block mapping scheme for log buffer-based FTL (flash translation layer). In Proceedings of IWSSPS’09. ACM, New York, NY, 1--12.
20. S. Lee, D. Park, T. Chung, D. Lee, S. Park, and H. Song. 2007. A log buffer-based flash translation layer using fully-associative sector translation. ACM Trans. Embed. Comput. Syst. 6, 3, Article 18 (July 2007). DOI:http://dx.doe.org/10.1145/1275986.1275990
21. S. Lee, D. Shin, Y.-J. Kim, et al. 2008. LAST: Locality-aware sector translation for NAND flash memory-based storage systems. ACM SIGOPS Op. Syst. Rev. 42, 6 (2008). DOI:http://dx.doe.org/10.1109/MSST.2011.5937215
22. Dongzhe Ma, Jianhua Feng, and Guoliang Li. 2011. LazyFTL: A page-level flash translation layer optimized for NAND flash memory. In Proceedings of SIGMOD’11. ACM, New York, NY, 12--16. DOI:http://dx.doe.org/10.1145/1989323.1989325
23. Microsoft Enterprise Traces. Retrieved October 2011, from http://iotta.snia.org/traces/list/BlockIO.
24. Microsoft Production Server Traces. http://iotta.snia.org/traces/.
25. Chanik Park, Wonmoon Cheon, Jeonguk Kang, Kangho Roh, and Wonhee Cho. 2008. A reconfigurable FTL architecture for NAND flash-based applications. ACM Trans. Embed. Comput. Syst. 7, 4, Article 38 (July 2008). DOI:http://dx.doe.org/10.1145/1376804.1376806
26. Sang-Hoon Park, Seung-Hwan Ha, and Kwanhu Bang, et al. 2009. Design and analysis of flash translation layers for Multi-Channel NAND flash-based storage devices. IEEE Trans. Consumer Elec. 55, 3 (2009), 1392--1400. DOI:http://dx.doe.org/10.1109/TCE.2009.5278005
27. Sung Kyu Park, Youngwoo Park, Gyudong Shim et al. 2011. CAVE: Channel-aware buffer management scheme for solid state disk. In Proceedings of SAC’11. ACM, New York, NY, 346--353. DOI:http://dx.doe.org/10.1145/1982185.1982262
28. Samsung Corporation. 2007. K9XXG08XXM Flash Memory Specification. (2007). Retrieved from http://www.samsung.com/global/system/business/semiconductor/product/2007/6/11/NANDFlash/SLC_LargeBlock/8Gbit/K9F8G08U0M/ds_k9f8g08x0m_rev10.pdf.
29. Ji-Yong Shin, Zeng-Lin Xia, Ning-Yi Xu, et al. 2009. FTL design exploration in reconfigurable high-performance SSD for server applications. In Proceedings of ICS’09. ACM, New York, NY, 338--349. DOI:http://dx.doe.org/10.1145/1542275.1542324
30. Guangyu Sun, Yongsoo Joo, Yibo Chen, et al. 2010. A hybrid solid-state storage architecture for the performance, energy consumption, and lifetime improvement. In Proceedings of HPCA’10. Elsevier Science Publishers B. V., Amsterdam, The Netherlands, 12 pages.
31. UMass Trace Repository. Retrieved October 2011, from http://traces.cs.umass.edu.

Index Terms

• Hardware

  • Electronic design automation

    • Methodologies for EDA

  • Hardware validation

  • Integrated circuits

    • Logic circuits

      • Arithmetic and datapath circuits

      • Design modules and hierarchy