A NOVEL APPROACH OF ASYNCHRONOUS CACHE PREFETCHING FOR STORAGE VOLUME CONTROL

Abstract

Cache prefetching is a commonly used technique in which the data is prefetched from the disk to cache in advance, before host actually requests it. These days this technique is used in almost all modern storage volume controllers. One of the widely popular classes of prefetching algorithms is sequential prefetching. But there are two problems with these state-of-the-art sequential prefetching algorithms: (i) cache pollution, which occurs when a prefetched data replaces some more useful prefetched or demandpaged data, and (ii) prefetch wastage, which occurs when prefetched data is evicted by LRU (maintained in the cache) from the cache before it can be used. A sequential prefetching algorithm [BINNY S. GILL at al 2007] can have a fixed (static) or adaptive (dynamic) degree of prefetch and can either have synchronous (when it can prefetch only on amiss) or asynchronous (when it can also prefetch on a hit) way of prefetching. To capture these distinctions there are four classes of prefetching algorithms [BINNY S. GILL at al 2007]: fixed synchronous (FS), fixed asynchronous (FA), adaptive synchronous (AS), and adaptive asynchronous (AA). After exploring all these sets algorithms, their advantages and disadvantages we found that the relatively unexplored class of AA algorithms is in fact the most promising type of algorithms for sequential prefetching. We studied the cache prefetch algorithm presently used in IBM’s SAN volume controller and AMP algorithm [BINNY S. GILL at al 2007]. We also analyzed the basic problems and deficiencies of these two algorithms. In this thesis we will discuss the basic aspect of cache prefetching, and the challenges for a prefetch algorithm in a volume controller. On the basis of knowledge gained by the analysis of above two algorithms we proposed a new algorithm that has capabilities to tackle most of the problems in the discussed 2 | P a g e algorithm. Also we implemented AMP algorithm and our proposed algorithm to compare the effectiveness of the two algorithms. We prepared a cache simulator which simulates a cache and all its basic features like staging and destaging of data from disk. At last we compared the two algorithms on the basis of results we got from the simulation of two algorithms.