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

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

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

Full text

Pdf (517 KB)

Source

International Conference on Compilers, Architecture and Synthesis for Embedded Systems archive
Proceedings of the seventh ACM international conference on Embedded software table of contents

Grenoble, France

SESSION: Flash memory table of contents

Pages 315-324

Year of Publication: 2009

ISBN:978-1-60558-627-4

Authors

Junseok Park	Seoul National University, Seoul, South Korea
Hyejeong Lee	Ewha University, Seoul, South Korea
Seunghwan Hyun	Seoul National University, Seoul, South Korea
Kern Koh	Seoul National University, Seoul, South Korea
Hyokyung Bahn	Ewha University, Seoul, South Korea

Sponsors

ACM: Association for Computing Machinery
SIGBED: ACM Special Interest Group on Embedded Systems
SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 26, Downloads (12 Months): 26, Citation Count: 0

Additional Information:

abstract references index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1629335.1629377 What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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.
	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.
	7	S. Bansal and D. S. Modha, "CAR: clock with adaptive replacement," Proceedings of the 3rd USENIX Conference on File and Storage Technologies, 2004.
	8	T. Johnson and D. Shasha, "2Q: A low overhead high performance buffer management replacement algorithm," Proceedings of the VLDB conference, 1994.
	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.
	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.
	11	E.G. Coffman and P.J. Denning, Operating Systems Theory, Prentice-Hall, Ch. 6, pp. 241--283, 1973.
	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.
	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.
	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.
	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.
	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.
	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.
	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.
	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.
	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.