成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	林倍寬 Lin, Pei-Kuan
論文名稱：	運用保留區空間的快閃記憶體位址轉譯層之設計 DESIGN OF A NOVEL FLASH TRANSLATION LAYER WITH EFFICIENT UTILIZATION OF SPARE AREA FOR NAND FLASH MEMORY
指導教授：	張大緯 Chang, Da-Wei
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 資訊工程學系 Department of Computer Science and Information Engineering
論文出版年：	2010
畢業學年度：	98
語文別：	英文
論文頁數：	75
中文關鍵詞：	快閃記憶體
外文關鍵詞：	Garbage collection, Flash translation layer, Flash memory
相關次數：	點閱：72 下載：2
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

在 NAND 快閃記憶體當中通常需要一層位址轉譯層來隱藏「Erase before write」的特性。其中一個著名的相關研究--- Superblock FTL, 在各種的位址轉譯層當中有良好的表現；它將數個鄰近的 logical blocks 組合成一個 superblock, 而一個 superblock 是以 coarse-grain 方式來作轉址，而在一個 superblock 當中的 pages 是以 fine-grain 的方式，可以任意地放置在數個 physical blocks 上的任一位置。Coarse-grain 的轉址資訊是存放在記憶體當中，而 fine-grain 的轉址資訊是存放在保留區空間( spare area )當中。這樣的設計減少了記憶體使用量，同時又保有 fine grain translation 的彈性。在這篇論文當中我們提出了ESB (Extended SuperBlock) FTL. ESB FTL 繼承了 Superblock FTL 的優點，同時將它的限制之處，作了改進。為了突破 Superblock FTL 的限制，我們試著為每一個 page 在 spare area 當中存放一個專屬的 PBN 和 Page offset。為了解決 spare area 太小的問題我們提出了「 Per-group PBMT」和「Dual spare area format」的方法。在解決了這個問題之後，一個 superblock 的大小可以作調整而不再有限制；隨著一個 superblock size 變大，NAND Flash Memory的空間使用率也隨之提升。實驗結果顯示 ESB FTL 與其他 FTL 相比之下，所減少的 Garbage collection overhead 高達 947%。而在反應時間和空間利用率方面， ESB FTL 也有較好的表現。

In NAND flash-based storage systems, a flash translation layer (FTL) is employed to hide the erase-before-write characteristics of NAND flash memory. Among several efficient FTLs, Superblock FTL achieves good performance in consideration of garbage collection (GC) overhead, space utilization and memory usage. It combines multiple adjacent logical blocks into a superblock which is mapped at coarse granularity, while the pages inside one superblock are mapped freely at fine granularity to any location in several physical blocks. The fine-grained mapping information is stored in the spare area of NAND flash memory for reducing memory usage. However, the restricted space of spare area limits the size of a superblock and thus reduces the benefits of Superblock FTL.
In this thesis, we propose ESB (Extended Superblock) FTL inheriting from the Superblock FTL. ESB keeps the advantage while eliminates the limitation of the Superblock FTL. This is achieved by dividing the mapping of a logical block into multiple groups, assigning different roles to spare areas, and storing different types of mapping information in the spare areas with different roles. The design of ESB allows it to support large superblocks, reducing the garbage collection overhead further. The simulation results on five traces show that the ESB FTL decreases the garbage collection overhead by up to 947%, compared to Superblock FTL. In addition, ESB achieves better performance in aspects of space utilization and response time

Chapter 1 Introduction .......................................................................... 1
1 Motivation ................................................................................................... 4
2 Research Method ......................................................................................... 5
3 Thesis Organization ..................................................................................... 7
Chapter 2 Background .......................................................................... 8
1 Background ................................................................................................. 8
1.1 Introduction to NAND Flash Memory .................................................................. 8
1.2 Flash Translation Layer ( FTL ) .......................................................................... 10
Chapter 3 Related Works .................................................................... 11
1 Page-mapped and Block-mapped FTL ........................................................ 11
2 Hybrid-mapped FTL .................................................................................. 13
3 Superblock FTL ......................................................................................... 19
3.1 Overall Architecture ........................................................................................... 19
3.2 The Motivation of ESB FTL ............................................................................... 25
Chapter 4 Design and Method ............................................................ 28
1Design Goal ................................................................................................ 28
2 Problems .................................................................................................... 29
3 The Proposed Solution ............................................................................... 31
3.1 Per-Group PBMT ............................................................................................... 31
3.2 Dual Spare Area Formats ................................................................................... 33
4 Hybrid Level Mapping Table ..................................................................... 39
5 Analysis of group size and the total number of groups per logical block ..... 42
6 Mapping-induced writes (MIW) ................................................................. 44
7 Garbage Collection Policy and Cache Management ................................... 47
Chapter 5 Performance Evaluation .................................................... 49
1 Evaluation Setup and Traces ...................................................................... 49
2 Garbage Collection Overhead .................................................................... 53
3 Space Utilization ........................................................................................ 56
4 Superblock Size ......................................................................................... 59
5 Cache Hit Ratio ......................................................................................... 63
6 Overall Overhead ....................................................................................... 64
7 Response time ............................................................................................ 68
Chapter 6 Conclusion .......................................................................... 71
                                    

[1] Intel Corporation, “Understanding the Flash Translation Layer (FTL) Specification”, Technical Report AP-684, 1998.

[2] Samsung Electronics, "512M x 8 Bit / 256M x 16 Bit NAND Flash Memory," Datasheet, available at http://www.datasheetcatalog.org/datasheets/700/389215_DS. pdf, 2005.

[3] J.U. Kang, H. Jo, J.S. Kim, and J. Lee, "A Superblock-based Flash Translation Layer for NAND Flash Memory" Proceedings of the Sixth ACM and IEEE International Conference Embedded Software, pp. 161-170, 2006.

[4] J. Kim, J. M. Kim, S. Noh, S. L. Min, and Y. Cho, “A Space-efficient Flash Translation Layer for Compactflash Systems”, Consumer Electronics, Vol. 48, No. 2, pp. 366-375, May 2002.

[5] A. Ban, Flash File System, United States Patent, No 5,404,485, 1993.

[6] M.L. Chiang, P. C. H. Lee, and R.C. Chang, “Using Data Clustering to Improve Cleaning Performance for Flash Memory.”, Software Practices and Experiences, Vol. 29, No. 3, pp. 267–290, 1999.

[7] S.W. Lee, D.J. Park, T.S. Chung, D.H. Lee, S. Park, and H.J. Song,
"A Log Buffer-Based Flash Translation Layer Using Fully-Associative Sector Translation," ACM Trans. Embedded Computing Systems, vol. 6, no. 3, article no. 18, Jul. 2007.

[8] Micron Technical Report (TN-29-07): Small-Block vs. Large-Block NAND Flash Devices. Technical Report (TN-29-07):Small-Block vs. Large-Block NAND Flash Devices. http://www.micron.com/products/nand/technotes.

[9] S. Lee, D. Shin, Y.J. 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, Oct. 2008.

[10] J.Y. Shin, Z.L. Xia, N.Y. Xu, R. Gao, “FTL Design Exploration in Reconfigurable High-Performance SSD for Server Applications”, In Proceedings of the 23rd International Conference on Supercomputing, 2009. (ICS’09)

[11] P. Torelli, "The Microsoft Flash File System," Dr. Dobb's Journal,
pp. 62-72, Feb. 1995.

[14] D. Jung, Y. Chae, H. Jo, J. Kim, and J. Lee. A Group-based Wear-Leveling Algorithm for Large-Capacity Flash Memory Storage Systems. In Proceedings of the International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES), pages 160–164, September 2007. ISBN 978-1-59593-826-8.
[15] A. Kawaguchi, S. Nishioka, and H. Motoda, "A Flash-Memory Based File System," Proc. 1995 USENIX Winter Technical Conference,pp. 155-164, Jan. 1995.

[16] K. M. J. Lofgren, R. D. Norman, G B. Thelin, and A. Gupta. Wear Leveling Techniques for Flash EEPROM. In United States Patent, No 6,850,443, 2005.

[17] Samsung Electronics, "512M x 8 Bit / 256M x 16 Bit NAND Flash Memory," Datasheet, available at http://www.datasheetcatalog.org/datasheets/700/389215_DS.pdf, 2005.

[18] Y.G. Lee, D. Jung, D. Kang and J.S. Kim, "μ-FTL: A Memory Efficient Flash Translation Layer Supporting Multiple Mapping Granularities," Proc. Eighth ACM and IEEE International Conference Embedded Software (EMSOFT08), pp. 21-30, Oct. 2008.

[19] Y. Lee, D. Jung, J.S. Kim, S. Maeng, “Memory Management Scheme for Cost-Effective Disk-On-Modules in Consumer Electronics Devices”, IEEE Transactions on Consumer Electronics, Vol. 54, No. 4, NOVEMBER 2008.

[20]A. Gupta, Y. Kim, B. Urgaonkar, “DFTL: A Flash Translation Layer Employing Demand-based Selective Caching of Page-level Address Mappings”, In Proceeding of the 14th international conference on Architectural support for programming languages and operating systems (ASPLOS 09), March 2009.

[21] D. Kang, D. Jung, J.-U. Kang and J.-S. Kim, “μ-Tree: An Ordered
Index Structure for NAND Flash Memory,” Proc. Seventh ACM and IEEE International Conference Embedded Software (EMSOFT07), pp.144-153, Oct. 2007.

[22] C.H. Wu and T.W. Guo, "An Adaptive Two-Level Management
for the Flash Translation Layer in Embedded Systems," Proc. IEEE/ACM Int’l Conf. Computer Aided Design, pp. 601-606, November 2006.

[23] IOzone http://www.iozone.org/

[24] FileBench http://www.solarisinternals.com/wiki/index.php/FileBench

校內：2014-10-26公開
校外：2014-10-26公開

簡易檢索 / 詳目顯示

相關論文