Very Close Bounds on Offline Optimal Performance: OPT-UB and OPT-LB

We computed the average response times for OPT-UB and OPT-LB for a wide range of traces (Section IV-A) and cache sizes (Figures 8 through 13), and found that on an average the bounds ran within $2.18$% and $2.83$% of each other for two and three level single-path hierarchies, respectively. The maximum separation between bounds for any trace and cache combination was only $8.6$% and $10.0$% for the two and three level caches, respectively. In terms of inter-cache bandwidth usage, OPT-LB is optimal and coincides with OPT-UB for the $C_1$-$C_2$ traffic. This is because OPT-LB does not use any demotions and achieves the maximum possible hits in the $C_1$ cache (as given by Belady's OPT). For $C_2$-$C_3$ traffic, the bounds run, on an average, within $3.4$% of each other. OPT-LB is not optimal for the $C_2$-$C_3$ traffic because it does not use demotions between the $C_1$ and $C_2$ which could have potentially reduced the number of misses flowing out of $C_2$.

In a more complex multi-path scenario shown in Figure 14 (and Figure 15), the bounds ran about $8.5$% (and $10.8$%) of each other in terms of the average response time, and coincided in terms of inter-cache traffic.

We believe that the closeness of these bounds in practice and the fact that they are significantly superior to the current state-of-the-art multi-level caching algorithms (Figures 8 through 13) constitute an extremely significant result, and provide an important missing perspective to the field of multi-level caching.