Short Sequences

Figure 12: We show the achieved throughput as a function of the average sequence length ranging from $1$ I/O (essentially random) to $8192$ I/Os. We use a single stream with thinktime = $0.2$ ms and a $100$ MB cache.

In Section III-B, we derived the optimality criteria for sequential prefetching in the steady state. We have not discussed the behavior of the sequential prefetching algorithms when the average length of sequences is rather short. Apart from providing close to optimal performance for long streams, AMP achieves the best overall performance for short streams as well. Figure 12 shows the throughput of various algorithms as the length of sequences go from $1$ (effectively random) to $8192$ read I/Os. The AS algorithms along with FS $_\textrm{8}$ and FA $_\textrm{8/3}$ perform well for short sequence lengths as they have a smaller $p$ and suffer from less prefetch wastage. As the sequence lengths are increased, the FA $_\textrm{256/127}$ becomes a strong contender. The fact that AMP starts off with a small $p$ and adapts to make it larger if necessary makes it perform reasonably well for short sequences. As the length of sequences becomes larger, the adaptive power of AMP allows it discover the right combination of $p$ and $g$. AMP is therefore not only provably optimal for steady sequential streams but also has the best overall performance for short sequences as well.