AMP Algorithm

The AMP algorithm, which adapts to achieve the optimality criteria set in the previous section, is outlined in Figures 3 and 4. We now draw attention to the important portions of the algorithm and the logic behind the choices we have made.

We make a conscious effort to avoid a separate data structure to track the adapted values of $p$ and $g$ for each detected sequential stream. We store the value of $p$ and $g$ in the page data structure. This removes any restriction on the number of streams that can be tracked.

Lines 20-23 implement the synchronous prefetching component of the algorithm. The number of pages to be prefetched on a read miss is not fixed (as in FS algorithms) but is the adapted value of $p$ stored in the metadata of the previous page.

Whenever the current $p$ is greater than the Asynchronous Prefetch Threshold ($APT$), asynchronous prefetching is activated. $APT$ is set to an empirically reasonable value of $4$. A page at a distance of $APT/2$ from the last page prefetched is chosen as the prefetch trigger page and the $tag$ is set (Lines 41, 49). When there is a hit on a $tag$ page, the $tag$ is reset and an asynchronous prefetch is initiated for $p$ pages as specified in the last page of the current set (Lines 27-30).

Adapting the degree of prefetch (p): As per Theorem III.1, we desire to operate at a point where $p = r\cdot L$. If $p$ is more than this optimal value, the last page in a prefetched set will reach the LRU end unaccessed. We give such a page another chance by moving it to the MRU position and setting the $old$ flag (Line 53). Whenever an unaccessed page is moved to the MRU position in this way, it is an indication that the current value of $p$ is too high, and therefore, we reduce the value of $p$ (Line 56). In Lines 31-35, $p$ is incremented by the $readsize$ (the size of read request is pages) whenever there is a hit on the $last$ page of a read set (pages read in the same I/O) which is also not marked $old$.

Adapting the trigger distance (g): The main idea is to increment $g$ if on the completion of a prefetch we find that a read is already waiting for the first page within the prefetch set (readWaiting()). If $g$ was larger, the prefetch would have been issued earlier, reducing or eliminating the stall time for the read. Thus, we increment $g$ in Line 47. However, we also need to decrement $g$ when $p$ itself is being decremented (Line 57). This keeps $g = r\cdot t(p)$ as per Lemmas III.1, III.2.

Whenever we adapt the value of $p$ and $g$ we store the updated values in the last page that has been read into the cache for the sequence. This is located by the lastInSequence($x$) method in Lines 11-19. The method simply returns the last page of the set that $x$ belongs to, or if the next set of pages has also been prefetched, it returns the last page of the next set. The logic is to keep the adapted values of $p$ and $g$ in the page that is most recently added to the cache and is thus most likely to stay in the cache for the longest time. In the unlikely case where the adapted values of $p$ and $g$ are forgotten because of page evictions, we set $p$ to the current prefetch size, and set $g$ to half of $p$.

Since AMP adapts to discover the optimal values of $p$ and $g$, it incurs a minor cost of adaptation which quickly becomes negligible and allows it achieve near optimal performance.

In the eviction part of the algorithm (Lines 50-59), pages that are $old$ or $accessed$ are evicted from the LRU end. Finally, we always make sure that $p \ge g + 1$ (Lines 44, 57) and $p \le p\_threshold$ (a reasonable $256$ pages for all algorithms).

Figure 3: AMP: Data structures and support functions

Figure 4: AMP: Main algorithm