More Web Proxy on the site http://driver.im/

research-article

A cost-aware page replacement algorithm for NAND flash based mobile embedded systems

Authors:

Seunghwan Hyun,

Hyokyung BahnAuthors Info & Claims

EMSOFT '09: Proceedings of the seventh ACM international conference on Embedded software

Pages 315 - 324

https://doi.org/10.1145/1629335.1629377

Published: 12 October 2009 Publication History

Abstract

NAND flash memory is widely used as secondary storage in mobile embedded systems such as cellular phones and digital cameras. These systems usually employ a compressed file system (CFS) to store system files which are fixed during the design phase, in combination with a normal file system to store data files. Since retrieving pages from a CFS requires additional decompression time, it is reasonable to grant them higher priorities when making a page replacement decision. In this paper, we present a new page replacement algorithm for NAND flash memory based embedded systems that considers asymmetric operation cost of each page. The proposed algorithm considers the decompression cost of a page from CFS as well as the asymmetric I/O costs of reads and writes in flash memory. To do this, the algorithm partitions the memory space into a read area, a write area, and a compressed area depending on different operation costs. The size of each area is then dynamically adjusted based on the change of access patterns and the contribution to reducing the I/O costs. Trace-driven simulations show that the proposed algorithm improves the I/O performance of mobile embedded systems significantly. Specifically, it reduces I/O time by 4.8-53.3% compared to widely acknowledged algorithms such as CLOCK, CAR, and CFLRU.

References

[1]

S. Hyun, H. Bahn and K. Koh, "LeCramFS: An Efficient Compressed File System for Flash-Based Portable Consumer Devices," IEEE Transactions on Consumer Electronics, vol. 53, no. 2, pp. 481--488, 2007.

Digital Library

[2]

http://valgrind.org/

[3]

N. Nethercote and J. Seward, "Valgrind: A Program Supervision Framework," Electronic Notes in Theoretical Computer Science, 2003.

[4]

SquashFS, http://squashfs.sourceforge.net/

[5]

CramFS, http://lxr.linux.no/source/fs/cramfs/README

[6]

S. Park, D. Jung, J. Kang, J. Kim and J. Lee, "CFLRU: replacement algorithm for flash memory," Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, 2006.

Digital Library

[7]

S. Bansal and D. S. Modha, "CAR: clock with adaptive replacement," Proceedings of the 3rd USENIX Conference on File and Storage Technologies, 2004.

Digital Library

[8]

T. Johnson and D. Shasha, "2Q: A low overhead high performance buffer management replacement algorithm," Proceedings of the VLDB conference, 1994.

Digital Library

[9]

Y. Zhou and J.F. Philbin, "The multi-queue replacement algorithm for second level buffer caches," Proceedings of the USENIX Annual Technical conference, 2001.

Digital Library

[10]

S. Jiang and X. Zhang, "LIRS: An efficient low inter-reference recency set replacement policy to improve buffer cache performance," Proceedings of the ACM SIGMETRICS conference, 2002.

Digital Library

[11]

E.G. Coffman and P.J. Denning, Operating Systems Theory, Prentice-Hall, Ch. 6, pp. 241--283, 1973.

Digital Library

[12]

http://www.samsung.com/global/business/semiconductor/productList.do?fmly_id=159

[13]

H. Jung, H. Shim, S. Park, S. Kang and J. Cha, "LRU-WSR: Integration of LRU and Writes Sequence Reordering for Flash Memory," IEEE Transactions on Consumer Electronics, vol. 54, no. 3, pp. 1215--1223, 2008.

Digital Library

[14]

H. Jo, J. Kang, S. Park, J. Kim and J. Lee, "FAB: Flash-Aware Buffer Management Policy for Portable Media Players," IEEE Transactions on Consumer Electronics, vol. 52, no. 2, pp. 485--493, 2006.

Digital Library

[15]

J. Kim, J.M. Kim, S.H. Noh, S.L. Min and Y. Cho, "A Space-Efficient Flash Translation Layer for Compact Flash Systems," IEEE Transactions on Consumer Electronics, vol. 48, no. 2, pp. 366--375, 2002.

Digital Library

[16]

S. Lee, D. Park, T. Chung, D. Lee, S. Park and H. Song, "A Log Buffer Based Flash Translation Layer Using Fully Associative Sector Translation," ACM Transactions on Embedded Computing Systems, vol. 6, no. 3, 2007.

Digital Library

[17]

H. Kim and S. Ahn, "BPLRU: a buffer management scheme for improving random writes in flash storage," Proceedings of the 6th USENIX Conference on File and Storage Technologies, 2008.

Digital Library

[18]

S. Kang, S. Park, H. Jung, H. Shim and J. Cha, "Performance Trade-Offs in Using NVRAM Write Buffer for Flash Memory-Based Storage Devices," IEEE Transactions on Computers, vol. 58, no. 6, pp. 744--758, 2009.

Digital Library

[19]

S. Jiang, F. Chen and X. Zhang, "CLOCK-Pro: An Effective Improvement of the CLOCK replacement," Proceedings of USENIX Annual Technical Conference, pp. 323--336, 2005.

Digital Library

[20]

H. Bahn, S. H. Noh, S. L. Min, and K. Koh, "Efficient Replacement of Nonuniform Objects in Web Caches," IEEE Computer, Vol.35, No.6, pp.65--73, 2002.

Digital Library

[21]

P. Cao and S. Irani, "Cost-Aware WWW Proxy Caching Algorithms," Proceedings of the USENIX Symposium on Internet Technology and Systems, pp. 193--206, 1997.

Digital Library

Cited By

Park SBahn H(2022)Memory Access Characteristics of Neural Network Workloads and Their Implications2022 IEEE Asia-Pacific Conference on Computer Science and Data Engineering (CSDE)10.1109/CSDE56538.2022.10089326(1-6)Online publication date: 18-Dec-2022
https://doi.org/10.1109/CSDE56538.2022.10089326
Yoon SPark HCho KBahn H(2022)Supporting Swap in Real-Time Task Scheduling for Unified Power-Saving in CPU and MemoryIEEE Access10.1109/ACCESS.2021.314016610(3559-3570)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2021.3140166
Lim SBahn H(2021)Selective Flushing of Modified Data for Smartphone Buffer Cache Management2021 IEEE Asia-Pacific Conference on Computer Science and Data Engineering (CSDE)10.1109/CSDE53843.2021.9718418(1-6)Online publication date: 8-Dec-2021
https://doi.org/10.1109/CSDE53843.2021.9718418
Show More Cited By

Index Terms

A cost-aware page replacement algorithm for NAND flash based mobile embedded systems
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Virtual memory

Recommendations

A Hybrid Approach to NAND-Flash-Based Solid-State Disks

Replacing power-hungry disks with NAND-flash-based solid-state disks (SSDs) is a recently emerging trend in flash-memory applications. One important SSD design issue is achieving a good balance between cost, performance, and lifetime. This study ...
Write-activity-aware nand flash memory management for pcm-based embedded systems
Flash-Aware RAID Techniques for Dependable and High-Performance Flash Memory SSD

Solid-state disks (SSDs), which are composed of multiple NAND flash chips, are replacing hard disk drives (HDDs) in the mass storage market. The performances of SSDs are increasing due to the exploitation of parallel I/O architectures. However, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EMSOFT '09: Proceedings of the seventh ACM international conference on Embedded software

October 2009

332 pages

ISBN:9781605586274

DOI:10.1145/1629335

Program Chairs:
Samarjit Chakraborty
TU Munich, Germany
,
Nicolas Halbwachs
Verimag/CNRS, Grenoble, France

Copyright © 2009 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 October 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ESWeek '09

Sponsor:

ESWeek '09: Fifth Embedded Systems Week

October 12 - 16, 2009

Grenoble, France

Acceptance Rates

EMSOFT '09 Paper Acceptance Rate 33 of 106 submissions, 31%;

Overall Acceptance Rate 60 of 203 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
608
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Park SBahn H(2022)Memory Access Characteristics of Neural Network Workloads and Their Implications2022 IEEE Asia-Pacific Conference on Computer Science and Data Engineering (CSDE)10.1109/CSDE56538.2022.10089326(1-6)Online publication date: 18-Dec-2022
https://doi.org/10.1109/CSDE56538.2022.10089326
Yoon SPark HCho KBahn H(2022)Supporting Swap in Real-Time Task Scheduling for Unified Power-Saving in CPU and MemoryIEEE Access10.1109/ACCESS.2021.314016610(3559-3570)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2021.3140166
Lim SBahn H(2021)Selective Flushing of Modified Data for Smartphone Buffer Cache Management2021 IEEE Asia-Pacific Conference on Computer Science and Data Engineering (CSDE)10.1109/CSDE53843.2021.9718418(1-6)Online publication date: 8-Dec-2021
https://doi.org/10.1109/CSDE53843.2021.9718418
Lim SBahn H(2021)Characterizing File Accesses in Android Applications and Caching ImplicationsIEEE Access10.1109/ACCESS.2021.31257799(150292-150303)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2021.3125779
Park YBahn H(2020)Modeling of the TLB miss rate and the Page fault rate for NVM-based Storage Systems2020 7th International Conference on Information Science and Control Engineering (ICISCE)10.1109/ICISCE50968.2020.00178(856-860)Online publication date: Dec-2020
https://doi.org/10.1109/ICISCE50968.2020.00178
Thakare ADeshpande P(2019)A Novel Adaptive Database Cache Optimization Algorithm Based on Predictive Working Sets in Cloud EnvironmentIEEE Access10.1109/ACCESS.2019.29127517(54343-54359)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2912751
Chang HChiang C(2018)PARC: A novel OS cache managerSoftware: Practice and Experience10.1002/spe.263348:12(2193-2222)Online publication date: 31-Aug-2018
https://doi.org/10.1002/spe.2633
Ou YJin PHärder T(2013)Flash-Aware Buffer Management for Database SystemsInternational Journal of Knowledge-Based Organizations10.4018/ijkbo.20131001023:4(22-39)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.4018/ijkbo.2013100102
Oh YChoi JLee DNoh SBolosky WFlinn J(2012)Caching less for better performanceProceedings of the 10th USENIX conference on File and Storage Technologies10.5555/2208461.2208486(25-25)Online publication date: 14-Feb-2012
https://dl.acm.org/doi/10.5555/2208461.2208486
Xiao WLei XLi RPark NLilja D(2012)PASSProceedings of the 2012 IEEE 10th International Symposium on Parallel and Distributed Processing with Applications10.1109/ISPA.2012.59(403-410)Online publication date: 10-Jul-2012
https://dl.acm.org/doi/10.1109/ISPA.2012.59
Show More Cited By

View Options

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents