Multiple Sequential Streams: varying cache size

Figure 8: On the left panel, we show the average achieved throughput over a period of two minutes as a function of the cache size for $100$ concurrent streams reading from five SCSI disks with thinktime = $10$ ms and readsize = $8$ KB. On the right panel, we show the corresponding wastage percentage (unaccessed pages evicted / total pages evicted * 100%).

It is extremely important to examine the common case where a limited cache is used by prefetching algorithms to cater to multiple sequential streams. In Figure 8, we depict the aggregate throughput achieved by a hundred parallel sequential streams with a thinktime of $10$ ms. The key observation is that different algorithms are suitable for different cache sizes, while AMP is universally the best, closely enveloping all the other plots.

Out of the FS algorithms, FS $_\textrm{8}$ is the best at very low cache sizes, while FS $_\textrm{64}$ is much better at the higher cache sizes. In FA algorithms, FA $_\textrm{8/3}$ is again the best at low cache sizes, while FA $_\textrm{256/127}$ is much superior at the higher cache sizes. As a rule of thumb, a lower prefetch degree performs better at lower cache sizes as high values of $p$ create prefetch wastage in smaller caches. This is in contrast to the single stream case, where a higher $p$ was always a better choice. This leads us to the adaptive synchronous algorithms. AS $_\textrm{Exp}$ increases $p$ exponentially, reaching higher values of $p$ quickly creating significant prefetch wastage for lower cache sizes. AS $_\textrm{Linear}$ , being slower in its adaptation, usually performs better than AS $_\textrm{Exp}$ at lower cache sizes while the reverse is true at higher cache sizes. The only algorithm that truly adapts the value of $p$ so as to minimize prefetch wastage is AMP. As a rough measure of the overall performance of each algorithm, we compute the average throughput across all cache sizes in Figure 8. We find that AMP outperforms the FA algorithms by $29$-$172$%, the AS algorithms by $12$-$24$%, the FS algorithms by $21$-$210$% and no prefetching and OBL by a factor of $8$. This is also a testimonial to the fact that AMP algorithm closely follows the optimality criteria derived in Section III-B.

In the right panel of Figure 8 we plot wastage, which is the percentage of evicted pages that were evicted before they could be accessed. We observe that the prefetching algorithms that have a high $p$ or aggressively increase $p$ suffer from the most prefetch wastage, and that wastage is larger for smaller cache sizes. The prefetch wastage in the case of AMP is always less than $0.1$%, while on an average, FA, FS, and AS algorithms waste up to $60$%, $41$%, and $11$% respectively.