An Adaptive Demand-Based Caching Mechanism for NAND Flash Memory Storage Systems

Abstract

During past decades, the capacity of NAND flash memory has been increasing dramatically, leading to the use of nonvolatile flash in the system’s memory hierarchy. The increasing capacity of NAND flash memory introduces a large RAM footprint to store the logical to physical address mapping. The demand-based approach can effectively reduce and well control the RAM footprint. However, extra address translation overhead is also introduced which may degrade the system performance.

In this article, we present CDFTL, an adaptive Caching mechanism for Demand-based Flash Translation Layer, for NAND flash memory storage systems. CDFTL adopts both the fine-grained entry-based caching mechanism to exploit temporal locality and the coarse-grained translation-page-based caching mechanism to exploit spatial locality of workloads. By selectively caching the on-demand address mappings and adaptively changing the space configurations of two granularities, CDFTL can effectively utilize the RAM space and improve the cache hit ratio. We evaluate CDFTL under a real hardware embedded platform using a variety of I/O traces. Experimental results show that our technique can achieve an 11.13% reduction in average system response time and a 35.21% reduction in translation block erase counts compared with the previous work.

References

1. Amir Ban. 1995. Flash file system. (April 4, 1995). US Patent No. 5,404,485.
2. Li-Pin Chang, Yu-Syun Liu, and Wen-Huei Lin. 2016. Stable greedy: Adaptive garbage collection for durable page-mapping multichannel SSDs. ACM Trans. Embed. Comput. Syst. 15, 1, Article 13 (Jan. 2016), 25 pages.
3. Yuan-Hao Chang and Tei-Wei Kuo. 2011. A management strategy for the reliability and performance improvement of MLC-based flash-memory storage systems. IEEE Trans. Comput. 60, 3 (March 2011), 305--320.
4. Renhai Chen, Zhiwei Qin, Yi Wang, Duo Liu, Zili Shao, and Yong Guan. 2015. On-demand block-level address mapping in large-scale NAND flash storage systems. IEEE Trans. Comput. 64, 6 (June 2015), 1729--1741.
5. Zhi Chen, Meikang Qiu, Zhong Ming, Laurence T. Yang, and Yongxin Zhu. 2013. Clustering scheduling for hardware tasks in reconfigurable computing systems. J. Syst, Architec, - Embedded Syst, Des, 59, 10-D (2013), 1424--1432.
6. Siddharth Choudhuri and Tony Givargis. 2007. Performance improvement of block based NAND flash translation layer. In Proceedings of the 5th IEEE/ACM International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS’07). 257--262.
7. Hua-Wei Fang, Mi-Yen Yeh, Pei-Lun Suei, and Tei-Wei Kuo. 2014. An adaptive endurance-aware B+-tree for flash memory storage systems. IEEE Trans. Comput. 63, 11 (Nov. 2014), 2661--2673.
8. Yong Guan, Guohui Wang, Yi Wang, Renhai Chen, and Zili Shao. BLog: Block-level log-block Management for NAND Flash Memorystorage Systems. In SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems, (LCTES’13). 111--120.
9. Aayush Gupta, Youngjae Kim, and Bhuvan Urgaonkar. 2009. DFTL: A flash translation layer employing demand-based selective caching of page-level address mappings. In Proceedings of the 14th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS’09). 229--240.
10. Miao Hu, Hai Li, Yiran Chen, Xiaobin Wang, and Robinson E. Pino. 2011. Geometry variations analysis of TiO2 thin-film and spintronic memristors. In Proceedings of the 16th Asia and South Pacific Design Automation Conference (ASP-DAC’11). 25--30.
11. Min Huang, Zhaoqing Liu, Liyan Qiao, Yi Wang, and Zili Shao. 2016. An endurance-aware metadata allocation strategy for MLC NAND flash memory storage systems. IEEE Trans. CAD Integr. Circ. Syst. 35, 4 (2016), 691--694.
12. Po-Chun Huang, Yuan-Hao Chang, and Tei-Wei Kuo. 2012. Joint management of RAM and flash memory with access pattern considerations. In Proceedings of the 2012 49th ACM/EDAC/IEEE Design Automation Conference (DAC’12). 882--887.
13. Sheng-Min Huang and Li-Pin Chang. 2016. Exploiting page correlations for write buffering in page-mapping multichannel SSDs. ACM Trans. Embed. Comput. Syst. 15, 1, Article 12 (Jan. 2016), 25 pages.
14. Chun-Hsiung Hung, Yih-Shan Yang, Yao-Jen Kuo, Tzu-Neng Lai, Shin-Jang Shen, Jo-Yu Hsu, Shuo-Nan Hung, Hang-Ting Lue, Meng-Fan Chang, Yen-Hao Shih, Shih-Lin Huang, Ti-Wen Chen, Tzung Shen Chen, Chung Kuang Chen, Chi-Yu Hung, and Chih-Yuan Lu. 2013. 3D stackable vertical-gate BE-SONOS NAND flash with layer-aware program-and-read schemes and wave-propagation fail-bit-detection against cross-layer process variations. In Proceedings of the 2013 Symposium on VLSI Circuits (VLSIC’13). C20--C21.
15. Song Jiang, Lei Zhang, XinHao Yuan, Hao Hu, and Yu Chen. 2011. S-FTL: An efficient address translation for flash memory by exploiting spatial locality. In Proceedings of the 2011 IEEE 27th Symposium on Mass Storage Systems and Technologies (MSST’11). 1--12.
16. Yongsoo Joo, Youngjin Cho, Donghwa Shin, and Naehyuck Chang. 2007. Energy-aware data compression for multi-level cell (MLC) flash memory. In Proceedings of the 44th Design Automation Conference (DAC’07). 716--719.
17. Dawoon Jung, Jeong-U. K. 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 (April 2010), 41 pages.
18. J. Katcher. 1997. Postmark: A New File System Benchmark{R}. Technical Report TR3022, Network Appliance.
19. Ryota Katsumata, Masaru Kito, Yoshiaki Fukuzumi, Masaru Kido, Hiroyasu Tanaka, Yosuke Komori, Megumi Ishiduki, Junya Matsunami, Tomoko Fujiwara, Yuzo Nagata, Li Zhang, Yoshihisa Iwata, Ryouhei Kirisawa, Hideaki Aochi, and Akihiro Nitayama. 2009. Pipe-shaped BiCS flash memory with 16 stacked layers and multi-level-cell operation for ultra high density storage devices. In Proceedings of the 2009 Symposium on VLSI Technology. 136--137.
20. Jesung Kim, Jong Min Kim, S. H. Noh, Sang Lyul Min, and Yookun Cho. 2002. A space-efficient flash translation layer for CompactFlash systems. IEEE Trans. Consumer Electron. 48, 2 (May 2002), 366--375.
21. M. Kuoppala. 2002. Tiobench-threaded I/O bench for Linux{J}. (2002).
22. Yongmyoung Lee, Taedong Jung, and Ilhoon Shin. 2013. Demand-based flash translation layer considering spatial locality. In Proceedings of the 28th Annual ACM Symposium on Applied Computing (SAC’13). 1550--1551.
23. Boxun Li, Peng Gu, Yi Shan, Yu Wang, Yiran Chen, and Huazhong Yang. 2015. RRAM-based analog approximate computing. IEEE Trans. Comput.-Aided Design Integr. Circ. Syst. 34, 12 (Dec. 2015), 1905--1917.
24. Jiayin Li, Meikang Qiu, Jianwei Niu, Laurence T. Yang, Yongxin Zhu, and Zhong Ming. 2013. Thermal-aware task scheduling in 3D chip multiprocessor with real-time constrained workloads. ACM Trans. Embedded Comput. Syst. 12, 2 (2013), 24.
25. Jiangpeng Li, Kai Zhao, Jun Ma, and Tong Zhang. 2015. True-damage-aware enumerative coding for improving NAND flash memory endurance. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 23, 6 (June 2015), 1165--1169.
26. Qingan Li, Jianhua Li, Liang Shi, Mengying Zhao, C. J. Xue, and Yanxiang He. 2014. Compiler-assisted STT-RAM-based hybrid cache for energy efficient embedded systems. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 22, 8 (Aug. 2014), 1829--1840.
27. Duo Liu, Yi Wang, Zhiwei Qin, Zili Shao, and Yong Guan. 2012. A space reuse strategy for flash translation layers in SLC NAND flash memory storage systems. IEEE Trans. Very Large Scale Integr (VLSI) Syst. 20, 6 (June 2012), 1094--1107.
28. Asit K. Mishra, Xiangyu Dong, Guangyu Sun, Yuan Xie, Narayanan Vijaykrishnan, and Chita R. Das. 2011. Architecting on-chip interconnects for stacked 3D STT-RAM caches in CMPs. In Proceedings of the 38th Annual International Symposium on Computer Architecture (ISCA’11). 211--216.
29. Dimin Niu, Yiran Chen, Cong Xu, and Yuan Xie. 2010. Impact of process variations on emerging memristor. In Proceedings of the 47th Design Automation Conference (DAC’10). 877--882.
30. Jianwei Niu, Zhong Ming, Meikang Qiu, Hai Su, Zonghua Gu, and Xiao Qin. 2015. Defending jamming attack in wide-area monitoring system for smart grid. Telecommun. Syst. 60, 1 (2015), 159--167.
31. Zhiwei Qin, Yi Wang, Duo Liu, and Zili Shao. 2010. Demand-based block-level address mapping in large-scale NAND flash storage systems. In Proceedings of the 8th IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS’10). 173--182.
32. Zhiwei Qin, Yi Wang, Duo Liu, and Zili Shao. 2011. A two-level caching mechanism for demand-based page-level address mapping in NAND flash memory storage systems. In 2011 17th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’11). 157--166.
33. Zhiwei Qin, Yi Wang, Duo Liu, and Zili Shao. 2012. Real-time flash translation layer for NAND flash memory storage systems. In Proceedings of the 2012 IEEE 18th Real Time and Embedded Technology and Applications Symposium (RTAS’12). 35--44.
34. Meikang Qiu, Zhong Ming, Jiayin Li, Keke Gai, and Ziliang Zong. 2015. Phase-change memory optimization for green cloud with genetic algorithm. IEEE Trans. Comput. 64, 12 (Dec. 2015), 3528--3540.
35. Meikang Qiu, Lei Zhang, Zhong Ming, Zhi Chen, Xiao Qin, and Laurence T. Yang. 2013. Security-aware optimization for ubiquitous computing systems with SEAT graph approach. J. Comput. Syst. Sci. 79, 5 (2013), 518--529.
36. Liang Shi, Jianhua Li, Qingan Li, C. J. Xue, Chengmo Yang, and Xuehai Zhou. 2014. A unified write buffer cache management scheme for flash memory. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 22, 12 (Dec. 2014), 2779--2792.
37. Liang Shi, Kaijie Wu, Mengying Zhao, C. J. Xue, Duo Liu, and E. H. Sha. 2016. Retention trimming for lifetime improvement of flash memory storage systems. IEEE Trans. Comput.-Aided Design Integr. Circ. Syst. 35, 1 (Jan. 2016), 58--71.
38. Zhenyu Sun, Xiuyuan Bi, Hai Li, Weng-Fai Wong, and Xiaochun Zhu. 2014. STT-RAM cache hierarchy with multiretention MTJ designs. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 22, 6 (June 2014), 1281--1293.
39. B. Tim. 2013. Bonnie. (2013). http://www.garloff.de/kurt/linux/bonnie/.
40. Chundong Wang and Weng-Fai Wong. 2013. TreeFTL: Efficient RAM management for high performance of NAND flash-based storage systems. In Proceedings of the Design, Automation Test in Europe Conference Exhibition (DATE’13). 374--379.
41. Guohui Wang, Yong Guan, Yi Wang, and Zili Shao. 2016. Energy-aware assignment and scheduling for hybrid main memory in embedded systems. Computing 98, 3 (2016), 279--301.
42. Tianzheng Wang, Duo Liu, Yi Wang, and Zili Shao. 2015. Towards write-activity-aware page table management for non-volatile main memories. ACM Trans. Embed. Comput. Syst. 14, 2, Article 34 (Feb. 2015), 23 pages.
43. Yi Wang, Min Huang, Zili Shao, H. C. B. Chan, L. A. D. Bathen, and N. D. Dutt. 2014a. A reliability-aware address mapping strategy for NAND flash memory storage systems. IEEE Trans. Comput.-Aided Design Integr. Circ. Syst. 33, 11 (Nov. 2014), 1623--1631.
44. Yi Wang, Duo Liu, Zhiwei Qin, and Zili Shao. An endurance-enhanced flash translation layer via reuse for NAND flash memory storage systems. In Proceedings of the Design, Automation and Test in Europe, (DATE’11), 14--19.
45. Yi Wang, Zili Shao, H. C. B. Chan, L. A. D. Bathen, and N. D. Dutt. 2014b. A reliability enhanced address mapping strategy for three-dimensional (3-D) NAND flash memory. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 22, 11 (2014), 1--12.
46. Wujie Wen, Yaojun Zhang, Yiran Chen, Yu Wang, and Yuan Xie. 2014. PS3-RAM: A fast portable and scalable statistical STT-RAM reliability/energy analysis method. IEEE Trans. Comput.-Aided Design Integr. Circ. Syst. 33, 11 (Nov. 2014), 1644--1656.
47. Chin-Hsien Wu, Tei-Wei Kuo, and Li-Pin Chang. 2006. The design of efficient initialization and crash recovery for log-based file systems over flash memory. ACM Trans. Storage 2, 4 (Nov. 2006), 449--467.
48. Chin-Hsien Wu and Hsin-Hung Lin. 2012. Timing analysis of system initialization and crash recovery for a segment-based flash translation layer. ACM Trans. Des. Autom. Electron. Syst, 17, 2, Article 14 (April 2012), 14:1--14:21.
49. Gang Wu, Huxing Zhang, Meikang Qiu, Zhong Ming, Jiayin Li, and Xiao Qin. 2013. A decentralized approach for mining event correlations in distributed system monitoring. J. Parallel Distrib. Comput. 73, 3 (2013), 330--340.
50. Qi Zhang, Xuandong Li, Linzhang Wang, Tian Zhang, Yi Wang, and Zili Shao. 2015b. Lazy-RTGC: A real-time lazy garbage collection mechanism with jointly optimizing average and worst performance for NAND flash memory storage systems. ACM Trans. Design Autom. Electr. Syst. 20, 3 (2015), 43.
51. Yaojun Zhang, Yong Li, Zhenyu Sun, Hai Li, Yiran Chen, and A. K. Jones. 2015a. Read performance: The newest barrier in scaled STT-RAM. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 23, 6 (June 2015), 1170--1174.
52. Bo Zhao, Jun Yang, Youtao Zhang, Yiran Chen, and Hai Li. 2013. Common-source-line array: An area efficient memory architecture for bipolar nonvolatile devices. ACM Trans. Des. Autom. Electron. Syst. 18, 4, Article 57 (Oct. 2013), 18 pages.
53. Mengying Zhao, Lei Jiang, Liang Shi, Youtao Zhang, and C. J. Xue. 2015. Wear relief for high-density phase change memory through cell morphing considering process variation. IEEE Trans. Comput.-Aided Design Integr. Circ. Syst. 34, 2 (Feb. 2015), 227--237.
54. Miao Zhou, Yu Du, Bruce Childers, Daniel Mosse, and Rami Melhem. 2016. Symmetry-agnostic coordinated management of the memory hierarchy in multicore systems. ACM Trans. Archit. Code Optim. 12, 4, Article 61 (Jan. 2016), 26 pages.

Index Terms

• Computer systems organization

  • Embedded and cyber-physical systems

• Hardware

  • Emerging technologies

    • Memory and dense storage

  • Integrated circuits

    • Semiconductor memory

      • Non-volatile memory

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Memory management

          • Allocation / deallocation strategies

          • Garbage collection

          • Secondary storage

• Theory of computation

  • Design and analysis of algorithms

    • Online algorithms

      • Caching and paging algorithms