A comparative evaluation of buffer replacement algorithms LIRS-WSR and AD-LRU for flash memory based systems
Date
2014
Authors
Singh Mahara, Dabbal
Journal Title
Journal ISSN
Volume Title
Publisher
Department of Computer Science and Information Technology
Abstract
Flash memory has characteristics of asymmetric I/O latencies for read, write and erase
operations and out-of-place update. Thus, buffering policy for flash based systems has to
consider these properties to improve the overall performance. Existing buffer replacement
algorithms such as LRU, LIRS, ARC etc do not deal with differing I/O latency of flash
memory. Therefore, these algorithms have been revised to make them suitable for buffering
policy for flash based systems. Among different flash aware buffer replacement algorithms
LIRS-WSR and AD-LRU are two new buffer replacement policies that can be suitable for
flash based systems. LIRS-WSR enhances LIRS by reordering the writes of not-cold-dirty
pages from the buffer cache to flash storage to focus on the reduction of number of
write/erase operations as well as preventing serious degradation of buffer hit ratio. AD-LRU
also focuses on improving overall performance of flash based systems by reducing number of
write /erase operations and by retaining high buffer hit ratio. We evaluate these two different
approaches with same objectives of improving buffering policy for flash based systems by
using trace driven simulation.
When workload has high reference locality, AD-LRU has significantly superior performance
than LIRS-WSR in terms of both hit rate and write count. AD-LRU has higher hit rate up to
22% and minimizes write count up to 40% in comparison to LIRS-WSR. This is because of
AD-LRU‟s good adaptive technique to handle changes in reference patterns.
For uniformly distributed workloads, the difference in hit rates and write count of AD-LRU
and LIRS-WSR is comparatively small. AD-LRU outperforms LIRS-WSR by increasing hit
rate up to 5% and decreasing write count up to 3% in comparison to LIRS-WSR in its worst
case.
Keywords: Flash memory, Buffer Replacement Algorithm, LIRS, LIRS-WSR, AD-LRU,
Hit Rate, Write Count
Description
Keywords
Flash memory, Buffer replacement algorithm