Check out the new USENIX Web site. next up previous
Next: Optimal Lower Bound: OPT-LB Up: Offline Optimal Previous: Quest for Offline Optimality

Optimal Upper Bound: OPT-UB

We define a conceptual policy OPT-UB that serves as an upper bound on performance, implying that no policy can perform better than this bound in terms of either average response time or inter-cache bandwidth usage by achieving better (lower) values for either metric. OPT-UB is a bound, not on the performance of a particular cache, but on the aggregate performance of the cache hierarchy.

Let OPT-UB be a policy that for a request sequence $ \sigma$, exhibits for each cache $ C_i$, $ h_i$ number of hits, while requiring no demotions or reloads from disks, where,

$\displaystyle h_i = hitOPT(\sigma, \sum_{j = 1}^i S_j) - hitOPT(\sigma, \sum_{j = 1}^{i-1} S_j)$ (3)

Note that we intend to compute a theoretical upper bound which is necessarily achievable.

Lemma 2.1   No policy can have more hits, up to any cache level, than OPT-UB. More precisely, OPT-UB maximizes $ \sum^k_{i = 1}h_k, \forall k \leq n$.

Proof. By Eqn. 3 the aggregate hits for the set of caches $ C_1,..,C_k$ is

$\displaystyle aggrHits_k = \sum_{i = 1}^k h_i = hitOPT(\sigma, \sum_{i = 1}^{k} S_i)$ (4)

By the definition of $ hitOPT$, this is the same as that obtained by Belady's OPT on a cache of the aggregate size. Since Belady's OPT is known to deliver the maximum possible hit ratio, $ aggrHits_k$ is maximized for all $ k \leq n$. $ \qedsymbol$

Theorem 2.1   No policy can have a lower total inter-cache traffic than OPT-UB.

Proof. Inter-cache traffic is the sum of misses and demotions between two adjacent caches (by Eqn. 2). Since, OPT-UB is defined to have no demotions and maximizes the aggregate hits at all levels of the cache (Lemma II.1), no other policy can have lower inter-cache traffic than OPT-UB. $ \qedsymbol$

Theorem 2.2   No policy can have a lower average response time than OPT-UB.

Proof. We prove by contradiction. Let a better performing policy achieve a lower average response time (equivalently, lower total response time) for a workload than OPT-UB, by providing $ h'_i$ hits at each corresponding cache $ C_i$, and $ m'$ overall misses, as compared to $ h_i$ hits and $ m$ misses for OPT-UB.
  % latex2html id marker 5713
$\displaystyle \therefore$ $\displaystyle \sum_{i = 1}^n h'_i\cdot t_i + m'\cdot t_{m}  < \sum_{i = 1}^n h_i\cdot t_i + m\cdot t_{m}$  
  $\displaystyle \Rightarrow$ $\displaystyle \sum_{i = 1}^n h'_i \cdot (t_i - t_{m}) + (m'+\sum^n_{i = 1}h'_i)\cdot t_{m}$  
    $\displaystyle  < \sum_{i = 1}^n h_i\cdot (t_i - t_{m}) + (m+\sum^n_{i = 1}h_i)\cdot t_{m}$  
  $\displaystyle \Rightarrow^{(a)}$ $\displaystyle \sum_{i = 1}^n h'_i \cdot (t_m - t_i)  > \sum_{i = 1}^n h_i \cdot (t_m - t_i)$  
  $\displaystyle \Rightarrow^{   }$ $\displaystyle \sum_{i = 1}^n h'_i \cdot (t_n - t_i + t_m - t_n)  > $  
    $\displaystyle        \sum_{i = 1}^n h_i \cdot (t_n - t_i + t_m - t_n)$  
  $\displaystyle \Rightarrow^{(b)}$ $\displaystyle \sum_{i = 1}^{n} h'_i \cdot (t_n - t_i )  > \sum_{i = 1}^{n} h_i \cdot (t_n - t_i)$  
    $\displaystyle         + (\sum_{i = 1}^{n} h_i - \sum_{i = 1}^{n} h'_i) \cdot (t_m - t_n )$  
  $\displaystyle \Rightarrow^{(c)}$ $\displaystyle \sum_{i = 1}^{n} h'_i \cdot (t_n - t_i )  > \sum_{i = 1}^{n} h_i \cdot (t_n - t_i)$  
  $\displaystyle \Rightarrow^{(d)}$ $\displaystyle \sum_{i = 1}^{n-1} h'_i \cdot (t_n - t_i ) > \sum_{i = 1}^{n-1} h_i \cdot (t_n - t_i)$  

(a) follows as the sum of all hits and misses is the same for both policies ( $ \vert\sigma_1\vert$) and the second term on both sides of the inequality can be removed. The second term on the right hand side of (b) is non-negative because $ t_m > t_n$ and by Lemma II.1, no policy can have more aggregate hits (up to any cache level) than OPT-UB. (c) follows by removing the non-negative second term in inequality (b). (d) follows as the $ n^{th}$ term in the summation is zero. Note that between step (a) and step (d), the superscript of the summation has dropped from $ n$ to $ n-1$. Steps (a) through (d) can be repeated until $ n = 2$ (as, for all $ i$, $ t_i > t_{(i-1)}$). We will then arrive at $ h'_1\cdot (t_2 - t_1) > h_1\cdot (t_2 - t_1)$. As $ t_2 > t_1$, it implies that $ h'_1 > h_1$, which contradicts Lemma II.1, which states that OPT-UB maximizes $ \sum^k_{i = 1}h_k, \forall k \leq n$ (including $ k = 1$).

$ \qedsymbol$


next up previous
Next: Optimal Lower Bound: OPT-LB Up: Offline Optimal Previous: Quest for Offline Optimality
root 2008-01-08