AccuSim: Accurate Simulation of Cache Replacement Algorithms
|
|
AccuSim: Accurate Simulation of Cache Replacement Algorithms |
|
A critical problem in improving file system performance is to design an effective block replacement algorithm for the buffer cache. Despite the well-known interactions between prefetching and caching, almost all buffer cache replacement algorithms have been proposed and studied comparatively without taking into account file system prefetching which exists in all modern operating systems. It has been shown [1] that kernel prefetching can have a significant impact on the relative performance in terms of the number of actual disk I/Os of many well-known replacement algorithms; it can not only narrow the performance gap but also change the relative performance benefits of different algorithms. Moreover, the response time for all disk I/Os is not the same, and hence the improvement in disk I/Os does not directly translate to improvement in execution time. These results demonstrate the importance for buffer caching research to take file system prefetching into consideration, and to study actual disk I/Os and execution time for comparing different algorithms.
Figure 1: Various kernel subsystems on the path from file system to the disk
Figure 1 shows the various kernel subsystems that come into play before an I/O access from an application is delivered to the actual disk. The complexity of interactions between such subsystems entails that the various buffer caching algorithms are comparatively studied in a realistic setting. However, creating an actual kernel implementation of the algorithm being designed and the algorithms to be compared against can be a laborious task. In addition, even with such a kernel implementation, it is often non-trivial to obtain a controlled environment, e.g., a fixed cache size in the presence of a unified buffer cache, in the actual kernel for comparing various algorithms on an even basis. To overcome this challenge faced by cache replacement algorithm designers, we have developed a buffer cache simulator AccuSim that realistically models all the kernel subsystems involved in buffer cache management in modern operating systems. AccuSim has the following features:
AccuSim is a trace-driven simulator and uses traces which can easily be collected using system call tracing tools such as strace.
AccuSim faithfully implements the Linux kernel prefetching and I/O clustering mechanisms.
AccuSim interfaces with a realistic disk simulator, DiskSim, to enable the compensative study of the hit ratios, the number of disk requests, and the execution times of applications.
AccuSim accurately simulates I/O time under I/O clustering and prefetching.
AccuSim implements eight representative cache replacement algorithms.
AccuSim greatly simplifies the otherwise difficult task of systematic and accurate evaluation of various caching algorithms.
AccuSim provides for easy integration of a new replacement algorithm, and allow the replacement algorithm designer to focus on the algorithm by providing support functionality.
Figure 2: The architecture of AccuSim
Figure 2 shows the various modules of AccuSim.
AccuSim is driven by a trace that records the I/O operations during
the execution of an application. In particular, for each I/O
operation, the trace contains the identifier (inode) of the file
that is accessed, the offset into the file of the first block that is
accessed, the number of blocks being accessed, the I/O issue time, and
the I/O completion time. A trace with this information can easily be
collected using the standard system call tracing tool strace,
which can be easily modified to collect only the desired information.
The trace is then processed to caculate the time difference between
completion time of an I/O operation and the issue time of the next
which is interpreted as the computation time in between the two I/O
operations. Afterwards, the I/O issue and completion times are
discarded and the processed trace only records the sequence of I/O
operations interleaved with the computation time in between.
Each recorded entry in the trace contains a head which has the
following format:
typedef struct _tracehead
{
unsigned type:5;
unsigned pid:27;
union
{
unsigned inode;
unsigned child;
unsigned fnamesize;
};
} trace_head;
The trace entry can be for many different types, e.g., TREAD, TWRITE,
etc. For example read and write> system
calls, the recorded trace entry has the following format:
typedef struct _rwEntry
{
unsigned pc;
unsigned pcf;
unsigned pcall;
int iosize;
int iosizer;
unsigned filedes:16;
unsigned execTime;
unsigned fsize;
} rwEntry;
AccuSim has been made freely available in order to further file system research. You can obtain the source code of AccuSim and the traces used in our study by following the instructions at the download page.
AccuSim has been used extensively for a comparative
study [1] of the hit ratios, number of disk requests, and
execution time of eight modern cache replacement algorithms. Moreover,
AccuSim has also been used for designing a new cache replacement
algorithm in [2].
[2]
Program Counter Based Pattern Classification in Buffer Caching.
Chris Gniady, Ali R. Butt, and Y. Charlie Hu.
Proceedings of the 6th Symposium on Operating Systems Design and Implementation
(OSDI), San Francisco, CA, December 6-8, 2004.
PDF
Up till 2005, almost all buffer cache replacement algorithms – one of the fundamental research topics in Computer Systems design -- were proposed and studied comparatively without taking into account the kernel-driven prefetching, supported in the file systems of almost all modern operating systems. The paper "The performance impact of kernel prefetching on buffer cache replacement algorithms" appearing at SIGMETRICS 2005 for the first time showed that prefetching, using Linux as an example, can have a significant impact on a comprehensive set of well-known buffer cache replacement algorithms developed over the decade before, which were largely evaluated and compared without taking into account kernel prefetching. The paper sent a clear wakeup call to the file/storage system research community, that it is paramount for buffer caching research to take file system prefetching into consideration.
The paper has made a significant impact on Computer System design in the past ten years:
Our SIGMETRICS paper has had 84 citations in Google Scholar, 914 downloads from the ACM Digitial Library, and about 2000 total downloads when including the downloads from the authors’ home pages. These are rather significant for a system paper. A list of sampled citations attesting to how the paper influenced future research on caching and prefetching in Computer Systems Design:
A partial list (60) of Institutions and Companies that have downloaded Accusim since 2008:
Affiliation: Princeton University Affiliation: Stanford University Affiliation: University of Arizona Affiliation: University of Illinois at Chicago Affiliation: Mcgill University Affiliation: York University Affiliation: Pennsylvania State University Affiliation: University Of Mining and Metallurgy Affiliation: North Carolina State University Affiliation: NCSU CSC Palm Group Affiliation: University of Arizona Affiliation: University of Minnesota, Twin Cities Affiliation: Virginia Tech Student Affiliation: Huazhong University of Science and Technology, Wuhan, China Affiliation: National Chung Hsing University, Taiwan R.O.C. Affiliation: National Cheng Kung University, Taiwan Affiliation: Peking University Affiliation: City University of Science and Information Technology, Pakistan. Affiliation: Wuhan University, P.R.C Affiliation: University of Seoul Affiliation: Hanyang University, Seoul, Korea Affiliation: Hanyang University in Republic of Korea Affiliation: Computer System lab in Hanyang University in Republic of Korea Affiliation: Department of Computer Science and Engineering at National Chung-Hsing University in R.O.C Affiliation: School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, China Affiliation: HuaZhong University of Science and Technology Affiliation: University of technology hcm city Affiliation: RzeszŰw University of TEchnology Affiliation: National Chung Hsing University Affiliation: Department of Computer Science, National ChungHsing Univeristy Affiliation: northwest polytechnic university in China Affiliation: south china university of technology Affiliation: Huazhong university of science and technology, china Affiliation: Beijing Institute of Technology Affiliation: universiti Sains Malaysia (USM) Affiliation: Nile university Affiliation: KAIST Affiliation: NCHU,Taiwan Affiliation: IIT Delhi Affiliation: Indian Institute of Science Affiliation: Pune University, India Affiliation: Nuance Communications, Nuance.com Affiliation: IBM T.J. Watson Research Center Affiliation: Samsung Electronics, Inc. Affiliation: Mentor AIX Chips Affiliation: VMware, Inc. Affiliation: Microsoft