Inverted Tree-like Hierarchy

We invert the cache hierarchy used above as shown in Figure 15. At the first level we have a single cache $C_{1a}$ ($50K$ blocks) and at the second level we have $C_{2a}$ ($40K$ blocks) and $C_{2b}$ ($30K$ blocks). The trace P1 accesses data through the $C_1, C_{2a}$ hierarchy, while the traces P2, P3, P4 or P5 are served through the $C_1, C_{2b}$ hierarchy. We again notice that PROMOTE-LRU performs within $1$% of the DEMOTE variant in terms of response time, and is twice as efficient in terms of bandwidth usage. PROMOTE-ARC performs much better than the LRU based algorithms as expected. DEMOTE cannot generalize ARC for this hierarchy and thus is not a contender. Again we observe that OPT-LB and OPT-UB provide close bounds ($10.8$% apart) on the optimal performance for the given hierarchy.