臺灣博碩士論文加值系統

反及閘快閃記憶體，是嵌入式計算系統中記憶體應用的主流之一，主要因為反及閘快閃記憶體具有體積小、省電、非揮發性和耐震等特性。由於快閃記憶體具有特殊半導體特性，不僅限制其運用範圍而且導致管理方法複雜化，所以如何有效率管理快閃記憶體，已經成為一項重要研究議題。特別當所管理的記憶體容量愈大時，有效管理機制的重要性將愈彰顯。
本論文中，針對反及閘快閃記憶體為主要研究議題，我們不但提出一套完整有效的管理機制，而且實作一個快速模型反及閘快閃記憶體。首先，我們探討反及閘快閃記憶體的管理機制。在此系統中，我們是以區塊存取為研究對象，因為區塊是反及閘快閃記憶體中清除的基本單位，因此，以區塊作為探討基礎最為貼切。在我們反及閘快閃記憶體管理機制中，以減少清除頻率進而延長其使用壽命及提升系統效能為目標。藉由動態方式分析資料屬性，分離成冷、熱資料屬性，並將其資料寫回至不同屬性區塊中，以降低無意義的搬移動作。更進一步，動態均勻清除策略可達到延長快閃記憶體使用壽命與提高可靠度。再經由所提出的分配與回收策略互相搭配，成效更可彰顯。
再者，我們實作一個快速模型反及閘快閃記憶體。在嵌入式儲存系統中，常被使用的快閃記憶體為反及閘快閃記憶體和反或閘快閃記憶體。但基於成本、存取速度、體積及容量綜合性的考量，我們以反或閘快閃記憶體為參考需求，實作一個快速模型反及閘快閃記憶體。此方法是利用隨機讀取速度較慢與低價位的反及閘快閃記憶體，加上一FPGA設計建構成為一個快速模型的反及閘快閃記憶體。使得快速模型反及閘快閃記憶體讀取速度約是反或閘快閃記憶體的90%；但其價位大約是反及閘快閃記憶體的15%。快速模型反及閘快閃記憶體的功能行為，可模擬大部份反或閘快閃記憶體之應用。

The NAND type flash memory, briefly denoted by NandFlash, is one of the major applications in the embedded computing system, for its advantages of small size, great capacity, light power consummation, not volatility, and enduring vibration. For the special characteristic of the semi-conductor in NandFlash, its applications will be limited and its manager method will also be complication. It is a major study topic to effectually manage this NandFlash. Especially, when a file system manages the huge size NandFlash, the performance of management mechanism will be more importance.
To aim at NandFlash as the main research topic in this thesis, we not only propose a completely effective management mechanism but also implement a fast model NandFlash in the system. We discuss this NandFlash management mechanism first. In our proposal of the management system, since the basic erasing unit is a block in NandFlash, we use a block as the study basis with the meaning. In our NandFlash management mechanism, to reduce the cost of the erasing frequency, to extend its life cycle, and to promotes the system performance are major purposes. By dynamically analyzing the state of the data attribution, the data is divided into cold or hot data attribution and then re-written into the different block for reducing the nonsensical actions. Further, we can reduce the cost and promote the performance of the system. Then, we adopt a dynamic cycle-leveling strategy to extend the life cycle of NandFlash. It only needs to sacrifice a jot cost for extending the life of flash memory and promoting the high usage. The performance will be more explicit with the allocation strategy index and the cycle-leveling strategy of our proposal model.
Furthermore, we implement the fast type model of NandFlash, said FNandFlash. According to the characteristic of the flash memory, NOR type flash memory, denoted by NorFlash, and NandFlash are generally in Embedded System used. Moreover, for the major factors, the unit cost, access speed, physical volume, and capacity size, of a flash memory to utilization, we implement a FNandFlash, which is based on the NorFlash issues. The implementation method is to combine a FPGA with NandFlash into a FNandFlash, whose cost is cheaper and random access speed is lower than that of NorFlash. Making the access speed of FNandFlash is about 90% of NorFlash. The major function behavior of FNandFlash can simulate the application of most NorFlash.

中文摘要 i
英文摘要 iii
誌謝 v
目錄 vi
表目錄 ix
圖目錄 x
第一章 緒論 1
1.1 研究背景、動機與目的 2
1.1.1 快閃記憶體產值及市場佔有率 2
1.1.2 NorFlash 及 NandFlash特性之探討 4
1.1.3 各種記憶體之比較 6
1.1.4 小 結 7
1.2 研究方法 7
1.2.1 NandFlash管理 7
1.2.2 FNandFlash 7
1.3 研究貢獻 8
1.4 論文架構 8
第二章 基本背景知識與相關原理 9
2.1 專有名詞解釋 9
2.1.1 快閃記憶體 9
2.1.2 反或閘快閃記憶體 9
2.1.3 反及閘快閃記憶體 9
2.1.4 快閃記憶體檔案管理系統 10
2.1.5 損壞區塊表 10
2.1.6 平均覆寫 10
2.1.7 直接記憶體存取 10
2.1.8 ECC 10
2.1.9 案描述區塊 11
2.1.10 案分配表 11
2.1.11 現場可程式化閘陣列 11
2.1.12 FNandFlash 11
2.2 基本背景知識與相關原理 11
2.2.1 快閃記憶體之分類 11
2.2.2 非揮發性記憶體的種類與特性 12
2.2.3 快閃記憶體 13
2.2.4 Nandflash與NorFlash之運用 24
第三章 FPGA數位電路設計與矽智產介紹 30
3.1 FPGA數位電路設計介紹 30
3.1.1 重要考量因子 31
3.1.2 FPGA優缺點 33
3.1.3 數位積體電路設計之流程 33
3.1.4 硬體描述語言 34
3.1.5 FPGA簡介與硬體架構 36
3.2 矽智產簡介 38
第四章NandFlash管理系統 40
4.1 研究基礎定義 40
4.1.1 快閃記憶體基本特性限制 40
4.1.2 研究基本單位定義 40
4.1.3 NandFlash管理機制 41
4.2 快閃記憶體應用特性探討 41
4.2.1 NorFlash之應用探討 42
4.2.2 NandFlash之應用探討 43
4.3 NandFlash 檔案系統管理條件限制 44
4.4 NandFlash存取行為之探討 45
4.4.1 讀取 46
4.4.2 編程 46
4.4.3 清除 46
4.4.4 搬移 46
4.5 相關文獻探討與改善 46
4.5.1 Log-Structured File System 46
4.5.2 eNVy, a Non-volatile Main Memory Storage System 47
4.5.3 Flash-Memory Based File System 47
4.5.4 Linux Flash Memory Device Driver 48
4.5.5 New Clean Policy for Flash Memory 48
4.5.6 An Effective Flash Memory Manager for Reliable Flash
Memory Space Management 48
4.5.7 商業化的快閃記憶體檔案系統 49
4.5.8 An Effective Flash Memory Manager for Reliable Flash
Memory Space Management探討 49
4.5.9 小 結 55
4.6 NandFlash 綜合性管理探討 55
4.6.1 NandFlash容量空間之規劃 56
4.6.2 NandFlash管理之檔案紀錄格式 56
4.6.3 重要參數紀錄 58
4.6.4 損壞區塊管理 60
4.6.5 均勻使用 61
4.6.6 背景清除 67
4.6.7 計算時間及空間考量 68
4.6.8 NandFlash檔案操作之探討 69
4.7 本節結論 71
第五章 FNandFlash驗證說明 73
5.1 FNandFlash 73
5.1.1 開發環境及工具 73
5.1.2 NandFlash-K9F5608U0A-YCB0 74
5.1.3 FPGA設計平台 77
5.2 實驗說明 79
5.2.1 驗證平台 80
5.2.2 硬體系統設計 81
5.2.3 功能設計 83
5.2.4 實驗系統說明及結果 92
5.2.5 本研究之推導應用模型 99
5.3 本節結論 100
第六章 結論與未來研究 102
6.1 結論 102
6.2 未來研究 103
6.2.1 FFS管理成本效益 103
6.2.2 JFFS之改進 103
6.2.3 FFS管理IP化 103
參考文獻 105
附錄A. Pseudo Code 109
附錄B. NandFlash基本功能模擬及實際量測 111
附錄C. NandFlash與EPROM位址對應表 117

參考文獻
[1] B. Dipert and M. Levy, A Flash memory file systems - in Designing with FLASH MEMORY, San Diego: Annabooks, 1994, pp.227—271.
[2] Flash Memory Databook, Intel,1995.
[3] Samsung Corp., Flash/SmartMedia /File System, Memory Databook, 2000.
[4] R. Bez; E. Camerlenghi; A. Modelli, A. Visconti, "Introduction to flash memory," Proc. of the IEEE , Volume: 91 , Issue: 4 , April 2003, pp.489-502.
[5] J.C. Chen, T.H Kuo, L.E.Cleveland, C.K. Chung, N. Leong, Y. K. Kim, T. Akaogi and Y. Kasa, "A 2.7 V only 8 Mb×16 NOR flash memory," VLSI Circuits, Digest of Technical Papers, 1996, pp.172 -173.
[6] 涂志豪，全球快閃記憶體市場，2004.
http://news.taiwannet.com.tw/newsdata/showdetail1.php?ID=6971
[7] Flash Memory Market Regaining its Luster, 2002.
http://www.ppa.com.tw/IN-STAT/news/021107_MDR.htm
[8] Fujitsu Semiconductor Corp., "Flash Memory CMOS 128 M (16 M×8) Bit NAND-type MBM30LV0128," Data Sheet, 2000. http://www.fujitsumicro.com/
[9] Intel Corp., "Series 2+ Flash Memory Card Family Datasheet," 1997.
http://www.intel.com/design/.card/datashts
[10] Intel, "Datasheet, " August 2003.
http://www.intel.com/ design/flcomp/PRODBREF/298044.htm
[11] G. Irlam, "Unix file size survey," 1993.
http://www.base.com/gordoni/gordoni.html
[12] Samsung Corp., "K9F1208U0M-YCB0, K9F1208U0M-YIB0,K9F5608U0M
-YCB0 Flash Memory, " Data Sheet, 2001.
http://www.samsung.com
[13] Samsung Corp., " K9W8G08U1M Flash Memory, " Data Sheet, 2003.
http://www.samsung.com
[14] Toshiba Corp., "TC58256AFT--256-MBIT (32M* 8 BITS) CMOS NAND E2PROM," Data Sheet, 2001.
[15] 黃文增，陳俊達，陳彥勝，劉倉吉，「以區塊為基礎之反及閘快閃記憶體管理模式」，台北科技大學學報，Vol. 37-2，Submitted，March，2004.
[16] 黃文增，陳彥勝，陳俊達，鄭重志，「高可靠度和低成本的快閃記憶體管理方法之研究」，台北科技大學學報，Vol. 37-1，Accepted，Oct，2003.
[17] 鄭重志，黃文增，陳俊達，陳錦杏，「快閃記憶體檔案管理系統的設計與實作」， 台北科技大學學報，Vol. 36-2，pp. 43-62, March，2003.
[18] H. S. Huang, J. H. Huang, and P. Y. Chuang, "Performance Improvement of Embedded Flash Memory," J. of National Taipei University of Technology, Vol. 35-1, Mar. 2002, pp.9-21.
[19] M. L. Chiang, Paul C. H. Lee, and R. C. Chang, "Using data clustering to improve cleaning performance for flash memory," Software Practice and Experience, Vol.29, No.3, 1999, pp.267—290.
[20] M. L. Chiang, Paul C. H. Lee, and R. C. Chang, "Managing Flash Memory in Personal Communication Devices," Proc. of the International Symposium on Consumer Electronics, 1997.
[21] H. J. Kim, and S. G. Lee, "A New Flash Memory Management for Flash Storage System," IEEE COMPSAC Computer Software and Applications Conference, 1999. pp.284-289.
[22] Kawaguchi, S. Nishioka, and H. Motoda, "Flash memory based file system," Proc. USENIX95, 1995, pp.155—164.
[23] J. N. Matthews, D. Roselli, A. M. Costello, R. Y. Wang, and T. E. Anderson, "Improving the performance of log-structured file systems with adaptive methods," Proc. Sixteenth ACM Symposium on Operating Systems Principles, 1997, pp.238—251.
[24] C. Ruemmler and J. Wilkes, "UNIX disk access patterns," Proc. USENIX93, 1993, pp.405—420.
[25] C. H. Wu, L. P. Chang, and T. W. Kuo, "An Efficient B-Tree Layer for Flash Memory Storage Systems," The 9th International Conference on Real-Time Computing Systems and Applications (RTCSA 2003), Taiwan, 2003.
[26] D. See, C. Thurlo, "Managing data in an embedded system utilizing flash memory," Intel Technical Note, 1995.
http://www.intel.com/design/.comp/papers/esc .sh.htm
[27] M. L. Chiang, A Study on the Design of Memory Based Embedded Storage Systems, Ph.D. Thesis, Department of Computer and Information Science, National Chiao Tung University, Jan. 1999.
[28] M. Wu and W. Zwaenepoel, "eNVy: A non-volatile main memory storage system," Proc. of the 6th Symposium on Architectural Support for Programming Languages and Operating Systems, 1994, pp.86—97.
[29] H. J. Kim and S. G. Lee, "An Effective Flash Memory Manager for Reliable Flash Memory Space Management," IEICE Trans. Information & System, Vol. E85-D, No. 6, June 2002, pp. 951-964.
[30] T. Blackwell, J. Harris, and M. Seltzer, "Heuristic Cleaning Algorithms in Log- Structured File Systems," Proc. of the 1995 USENIX Technical Conference, 1995, pp.277-288.
[31] R. Shirota, "Test and repair of non-volatile commodity and embedded memories (NAND flash memory)," Proc. of International Test Conference, 2002. , 7-10 Oct. 2002, pp.1223.
[32] P. Torelli, "The Microsoft Flash File System," Dr. Dobb''s Journal, February 1995, pp. 62-72.
[33] David Woodhouse, "JFFS The Journaling Flash File System," Ottawa Linux Symposium, 2001.
[34] 黃文增，陳俊達，鄭重志，郭榮洲，「快速且低價的快閃記憶體之方法研究與實作」，台北科技大學學報， Vol. 37-1，Accepted，Oct，2003.
[35] AMD Corp., Am29LV652D128 Megabit (16 M x 8-Bit) Flash Memory, 2001,
http://www.amd.com
[36] Samsung Datasheet.
http://www.samsung.com/Products/Semiconductor/Flash/NAND/64Mbit/KM29U
64000AT/ KM29U64000AT.htm.
[37] Intel, What is Flash Memory ?
http://www.intel.com/design/flash/articles/what.htm
[38] 林傳生，使用VHDL電路設計語言之數位電路設計台北：儒林圖書，民國九十年。
[39] 林容益，CPU/SOC及週邊設(FPGA/CPLD)，台北：全華科技圖書，民國九十二年四月。
[40] 鄭信源，“VHDL 數位電路設計-進階篇”，台北：儒林圖書，民國九十二年二月。
[41] 葉丞淵，具多目標式腓特比解碼器之矽智財產生器，碩士論文，國立台北科技大學電腦通訊與控制研究所，台北，2002。
[42] R. Ceres, F. Douglis, K. Li, and B. Marsh, "Operating system implications of solid-state mobile computers," Technical Report MITL-TR-56-93, Matsushita Information Technology Laboratory, 1993.
[43] F. Douglis, R. C’eres, F. Kaashoek, K. Li, B. Marsh, and J.A. Tauber, "Storage alternatives for mobile computers," Proc. OSDI94, 1994, pp.25—37.
[44] 洪鵬雲，行動裝置上的快閃記憶體儲存管理與清除策略的研究，碩士論文，暨南國際大學資訊管理學系，南投，2000。
[45] 郭健，jffs檔系統分析，2003.
http://www.gzlinux.org/docs/category/filesystem/jffs-analysis.pdf
[46] R. Dan and J. Williams, "A TrueFFS and Flite Technical Overview of
M-Systems Flash File Systems", 80-SR-002-00-6L Rev. 1.30.
http://www.m-sys.com/tech1.htm, March 1997.
[47] P.J. Denning, "Working sets past and present," IEEE Trans. Software Eng., Vol.6, No.1, ,1980, pp.64—84.
[48] J. T. Robinson, "Analysis of steady-state segment storage utilization in a log-structured file system with least-utilized segment cleaning," OS Review, Vol.30, No.4, 1996, pp.29—32.
[49] D. Rossi, C. Metra, B. Ricc'o, "Fast and Compact Error Correcting Scheme for
Reliable Multilevel Flash Memories," Proc. IOLTW’02, 2002, pp.221-225.
[50] Holtek Corp., "HT27C020 CMOS 256K_8-Bit OTP EPROM," Data Sheet, 2002.
[51] Oki Electric Industry Co., Ltd., OKI VOICE SYNTHESIS LSI (’92-’93) DATA BOOK, Japan, 1992, pp.51-66.
[52] M. Aydos, T. Yanik, "High-speed implementation of an ECC-based wireless authentication protocol on an ARM microprocessor," IEE Proc. Commun., Vol 148, No.5, October 2001, pp.273-279.