Pierre Michaud
email: pierre.michaud@inria.fr

Some mathematical facts about optimal cache replacement

This paper exposes and proves some mathematical facts about optimal cache replacement that were previously unknown or not proved rigorously. An explicit formula is obtained, giving OPT hits and misses as a function of past references. Several mathematical facts are derived from this formula, including a proof that OPT miss curves are always convex, and a new algorithm called OPT tokens, for reasoning about optimal replacement.

Introduction

Accessing a small and nearby memory is generally faster than accessing a large or distant one. Caching is the idea, ubiquitous in computer architecture, to keep some data in a small and nearby memory called a cache. The total data set is often larger than the cache. When the requested data is not in the cache, this is a miss. Otherwise, this is a hit. Upon a miss, a decision must be made: should the accessed data be kept in the cache, and if so, which data should be evicted from the cache to make room for the missing data ? This decision is taken by an algorithm called a replacement policy. Not all replacement policies generate the same number of misses. The performance and energy cost of a miss is greater than that of a hit, and we would like to have as few misses as possible.

Fifty years ago, Belady introduced a replacement policy minimizing the number of misses [START_REF] Belady | A study of replacement algorithms for virtual-storage computers[END_REF]. However, this optimal policy requires to know future memory accesses, while replacement policies that can be implemented in practice generally base their decisions on past accesses. Still, optimal replacement is a valuable conceptual tool for evaluating and analyzing practical replacement policies. Even though practical replacement policies cannot be optimal in general, they can be optimal or close to optimal on certain classes of program behavior. Moreover, optimal replacement was a direct inspiration for some cache replacement policies, in principle implementable, that were proposed recently [START_REF] Rajan | Emulating optimal replacement with a Shepherd cache[END_REF][START_REF] Jain | Back to the future: leveraging Belady's algorithm for improved cache replacement[END_REF].

Though introduced five decades ago, optimal replacement is unintuitive and not completely understood. The main goal of this paper is to expose new, unknown mathematical facts about optimal replacement and to prove them rigorously. In pursuing this goal, we also clarify some facts about optimal replacement that we believe are not well known. We consider optimal replacement both with and without cache bypassing.

Although the term cache is used throughout this paper, optimal replacement is of interest for any cachelike structure, such as Translation Lookaside Buffer (TLB), Branch Target Buffer (BTB), main memory (paging), etc. We call items the objects stored in the cache. E.g., an item may be an aligned memory block (hardware cache), a virtual page address (TLB), a branch address (BTB), etc. In this study, we consider fully-associative caches. Nevertheless, most of our conclusions apply to set-associative caches, as every cache set behaves like a small independent fully-associative cache.

Structure of the paper

The goal of Sections 4 and 6 is to obtain equations ( 14) and [START_REF] Smith | Instruction cache replacement policies and organizations[END_REF]. All subsequent mathematical facts are derived from these equations. We provide some corroboration for these equations in Section 5 by proving the (already known) fact that all LRU hits are OPT hits, and in Section 7 by computing the OPT miss probability for random traces and comparing with Monte Carlo simulations. In Section 8, we introduce the OPT matrix, an algorithm for reasoning about all cache sizes simultaneously. Using the OPT matrix, we show that the output trace of OPT distances has a special structure, described by theorem 1. Using theorem 1, we prove in Section 9 that the OPT miss curve is always a convex function of the cache size, a fact discovered recently but not proved rigorously [START_REF] Beckmann | Talus: A simple way to remove cliffs in cache performance[END_REF]. In Section 10, we focus on a single cache size and derive from the OPT matrix an algorithm called the OPT tokens for obtaining OPT hits and misses. In Section 11, we derive directly from the OPT tokens an equivalence between a cache of size j + 1 without bypassing and a cache of size j with bypassing. Finally, in Section 12, and using the OPT tokens, we explain why accessing a data set in a circular fashion maximizes the number of OPT misses. We cite related work where we think appropriate. Results for which we do not mention explicitly any related work are, to the best of our knowledge, new results.

This paper contains only mathematical facts, independent of empirical properties of applications. We had to introduce a substantial amount of notations permitting to reason with precision. Our most important notations are listed in Table 2.

Belady's MIN and Mattson's OPT

Belady's 1966 paper [START_REF] Belady | A study of replacement algorithms for virtual-storage computers[END_REF] and Mattson et al.'s 1970 paper [START_REF] Mattson | Evaluation techniques for storage hierarchies[END_REF] are important and widely cited. Yet, there seems to be a long-lived confusion between Belady's MIN and Mattson's OPT. Many authors who referred to Belady's MIN actually described Mattson's OPT. 1Upon a cache miss, Mattson's OPT replacement policy evicts from the cache the item that will be rereferenced the furthest in time. This is stated very clearly by Mattson et al., who provide a proof that OPT is indeed optimal, in the sense that it minimizes the number of misses. Mattson et al. showed that OPT (like LRU) is a stack replacement policy, i.e., the content of a cache of size j is always included in a cache of size j + 1. They introduced the OPT stack, based on the OPT replacement policy, for computing the minimum number of cache misses for all cache sizes at once.

Belady's MIN is not identical to Mattson's OPT. The MIN algorithm and the MIN replacement policy should be distinguished. The MIN algorithm is for determining hits and misses under optimal replacement [START_REF] Belady | A study of replacement algorithms for virtual-storage computers[END_REF][START_REF] Belady | On-line measurement of paging behavior by the multivalued MIN algorithm[END_REF].

Table 1 shows how the MIN algorithm works on an example, assuming a 3-entry cache. MIN can be explained with a matrix where rows are associated with distinct items and columns represent successive times. 2 When the item referenced at time t and previously referenced at time t is determined to be in the cache at t (hit), a cache entry is reserved for the item for the time interval ]t , t + 1], under the constraint that the number of reserved entries at any time cannot exceed the cache capacity. If cache entries cannot be reserved in ]t , t + 1] (because of the capacity constraint), this is a miss, and an entry is reserved only for the time t + 1.

A B C D E E C D F A B D B A D E F B MIN matrix A r r r r r r B r r r r r r r r C r r r r r D r r r r r r r r r r r r E r r r F r r hits h h h h h h h h evictions MIN A B E C F A D OPT B A C F E A D
The MIN algorithm determines evicted items after a delay. More specifically, when a column of the MIN matrix contains a number of reservations equal to the cache capacity, we know which items are not in the cache and must have been evicted. For instance in Table 1, at time t = 8, the MIN algorithm determines that the cache contained items C,D and E at time t = 7, hence that items A and B had been evicted earlier.

The MIN replacement policy attributes evictions to misses in the following way: among a group of items to evict, the least-recently referenced item is evicted the earliest [START_REF] Belady | A study of replacement algorithms for virtual-storage computers[END_REF]. As can be seen in Table 1, MIN and OPT, although both optimal, are different replacement policies. Note that, at t = 8, when MIN determines the eviction of A and B, it is not known yet which of A or B will be re-referenced first.

In 1966, Belady did not prove that MIN is optimal. The optimality of MIN was proved in 1974 when Belady and Palermo, relying on Mattson's proof of optimality for OPT, showed that MIN and OPT yield the same hits and misses [START_REF] Belady | On-line measurement of paging behavior by the multivalued MIN algorithm[END_REF].

Remarkably, the MIN algorithm is an online algorithm: it provides hit/miss information without delay, determining at time t, without look-ahead, if the item referenced at time t is or is not in the cache. That is, even though optimal replacement depends on future references, whether the current reference is a hit or a miss depends only on past references. This property was not mentioned in the 1966 paper. It was emphasized later in the 1974 paper [START_REF] Belady | On-line measurement of paging behavior by the multivalued MIN algorithm[END_REF]. This property of MIN has been exploited in a new cache replacement policy published recently [START_REF] Jain | Back to the future: leveraging Belady's algorithm for improved cache replacement[END_REF].

u t (1) = t -1 u t (i + 1) < u t (i) q t q t := min{i ≥ 1 : X ut(i) = X t } LRU stack position of item X t X t / ∈ R [ut(qt)+1,t[ D j t (i) D j t (i) := i -M j [ut(i)-β+1,t[ D st t (i) = i I j t I j t := min{i ∈ [1, s t ] : D j t (i) = j} I st t = s t

OPT hits and misses depend only on past references

Belady's MIN algorithm demonstrates that, under optimal replacement, hits and misses depend only on past references. Hence, there must exist an explicit formula giving hits and misses as a function of past references. The goal of this section is to find this formula (equation ( 8)). Our motivation is that such formula will be useful for understanding OPT hits and misses. Our starting point is the OPT replacement policy, for which multiple proofs of optimality are known [START_REF] Mattson | Evaluation techniques for storage hierarchies[END_REF][START_REF] Coffman | Operating Systems Theory[END_REF][START_REF] Cohen | A proof of the optimality of the MIN paging algorithm using linear programming duality[END_REF][START_REF] Van Roy | A short proof of optimality for the MIN cache replacement algorithm[END_REF][START_REF] Vogler | Another short proof of optimality for the MIN cache replacement algorithm[END_REF][START_REF] Lee | A simple prooof of optimality for the min cache replacement policy[END_REF].

Figure 1 (left part) illustrates Mattson's OPT-stack update procedure [START_REF] Mattson | Evaluation techniques for storage hierarchies[END_REF]. In this example, the item A referenced at time t in the reference stream is found at position 5 in the stack, meaning that 5 is the smallest cache size giving a cache hit at time t. Figure 2 gives a similar example where bypassing is allowed. In the paper we consider both the classical case (no bypassing) and the case with bypassing. We use parameter β to indicate if bypassing is allowed (β = 1) or not (β = 0).

Table 2 lists our main notations. We use the usual notations of set theory and the usual notations for intervals (e.g., [t, t [ is the set of values τ such that t ≤ τ < t ). For t < t , R [t,t [ represents the set of items referenced at least once between times t (included) and t (not included). The stack size s t is the number of distinct items referenced at least once before time t, i.e., s t = |R [0,t[ |. The OPT stack position of item X t referenced at time t (aka OPT distance) is denoted p t . If item X t is referenced for the first time, we define p t = s t + 1 = s t+1 . C j t is the set of items in a cache of size j (items) at time t under optimal replacement (C 0 t = ∅). I.e., C j t is the set of items whose position in the OPT stack at t does not exceed position j. Let us focus on one item, X, referenced at time t 2 , and let us assume that X was previously referenced at time

t 1 < t 2 -1. That is, X = X t 1 = X t 2 and X / ∈ R [t 1 +1,t 2 [ . Let π t ∈ [1, s t ] denote the position of X in the OPT stack at time t ∈]t 1 , t 2 ]
. First, it should be observed that the stack position of an item cannot decrease unless the item is referenced. As X is not referenced during ]t 1 , t 2 [, π t is non-decreasing in ]t 1 , t 2 ]. A necessary condition for X to go up in the stack (i.e.,

time t time t+1 C D F B H A C G A B G H D F E E time t time t+1 X X X t X t π t+1 p t π t Figure 1:
Mattson's OPT stack on an example (no bypassing). Left: The item X t = A referenced at time t is found at position p t = 5 in the stack. Circles represent sorting networks: the item whose time of next reference is furthest is sent to higher stack positions. The alphabetical order indicates how items are ordered at time t by their time of next reference. Right: Another example, focusing on a particular item X. Darkened stack entries hold items that will be referenced before X. Item X goes up in the stack when X t is above X and all the stack positions below X are occupied by items referenced before X. Right: Focus on a particular item X. Item X goes up in the stack when X t is above X, X t is re-referenced before X, and all the stack positions below X are occupied by items that will be referenced before X.

time t time t+1 F B H C G B G H F E E D A C D A time t time t+1 X X X t π t+1 p t π t
π t+1 > π t ) is that p t > π t and all the stack positions below π t are occupied by items that are referenced in [t + 1, t 2 [. A useful quantity to consider is the number N j t of items in the cache of size j, at time t, that are referenced in [t, t 2 [:

for t ∈]t 1 , t 2 ] N j t := C j t ∩ R [t,t 2 [ (1)
Another useful quantity is

e t := R [t,t 2 [ -R [t+1,t 2 [
Notice that e t ∈ {0, 1} and N j t+1 + (1β)e t ≤ j When X goes up in the stack, the new position of X is h t+1 defined as

h t+1 := min{j ∈ [1, s t+1 ] : N j t+1 < j -(1 -β)e t } For t ∈]t 1 , t 2 [, we have π t+1 = max(π t , h t+1 ). Note that π t 1 +1 = 1 for β = 0 and π t 1 +1 = h t 1 +1 for β = 1. Therefore p t 2 = π t 2 = max{h t : t ∈]t 1 + 1 -β, t 2 ]} (2)
The OPT stack update procedure leads to the following recurrence relation:

j ≥ p t N j t+1 = N j t -e t j < p t N j t+1 = min(j, N j t + 1 -βe t ) -(1 -β)e t (3)
The values N j t 1 +1 are not known. However, we know that N j t 2 = 0. If recurrence (3) could be reversed, we could obtain N j t . Actually, recurrence (3) can be reversed partially. Notice that j < p t means a miss in the cache of size j at time t. Let us define

M j [t ,t[ := {τ ∈ [t , t[: p τ > j} M j [t ,t[
is the number of misses 3 occurring in [t , t[ for an OPT cache of size j. The partially reversed recurrence is:

N j t+1 < j -(1 -β)e t =⇒ N j t -N j t+1 = e t -M j [t,t+1[ (4)
Let us denote rev(t) the condition on the left-hand side of (4):

rev(t) : N j t+1 < j -(1 -β)e t We have rev(τ ) ∀τ ∈ [t, t 2 [ =⇒ N j t -N j t 2 = τ ∈[t,t 2 [ e τ -M j [τ,τ +1[ Hence rev(τ ) ∀τ ∈ [t, t 2 [ =⇒ N j t = R [t,t 2 [ -M j [t,t 2 [ and rev(τ ) ∀τ ∈ [t + 1, t 2 [ =⇒ N j t+1 + (1 -β)e t = R [t+β,t 2 [ -M j [t+1,t 2 [ (5)
As the equality on the right-hand side of ( 5) is always true for t = t 2 -1, we can apply a backward induction on condition rev(τ ):

rev(τ ) ∀τ ∈ [t, t 2 [ ⇐⇒ ∀τ ∈ [t, t 2 [ R [τ +β,t 2 [ -M j [τ +1,t 2 [ < j (6)
Let us define for β = 0, j > 1 and for β = 1, j > 0

T j t 2 := min t < t 2 : ∀τ ∈ [t, t 2 [, R [τ +β,t 2 [ -M j [τ +1,t 2 [ < j (7)
and for β = 0, T 1 7) and using equivalence [START_REF] Burger | The SimpleScalar tool set, version 2.0[END_REF], condition rev(t) must be false. Hence h t+1 > j, which implies (from (2)) p t 2 > j. On the other hand, when

t 2 := t 2 . Consider the case T j t 2 > t 1 + 1 -β. Then for t = T j t 2 -1 > t 1 -β, by definition (
T j t 2 ≤ t 1 + 1 -β, condition rev(t) is true for all t ∈ [t 1 + 1 -β, t 2 [, hence h t+1 ≤ j for all t ∈ [t 1 + 1 -β, t 2 [, and p t 2 ≤ j. Therefore p t 2 = min{j ≥ 1 : T j t 2 ≤ t 1 + 1 -β} (8)
So far, we have assumed t 2 > t 1 + 1, but equation ( 8) is valid also for t 2 = t 1 + 1 (p t 2 = 1). It should be noted that T j t 2 does not depend on which item is referenced at t 2 . Only the t 1 in equation ( 8) depends on the item referenced at t 2 .

We end this section with two facts that are used later in the paper. First,

∀j T j+1 t ≤ T j t (9)
This can be seen as follows. Instead of referencing X t at t = t 2 , let us reference the item that was last referenced at t 1 = T j t -1 + β. That item exists because, by definition of T j t , R [τ +β,t[ must be incremented when going from τ = T j t to τ = T j t -1. As T j t = t 1 + 1β, we must have p t ≤ j, hence p t ≤ j + 1, which implies

T j+1 t ≤ t 1 + 1 -β, that is, T j+1 t ≤ T j t . The second fact is τ ∈ [T j t , t[ =⇒ M j [τ,t[ -M j+1 [τ,t[ ∈ {0, 1} (10)
To see this, let us reference at t = t 2 the item that was last referenced at t 1 = T st t -1 + β, and let us consider j < s t . We must have T j+1 t ≥ T st t = t 1 + 1β. Hence for τ ∈ [T j t , t], quantities N j τ and N j+1 τ are defined. From ( 7), ( 6) and ( 5), we have

τ ∈ [T j t -1, t[ =⇒ rev(t ) ∀t ∈ [τ + 1, t[ =⇒ N j τ +1 + (1 -β)e τ = R [τ +β,t[ -M j [τ +1,t[ =⇒ M j [τ +1,t[ -M j+1 [τ +1,t[ = N j+1 τ +1 -N j τ +1
which, from definition (1), proves [START_REF] Knuth | An analysis of optimum caching[END_REF].

All LRU hits are OPT hits

The fact that OPT is optimal means that no replacement policy can generate fewer misses than OPT. However, an individual reference that is a hit under a given policy P is not necessarily a hit under OPT. Still, it is known (though perhaps not widely) that every LRU hit is also an OPT hit [START_REF] Puzak | Analysis of cache replacement algorithms[END_REF][START_REF] Lin | Predicting last-touch references under optimal replacement[END_REF][START_REF] Brock | Pacman: program-assisted cache management[END_REF]. It can be verified that equation ( 8) is consistent with this fact. Let us assume p t 2 > 1. From (8), we must have

T pt 2 -1 t 2 > t 1 +1-β. Letting t = T pt 2 -1 t 2
-1, and from [START_REF] Coffman | Operating Systems Theory[END_REF],

p t 2 -1 = R [t+β,t 2 [ -M pt 2 -1 [t+1,t 2 [ ≤ R [t+β,t 2 [ < R [t 1 ,t 2 [
Let us define

q t 2 := R [t 1 ,t 2 [
Quantity q t 2 is the LRU stack position (aka reuse distance) of the item X referenced at time t 2 . We have

p t 2 ≤ q t 2 (11)
Inequation ( 11) is valid in the case p t 2 = 1, and also when item X t 2 is referenced for the first time (p

t 2 = q t 2 = |R [0,t 2 [ | + 1).
In words, inequation [START_REF] Lee | A simple prooof of optimality for the min cache replacement policy[END_REF] means that every LRU hit is also an OPT hit.

There is something remarkable here. The LRU replacement policy, which evicts from the cache the item referenced the least recently, is an online policy: it makes replacement decisions without knowing future references. LRU is not optimal in general, but it works well in many practical applications. The performance of LRU lies in empirical properties of traces, not in LRU itself. Indeed, if we consider random traces (items have equal probability to be referenced), all online replacement policies yield the same average hit ratio, equal to the cache size divided by the number of distinct items. Without considering trace properties, LRU is neither better nor worse than any other online policy. Still, inequation [START_REF] Lee | A simple prooof of optimality for the min cache replacement policy[END_REF] highlights a special relationship between LRU and OPT. This suggests a (rather theoretical) question, which we will not try to answer in this paper: is there an online policy P other than LRU such that, for any trace, all hits under policy P are hits under OPT ?

6 Putting the reuse distance into the equation Equation ( 8) is written in terms of t 1 and t 2 . In this section, we rewrite it in terms of t and q t (the reuse distance). Let us define

I j t := R [T j t -1+β,t[ (12)
Note that (9) implies ∀j

I j+1 t ≥ I j t (13)
Equation ( 8) can be written p t = min{j ≥ 1 :

I j t ≥ q t } (14)
except for the special case p t = s t + 1 for a first reference. As we defined it, I j t depends on T j t . For the sake of convenience, we would like to find a more direct expression for I j t . Let us introduce the quantity

D j [τ,t[ := R [τ +β,t[ -M j [τ +1,t[
we can rewrite (7) as

T j t = min t < t : ∀τ ∈ [t , t[, D j [τ,t[ < j (15)
When τ decreases, D j [τ,t[ increases only when R [τ +β,t[ is incremented. Instead of considering all values τ , we can focus on the values τ such that R [τ,t[ is incremented. For i > 0, let

u t (i) := max{τ < t : R [τ,t[ = i} (16)
As R [T j t +β,t[ < I j t (cf. the argument used in proving ( 9)), we must have

u t (I j t ) = T j t -1 + β Consequently, i < I j t =⇒ u t (i) > u t (I j t ) =⇒ u t (i) -β ≥ T j t =⇒ D j [ut(i)-β,t[ < j
Moreover,

D j [ut(I j t )-β,t[ = D j [T j t -1,t[ = j Let us define for i ∈ [1, s t ] D j t (i) := D j [ut(i)-β,t[ = i -M j [ut(i)-β+1,t[ (17)
We find that I j t can be obtained as

I j t = min{i ∈ [1, s t ] : D j t (i) = j} (18)
Notice that D j t (i) ≤ i, hence from (18), j = D j t (I j t ) ≤ I j t . Therefore I qt t ≥ q t and, from (14), p t ≤ q t (already shown in section 5). The rest of the paper is built on equations ( 14) and [START_REF] Smith | Instruction cache replacement policies and organizations[END_REF].

If we focus on a single cache size j, the procedure for determining whether the reference at time t is a hit or a miss is simply:

OPT hit at time t ⇐⇒ p t ≤ j ⇐⇒ I j t ≥ q t ⇐⇒ ∀i < q t , D j t (i) < j
This is illustrated in Table 3 on an example, assuming bypassing (β = 1) and cache size j = 3. This example shows how the hit/miss outcome at time t is obtained from past hit/miss outcomes. On this example, this is a hit at time t, as all the D j t (i) values for i < q t are strictly less than three.

Random traces

Equations ( 14) and ( 18) can be used to compute the OPT miss probability for random traces, i.e., traces such that the number s of distinct items is fixed and items have equal probability 1/s to be referenced. Smith [START_REF] Smith | Analysis of the optimal, look-ahead demand paging algorithms[END_REF] and Knuth [START_REF] Knuth | An analysis of optimum caching[END_REF] have shown that the exact miss ratio of an OPT cache of size j on random traces can be obtained by solving a Markov chain with s j states. According to Knuth, there does not seem to be any simple formula for the exact OPT miss ratio of random traces for any s and j in general, although Knuth time

• • • t -9 t -8 t -7 t -6 t -5 t -4 t -3 t -2 t -1 t trace • • • A D F C F E C B B A hit/miss • • • hit miss hit hit miss hit miss hit hit u t (i) • • • u t (q t ) u t (5) u t (4) u t (3) u t (2) u t (1) M 3 [ut(i),t[ • • • 3 2 2 1 0 D 3 t (i) • • • 2 2 1 1 1
Table 3: Example: determining hit/miss at time t from past hits/misses (β = 1 and cache size j = 3).

found closed-form expressions for the special cases j = 2 and j = s -1. In general, for obtaining the OPT miss ratio on random traces, one must solve a (possibly huge) Markov chain or do Monte-Carlo simulations.

Here we search an approximation for the case s → ∞, j → ∞ but j/s ∈ [0, 1] fixed. Let us consider an interval [t, t + ∆t[ with ∆t large. For a given item x, the probability that x is not in

R [t,t+∆t[ is (1 -1 s ) ∆t . Hence R [t,t+∆t[ ≈ s × (1 -(1 -1 s ) ∆t ) ≈ s × (1 -e -∆t s )
Then, we have

t -u t (i) ≈ -s × ln(1 - i s )
Denoting m the miss probability and taking β = 1, we have

D j t (i) ≈ i + s × ln(1 - i s ) × m
As D j t (I j t ) = j, we obtain the following equation:

j ≈ I j t + s × ln(1 - I j t s ) × m
But m is the probability that p t > j, i.e., the probability that q t > I j t . As q t is uniformly distributed in [1, s], we have

m = 1 - I j t s Substituting I j t s with 1 -m, we obtain j s ≈ 1 -m + m × ln(m) (19)
Figure 3 shows a plot of j/s vs. m as given by ( 19), compared with Monte Carlo simulations. Formula (19) models the asymptotic behavior and is more accurate as s gets larger. OPT is very effective on random traces: asymptotically, the number of distinct items must be about ten times the cache size for the OPT miss ratio to exceed sixty percent.

The OPT matrix

In Section 6, we considered a fixed t. Let us look at how D j t (i) changes from t to t + 1. First, notice that

i ≤ q t u t+1 (i) = u t (i -1) i > q t u t+1 (i) = u t (i)
Then, from [START_REF] Smith | Analysis of the optimal, look-ahead demand paging algorithms[END_REF], we obtain the following update procedure for p t ∈ [1, s t ]:

i > q t i ∈ [2, q t ] i = 1 j ∈ [p t , s t ] D j t+1 (i) = D j t (i) D j t+1 (i) = D j t (i -1) + 1 D j t+1 (1) = 1 j < p t D j t+1 (i) = D j t (i) -1 D j t+1 (i) = D j t (i -1) D j t+1 (1) = 1 -β (20)
In the special case q t = p t = s t + 1 = s t+1 , we have D st+1 t+1 (i) = i. Procedure (20) (along with equations ( 14) and ( 18)) defines an algorithm for computing p t . We call this algorithm the OPT matrix. The OPT matrix is not intended for analyzing real traces. It is inefficient in computational complexity and memory usage. 4 Nevertheless, the OPT matrix is a useful conceptual tool for reasoning about OPT, considering all cache sizes simultaneously. In particular, we are going to show that, whatever the input trace, the sequence of OPT distances has a remarkable structure:

Theorem 1. Given t > t such that p t = p t > 2 -β and ∀τ ∈]t, t [, p τ = p t , ∀j ∈ [2 -β, p t [ there exists τ ∈]t, t [ such that p τ = j.
In words, theorem 1 states that, in the sequence of OPT distances p t , a given distance greater than 2β cannot reoccur until all lower distances (except 1 in the no-bypassing case) have occurred at least once. Below is a sequence of OPT distances that we generated from a random input trace with 8 distinct items, without bypassing: 1 2 3 1 2 4 2 1 3 2 4 3 2 5 3 2 4 6 2 2 3 7 1 4 2 3 8 2 5 4 1 1 6 2 1 3 7 2 4 5 2 2 3 8 2 4 6 2 5 1 3 7 2 2 2 4 5 2 3 4 6 5 7 2 2 3 1 4 5 2 8 3 4 2 3 2 2 2 1 5 6 2 1 2 7 2 4 3 5 8 6 2 1 3 4 5 1 7 2 3 4 1 6 2 5 3 2 4 3 6 5 2 8 2 2 1 3 4 5 1 7 6 2 2 3 4 5 6 1 1 2 3 1 2 3 4 5 7 2 3 4 2 6 3 4 2 8 2 2 5 6 3 2 4 7 8 2 2 3 4 2 5 2 3 4 6 5 2 3 4 5 1 7 2 8 2 3 4 5 1 1 2 1 3 4 2 1 6 5 2 3 2 4 3 5 1 2 7 8 3 2 6 3 4 5 2 1 7 3 2 3 2 4 3 2 5 2 1 6 3 2 3 4 1 8 2 1 3 4 5 We have highlighted a few parts of the sequence to illustrate theorem 1. Here is the sequence of OPT distances produced from the same input trace when bypassing is allowed: Notice that, without bypassing, distance 2 can occur several times consecutively, while this does not occur with bypassing.

Before proving theorem 1, let us make some preliminary observations. From ( 17) and ( 10) we must have ∀i ∈ [1,

I j t ], D j+1 t (i) -D j t (i) ∈ {0, 1} and for any k ≥ 0 ∀i ∈ [1, I j t ], D j+k t (i) ≤ D j t (i) + k Also, observe (from (17)) that D j t (i) = D j-1 t (i) =⇒ D j t (i + 1) = D j-1 t (i + 1)
Let us define

Y j t := min{i ≥ 1 : D j t (i) = D j-1 t (i)} As D j-1 t (I j-1 t ) = j -1, I j t > I j-1 t =⇒ D j t (I j-1 t ) < j =⇒ D j t (I j-1 t ) = j -1 =⇒ Y j t > I j-1 t
On the one hand, from ( 13), ( 14), [START_REF] Smith | Instruction cache replacement policies and organizations[END_REF], and (20), we have

∀j I j t < I pt t =⇒ I j t+1 = I j t + 1
On the other hand, consider the smallest j such that I j t > I pt t . As

I j t > I j-1 t = I pt t , we have Y j t > I j-1 t = I pt t , hence D j t (i) = D j-1 t (i) for all i ≤ I pt t . Therefore i < I pt t =⇒ D j-1 t (i) < j -1 =⇒ D j t (i) < j -1 =⇒ D j+k t (i) < j + k -1
for any k ≥ 0. Consequently, and from [START_REF] Temam | An algorithm for optimally exploiting spatial and temporal locality in upper memory levels[END_REF], 20), we must have

∀j I j t > I pt t =⇒ I j t+1 = I j t I j t cannot decrease unless I j t = I pt t . From (
∀j I j t = I j-1 t = I pt t =⇒ I j t+1 ≥ Y j t + 1
From (20), Y j t is updated as follows:

Y pt t+1 = 2 -β j = p t , Y j t ≤ q t =⇒ Y j t+1 = Y j t + 1 j = p t , Y j t > q t =⇒ Y j t+1 = Y j t
We are ready to prove theorem 1.

Proof. As I j t+1 ≥ j and Y pt t+1 = 2β, we must have ∀j ≥ 2β, I j t+1 ≥ Y pt t+1 . From ( 14) and the assumption p t = p t , we must have , an event that we call crossing. This τ must be such that I pτ τ ≤ I j τ (otherwise I j τ would be incremented and crossing at τ would not be possible). We prove by contradiction that in fact we must have I j τ = I pτ τ . Let us assume I pτ τ < I j τ . Consequently, I j τ +1 = I j τ and crossing at τ implies I j τ = Y pt τ ≤ q τ ≤ I pτ τ , which contradicts the assumption. Therefore, I j τ = I pτ τ . If p τ = j, we are done with the proof (we found a τ ∈]t, t [ such that p τ = j). Otherwise, we have j > p τ and

I pt t > I pt-1 t , hence Y pt t > I pt-
I j τ = I j-1 τ = I pτ τ , hence Y j τ + 1 ≤ I j τ +1 < Y pt τ +1 ≤ Y pt τ + 1 (as p τ = p t ). Therefore Y j τ < Y pt τ , which implies (as Y j t+1 ≥ Y pt t+1 ) that there is a τ ∈]t, τ [ such that p τ = j.
Belady and Palermo noticed that the sequence of OPT distances is constrained [START_REF] Belady | On-line measurement of paging behavior by the multivalued MIN algorithm[END_REF]. In particular, they understood that no two consecutive references can have the same OPT distance if that distance is greater than two (they were assuming β = 0). However, they did not mention theorem 1.

Theorem 1 provides a sanity test for OPT stack implementations or algorithms emulating an OPT stack. If, by a visual inspection of the sequence of OPT distances, we find a case where theorem 1 is violated, this is a sure indication that the algorithm or its implementation is incorrect. Note that there is no such sanity test for an LRU stack.

Corollary 1. For an OPT cache of size j, a time interval [t, t [ such that s t = s t = s > j and containing sj + 1 cache misses must also contain at least j -1 + β cache hits.

Proof. In [t, t [, only sj distinct stack positions greater than j can be accessed. As there are sj + 1 misses in [t, t [, by the pigeonhole principle, there must exist a repetition, i.e., two references in [t, t [ at the same stack position greater than j. By theorem 1, all j -1 + β stack positions between 2β and j must be accessed between the repetition. Corollary 2. If the number of distinct items is bounded and equal to s, for any j < s

lim t→∞ M j [0,t[ t ≤ s -j s -1 + β
I.e., the asymptotic miss ratio of an OPT cache of size j cannot exceed s-j s-1+β .

Proof. There is a miss at a finite time t 0 such that ∀t ≥ t 0 , s t = s. The next miss occurs at t 1 > t 0 , the next one at t 2 > t 1 , and so forth. An interval [t k(s-j) , t (k+1)(s-j) ] contains exactly sj + 1 misses. By corollary 1, there must be at least j-1+β hits in ]t k(s-j) , t (k+1)(s-j) [. Interval [t 0 , t k(s-j) ] contains at least k(j-1+β) hits. That is, [t 0 , t k(s-j) ] contains exactly k(sj) + 1 misses and at least k(sj)

+ 1 + k(j -1 + β) = k(s -1 + β) + 1 references, that is, t k(s-j) -t 0 ≥ k(s -1 + β).
As k grows to infinity, the impact of initial misses (before t 0 ) on the overall miss ratio vanishes, and the asymptotic miss ratio does not exceed

k(s-j) k(s-1+β) = s-j s-1+β .
For example, let us consider an 8-way set-associative cache (j = 8) managed by LRU, without bypassing (β = 0), and an application with a data set twice larger than the cache (s = 16). If the measured LRU miss ratio is significanly greater than s-j s-1+β = 16-8 16-1 ≈ 53%, we do not need to run simulations with OPT to know that OPT outperforms LRU significantly on that application.

It should be noted that, for online replacement policies (such as LRU), the upper bound for the miss ratio is 100%. Indeed, one can generate an ad hoc trace defeating the replacement policy, by referencing at each time t an item X t not in the cache at time t. Corollary (2) implies that it is impossible to defeat OPT when the number of distinct items is bounded. The content of the OPT cache at time t is not fixed, it depends on the item X t we are going to choose. OPT knows the future and can anticipate our moves.

The OPT miss curve is convex

Recently, Beckmann and Sanchez argued that, under optimal replacement, the miss curve must be a convex function of the cache size [START_REF] Beckmann | Talus: A simple way to remove cliffs in cache performance[END_REF]. They argue that, for any replacement policy with a non-convex miss curve, it is possible, by partitioning the cache in a certain way, to derive a policy yielding fewer misses. They assume that removing some items from a trace entirely is equivalent to enlarging the cache, whatever the replacement policy. This might be approximately valid, empirically. Whether this is always true is uncertain.

With Theorem 1, we can prove rigorously that the OPT miss curve is always convex.

Corollary 3. For all t and for all j ≥ 3,

M j-1 [0,t[ -M j [0,t[ ≤ M j-2 [0,t[ -M j-1 [0,t[ (21)
Proof. The terms on the left-hand and right-hand sides of inequality [START_REF] Van Roy | A short proof of optimality for the MIN cache replacement algorithm[END_REF] are respectively the number of references in [0, t[ accessing position j in the OPT stack and the number of references accessing position j -1. The first reference in the trace accessing position j -1 (i.e., when the stack size is incremented from j -2 to j -1) occurs before the first reference at position j (when the stack size is incremented from j -1 to j). So ( 21) is true on the first access at position j. From theorem 1, between two accesses at position j, there must exist at least one access at position j -1. Therefore on each new access at position j, inequality

As noted by Beckmann and Sanchez, if a replacement policy's miss curve is markedly non convex, it is certainly far from the OPT miss curve [START_REF] Beckmann | Talus: A simple way to remove cliffs in cache performance[END_REF].

The OPT tokens algorithm

The OPT matrix introduced in Section 8 considers all cache sizes simultaneously. When we focus on a single cache size, a simpler algorithm can be derived from the OPT matrix.

I 3 t (1) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 miss m m m m m m m m m with bypassing (β = 1) I 3 t (3) 3
I 3 t (1) 1 1 1 1 2 3 4 1 1 1 2 3 4 1 1 1 2 3 miss m m m m m m m m m
Table 4: OPT tokens algorithm on an example with cache size j = 3.

Notice that, for a fixed j, the s t values D j t (i) for i ∈ [1, s t ] are sufficient to determine hits and misses in a cache of size j. In practice, we only need the values D j t (i) ≤ j. Moreover, there are only j such distinct values. Let us generalize quantity I j t as follows:

for i ∈ [1, j], I j t (i) := min{k ∈ [1, s t ] : D j t (k) = i}
We have I j t (j) = I j t . Note that I j t (i) < I j t (i + 1) (cf. definition [START_REF] Smith | Analysis of the optimal, look-ahead demand paging algorithms[END_REF]). From the update procedure [START_REF] Temam | An algorithm for optimally exploiting spatial and temporal locality in upper memory levels[END_REF], we obtain what we call the OPT tokens algorithm:

case action start I j 0 (i) = i q t > I j t (j) β = 0 I j t+1 (1) = 1 miss i ≥ 2 -β I j t+1 (i) = I j t (i) + 1 q t ≤ I j t (j) I j t+1 (1) = 1 hit I j t (i) < q t I j t+1 (i + 1) = I j t (i) + 1 I j t (i) ≥ q t I j t+1 (i + 1) = I j t (i + 1) (22)
The OPT tokens algorithm takes as input the LRU stack positions (q t ) generated from the input trace (X t ). Consistent with our choice to define q t = s t +1 upon referencing an item for the first time, the first reference to an item occurring at a time t such that s t < j is counted as a hit. Misses can occur only when s t ≥ j. Table 4 shows how the OPT tokens algorithm works on an example with 6 distinct items referenced in a circular fashion, assuming cache size j = 3.

Figure 4 shows a visual for the OPT tokens. The number of tokens is equal to the cache size j. I j t (i) is the height of the i th token. An OPT miss occurs if q t is above the highest token, i.e., I j t (j). Otherwise this is an OPT hit. Then, the tokens are moved according to the rules [START_REF] Vogler | Another short proof of optimality for the MIN cache replacement algorithm[END_REF]. 4: Visual for the OPT tokens. The number of tokens is equal to the cache size (here 5). If q t (the LRU stack position of item X t ) is above the highest token, this is an OPT miss, otherwise this is an OPT hit.

Cache bypassing

Historical papers about optimal replacement studied paging in main memory [START_REF] Belady | A study of replacement algorithms for virtual-storage computers[END_REF][START_REF] Mattson | Evaluation techniques for storage hierarchies[END_REF][START_REF] Belady | On-line measurement of paging behavior by the multivalued MIN algorithm[END_REF]. They considered the caching problem without bypassing the cache (which is main memory here). To the best of our knowledge, Scott McFarling was the first to consider optimal replacement with bypassing [START_REF] Mcfarling | Program analysis and optimization for machines with instruction cache[END_REF]. McFarling modified the OPT policy as shown in Figure 2. Let us denote OPTb and OPTn the OPT policy with and without bypassing respectively.

We are not aware of any published proof that OPTb is optimal. 5 It is relatively straightforward, however, to take one of the several published optimality proofs for OPTn, e.g., [START_REF] Lee | A simple prooof of optimality for the min cache replacement policy[END_REF], and to adapt it to prove the optimality of OPTb. We will not do this here.

In his thesis, McFarling proved the following:

McFarling's inequality. An OPTb cache of size j generates no more misses than an OPTn cache of size j and no more hits than an OPTn cache of size j + 1.

McFarling's argument is very simple. An OPTn cache cannot generate fewer misses than an equal-sized OPTb cache, as OPTb is optimal and outperforms all policies, including those like OPTn that never bypass the cache. For the other part of the inequality, McFarling gives the following argument. If one takes an OPTb cache of size j and stores in a victim cache of size 1 the item evicted from the OPTb cache or bypassing the OPTb cache, the OPTb cache and the victim cache together can be viewed as a cache of size j + 1 that is not bypassed. Hence the OPTb+victim cache (and the OPTb cache alone) does not generate more hits than an OPTn cache of size j + 1.

The OPT tokens algorithm provides another way to relate OPTn and OPTb. Upon an OPTn miss (see Figure 4), all the tokens but the lowest one move upwards. The lowest token never leaves the bottom position. Apart from that, OPTn and OPTb behave identically. More precisely, if we ignore hits at q t = 1, an OPTn cache of size j + 1 behaves like an OPTb cache of size j seeing reuse distances q t = q t -1. That is, the two caches yield exactly the same hits and misses. This equivalence is summarized in Figure 5.

For example, consider a random trace with s distinct items, i.e., such that all LRU stack positions in [1, s] have equal probability 1/s to be accessed. Let us denote m n (j, s) and m b (j, s) the OPT miss ratios LRU stack hit hit/miss q t q t = 1 for an OPT cache of size j on random traces, without and with bypassing respectively. We mentioned in Section 7 that there is probably no simple mathematical formula for computing exactly m n and m b . Yet, from the equivalence of Figure 5, we can derive a simple equation relating m n and m b . A fraction 1/s of references are such that q t = 1 (hit). After applying the transformation shown in Figure 5, we obtain a random trace such that all LRU stack positions in [1, s -1] have equal probability to be accessed. This yields the following equality:

q t > 1 X t q ′ t = q t -1 q ′ t OPT
m n (j + 1, s) = (1 - 1 s ) × m b (j, s -1)

Circular traces

We already mentioned that, if the number s of distinct items is bounded, OPT cannot be defeated, i.e., its miss ratio is always below 100% (corollary 2). On the other hand, all online replacement policies can be defeated. In particular, it is well known that, when the cache size j is less than s, accessing s distinct items in a circular fashion (as in the example of Table 4) defeats LRU.

The OPT miss ratio on a circular trace can be calculated easily (see for instance [START_REF] Smith | Instruction cache replacement policies and organizations[END_REF] for an OPT cache without bypassing). One can check that the OPT tokens algorithm yields the correct result (see Table 4). For OPT with bypassing, the steady-state miss ratio on a circular trace is OPTb miss ratio on a circular trace = sj s For OPT without bypassing, we replace j by j -1 and s by s -1 in the expression above (cf. Figure 5) and we obtain (s-1)-(j-1) s-1

, that is, OPTn miss ratio on a circular trace = sj s -1

The steady-state OPT miss ratio is equal to the upper bound stated by corollary 2. In other words, accessing a data set in a circular fashion maximizes the OPT miss ratio. It is not coincidental that the trace with the worst OPT miss ratio is the one that maximizes q t . We are going to show the following: Proposition 1. If two traces T = (X t ) and T = (X t ), generating reuse distances (q t ) and (q t ) respectively, have the same length and are such that q t ≤ q t for all t, then T does not generate more OPT misses than T .

DIVERGENCE STILL DIVERGED CONVERGENCE

hit hit q τ q ′ τ τ τ + 1 hit τ miss q τ q ′ τ τ + 1 hit hit t + 1 hit miss t q t t + 1 q t t hit hit t + 1 t q t Figure 6:
The different cases for proving proposition 1. At time τ , trace T accesses LRU stack position q τ , and trace T accesses LRU stack position q τ = q τ + 1. For t > τ , the two traces access the same LRU stack positions. The diverging token for trace T is colored in yellow, the diverging token for T in green (the diverging token for a trace is not a token for the other trace; they are shown simultaneously for the sake of succinctness). The "leader" trace is the one whose diverging token is the lowest. When a miss for the leader trace is a hit for the other trace, the leader changes.

Proof. To show proposition 1, it is sufficient to start from a trace (q t ), increment one q τ (q τ = q τ +1, q t = q t for t = τ ), and show that the number of misses does not decrease. Figure 6 provides examples illustrating the different cases. Before time τ , the two traces have exactly the same behavior. If q τ does not coincide with a token, no divergence occurs, and the two traces continue to have the same behavior. Otherwise, if q τ coincides with a token, the two traces diverge. Once diverged, the two sets of tokens (one set for each trace) coincide except for one token, the diverging token. In Figure 6, the two diverging tokens (one for each trace) are shown simultaneously, the one for trace T colored in yellow, and the one for trace T colored in green. We distinguish two situations. We say that trace T is the "leader" if its diverging token is lower than the diverging token of trace T . Otherwise, trace T is the leader.

If there is divergence at τ , two situations can occur (left part of Figure 6):

1. both T and T hit at τ : T is the leader at τ + 1 2. T hits and T misses: T is the leader at τ + 1

For t > τ and before convergence, two situations can occur (middle part of Figure 6):

1. T and T both hit or both miss at t: the leader at t is the leader at t + 1 2. the leader trace misses and the other trace hits: the leader changes Finally, convergence can occur only when both traces hit (right part of Figure 6). After convergence, the two sets of tokens coincide, and the two traces have exactly the same behavior. Between divergence and convergence, for having a miss for T and a hit for T at t, the leader at t must be T . But if T is the leader at t, it means that there was previously a hit for T and a miss for T . Hence T does not generate more misses than T .

From proposition 1, it is obvious why circular accesses are worst for OPT. Sometimes, proposition 1 can also provide a lower bound for the number of OPT misses: Corollary 4. For an OPT cache of size j, on an infinitely long trace, if there exists a finite time τ such that for all t ≥ τ , q t ≥ q min > j, the asymptotic OPT miss ratio is greater than or equal to q min -j q min -1+β .

Proof. We transform trace (q t ) into (q t ) such that q t = q t for t < τ and q t = q min for t ≥ τ . From proposition 1, the OPT miss ratio of (q t ) is greater than or equal to that of (q t ). For t ≥ τ , trace (q t ) has a circular behavior (i.e., q t is constant). Whatever the positions of tokens at τ , the asymptotic miss ratio of (q t ) is q min -j q min -1+β .

If a trace is such that q t is not constant but remains in an interval [q min , q max ], the asymptotic OPT miss ratio is in the interval [ q min -j q min -1+β , qmax-j qmax-1+β ]. If q min and q max are close, we know approximately the OPT miss ratio.

Conclusion

Belady's MIN algorithm and Mattson's OPT replacement policy provide two different ways to think about optimal replacement. This paper brings three new equivalent ways to reason about OPT hits and misses: equation ( 14), the OPT matrix, and the OPT tokens. With these conceptual tools, we have discovered and proved several facts that were previously unknown, and we have proved rigorously the convexity of OPT miss curves. Theorem 1 highlights a remarkable structure in traces of OPT distances, and offers a very simple way to detect bugs in OPT stack implementations, just by a visual inspection of the output. Also, we found that the notion of reuse distance, which is naturally related to the LRU policy, is also useful for understanding optimal replacement. Probably, many mathematical facts about optimal replacement remain to be discovered.

Though the goal of this paper is to improve our understanding of optimal replacement, some of our results might lead to practical findings. For instance, the Hawkeye cache replacement policy is directly inspired from Belady's MIN algorithm [START_REF] Jain | Back to the future: leveraging Belady's algorithm for improved cache replacement[END_REF]. The OPT tokens algorithm might inspire alternate implementations of the Hawkeye policy.

Figure 2 :

 2 Figure 2: OPT stack with bypassing. Left: The alphabetical order indicates how items are ordered at time t + 1 by their time of next reference.Right: Focus on a particular item X. Item X goes up in the stack when X t is above X, X t is re-referenced before X, and all the stack positions below X are occupied by items that will be referenced before X.

Figure 3 :

 3 Figure 3: OPT cache of size j (bypassing allowed) and random trace with s distinct items. Relation between j/s and the miss probability m.

  t

Figure 5 :

 5 Figure 5: Equivalence between an OPT cache of size j + 1 without bypassing and an OPT cache of size j with bypassing.

Table 1 :

 1 Belady's MIN algorithm on an example, assuming a 3-entry cache. Each row of the MIN matrix is associated

with a distinct item. Columns represent successive times. Yellow cells show when items are referenced. A cell is marked "r" when a cache entry is reserved at that time for that item.

Table 2 :

 2 Main notations.

1 t

 1 and ∀j < p t , I j t < Y pt t . Let us focus on one j ∈ [2β, p t [. There must exist a τ ∈]t, t [ such that I j τ ≥ Y pt τ and I j τ +1 < Y pt τ +1

The origin of this confusion is not clear. Confusion was already there in the early years[START_REF] Aho | Principles of optimal page replacement[END_REF][START_REF] Coffman | Operating Systems Theory[END_REF].

Belady's 1966 algorithm uses a vector, not a matrix. However the matrix captures the essence of MIN and is easier to explain[START_REF] Belady | On-line measurement of paging behavior by the multivalued MIN algorithm[END_REF][START_REF] Temam | An algorithm for optimally exploiting spatial and temporal locality in upper memory levels[END_REF][START_REF] Jain | Back to the future: leveraging Belady's algorithm for improved cache replacement[END_REF].

We recall that when item Xτ is referenced for the first time at τ ∈ [t , t[, we define pτ = sτ + 1. With our definition of M j [t ,t[ , the reference at τ is counted as a hit for all j ≥ sτ + 1.

Our goal here is not to obtain a computationally efficient algorithm. Sugumar and Abraham described an efficient OPT stack implementation requiring a single pass (unlike Mattson's original algorithm), but with some look-ahead[START_REF] Sugumar | Efficient simulation of caches under optimal replacement with applications to miss characterization[END_REF]. They implemented this algorithm in a cache simulator called Cheetah, distributed with the Simplescalar processor simulation infrastructure[START_REF] Burger | The SimpleScalar tool set, version 2.0[END_REF]. We believe that Cheetah is fast enough for most practical purposes.

McFarling did not provide an actual proof that OPTb is optimal.