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,

$$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

$$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.

$$\therefore \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}$$

$$\Rightarrow \sum_{i = 1}^n h'_i \cdot (t_i - t_{m}) + (m'+\sum^n_{i = 1}h'_i)\cdot t_{m}$$

$$< \sum_{i = 1}^n h_i\cdot (t_i - t_{m}) + (m+\sum^n_{i = 1}h_i)\cdot t_{m}$$

$$\Rightarrow^{(a)} \sum_{i = 1}^n h'_i \cdot (t_m - t_i) > \sum_{i = 1}^n h_i \cdot (t_m - t_i)$$

$$\Rightarrow^{ } \sum_{i = 1}^n h'_i \cdot (t_n - t_i + t_m - t_n) >$$

$$\sum_{i = 1}^n h_i \cdot (t_n - t_i + t_m - t_n)$$

$$\Rightarrow^{(b)} \sum_{i = 1}^{n} h'_i \cdot (t_n - t_i ) > \sum_{i = 1}^{n} h_i \cdot (t_n - t_i)$$

$$+ (\sum_{i = 1}^{n} h_i - \sum_{i = 1}^{n} h'_i) \cdot (t_m - t_n )$$

$$\Rightarrow^{(c)} \sum_{i = 1}^{n} h'_i \cdot (t_n - t_i ) > \sum_{i = 1}^{n} h_i \cdot (t_n - t_i)$$

$$\Rightarrow^{(d)} \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$