{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T15:59:12Z","timestamp":1774540752454,"version":"3.50.1"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,7,24]],"date-time":"2023-07-24T00:00:00Z","timestamp":1690156800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Ministry of Science and Technology","award":["MOST 111-2221-E-011-086-MY3"],"award-info":[{"award-number":["MOST 111-2221-E-011-086-MY3"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2023,7,31]]},"abstract":"<jats:p>In recent years, solid-state drives (SSDs) that adopt NAND flash memory have been widely used as the main storage devices. In particular, NAND flash memory has a special feature of \u201cout-of-place\u201d 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 (GC) 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 GC so as to improve the SSD performance. However, previous clustering methods usually use a static number of clusters or a fixed size of granularity (i.e., a fine-grained or a coarse-grained granularity), so they may not always perform well for different kinds of workloads. Therefore, we propose a granularity-based clustering method to adaptively adjust the size of granularity groups for an appropriate number of clusters at runtime according to the update distances of logical addresses. According to the experimental results, we can improve SSD performance by reducing the overhead of GC and decrease the write amplification. Furthermore, we can show that the proposed method can utilize a fine-grained granularity to retain the record accuracy of update distances and also utilize a coarse-grained granularity to reduce the space required to record update distances.<\/jats:p>","DOI":"10.1145\/3605779","type":"journal-article","created":{"date-parts":[[2023,6,22]],"date-time":"2023-06-22T02:07:56Z","timestamp":1687399676000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["A Granularity-Based Clustering Method for Reducing Write Amplification in Solid-State Drives"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-6886-6107","authenticated-orcid":false,"given":"Yao-Jen","family":"Hsu","sequence":"first","affiliation":[{"name":"National Taiwan University of Science and Technology"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8704-1483","authenticated-orcid":false,"given":"Chin-Hsien","family":"Wu","sequence":"additional","affiliation":[{"name":"National Taiwan University of Science and Technology"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6969-8166","authenticated-orcid":false,"given":"Yu-Chieh","family":"Tsai","sequence":"additional","affiliation":[{"name":"National Taiwan University of Science and Technology"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2249-9725","authenticated-orcid":false,"given":"Chia-Cheng","family":"Liu","sequence":"additional","affiliation":[{"name":"National Taiwan University of Science and Technology"}]}],"member":"320","published-online":{"date-parts":[[2023,7,24]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/2554850.2554900"},{"key":"e_1_3_2_3_2","first-page":"187","volume-title":"Proceedingsof the 8th IEEE Real-Time and Embedded Technology and Applications Symposium","author":"Chang Li-Pin","year":"2002","unstructured":"Li-Pin Chang and Tei-Wei Kuo. 2002. An adaptive striping architecture for flash memory storage systems of embedded systems. In Proceedingsof the 8th IEEE Real-Time and Embedded Technology and Applications Symposium. IEEE, Los Alamitos, CA, 187\u2013196."},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/2820613"},{"key":"e_1_3_2_5_2","first-page":"177","volume-title":"Proceedings of the 1997 IEEE International Symposium on Consumer Electronics (ISCE\u201997)","author":"Chiang Mei-Ling","year":"1997","unstructured":"Mei-Ling Chiang, Paul C. H. Lee, and Ruei-Chuan Chang. 1997. Managing flash memory in personal communication devices. In Proceedings of the 1997 IEEE International Symposium on Consumer Electronics (ISCE\u201997). IEEE, Los Alamitos, CA, 177\u2013182."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-024X(199903)29:3<267::AID-SPE233>3.0.CO;2-T"},{"key":"e_1_3_2_7_2","unstructured":"Storage Performance Council. 2002. SPC Trace File Format Specification . Storage Performance Council."},{"key":"e_1_3_2_8_2","first-page":"226","volume-title":"Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining (KDD\u201996)","author":"Ester Martin","year":"1996","unstructured":"Martin Ester, Hans-Peter Kriegel, J\u00f6rg Sander, and Xiaowei Xu. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining (KDD\u201996). 226\u2013231."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3487064"},{"key":"e_1_3_2_10_2","first-page":"1184","volume-title":"Proceedings of the 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201917)","author":"Guo Jiayang","year":"2017","unstructured":"Jiayang Guo, Yiming Hu, Bo Mao, and Suzhen Wu. 2017. Parallelism and garbage collection aware I\/O scheduler with improved SSD performance. In Proceedings of the 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201917). IEEE, Los Alamitos, CA, 1184\u20131193."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3264746.3264790"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/1138041.1138043"},{"key":"e_1_3_2_13_2","volume-title":"An Update-Distance-Based Clustering Method for Reducing Write Amplification in Solid-State Drives","author":"Hsu Yao-Jen","year":"2021","unstructured":"Yao-Jen Hsu. 2021. An Update-Distance-Based Clustering Method for Reducing Write Amplification in Solid-State Drives. Master\u2019s thesis. National Taiwan University of Science and Technology. https:\/\/hdl.handle.net\/11296\/cqmbe2."},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/1534530.1534544"},{"key":"e_1_3_2_15_2","first-page":"237","volume-title":"Proceedings of the 2011 IEEE 19th Annual International Symposium on Modelling, Analysis, and Simulation of Computer and Telecommunication Systems","author":"Hu Xiao-Yu","year":"2011","unstructured":"Xiao-Yu Hu, Robert Haas, and Eleftheriou Evangelos. 2011. Container marking: Combining data placement, garbage collection and wear levelling for flash. In Proceedings of the 2011 IEEE 19th Annual International Symposium on Modelling, Analysis, and Simulation of Computer and Telecommunication Systems. IEEE, Los Alamitos, CA, 237\u2013247."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2010.09.005"},{"key":"e_1_3_2_17_2","unstructured":"Atsuo Kawaguchi Shingo Nishioka and Hiroshi Motoda. 1995. A flash-memory based file system. In Proceedings of the USENIX 1995 Technical Conference (TCON\u201995) . 1\u201313."},{"key":"e_1_3_2_18_2","first-page":"20150984","article-title":"Clustering data according to update frequency to reduce garbage-collection overhead in solid-state drives","author":"Kim Jaehyun","year":"2015","unstructured":"Jaehyun Kim and Ilhoon Shin. 2015. Clustering data according to update frequency to reduce garbage-collection overhead in solid-state drives. IEICE Electronics Express 13, 1 (2015), 20150984.","journal-title":"IEICE Electronics Express"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3078468.3078479"},{"key":"e_1_3_2_20_2","first-page":"273","volume-title":"Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST\u201915)","author":"Lee Changman","year":"2015","unstructured":"Changman Lee, Dongho Sim, Joo-Young Hwang, and Sangyeun Cho. 2015. F2FS: A new file system for flash storage. In Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST\u201915). 273\u2013286."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/2485732.2485745"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/1453775.1453783"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2019.2959318"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/2668930.2688036"},{"key":"e_1_3_2_25_2","first-page":"117","volume-title":"Proceedings of the 2012 Design, Automation, and Test in Europe Conference and Exhibition (DATE\u201912)","author":"Lin Wen-Huei","year":"2012","unstructured":"Wen-Huei Lin and Li-Pin Chang. 2012. Dual Greedy: Adaptive garbage collection for page-mapping solid-state disks. In Proceedings of the 2012 Design, Automation, and Test in Europe Conference and Exhibition (DATE\u201912). IEEE, Los Alamitos, CA, 117\u2013122."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3400286.3418239"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/MSST.2015.7208284"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/1416944.1416949"},{"key":"e_1_3_2_29_2","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1109\/ISSCC.2019.8662445","volume-title":"Proceedings of the 2019 IEEE International Solid-State Circuits Conference (ISSCC\u201919)","author":"Siau Chang","year":"2019","unstructured":"Chang Siau, Kwang-Ho Kim, Seungpil Lee, Katsuaki Isobe, Noboru Shibata, Kapil Verma, Takuya Ariki, et\u00a0al. 2019. A 512Gb 3-bit\/cell 3D flash memory on 128-wordline-layer with 132MB\/s write performance featuring circuit-under-array technology. In Proceedings of the 2019 IEEE International Solid-State Circuits Conference (ISSCC\u201919). IEEE, Los Alamitos, CA, 218\u2013220."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2018.00041"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2021.3091957"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2020.2982623"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/2915916"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2016.10.006"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3319647.3325840"},{"key":"e_1_3_2_36_2","first-page":"1","volume-title":"Proceedings of the 10th USENIX Conference on Hot Topics in Storage and File Systems (HotStorage\u201918)","author":"Yong Hwanjin","year":"2018","unstructured":"Hwanjin Yong, Kisik Jeong, Joonwon Lee, and Jin-Soo Kim. 2018. VStream: Virtual stream management for multi-streamed SSDs. In Proceedings of the 10th USENIX Conference on Hot Topics in Storage and File Systems (HotStorage\u201918). 1\u20136."}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3605779","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3605779","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:19Z","timestamp":1750178179000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3605779"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,24]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,7,31]]}},"alternative-id":["10.1145\/3605779"],"URL":"https:\/\/doi.org\/10.1145\/3605779","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,24]]},"assertion":[{"value":"2022-10-25","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-04","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-07-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}