(3.235.41.241) 您好!臺灣時間:2021/04/21 13:25
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:孟柏文
研究生(外文):Po-wen Meng
論文名稱:索引結構在快閃記憶體儲存系統之研究
論文名稱(外文):A Survey of Index Structures on Flash–Memory Storage Systems
指導教授:吳晉賢吳晉賢引用關係
指導教授(外文):Chin-Hsien Wu
學位類別:碩士
校院名稱:國立臺灣科技大學
系所名稱:電子工程系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2009
畢業學年度:98
語文別:中文
論文頁數:44
中文關鍵詞:快閃記憶體索引結構
外文關鍵詞:flash memorybuffer controlindex structure
相關次數:
  • 被引用被引用:0
  • 點閱點閱:125
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
近年來隨著嵌入式系統的應用越來越廣泛,高容量快閃記憶體的需求也隨之上升。許多儲存媒介因為製造成本低廉、體積小及省電等優點[1],逐漸使用快閃記憶體取代原本的硬碟,使得快閃記憶體的索引架構(index structure)成為當前一項重要的研究議題。然而快閃記憶體所擁有之硬體特性,如寫入前刪除(erase-before-write)、區塊存取(Block Access)、平均磨損(wear-leveling)等[2],皆令當前運作於快閃記憶體上之嵌入式系統的索引結構,出現許多需要解決的問題。
本論文將介紹現行使用於快閃記憶體儲存系統上之索引架構[3]如: BFTL[4]、IBSF[5]、RBFTL[6]、IPL Approach[7],以及μ-tree[8]。本論文將針對資料存取的效能[9][10]、不同資料量多寡對於系統的負擔,以及系統出現錯誤當機時的可靠度[11][12][13][14]等方面進行探討比較,透過詳盡的比較分析也可為未來的系統設計提供他們的想法與分析各種因素,而當面臨多個程序需同時存取同一索引結構時,所產生的一些有關鎖定協定 (locking protocol)[15][16]和暫存區的並行控制(concurrency buffer control)[17]等具有挑戰性的問題,也將會在本篇論文中被討論。
With the applications of embedded systems in recent years, more and more demand for reliable and huge-capacity flash-memory storage systems is rising. Many flash-memory storage systems have gradually replaced hard-disk drives in many applications because of its advantages such as low cost, small size and low-power consumption[1] [2]. Therefore, index structures on flash-memory have become an important research topic[3]. However, flash-memory has distinct characteristics such as out-place update, erase-before-write, garbage collection, and wear-leveling such that current implementation of index structures on flash-memory requires a delicate design.
In the thesis, we will introduce some famous index structures on flash-memory storage systems such as BFTL[4], IBSF[5], RBFTL[6], IPL Approach[7], as well as the μ-tree[8]. This thesis will compare these index structures in terms of their performance on data access[9][10], system workload on different amount of data written [11][12][13][14] and crash recovery from a failure. The detailed comparison can provide their design insight and analyze the various factors for future design. Some challenging issues about a locking protocol[15][16] and concurrency buffer control[13][17] will be discussed when two or more processes will access a same index structure.
論文摘要 III
ABSTRACT IV
誌 謝 V
表格索引 VI
圖表索引 VII
第一章 引言 1
第二章 研究動機 3
第三章 快閃記憶體之硬體特性 4
第四章 相關文獻 8
4.1 BFTL (B-tree Layer for Flash Translation Layer) 8
4.2 IBSF (an Index Buffer management Scheme of FTL) 10
4.3 RBFTL (Reliable-BFTL) 11
4.4 IPL Approach (In-Page-Logging Approach) 13
4.5μ-tree 14
第五章 快閃記憶體之索引結構研究與分析 16
5.1 各種索引結構之運作 16
5.1.1 BFTL 16
5.1.2 IBSF 17
5.1.3 RBFT L 19
5.1.4 IPL Approach 21
5.1.5 μ-TREE 22
5.2 目前應用在快閃記憶體上之分析比較 23
5.2.1 各系統架構之優缺點 23
5.2.2各系統架構間之特點比較 25
5.3 各索引結構比較表 28
5.4 挑戰議題 30
5.3.1 概覽 30
5.3.2 以鎖定方式改善並行控制問題 30
5.3.3 改善暫存器設計方式增加系統效能 31
第六章 結論 32
參考文獻 33
作者簡介 36
授權書 37
[1] Bez, R., Camerlenghi, E., Modelli, A. and Visconti, A. Introduction to flash memory. Proceedings of the IEEE, 91, (4 2003), 489-502.
[2] Kawaguchi, A., Nishioka, S. and Motoda, H. A flash-memory based file system. In Proceedings of the Proceedings of the USENIX 1995 Technical Conference Proceedings on USENIX 1995 Technical Conference Proceedings (New Orleans, Louisiana, 1995). USENIX Association.
[3] Wu, M. and Zwaenepoel, W. eNVy: a non-volatile, main memory storage system. In Proceedings of the Proceedings of the sixth international conference on Architectural support for programming languages and operating systems (San Jose, California, United States, 1994). ACM.
[4] Wu, C.-H., Kuo, T.-W. and Chang, L. P. An efficient B-tree layer implementation for flash-memory storage systems. ACM Trans. Embed. Comput. Syst., 6, (3 2007), 19.
[5] Lee, H.-S., Park, S., Song, H.-J. and Lee, D.-H. An Efficient Buffer Management Scheme for Implementing a B-Tree on NAND Flash Memory. In Proceedings of the Proceedings of the 3rd international conference on Embedded Software and Systems (Daegu, Korea, 2007). Springer-Verlag.
[6] Xiang, X., Yue, L., Liu, Z. and Wei, P. A reliable B-tree implementation over flash memory. In Proceedings of the Proceedings of the 2008 ACM symposium on Applied computing (Fortaleza, Ceara, Brazil, 2008). ACM.
[7] Lee, S.-W. and Moon, B. Design of flash-based DBMS: an in-page logging approach. In Proceedings of the Proceedings of the 2007 ACM SIGMOD international conference on Management of data (Beijing, China, 2007). ACM.
[8] Kang, D., Jung, D., Kang, J.-U. and Kim, J.-S. Mu-tree: an ordered index structure for NAND flash memory. In Proceedings of the Proceedings of the 7th ACM \& IEEE international conference on Embedded software (Salzburg, Austria, 2007). ACM.
[9] Park, C., Seo, J., Seo, D., Kim, S. and Kim, B. Cost-Efficient Memory Architecture Design of NAND Flash Memory Embedded Systems. In Proceedings of the Proceedings of the 21st International Conference on Computer Design (2003). IEEE Computer Society.
[10] Yin, S., Pucheral, P. and Meng, X. A sequential indexing scheme for flash-based embedded systems. In Proceedings of the Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology (Saint Petersburg, Russia, 2009). ACM.
[11] Jaluta, I., Sippu, S. and Soisalon-Soininen, E. Concurrency control and recovery for balanced B-link trees. The VLDB Journal, 14, 2 (2005), 257-277.
[12] Wu, C.-H., Kuo, T.-W. and Chang, L.-P. The Design of efficient initialization and crash recovery for log-based file systems over flash memory. Trans. Storage, 2, (4 2006), 449-467.
[13] Wu, C.-H., Kuo, T.-W. and Chang, L.-P. Efficient initialization and crash recovery for log-based file systems over flash memory. In Proceedings of the Proceedings of the 2006 ACM symposium on Applied computing (Dijon, France, 2006). ACM.
[14] Wu, C.-H. and Kuo, T.-W. An adaptive two-level management for the flash translation layer in embedded systems. In Proceedings of the Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design (San Jose, California, 2006). ACM.
[15] S. Byun, M. H. a. H. H. Flash memory lock management for portable information systems. International Journal of Cooperative Information Systems, vol.15, no.3 (15 2006), 79.
[16] Bayer, R. and Schkolnick, M. Concurrency of operations on B-trees. Morgan Kaufmann Publishers Inc., City, (1988).
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔