Although sequential and non-sequential data typically occupy the same cache, it is worthwhile to examine the prefetched data alone as most known prefetching algorithms suffer from cache pollution and prefetch wastage, and thus, can be improved.
We examine the case where an LRU (Least Recently Used) cache houses prefetched data for multiple concurrent sequential streams. We provide a theoretical analysis and prove the sufficient conditions for optimal online cache management for steady-state sequential streams. We also provide a simple implementation called AMP, the first member of the AA class which optimally adapts both the degree of prefetch and the timing thereof according to the workload and cache size constraints.
With a theoretically optimal design, AMP minimizes prefetch wastage and
cache pollution within the prefetched data while maximizing the aggregate
throughput achieved by the sequential streams.
To demonstrate the effectiveness of AMP, we compare it with 
other
prefetching algorithms including the best representatives from the FA, FS,
and AS classes, over a wide range of cache sizes, request rates,
request sizes, number of concurrent streams, and workloads.
We observe that AMP convincingly outperforms all the
FA, FS, and AS algorithms for any number of streams, and over all
cache sizes. In an experiment with a 
concurrent sequential streams and varying cache sizes, AMP beats the
FA, FS, and AS algorithms by 
-
%, 
-
%, and
-
% respectively while outperforming no prefetching and OBL
by a factor of 
.
AMP is consistently the
best performing algorithm in both the small cache and large cache scenarios,
even for complex workloads like SPC1-Read.
For SPC2 Video-on-Demand workload, AMP can support at least 
% more
streams than the next best algorithm. For streams with short sequences, as well,
for which optimality is more elusive, AMP surpasses all the other
contenders in its overall performance.