Tree-like Hierarchy

We use a hierarchy of three caches, $C_{1a}$ ($40K$ blocks) and $C_{1b}$ ($30K$ blocks) at the first level, and a shared cache $C_2$ ($50K$ blocks) at the second-level (see Figure 14). While $C_{1a}$ serves one of P2, P3, P4 or P5 traces, $C_{1b}$ serves the P1 trace. We impose no bandwidth restrictions and assume free demotions for the DEMOTE algorithm. We observe that for all four combinations, the PROMOTE-LRU has equal or better average response time while generating only half the inter-cache traffic than DEMOTE-LRU. DEMOTE cannot be applied to tree-like ARC hierarchies, allowing PROMOTE-ARC to win by default. This is because DEMOTE simulates a global ARC algorithm which adapts the ratio of the global ARC lists, $T_1$ and $T_2$. In single-path scenarios, the same ratio of the two ARC lists, $\vert T_1\vert:\vert T_2\vert$, can be enforced at all levels. However, in multi-path scenarios, this is not always possible, as the amount of $T_2$ pages in a cache depends on the workload it sees, and the ratio determined by ARC may not be enforceable.

In Figure 14, we also show the steps used to compute OPT-UB and OPT-LB in accordance to Section II-D. As usual, we observe that OPT-LB and OPT-UB provide close bounds ($8.5$% apart) on the optimal performance for the given hierarchy.