Program Counter Based Pattern Classification in Pattern Based Buffer Caching

One of the most important problems in improving file system performance is to design effective block replacement schemes for the buffer cache. Recently, replacement schemes making use of regularities of references such as sequential and looping references were proposed and shown to be more effective than purely recency or frequency based schemes such as LRU. However, these schemes classify access patterns at the granularity of an application or a file, and thus cannot discern multiple access patterns within the same file and have to redetect the same access patterns that appear in multiple files. In this paper, we propose a Program Counter based Classification (PCC) technique that reduces the overhead and improves the accuracy of the classification techniques in previous pattern based replacement schemes. In addition to accurately recognizing access patterns as in previous schemes, PCC is able to (1) recognize, without additional training, the reoccurrence of the same access pattern even if they appear in multiple files, and (2) differentiate concurrent access patterns within a single file. We show via trace-driven simulations that the performance gain of PCC compared to UBM is substantial. In particular, the hit ratio improves by as much as 25% and the execution time is reduced by as much as 14% compared to the UBM scheme for the traces we considered