A buffer replacement algorithm exploiting multi-chip parallelism in solid state disks

ABSTRACT

Solid State Disks (SSDs) are superior to magnetic disks from a performance point of view due to the favorable features of NAND flash memory. Furthermore, thanks to improvement on flash memory density and adopting a multi-chip architecture, SSDs replace magnetic disks rapidly. Most previous studies have been conducted for enhancing the performance of SSDs, but these studies have been worked on the assumption that the operation unit of a host interface is the same as the operation unit of NAND flash memory, where it is needless to give consideration to partially-filled pages. In this paper, we analyze the overhead caused by the partially-filled pages, and propose a buffer replacement algorithm exploiting multi-chip parallelism to enhance the write performance. Our simulation results show that the proposed algorithm improves the write performance by up to 30% over existing approaches.

REFERENCES

• 1: 2Gx8 bit NAND flash memory (K9GAG08U0M). Samsung Electronics, 2006.
• 2: 2Gx8 bit NAND flash memory (K9WAG08U1A). Samsung Electronics, 2006.
• 3: SystemC. http://www.systemc.org/home, 2007.
• 4: N. Agrawal, V. Prabhakaran, T. Wobber, J. D. Davis, M. Manasse, and R. Panigrahy. Design tradeoffs for SSD performance. In Proceedings of USENIX Annual Technical Conference, pages 57--70, 2008.
• 5: A. Birrell, M. Isard, C. Thacker, and T. Wobber. A design for high-performance flash disks. ACM SIGOPS Operating Systems Review, 41(2):88--93, 2007.
• 6: T. Bisson, S. A. Brandt, and D. D. Long. A hybrid Disk-Aware Spin-Down algorithm with I/O subsystem support. In Proceedings of the 26th International Performance, Computing, and Communications Conference (IEEE IPCCC), pages 236--245, 2007.
• 7: L. Cai and D. Gajski. Transaction level modeling: an overview. In Proceedings of the 1st IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, pages 19--24. ACM, 2003.
• 8: A. M. Caulfield, L. M. Grupp, and S. Swanson. Gordon: using flash memory to build fast, power-efficient clusters for data-intensive applications. In Proceeding of the 14th international conference on Architectural support for programming languages and operating systems, pages 217--228, Washington, DC, USA, 2009. ACM.
• 9: L. Chang and T. Kuo. An adaptive striping architecture for flash memory storage systems of embedded systems. In Proceedings of the 8th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 187--196, 2002.
• 10: P. M. Chen, E. K. Lee, G. A. Gibson, R. H. Katz, and D. A. Patterson. RAID: high-performance, reliable secondary storage. ACM Computing Surveys, 26(2):145--185, 1994.
• 11: H. Jo, J. Kang, S. Park, J. Kim, and J. Lee. FAB: flash-aware buffer management policy for portable media players. IEEE Transactions on Consumer Electronics, 52(2):485--493, 2006.
• 12: T. Johnson and D. Shasha. 2Q: a low overhead high performance buffer management replacement algorithm. In Proceedings of the 20th International Conference on Very Large Data Bases, pages 439--450. Morgan Kaufmann Publishers Inc., 1994.
• 13: J. Kang, J. Kim, C. Park, H. Park, and J. Lee. A multi-channel architecture for high-performance NAND flash-based storage system. Journal of Systems Architecture, 53(9):644 -- 658, 2007.
• 14: H. Kim and S. Ahn. BPLRU: a buffer management scheme for improving random writes in flash storage. In Proceedings of the 6th USENIX Conference on File and StorageTechnologies, pages 1--14, 2008.
• 15: J. Kim, D. Jung, J. Kim, and R. Huh. A methodology for extracting performance parameters in solid state disks (SSDs). In Proceedings of the 17th IEEE International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (IEEE MASCOTS '09), London, United Kingdom, 2009.
• 16: J. H. Kim, S. H. Jung, and S. Y. Ho. Cost and performance analysis of NAND mapping algorithms in shared-bus multi-chip configuration. In Proceedings of the International Workshop on Software Support for Portable Storage (IWSSPS), 2008.
• 17: T. Kuo, J. Hsieh, L. Chang, and Y. Chang. Configurability of performance and overheads in flash management. In Proceedings of the 2006 conference on Asia South Pacific design automation, pages 334--341, 2006.
• 18: S. Lee, D. Shin, and J. Kim. Buffer-Aware garbage collection for NAND flash Memory-Based storage systems. In Proceedings of the International Workshop on Software Support for Portable Storage (IWSSPS), pages 27--32, 2008.
• 19: D. R. Llanos. TPCC-UVa benchmark. http://www.infor.uva.es/~diego/tpcc-uva.html, 2006.
• 20: N. Megiddo and D. S. Modha. ARC: a Self-Tuning, low overhead replacement cache. In Proceedings of the 2nd USENIX Conference on File and Storage Technologies, pages 115--130, San Francisco, CA, 2003. USENIX Association.
• 21: B. Ozden, R. Rastogi, and A. Silberschatz. Buffer replacement algorithms for multimedia storage systems. In Proceedings of the Third IEEE International Conference on Multimedia Computing and Systems, pages 172--180, 1996.
• 22: J. Shin, Z. Xia, N. Xu, R. Gao, X. Cai, S. Maeng, and F. Hsu. FTL design exploration in reconfigurable high-performance SSD for server applications. In Proceedings of the 23rd international conference on Supercomputing (ICS '09), pages 338--349, Yorktown Heights, NY, USA, 2009. ACM.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.3 Performance Analysis and Design Aids**
          Subjects: Simulation**

General Terms:
Algorithms, Design, Measurement, Performance

Keywords:
buffer replacement algorithm, nand flash memory, solid state disk (SSD)