注:中括号可不用管
II. Sequential Prefetching
A. Rules of engagement
B. Synchronous Vs. Asynchronous Prefetching
There are two kinds of prefetch requests: (i) synchronous prefetch, and (ii) asynchronous prefetch. A synchronous prefetch is when on a miss on page x, we prefetch p extra pages beyond page x. It merely extends the extent of the client’s read request to include more pages. On the other hand, an asynchronous prefetch is when on a cache hit on a page x, we create a new read request to prefetch p pages beyond those already in the cache. In each set of p prefetched pages, a trigger page is identified at a trigger distance of g from the end of the prefetched set of pages (Figure 1). When g = 0, the trigger is set on the last page of the prefetched set. When a trigger page is hit, an asynchronous prefetch is requested for the next set of p sequential pages. Unlike synchronous prefetching, asynchronous prefetching enables us to always stay ahead of sequential read requests and for suitable values of p and g, never incur a read miss after the initial miss for a sequential stream [17]. Asynchronous prefetching is always used in conjunction with some form of synchronous prefetching to prefetch the initial set of pages. Notice that asynchronous prefetching creates new read requests on its own and, therefore, in cases where prefetches are wasted, asynchronous prefetching will have more disk seeks on the backend for the same workload than synchronous prefetching. However, for larger prefetches on data striped across disks, even synchronous prefetches will result in new read requests. As a guideline, asynchronous prefetching should be avoided in cases where prefetch wastage is high.
C. A Classification of Prefetching Algorithms
Sequential prefetching is the most promising and widely deployed prefetching technique for data servers. It has a high predictive accuracy and is extremely simple to implement. Simple methods are used to isolate the sequential components of workloads [17], upon which prefetching is applied. We can classify the known sequential prefetching techniques as follows:
• Fixed Synchronous (FS) prefetching: The simplest form of sequential prefetching is where we prefetch the next page on a miss (OBL [18]). Another variant is where a fixed number of pages (p) are prefetched on every miss.
• Adaptive Synchronous (AS) prefetching: This is a popular form of sequential prefetching where the number of pages prefetched on every miss (p) is gradually increased as the length of the sequence referenced becomes longer. The degree of prefetch, p starts with 1 and is either linearly incremented on every miss [20] (Linear-AS) or exponentially incremented (Exp-AS). Usually, there is a predefined upper limit for incrementing p. Although Exp-AS adapts faster than the Linear-AS method, it is prone to more wastage in workloads with many short sequences or when cache space is limited.