Marginal Utility of SEQ

When we have multiple streams, their think times will in general be different. Also, in general, each client will have different number of accesses to each track before moving onto the next track. Fortunately, these differences do not enter our analysis below.

Let us suppose that there are $\ell$ streams. The parameter $\ell$ will not appear anywhere in our algorithm. Let $s_i^a$, $1 \leq i \leq \ell$, denote the rate of sequential misses of stream $i$ for synchronous+asynchronous prefetching. Observe that these individual numbers are generally not easily observable. However, their sum

$$s = \sum_{i=1}^{\ell} s_i^a$$ (4)

is simple to observe in a real system.

Let $L$ denote the length of the list SEQ in number of $4$K pages. To compute the marginal utility of SEQ, we examine how the overall rate of sequential misses changes, namely, $\Delta s$, in response to a small change $\Delta L$ in $L$. By the stack property of SEQ, as $L$ increases (respectively, decreases) $s$ decreases (respectively, increases). Hence, $\Delta s/\Delta L$ is always negative. The marginal utility is measured by the magnitude of this quantity. We shall lower bound this negative quantity, and, in turn, upper bound the marginal utility.

$$\frac{\Delta s}{\Delta L} = \frac{\Delta T}{\Delta L} \frac{\Delta s}{\Delta T}$$

$$\stackrel{(a)}{=} \frac{\Delta T}{\Delta L} \sum_{i=1}^{\ell} \frac{\Delta s_i^a}{\Delta T}$$

$$\stackrel{(b)}{\geq} \frac{\Delta T}{\Delta L} \sum_{i=1}^{\ell} \frac{\Delta s_i'}{\Delta T}$$

$$\stackrel{(c)}{=} \frac{\Delta T}{\Delta L} \sum_{i=1}^{\ell} I (T < T_i) \cdot \left( \frac{\Delta s_i}{\Delta T} - \frac{s_i^s}{T_i} \right)$$

$$\stackrel{(d)}{=} \frac{\Delta T}{\Delta L} \sum_{i=1}^{\ell} I (T < T_i) \cdot \left( - \frac{s_i}{T} - \frac{s_i}{T} \left( \frac{T}{T_i} \right)^2 \right)$$

$$\stackrel{(e)}{>} \frac{\Delta T}{\Delta L} \sum_{i=1}^{\ell} \left( -2 \frac{s_i^a}{T} \right)$$

$$\stackrel{(f)}{=} - 2 \frac{\Delta T}{\Delta L} \frac{s}{T}$$

$$= - 2 \frac{L \Delta T}{T \Delta L} \frac{s}{L}$$

$$\stackrel{(g)}{=} - 2 \frac{s}{L},$$ (5)

where (a) follows from (4); (b) follows since, by definitions in (2) and (3), $s_i'$ that is steeper than $s_i^a$ throughout the continuous region $[0, T_i)$; (c) follows from (3) and $I$ is the indicator function that takes value $1$ or 0 depending upon whether $T< T_i$ or not; (d) follows from (1); (e) follows since $T< T_i$ and the indicator function $I(T < T_i)$ can be removed since when $I$ is zero $s_i^a$ is also zero; (f) follows from (4); and (g) follows since, in practice, there is linear relationship between $L$ and $T$. In other words, as the length of the list increases (respectively, decreases) the time difference between the MRU and LRU time stamps of the list increases (respectively, decreases) proportionately for any given workload.

Let $T_i$, $1 \leq i \leq \ell$, denote the times at which various streams attain zero misses (see Figure 3). Mathematically, the above chain of inequalities is valid at all points in $[0, \infty)$ except at $T_i$, $1 \leq i \leq \ell$, since at $T_i$, $\Delta s_i^a$/$\Delta T$ is not defined. However, our choice of the approximating curve $s_i'$ is such that it cleverly distributes the magnitude of the drop in $s_i^a$ at $T_i$ evenly throughout the interval $[0, T_i)$, and, hence, in practice, the inequalities are applicable. This approximation smoothes out the changes in $\Delta s$ in relation to $\Delta L$ at the discontinuities and paves the way for designing a locally adaptive algorithm such as ours.

We now have the following bounds

$$- \frac{s}{L} \geq \frac{\Delta s}{\Delta L} \geq - 2 \frac{s}{L},$$

where the upper bound follows from (1) and (2) and the lower bound follows from (5). In other words, the marginal utility lies somewhere between $s/L$ and $2s/L$, but closer to latter in practice. In this paper, we have chosen $2s/L$ to approximate the marginal utility of SEQ.