Single Sequential Stream

Figure 7: We show the achieved throughput as a function of the requested throughput for $8$ KB reads using a $100$ MB cache and one SCSI disk. For clarity, we split the comparison with AMP into two panels. AMP keeps up with the requested throughput and outperforms all other algorithms.

Our goal is to create an intimate understanding of the behavior of various sequential prefetching algorithms. We implemented $9$ prefetching algorithms and compared them with AMP. In Figure 7, we examine the actual throughput achieved as a function of the requested rate by a single sequential stream when assisted by various prefetching algorithms.

As expected, we observe the lowest throughput for no prefetch. The One Block Lookahead (OBL) algorithm performs about the same because we prefetch only one page and the request size is $2$ pages. A two or more block lookahead algorithm would have worked better by reducing the amount of misses. This is precisely the intent of the Fixed Synchronous (FS) class of algorithms which have a fixed degree of prefetch ($p$).

FA algorithms are superior to the FS algorithms because they can start a prefetch on a hit thereby avoiding more misses than the FS algorithms. Both the FS and FA algorithm results seem to indicate that the larger the $p$, the better the performance. This is true for a single sequential stream where the cache is abundantly available. In multiple stream experiments which compete for cache space, we will better appreciate the need for a careful choice of $p$.

We also measure the performance of the adaptive synchronous algorithms. AS $_\textrm{Linear}$ and AS $_\textrm{Exp}$ increase $p$ as the detected sequence becomes longer. For all the adaptive algorithms in this paper we uniformly use a maximum degree of prefetch of $256$ for a fair comparison. Both AS variants perform roughly the same as they adapt and reach this maximum value of $p$ during the first few seconds on the experiment.

AMP being able to adapt not only $p$ but also $g$ convincingly outperforms the FA algorithms by $2$-$50$%, the AS algorithms by $37$%, the FS algorithms by $37$-$52$% and no prefetching and OBL by $88$%. AMP closely followed by FA $_\textrm{256/127}$ was able to satisfy the request rate throughout the single stream experiment.