簡易檢索 / 詳目顯示

回結果列表
研究生： 許耀仁
Yao-Jen Hsu
論文名稱： 一個基於請求更新距離的分群方法以降低固態硬碟之寫入放大
An Update-Distance-based Clustering Method for Reducing Write Amplification in Solid-State Drives
指導教授： 吳晋賢
Chin-Hsien Wu
口試委員: 吳晋賢
Chin-Hsien Wu
張原豪
Yuan-Hao Chang
張立平
Li-Pin Chang
謝仁偉
Jen-Wei Hsieh
學位類別： 碩士
Master
系所名稱： 電資學院 - 電子工程系
Department of Electronic and Computer Engineering
論文出版年： 2021
畢業學年度： 109
語文別： 中文
論文頁數： 41
中文關鍵詞： 分類方法 、寫入放大 、固態硬碟 、快閃記憶體
外文關鍵詞： Clustering Method, Write Amplification, Solid-State Drives, NAND Flash Memory
相關次數： 點閱：233  下載：7 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  •  上一筆

    • In recent years, solid-state drives (SSDs) that adopt NAND flash memory are widely used as the main storage devices. In particular, NAND flash memory has a special feature of ”out-of-place” updates to write the up-to-date data to a free page, and the corresponding old page will become invalid. When the number of free pages in SSDs is insufficient, garbage collection will be executed to reclaim the invalid pages in a block by erasing the block. Many studies have shown that a good hot/cold data separation (i.e., clustering) can greatly reduce the overhead of garbage collection so as to improve the SSD performance. However, we observe that most clustering methods provide the static setting of the number of clusters so that they may not always perform well for different kinds of workloads. Therefore, we will propose an update-distance-based clustering method to dynamically adjust an appropriate number of clusters at run time according to the current workload. With such a design, we can improve the SSD performance by reducing the overhead of garbage collection and further decrease the write amplification. Consequently, the experimental results show that the proposed method can decrease the total number of page writes in average by up to 23.1% when compared to the existing methods.

    Abstract IV Directory V Figure Directory VI Table Directory VI 1. Introduction 1 2. Background Knowledge 3 2.1 Flash Memory: Garbage Collection 3 2.2 Hot/Cold Data Separation for Garbage Collection 4 3. Related Work 5 3.1 UTC 5 3.2 WARM 6 3.3 PGIS 6 3.4 EDC 7 4. Motivation 8 5. An Update-Distance-based Clustering Method for Reducing Write Amplification in Solid-State Drives 10 5.1 System Overview 10 5.2 Cluster Information: Update Distance, Cluster Boundary and Cluster Table 12 5.2.1 Update Distance 12 5.2.2 Cluster Boundary 13 5.2.3 Cluster Table 14 5.3 An Update-Distance-based Clustering Method 16 5.3.1 Step (1): Identify Core Requests 16 5.3.2 Step (2): Cluster Core Requests 17 5.3.3 Step (3): Combine the Sub-Clusters 19 5.3.4 Step (4): Calculate the new Boundary of each Active Cluster 21 5.3.5 Step (5): Handle the Mapping between the Old and New Active Clusters 22 5.4 A Cluster-based GC Policy 24 6. Performance Evaluation 26 6.1 Experimental Setup and Performance Metrics 26 6.2 Total Numbers of Page Writes, Page Reads and Block Erases 29 6.3 Overhead of Garbage Collection and Average Response Time 32 6.4 Dynamic Adjustments of Number of Active Clusters at Runtime 35 6.5 Comparison of Space Overhead and Computation Overhead 36 7. Conclusion 39 Reference 40

    [1] A. Kawaguchi, S. Nishioka, and H. Motoda, “A flash-memory based file system.,” in USENIX, pp. 155–164, 1995.
    [2] M.-L. Chiang, P. C. Lee, and R.-C. Chang, “Managing flash memory in personal communication devices,” inISCE’97. Proceedings of 1997 IEEE International Symposium on Consumer Electronics (Cat. No. 97TH8348), pp. 177–182, IEEE, 1997.
    [3] X.-Y. Hu, E. Eleftheriou, R. Haas, I. Iliadis, and R. Pletka, “Write amplification analysis in flash-based solid state drives,” inProceedings of SYSTOR 2009: The Israeli Experimental Systems Conference, pp. 1–9, 2009.
    [4] C. Siau, K.-H. Kim, S. Lee, K. Isobe, N. Shibata, K. Verma, T. Ariki,J. Li, J. Yuh, A. Amarnath,et al., “13.5 a 512gb 3-bit/cell 3d flash memory on 128-wordline-layer with 132mb/s write performance featuring circuit-under-array technology,” in2019 IEEE International Solid-State Circuits Conference-(ISSCC), pp. 218–220, IEEE,2019.
    [5] M.-L. Chiang, P. C. Lee, and R.-C. Chang, “Using data clustering to improve cleaning performance for flash memory, ”Software: Practice and Experience, vol. 29, no. 3, pp. 267–290, 1999.
    [6] L.-P. Chang and T.-W. Kuo, “An adaptive striping architecture for flash memory storage systems of embedded systems,” inProceedings. Eighth IEEE Real-Time and Embedded Technology and Applications Symposium, pp. 187–196, IEEE, 2002.
    [7] J.-W. Hsieh, T.-W. Kuo, and L.-P. Chang, “Efficient identification of hot data for flash memory storage systems, ”ACM Transactions on Storage (TOS), vol. 2, no. 1, pp. 22–40, 2006.
    [8] S. Im and D. Shin, “Comboftl: Improving performance and lifespan of mlc flash memory using slc flash buffer, ”Journal of Systems Architecture, vol. 56, no. 12, pp. 641–653, 2010.
    [9] X.-Y. Hu, R. Haas, and E. Evangelos, “Container marking: Combining data placement, garbage collection and wear levelling for flash,” in2011 IEEE 19th Annual International Symposium on Modelling, Analysis, and Simulation of Computer and Telecommunication Systems, pp. 237–247, IEEE, 2011.
    [10] W.-H. Lin and L.-P. Chang, “Dual greedy: Adaptive garbage collection for page-mapping solid-state disks,” in2012 Design, Automation & Test in Europe Conference & Exhibition (DATE), pp. 117–122, IEEE, 2012.
    [11] J. Lee and J.-S. Kim, “An empirical study of hot/cold data separation policies in solid state drives (ssds), ” inProceedings of the 6thInternational Systems and Storage Conference, pp. 1–6, 2013.
    [12] D.-H. Bae, J.-W. Chang, S.-M. Park, B.-S. Jeong, S.-W. Kim, and S.-j. Cho, “An effective data clustering method based on expected update time in flash memory environment,” inProceedings of the29th Annual ACM Symposium on Applied Computing, pp. 1492–1497,2014.
    [13] J.Kim and I. Shin, “Clustering data according to update frequency to reduce garbage-collection overhead in solid-state drives, ”IEICE Electronics Express, pp. 12–20150984, 2015.
    [14] Y. Luo, Y. Cai, S. Ghose, J. Choi, and O. Mutlu, “Warm: Improving nand flash memory lifetime with write-hotness aware retention management,” in2015 31st Symposium on Mass Storage Systems and Technologies (MSST), pp. 1–14, IEEE,
    [15] J. Guo, Y. Hu, B. Mao, and S. Wu, “Parallelism and garbage collection aware i/o scheduler with improved ssd performance,”in2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 1184–1193, IEEE, 2017.
    [16] N.-V. Hiep and J.-W. Hsieh, “Timestamp-based hot/cold data identification scheme for solid state drives,” inProceedings of the 2018 Conference on Research in Adaptive and Convergent Systems,pp. 255–259, 2018.
    [17] Y.-Y. Lu, C.-H. Wu, and Y.-S. Chen, “A machine-learning-based data classifier to reduce the write amplification in ssds,” inProceedings of the International Conference on Research in Adaptive and Convergent Systems, pp. 213–218, 2020.
    [18] Y. Li, P. P. Lee, J. C. Lui, and Y. Xu, “Impact of data locality on garbage collection in ssds: A general analytical study,” inProceedings of the 6th ACM/SPEC International Conference on Performance Engineering, pp. 305–315, 2015.
    [19] L.-P. Chang, Y.-S. Liu, and W.-H. Lin, “Stable greedy: Adaptive garbage collection for durable page-mapping multichannel ssds,”ACM Transactions on Embedded Computing Systems (TECS), vol. 15,no. 1, pp. 1–25, 2016.
    [20] M. Ester, H.-P. Kriegel, J. Sander, X. Xu,et al., “A density-based algorithm for discovering clusters in large spatial databases with noise.,” inkdd, vol. 96, pp. 226–231, 1996.
    [21] “SNIA IOTTA Repository.” http://iotta.snia.org/.
    [22] “UMass Trace Repository.” http://traces.cs.umass.edu/.
    [23] S. Lee, D. Shin, Y.-J. Kim, and J. Kim, “Last: locality-aware sector translation for nand flash memory-based storage systems, ”ACMSIGOPS Operating Systems Review, vol. 42, no. 6, pp. 36–4

    QR CODE