research-article

An adaptive, low-cost wear-leveling algorithm for multichannel solid-state disks

Authors:

Tung-Yang Chou,

Li-Chun HuangAuthors Info & Claims

ACM Transactions on Embedded Computing Systems (TECS), Volume 13, Issue 3

Article No.: 55, Pages 1 - 26

https://doi.org/10.1145/2539036.2539051

Published: 24 December 2013 Publication History

Abstract

Multilevel flash memory cells double or even triple storage density, producing affordable solid-state disks for end users. As flash memory endures only limited program-erase cycles, solid-state disks employ wear-leveling methods to prevent any portions of flash memory from being retired prematurely. Modern solid-state disks must consider wear evenness at both block and channel levels. This study first presents a block-level wear-leveling method whose design has two new ideas. First, the proposed method reuses the intelligence available in flash-translation layers so it does not require any new data structures. Second, it adaptively tunes the threshold of block-level wear leveling according to the runtime write pattern. This study further introduces a new channel-level wear-leveling strategy, because block-level wear leveling is confined to a channel, but realistic workloads do not evenly write all channels. The proposed method swaps logical blocks among channels for achieving an eventually-even state of channel lifetimes. A series of trace-driven simulations show that our wear-leveling method outperforms existing approaches in terms of wear evenness and overhead reduction.

References

[1]

Agrawal, N., Bolosky, W. J., Douceur, J. R., and Lorch, J. R. 2007. A five-year study of file-system metadata. Trans. Storage 3.

Digital Library

[2]

Agrawal, N., Prabhakaran, V., Wobber, T., Davis, J. D., Manasse, M., and Panigrahy, R. 2008. Design tradeoffs for SSD performance. In Proceedings of the USENIX Annual Technical Conference on Annual Technical Conference (ATC'08). USENIX Association, 57--70.

Digital Library

[3]

Balakrishnan, M., Kadav, A., Prabhakaran, V., and Malkhi, D. 2010. Differential raid: Rethinking raid for SSD reliability. Trans. Storage 6, 2, 4:1--4:22.

Digital Library

[4]

Chang, L.-P. 2010. A hybrid approach to NAND-flash-based solid-state disks. IEEE Trans. Comput. 59, 10, 1337--1349.

Digital Library

[5]

Chang, L.-P. and Du, C.-D. 2009. Design and implementation of an efficient wear-leveling algorithm for solid-state-disk microcontrollers. ACM Trans. Des. Autom. Electron. Syst. 15, 1, 1--36.

Digital Library

[6]

Chang, L.-P. and Huang, L.-C. 2011. A low-cost wear-leveling algorithm for block-mapping solid-state disks. In Proceedings of the SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems (LCTES'11). ACM, New York, NY, 31--40.

Digital Library

[7]

Chang, L.-P. and Kuo, T.-W. 2002. An adaptive striping architecture for flash memory storage systems of embedded systems. In Proceedings of the 8th IEEE Real-Time and Embedded Technology and Applications Symposium. 187--196.

Digital Library

[8]

Chang, Y.-H., Hsieh, J.-W., and Kuo, T.-W. 2010. Improving flash wear-leveling by proactively moving static data. IEEE Trans. Comput. 59, 1, 53--65.

Digital Library

[9]

Dirik, C. and Jacob, B. 2009. The performance of pc solid-state disks (SSDs) as a function of bandwidth, concurrency, device architecture, and system organization. In Proceedings of the 36th Annual International Symposium on Computer Architecture (ISCA'09). ACM, New York, NY, 279--289.

Digital Library

[10]

Global Unichip Corp. 2009. GP5086 Datasheet. http://www.globalunichip.com/4-10.php.

[11]

Gupta, A., Kim, Y., and Urgaonkar, B. 2009. 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). ACM, 229--240.

Digital Library

[12]

Jung, D., Chae, Y.-H., Jo, H., Kim, J.-S., and Lee, J. 2007. 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'07). ACM, 160--164.

Digital Library

[13]

Kang, J.-U., Kim, J.-S., Park, C., Park, H., and Lee, J. 2007. A multi-channel architecture for high-performance NAND flash-based storage system. J. Syst. Archit. 53, 9, 644--658.

Digital Library

[14]

Katcher, J. 1997. Postmark: A new file system benchmark. Tech. rep., TR3022, Network Appliance.

[15]

Lee, S.-W., Park, D.-J., Chung, T.-S., Lee, D.-H., Park, S., and Song, H.-J. 2007. A log buffer-based flash translation layer using fully-associative sector translation. Trans. Embed. Comput. Syst. 6, 3, 18.

Digital Library

[16]

Micron®. 2008. Wear-Leveling Techniques in NAND Flash Devices. Micron Application Note (TN-29-42).

[17]

Open Source Development Lab. 2003. Iometer. http://http://www.iometer.org/.

[18]

Park, C., Cheon, W., Kang, J., Roh, K., Cho, W., and Kim, J.-S. 2008. A reconfigurable FTL architecture for NAND flash-based applications. ACM Trans. Embed. Comput. Syst. 7, 4, 1--23.

Digital Library

[19]

Park, S.-H., Park, J.-W., Kim, S.-D., and Weems, C. C. 2010. A pattern adaptive NAND flash memory storage structure. IEEE Trans. Comput. 99.

Digital Library

[20]

Rosen, K. 2003. Discrete Mathematics and Its Applications. McGraw-Hill, New York.

[21]

Samsung Electronics. 2006. K9F8G08B0M 1Gb &ast; 8 Bit SLC NAND Flash Memory. Data sheet.

[22]

Samsung Electronics. 2008. K9MDG08U5M 4G &ast; 8 Bit MLC NAND Flash Memory. Data sheet.

[23]

Seong, Y. J., Nam, E. H., Yoon, J. H., Kim, H., Choi, J.-Y., Lee, S., Bae, Y. H., Lee, J., Cho, Y., and Min, S. L. 2010. Hydra: A block-mapped parallel flash memory solid-state disk architecture. IEEE Trans. Comput. 59, 905--921.

Digital Library

[24]

Shang, P., Wang, J., Zhu, H., and Gu, P. 2011. A new placement-ideal layout for multiway replication storage system. IEEE Trans. Comput. 60, 8, 1142--1156.

Digital Library

[25]

Spansion®. 2008. Wear Leveling. Spansion Application Note (AN01).

Cited By

Bartolo ASabry Aly MMichelogiannakis GMitra S(2023)MC-ELMM: Multi-Chip Endurance-Limited Memory ManagementProceedings of the International Symposium on Memory Systems10.1145/3631882.3631905(1-16)Online publication date: 2-Oct-2023
https://dl.acm.org/doi/10.1145/3631882.3631905
Huang DFeng DLiu QDing BZhao WWei XTong W(2023)SplitZNS: Towards an Efficient LSM-Tree on Zoned Namespace SSDsACM Transactions on Architecture and Code Optimization10.1145/360847620:3(1-26)Online publication date: 7-Aug-2023
https://dl.acm.org/doi/10.1145/3608476
Choi JKim KKwak J(2020)WPA: Write Pattern Aware Hybrid Disk Buffer Management for Improving Lifespan of NAND Flash MemoryIEEE Transactions on Consumer Electronics10.1109/TCE.2020.298161866:2(193-202)Online publication date: May-2020
https://doi.org/10.1109/TCE.2020.2981618
Show More Cited By

Index Terms

An adaptive, low-cost wear-leveling algorithm for multichannel solid-state disks
1. Hardware
  1. Communication hardware, interfaces and storage
    1. External storage
  2. Integrated circuits
    1. Semiconductor memory
      1. Non-volatile memory
2. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection

Recommendations

Design and implementation of an efficient wear-leveling algorithm for solid-state-disk microcontrollers

Solid-state disks (SSDs) are storage devices that emulate hard drives with flash memory. They have been widely deployed in mobile computers as disk drive replacements. Flash memory is organized in terms of erase blocks. With the current technology, a ...
A low-cost wear-leveling algorithm for block-mapping solid-state disks
LCTES '10

Multilevel flash memory cells double or even triple storage density, producing affordable solid-state disks for end users. However, flash lifetime is becoming a critical issue in the popularity of solid-state disks. Wear-leveling methods can prevent ...
A low-cost wear-leveling algorithm for block-mapping solid-state disks
LCTES '11: Proceedings of the 2011 SIGPLAN/SIGBED conference on Languages, compilers and tools for embedded systems

Multilevel flash memory cells double or even triple storage density, producing affordable solid-state disks for end users. However, flash lifetime is becoming a critical issue in the popularity of solid-state disks. Wear-leveling methods can prevent ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Embedded Computing Systems

ACM Transactions on Embedded Computing Systems Volume 13, Issue 3

December 2013

385 pages

ISSN:1539-9087

EISSN:1558-3465

DOI:10.1145/2539036

Issue’s Table of Contents

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 24 December 2013

Accepted: 01 December 2012

Revised: 01 February 2012

Received: 01 October 2011

Published in TECS Volume 13, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

ADATA Technology Co., Ltd.
National Science Council Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
562
Total Downloads

Downloads (Last 12 months)18
Downloads (Last 6 weeks)3

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bartolo ASabry Aly MMichelogiannakis GMitra S(2023)MC-ELMM: Multi-Chip Endurance-Limited Memory ManagementProceedings of the International Symposium on Memory Systems10.1145/3631882.3631905(1-16)Online publication date: 2-Oct-2023
https://dl.acm.org/doi/10.1145/3631882.3631905
Huang DFeng DLiu QDing BZhao WWei XTong W(2023)SplitZNS: Towards an Efficient LSM-Tree on Zoned Namespace SSDsACM Transactions on Architecture and Code Optimization10.1145/360847620:3(1-26)Online publication date: 7-Aug-2023
https://dl.acm.org/doi/10.1145/3608476
Choi JKim KKwak J(2020)WPA: Write Pattern Aware Hybrid Disk Buffer Management for Improving Lifespan of NAND Flash MemoryIEEE Transactions on Consumer Electronics10.1109/TCE.2020.298161866:2(193-202)Online publication date: May-2020
https://doi.org/10.1109/TCE.2020.2981618
Cârstoiu GMicea MUngurean LMarcu M(2020)Novel battery wear leveling method for large‐scale reconfigurable battery packsInternational Journal of Energy Research10.1002/er.5879Online publication date: 7-Sep-2020
https://doi.org/10.1002/er.5879
Li JXu XPeng XLiao J(2019)Pattern-based Write Scheduling and Read Balance-oriented Wear-Leveling for Solid State Drivers2019 35th Symposium on Mass Storage Systems and Technologies (MSST)10.1109/MSST.2019.00-10(126-133)Online publication date: May-2019
https://doi.org/10.1109/MSST.2019.00-10
Wang SWu FLu ZZhou YXiong QZhang MXie C(2017)Lifetime adaptive ECC in NAND flash page managementProceedings of the Conference on Design, Automation & Test in Europe10.5555/3130379.3130674(1253-1256)Online publication date: 27-Mar-2017
https://dl.acm.org/doi/10.5555/3130379.3130674
Kim HNam EYun JLee SMin S(2017)P-BMSACM Transactions on Embedded Computing Systems10.1145/312655016:5s(1-19)Online publication date: 27-Sep-2017
https://dl.acm.org/doi/10.1145/3126550
Chang LHuang SChou KChen DDesnoyers Pde Lara E(2017)Relieving self-healing SSDs of heal stormsProceedings of the 10th ACM International Systems and Storage Conference10.1145/3078468.3078476(1-7)Online publication date: 22-May-2017
https://dl.acm.org/doi/10.1145/3078468.3078476
Lim SKim Y(2017)A quantitative model of application slow-down in multi-resource shared systemsPerformance Evaluation10.1016/j.peva.2016.10.004108(32-47)Online publication date: Feb-2017
https://doi.org/10.1016/j.peva.2016.10.004
Chang YLi YLin PLi HChang Y(2016)Realizing erase-free SLC flash memory with rewritable programming designProceedings of the Eleventh IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis10.1145/2968456.2968462(1-10)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1145/2968456.2968462
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents