02129 RR111

RIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

laboratoire de recherche
en informatique
et automatique

Record allocation
for minimizing expected
retrieval costs on
drum-like storage devices

R. Cody, E. G. Coffman.

Rapport de Recherche n° 111

Avril 1975
RECORD ALLOCATION FOR MINIMIZING EXPECTED RETRIEVAL COSTS ON DRUM-LIKE STORAGE DEVICES

R. CODY, E.G. COFFMAN

Dans cet article, on suppose donnée une collection d'enregistrements de même longueur et une distribution de probabilité discrète décrivant les fréquences stationnaires d'accès à ces enregistrements. On examine des heuristiques simples pour regrouper les enregistrements selon les secteurs d'une mémoire du genre tambour de façon à minimiser le temps moyen d'accès. On montre que le problème général est NP-complet et on dérive des limites de performance pour les heuristiques étudiés, qui s'avèrent très efficaces.

The paper assumes as given a collection of equal-length records and an associated discrete probability distribution describing stationary record access frequencies. Simple heuristics are examined for partitioning the records among the sectors of a drum-like storage device so as to tend to minimize average access times. The general problem is shown to be NP-complete and performance bounds are derived for the heuristics, which are found to be very efficient.
RECORD ALLOCATION FOR MINIMIZING EXPECTED RETRIEVAL

COSTS ON DRUM-LIKE STORAGE DEVICES*

R. Cody
The Pennsylvania State University

E. G. Coffman, Jr. +
Institut de Recherche d'Informatique et d'Automatique

I. Introduction

We consider the problem of partitioning a set of equal-length records into a set of blocks to be assigned to the sectors of a drum, or a cylinder of a disk system, so as to minimize the expected cost of latency time. Assuming a stationary probability distribution describing record access frequencies, we shall formulate the problem as a catenated search [1] problem. Thus, we shall be considering minimum latency costs under the assumptions that a queue of requests is serviced first-in-first-out (FIFO) and that the system is operating at full capacity; i.e. a saturated demand for record accesses is assumed. For analyses of a number of other interesting catenated search problems the reader is referred to [1]. A particularly relevant application of our study exists in those paging systems [2] containing paging drums or disks, where the equal-length records are pages.

We shall begin in the next section by defining the model and the cost function to be minimized. In this section we also verify that the basic minimization problem is NP-complete [3]. In section III and IV we analyze a simple heuristic approach to the problem in which records are assigned to blocks largest-first, in terms of access probabilities, in the same manner described by Graham [4] for sequencing independent tasks on multiple processors with execution times known. Performance bounds are derived under two assumptions: First, there is no bound on the number of records that can be assigned to a sector, and second there exists a fixed bound $k$ on this number for all sectors. (We shall always assume that $n \le m \le k$ where $n$ is the number of records and $m$ is the number of sectors.) We show that even in the worst-case the performance of the heuristics is very close to optimal.

<footnote>* This research was supported in part by NSF Grnat N° 28290 at the Pennsylvania State University</footnote>
## II. The Model

Let the set of n records be represented by their stationary access probabilities, $P = \{p_1, ..., p_n\}$. The problem of allocating these records on a drum having m sectors so that the expected latency cost is minimized, consists of finding a partition, $\mu$, of n records into m blocks, and an assignment function, $\pi$, which assigns these blocks to the m sectors on the drum. (Our terminology will be restricted to drum systems although the applications also include disk systems.) To define the cost function, we suppose an unbounded FIFO queue of requests for which the probability that the j-th request is for the i-th record is simply $p_i$ for all j. If $S_i$ denotes the sum of the probabilities of records assigned to sector i, then the expected latency cost $C(\mu, \pi)$ of a record access (for all requests beyond the first) may be written as

$$ (1) \qquad C(\mu, \pi) = \sum_{i,j=1} S_i S_j d_{ij} $$

where $d_{ij}$ is the latency cost incurred in the motion of the drum from the end of sector i to the beginning of sector j. Equation (1) in effect characterizes categorized search problems [1]. Assuming a unit cost for the time taken by the drum to rotate over one sector, the latency cost function will be given by

$$ (2) \qquad \begin{aligned} d_{ij} &= j-i-1 \\ d_{ji} &= m-2-d_{ij} \\ d_{ii} &= m-1 \end{aligned} \qquad \begin{array}{l} \text{for } 1 \le i < j \le m \\ \text{for } 1 \le i \le m \end{array} $$

The following result simplifies our minimization problem.

**Lemma 1** $C(\mu, \pi) = C(\mu, \pi')$ for all $\pi$ and $\pi'$; that is, the assignment of sector numbers to sector blocks does not affect the expected cost.

*Proof:* It can be shown that for any assignment functions, $\pi$ and $\pi'$, that differ only by a single interchange of two sector blocks, $C(\mu, \pi) - C(\mu, \pi') = 0$. The result then follows, since any assignment can be obtained from any other by a sequence of such simple interchanges. $\square$

In view of Lemma 1 we shall hereafter use the simpler notation $C(\mu) = C(\mu, \pi)$. Therefore, our specific problem is: Given a number, m, of sectors and a set P find a partition $\mu$ that minimizes (1) assuming the cost function (2).
We may render this problem into a simpler form as follows.

Let $S = (S_1, \dots, S_m)$, where without loss of generality, $S_1 \ge S_2 \ge \dots \ge S_m$ and let $f(S) = \sum_{i=1}^m S_i^2$. Also, let $\delta_i = S_i - \frac{1}{m}$, $\delta = (\delta_1, \dots, \delta_m)$ and $f(\delta) = \sum_{i=1}^m \delta_i^2$.

**Theorem 1** We have

$$ (3) \qquad C(\mu) = \frac{m-2}{2} + \frac{m}{2} f(S) = \frac{m-1}{2} + \frac{m}{2} f(\delta) $$

so that the partition, $\mu^*$, which minimizes $f(\delta)$ and $f(S)$ also minimizes the expected latency cost function and conversely.

**Proof** : Using the symmetry of the cost function, we may rewrite (1) as

$$ C(\mu) = \frac{1}{2} \sum_{i,j=1} S_i \bar{S}_j (d_{ij} + d_{ji}) $$

By observing that

$$ \begin{aligned} d_{ij} + d_{ji} &= m-2 & 1 \le i < j \le m \\ &= 2(m-1) & i=j \end{aligned} $$

We have

$$ (4) \qquad C(\mu) = \frac{m-2}{2} \sum_{i \ne j} S_i S_j + (m-1) \sum_{i=1}^{m} S_i^2 $$

Making use of

$$ \sum_{i=1}^{m} S_i^2 + \sum_{i \ne j} S_i S_j = \left( \sum_{i=1}^{m} S_i \right)^2 = 1 $$

we substitute into (4), simplify, and obtain the first part of (3). The second part of (3) follows from $f(\delta) = f(S) - \frac{1}{m}$. $\square$

The next result verifies that in fact our problem is a hard one.

**Theorem 2** For any $m \ge 2$ the problem of constructing $\mu^*$ is NP-complete.

**Proof** : The idea is to consider the problem of finding a partition for $m = 2$ such that $f(S) \le k$, for some given $k$. Letting $k = 1/2$ we see that $f(S) \le k$ if and only if there is a partition of $P$ into two blocks such that the block sums $S_1$ and $S_2$
are equal. It is well-known that this partitioning problem is NP- complete [3].
The details of a complete proof based on this reduction are routine and hence,
we leave them to the concerned reader. []

We should note immediately that Theorem 2 is easily extended to include the
case where there is a fixed bound k on the cardinality of the blocks of the
partition (see [5]).

In view of the complexity one can expect from any exact algorithm for calculating μ*, it is reasonable to consider how well a simple heuristic might do.
In the following we shall be examining two easily implemented heuristics for partitioning a set of records. Our goal is to bound how bad the heuristics can be by computing a bound to the ratio of the cost obtained by the heuristic to that of an optimal partition. For even moderately large m we shall see that the cost ratios are very close to one. Best (i.e. achievable) upper bounds are not known as yet, except for the case m = 2.

To motivate the study of heuristics we show that an arbitrary assignment can
have a cost up to twice that of an optimal assignment. First, we need some no-
tation and a preliminary result.

For convenience the partitioning rules to be defined will be based on the
notion of assigning record access probabilities to blocks rather than records
to blocks. Of course, the record distribution is completely defined by the
partitioning of record probabilities. Also, for ease in reading and writing we
shall refer to record access probabilities as RP's.

Let A be an arbitrary rule for assigning RP's to blocks, let $B_i$ denote the set of RP's in sector (block) i, and as before let $S_i$ denote the total probability mass in $B_i$ ($1 \le i \le m$) for the A-assignment of a given set P. Let $\delta_A$ and $S_A$ denote the vectors obtained by applying A to P, and denote the cost ratio for two assignment rules and a given m as

$$
(5) \quad \eta_m (A/A') = \frac{\frac{m-1}{m} + f(\delta_A)}{\frac{m-1}{m} + f(\delta_{A'})} = \frac{\frac{m-2}{m} + f(\delta_A)}{\frac{m-2}{m} + f(\delta_{A'})}
$$
Finally, we present the following result whose routine proof is omitted.

**Lemma 2** Given the set $X = \{x_1, \dots, x_m\}$ such that $\sum_{i=1}^{m} x_i = 1$, and $0 \le x_i \le 1$ ($1 \le i \le m$), we have

$$ \frac{1}{m} \le \sum_{i=1}^{m} x_i^2 \le 1 $$

Moreover, the sets $X_1$ such that for some $i, x_i = 1$, $x_i = 0$ ($j \ne i$), and $X_2$ such that $x_i = 1/m$ for all $i$ achieve, respectively, the upper and lower bounds.

**Theorem 3** For any set $P$ and a given $m$ let $A$ and $A'$ denote two arbitrary assignment rules. Then

$$ (6) \qquad \eta_m(A/A') \le 2 \qquad m \ge 2 $$

and this is a best bound. Moreover, (6) is a best bound if $A$ and $A'$ are drawn from a restricted class of assignment rules defined by a fixed block-size constraint.

**Proof** : From Lemma 2 substitute upper and lower bounds on $f(S_A)$ and $f(S_{A'})$, respectively, into (5) to obtain

$$ \eta_m(A/A') \le \frac{\frac{m-2}{m} + 1}{\frac{m-2}{m} + \frac{1}{m}} = 2 $$

The set for which $n = m^2$ and $p_i = 1/m$ ($1 \le i \le m$), $p_i = 0$ ($m+1 \le i \le m^2$) shows that the bound is achievable in general and, in particular, under an equal block-size constraint on both $A$ and $A'$. $\square$

### III. Largest-First Assignment Heuristics

We now present an assignment rule whose execution time will have a complexity no worse than that associated with the sorting of $n$ numbers. Basically, the rule iteratively assigns the RP's largest-first to the $B_i$ currently having the least total probability mass, subject to the constraint that no $B_i$ can have more than $k$ RP's.

**Input** : A probability distribution $P = \{p_1, \dots, p_n\}$, an integer $m \ge 2$, and an integer $k$ such that $n \le k m$.
**Output**: A partition {$B_1, ..., B_m$} of P such that $|B_i| \le k, 1 \le i \le m$.

**Method**: procedure L\*-assignment

1. Set $S_i \leftarrow 0$ and $B_i \leftarrow \emptyset$ for all $i, 1 \le i \le m$
   Set $Q \leftarrow P$, and $i \leftarrow 0$.

2. If $Q = \emptyset$ the procedure terminates.

3. Find a $B_i$ among those satisfying $|B_i| < k$ such that $S_i$ is minimal. Find a $p$ that is a largest RP in $Q$ and set

$$B_i \leftarrow B_i + p$$

$$S_i \leftarrow S_i + p$$

$$Q \leftarrow Q - p$$

Return to step 2.

**end**

If in step 3 of the procedure we remove the $|B_i| < k$ condition (or simply assume $k=n$, for example), then we have what we shall call an **L-assignment**. An optimal, unconstrained assignment will be termed an **O-assignment**, and the optimal, subject to $|B_i| \le k, 1 \le i \le m$, will be termed an **O\*-assignment**.

Examples are shown in Figure 1 which illustrate these rules and the fact that L\*-assignments are not generally optimal. In this section we shall restrict ourselves to a comparison of L and O-assignments.

In the following it will be convenient to adopt as a convention that the elements of each $B_i$ are ordered, as in Figure 1. Thus, $B_i = (p_{i1}, ..., p_{ik})$ implies $p_{i1} \ge p_{i2} \ge ... \ge p_{ik}$. Assuming the above ordering we introduce the notation $S(p_i) = \sum_{j=1}^{j} p_{ij}$ and $R(p_i) = S(p_i) - p_i$. We say that $p$ begins at $R(p)$ and terminates at $S(p)$. Also, the block-sum notation $S_i$ will always refer to the heuristic under discussion while the primed notation $S'_i$ refers to an optimal assignment.

Our ultimate objective in this section is a bound on $\eta_m(L/O)$.
For this purpose we require a number of preliminary results, most of which are
simple observations which will lend insight into our combinatorial problem.
1/3

<figure><img src="image_1.png" /></figure>

B₁ B₂ B₃
O*- assignment

1/3

<figure><img src="image_2.png" /></figure>

B₁ B₂ B₃
L* - assignment

$m = k = 3$

$C_{L*} - C_{O*} = \frac{1}{648}$

1/3

<figure><img src="image_3.png" /></figure>

B₁ B₂ B₃
O - assignment

1/3

<figure><img src="image_4.png" /></figure>

B₁ B₂ B₃
L - assignment

$n = 3$

$C_L - C_O = \frac{1}{1352}$

FIGURE 1
**Lemma 3** Let $p$ and $p'$ be any two RP's in an L or O-assignment and suppose $p$ terminates a block. Then $R(p') \le S(p)$ for all $p' \ne p$. Also, if $p'$ and $p$ both terminate blocks in an $L^*$ or $O^*$-assignment and if $R(p') \ge S(p)$ then $p'$ cannot exceed any RP in the block containing $p$.

Note that this result implies that $R(p) < 1/m$ for all $p$ in L and O-assignments. The first part of the lemma is trivial to show. A simple exchange argument suffices to prove the second part of the lemma. The following result follows easily from Lemma 3.

**Lemma 4** In $P = \{p_1, \dots, p_n\}$ let $P_j = \{p_1, \dots, p_j\}$ be that subset containing just those RP's exceeding $1/m$. The L and O-assignments both distribute the RP's in $P_j$ one to a block, and the blocks containing these RP's have only one RP.

We can identify the following special case in which L-assignments are optimal.

**Lemma 5** Suppose $n \le 2m$ for a set $P = \{p_1, \dots, p_n\}$ and suppose the L-assignment places at most two RP's per block. Then the L-assignment must be optimal.

**Proof** : Lemma 3 can be used to show that the O-assignment must have at most two RP's per block and that the RP's in blocks having only one are all larger than those in blocks with two. A routine exchange argument then suffices to show that the blocks with two RP's in the L and O-assignments are in one-to-one correspondence in terms of the RP pairs they contain, subject possibly to a re-naming of RP's of equal size. $\square$

As a final preliminary result we have.

**Lemma 6** Let $x_1 \ge x_2 \ge \dots \ge x_t$ constitute a set (to be called a *profile*) of non-negative real numbers. For a non-negative real number $b$ we have

$$ \sum_{i=1}^{t} (x_i - b)^2 \le t \left[ (a-b)^2 + \frac{(x_1 - x_t)^2}{4} \right] $$
where

$$ (7) \qquad a = \frac{1}{t} \sum_{i=1}^{t} x_i $$

**Proof** First, from $x_i - b = (x_i - a) + (a - b)$ we can write

$$ \sum_{i=1}^{t} (x_i - b)^2 = t(a-b)^2 + 2(a-b) \sum_{i=1}^{t} (x_i - a) + \sum_{i=1}^{t} (x_i - a)^2 $$

The second term vanishes because of (7), so that we need only show that

$$ (8) \qquad \sum_{i=1}^{t} (x_i - a)^2 \le \frac{t}{4} (x_1 - x_t)^2 $$

Let $v = x_1 - x_t$, $x_1 - a = \alpha v$, and $a - x_t = (1 - \alpha)v$, $(0 < \alpha < 1)$. Let $j$ be defined such that $x_j > a$ and $x_{j+1} \le a$. We proceed by considering two symmetric cases.

**Case 1** $\alpha < (1 - \alpha)(t - j)$

In this case we can write

$$ (9) \qquad \sum_{i=1}^{t} (x_i - a)^2 \le j^{\alpha^2 v^2} + \sum_{i=j+1}^{t} (x_i' - a)^2 $$

where $x_i' \le x_i$ ($j+1 \le i \le t$) and $\sum_{i=j+1}^{t} (a - x_i') = j\alpha v$. We know such a collection $\{x_i'\}_{i=j+1}^t$ exists because the assumption of case 1 implies $j \alpha v < (t-j)(i-\alpha)v$. Figure 2 shows the profile transformation corresponding to (9).

Next, suppose for some $i < \ell$ that $x_i' > x_\ell' > x_t$. Now define

$$ x_\ell'' = x_\ell' - \min \{ x_\ell' - x_t, a - x_i' \} $$

and

$$ x_i'' = x_i' + [x_\ell' - x_\ell''] $$

thus retaining

$$ \sum_{i=j+1}^{t} (a - x_i'') = \sum_{i=j+1}^{t} (a - x_i') $$

It follows simply from the relations $x_\ell'' = x_\ell' - c$, $x_i'' = x_i' + c$, for some $c > 0$ and $x_\ell' < x_i'$ that

$$ (a - x_\ell'')^2 + (a - x_i'')^2 \ge (a - x_\ell')^2 + (a - x_i')^2 $$
(This type of transformation is pictured in Fig. 3). If we apply this transformation exhaustively in the order $x'_{t-1}, x'_{t-2}, \dots, x'_{j+2}$ we shall obtain a $j'$ ($j + 1 \le j' \le t$) such that $x_t \le x''_j \le a$, and $x''_{j+1} = \dots = x''_t = x_t$, as shown in Fig. 4. To continue producing a worse case we regard the index set $\{1, 2, \dots, t\}$ as the real interval $(0, t)$ and the profile a function $x(q)$ of the continuous variable $q$ ($0 \le q \le t$). This motivates our replacement of the $(a-x''_j) \times 1$ rectangle by the rectangle $(1-\alpha)v \times d$, where $d = (a-x''_j)/(1-\alpha)v$ (see Fig. 4). Since $d(1-\alpha)^2 v^2 > (a-x''_j)^2$ we can write

$$ \sum_{i=j'}^{t} (a - x'_{i})^{2} \leq [t - (j' - d)] (1 - \alpha)^{2} v^{2} $$

where $(t - j' + d)(1 - \alpha)v = j' \alpha v$.

As a last step we find that point $q$ which divides the interval $(j, j' - d)$ in the proportion $(1 - \alpha)/\alpha$ and extend the rectangles up to $q$ as shown in Fig. 5. Finally, we can write

$$ (10) \qquad \sum_{i=1}^{t} (x_i - a)^2 \le q \alpha^2 v^2 + (t-q) (1-\alpha)^2 v^2 $$

where $q \alpha v = (t - q)(1 - \alpha)v$ or

$$ (11) \qquad q = t(1-\alpha) $$

### Case 2

This case is treated in a fashion that is exactly symmetric to case 1. Again we arrive at (10).

Using (11) in (10) we get

$$ \begin{aligned} \sum_{i=1}^{t} (x_i - a)^2 &\le t\alpha^2(1-\alpha)v^2 + t\alpha(1-\alpha)^2 v^2 \\ &= t\alpha(1-\alpha)v^2 \end{aligned} $$

This function of $\alpha$ is maximized at $\alpha = 1/2$ and hence (8) follows immediately. $\square$
<figure><img src="image_5.png" /><figcaption>Figure 2</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Figure 3</figcaption></figure>
It may be observed that the bound in (8) is achievable for t even, but not when t is odd. In the main result which follows we adopt the following notion of rank. For a set of RP's, $p_1 \ge p_2 \ge \dots \ge p_n$, we say that $p_1$ through $p_m$ are rank-1 RP's, $p_{m+1}$ through $p_{2m}$ are rank-2 RP's, and so on.

**Theorem 6** For any set $P = \{p_1, \dots, p_n\}$ we have

$$ (12) \qquad \eta_m (L/O) \le 1 + \frac{1}{16(m-1)} $$

**Proof** Suppose first that in the L-assignment

$$ v = \max_i \{S_i\} - \min_i \{S_i\} \le 1/2m $$

Then by Lemma 6 we have

$$ f(\delta_L) = \sum_{i=1}^{m} (S_i - 1/m)^2 \le \frac{m}{4} \left(\frac{1}{2m}\right)^2 = \frac{1}{16m} $$

Thus,
$$ \eta_m (L/O) = 1 + \frac{f(\delta_L) - f(\delta_0)}{\frac{m-1}{m} + f(\delta_0)} \le 1 + \frac{m}{m-1} f(\delta_L) \le 1 + \frac{1}{16(m-1)} $$

and we are done.

Now suppose $v > 1/2m$. From the property of L-assignments in Lemma 3 we conclude that a rank-1 or rank-2 RP must terminate the L-assignment. Let $P'$ be precisely the set of RP's in the set $U$ of blocks whose block-sums exceed $\min \{S_i\}$ by more than $1/2m$. Assume for convenience that $U = \{B_1, \dots, B_j\}$ ($j \ge 1$). If $U$ contains only blocks having exactly one RP (of rank-1 necessarily), then we may assume from Lemma 3 that $U' = \{B'_1, \dots, B'_j\}$ in the O-assignment is such that $B'_i = B_i$ ($1 \le i \le j$).

Moreover,

$$ \sum_{i=1}^{j} (S_i - 1/m)^2 = \sum_{i=1}^{j} (S'_i - 1/m)^2 $$
<figure><img src="image_7.png" /><figcaption>Figure 4</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Figure 5</figcaption></figure>
and a $η_m(L/0) > 1$ must result from the assignments of $B_{j+1}, \dots, B_m$.

We now want to show that $η_m(L/0) > 1$ must result from the assignments in $\{B_{r+1}, \dots, B_m\}$ where $V = \{B_1, \dots, B_r\}$ contains all those blocks having rank-2 RP's exceeding $1/2m$ or rank-1 RP's exceeding $1/m$. Since blocks with only rank-$\uparrow$ RP's exceeding $1/m$ can be removed from consideration by Lemma 3, we can reduce our problem immediately by assuming that each $B_i \in V$ has a rank-2 RP.

Let $P_r = \bigcup_{i=1}^r B_i$. Since $p > 1/2m$ for $p \in P_r$, it follows easily from Lemma 3 that each $B_i \in V$ has exactly one rank-1 RP and one rank-2 RP. Let $V' = \{B_{i_1}', \dots, B_{i_s}'\}$ be the set of blocks in the O-assignment to which the rank-2 RP's in $P_r$ are assigned, and let $P'_s = \bigcup_{j=1}^s B_{i_j}'$. We claim that $r = s$; i.e. $|V| = |V'|$. For the only way $r \neq s$ can occur is to have at least one block $B'$ in $V'$ contain exactly two of the rank-2 RP's in $P_r$. This would imply that some block $B''$ in the O-assignment has exactly two rank-1 RP's. Interchanging the smallest RP's in $B'$ and $B''$ reduces the sum of the squares of the two block-sums and therefore contradicts the assumption of an optimal assignment. Thus, $|V| = |V'|$.

We now claim that

$$ (13) \qquad \sum_{B_i \in V} (S_i - 1/m)^2 \le \sum_{B_i' \in V'} (S_i' - 1/m)^2 $$

We note from Lemma 5 that the set $P'$ consisting of the $m$ rank-1 RP's and just those rank-2 RP's in $P_r$ is optimally assigned by the L-rule, in the sum-of-squares sense. The inequality in (13) follows routinely. Moreover, we can verify

$$ (14) \qquad \sum_{p \in P_r} p \le \sum_{p \in P_r'} p $$

By definition $P_r$ and $P_r'$ can differ only in the rank-1 RP's they contain.

But in the L-assignment $P_r$ contains the smallest $r$ rank-1 RP's, and therefore (14) must hold.
Without loss of generality assume that the indexing of the $B_i'$ is such that
$V' = \{B_1', \dots, B_r'\}$ and let $S_{r+1} \ge S_{r+2} \ge \dots \ge S_m$ and $S_{r+1}' \ge S_{r+2}' \ge \dots \ge S_m'$. 
From (13) and (14) our problem has been reduced to showing that

$$ \sum_{i=r+1}^{m} (S_i - 1/m)^2 - \sum_{i=r+1}^{m} (S_i' - 1/m)^2 \le 1/16m $$

where by our definition of $r$, we have

$$ v_{r+1} = S_{r+1} - S_m \le 1/2m $$

But if we let $t = m-r$, $x_i = S_i$, $a = \frac{1}{m-r} \sum_{i=r+1}^{m} S_i$, and $b = 1/m$ we have
from Lemma 6

$$ (15) \quad \sum_{i=r+1}^{m} (S_i - 1/m)^2 \le \left[ \frac{1}{m} - \frac{1}{m-r} \sum_{i=r+1}^{m} S_i \right]^2 + (m-j) \frac{v_{r+1}^2}{4} $$

where

$$ \frac{1}{m-r} \sum_{i=r+1}^{m} S_i = \frac{1}{m-r} \left[ 1 - \sum_{p \in P_r} p \right] \le 1/m $$

Also, by arguments similar to those demonstrating Lemma 2 we deduce

$$ (16) \quad \sum_{i=r+1}^{m} (S_i' - 1/m)^2 \ge \left[ \frac{1}{m} - \frac{1}{m-r} \sum_{i=r+1}^{m} S_i' \right]^2 $$

where

$$ \frac{1}{m-r} \sum_{i=r+1}^{m} S_i' = \frac{1}{m-r} \left[ 1 - \sum_{p \in P_r'} p \right] $$

But from (14)

$$ \frac{1}{m-r} \left[ 1 - \sum_{p \in P_r'} p \right] \le \frac{1}{m-r} \left[ 1 - \sum_{p \in P_r} p \right] \le 1/m $$

and hence

$$ (17) \quad \left[ \frac{1}{m} - \frac{1}{m-r} \sum_{i=r+1}^{m} S_i \right]^2 \le \left[ \frac{1}{m} - \frac{1}{m-r} \sum_{i=r+1}^{m} S_i' \right]^2 $$

Finally, from (15), (16), and (17) we get

$$ f(\delta_L) - f(\delta_O) \le \sum_{i=r+1}^{m} (S_i - 1/m)^2 - \sum_{i=r+1}^{m} (S_i' - 1/m)^2 $$
$$ \leq (m-j) \frac{v_{t+1}^2}{4} \leq \frac{m}{4} \left(\frac{1}{2m}\right)^2 = \frac{1}{16m} \quad \square $$

The result of Theorem 6 has not been shown to be a least upper bound on $\eta_m(L/O)$. For $m = 2$, however, we can compute this least upper bound (1.u.b.) exactly. Note that for $m = 2$, minimizing $\eta_2(L/O)$ reduces to minimizing $((S_L)/f(S_0))$ a problem that has been studied separately, quite recently, by Chandra and Wong [6]. They have shown that maximization over $y$ and $z$ in Figure 6 gives the 1.u.b. $[f(S_L)/f(S_0)]$. Specifically, one obtains

$$ (18) \qquad \eta_2(L/O) \leq \frac{(y+2z)^2 + (y+z)^2}{(2y)^2 + (3z)^2} $$

where

$$ z = (1 + 5\sqrt{13}y)/27, \quad 2y + 3z = 1 $$

Note that the least upper bound is not achieved by a set $P$ for which the optimal assignment is such that $f(\delta_0) = 0$. This fact along with the form of (18) are rather discouraging to anyone expecting simple least upper bounds for arbitrary $m$.

It is of obvious interest to determine how far (12) can be from the 1.u.b. $\eta_m(L/O)$. For this purpose it is only necessary to consult the example in Figure 7 to verify that

$$ (19) \qquad 1 + \frac{1}{36m} \leq 1 \cdot \text{u.b.} \eta_m(L/O) \leq 1 + \frac{1}{16(m-1)} $$

## IV. The L*-assignment Rule

Clearly, for heavy use of storage we can not assume that the bound $k$ on the number of records that can be put on a sector has no influence. Thus, the L*-assignment rule will be analysed in this section, resulting in a simple bound for $\eta_m(L*/O)$ and hence $\eta_m(L*/O^*) \leq \eta_m(L*/O)$.

We shall assume without loss of generality that $n = k = m$ (we can always add enough zero-RFs to $P$ to ensure this without affecting the cost ratios). Before presenting the main result we need the following lemma.

**Lemma 7** Let the (ordered) blocks $B_i = (p_i, \dots, p_i^k)$, $1 \leq i \leq m$, be an L*-assignment for $P$, $|P| = n = m$ $k$. Then for any two blocks $B_i$ and $B_j$ we have
<figure><img src="image_9.png" /><figcaption>L-assignment</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>O-assignment</figcaption></figure>

FIGURE 6
$m$ even

<figure><img src="image_11.png" /></figure>

$F_m$ ($m=2k$)

L - assignment

$$ \eta_m(4/0) = 1 + \frac{1}{36(m-1)} $$

<figure><img src="image_12.png" /></figure>

O - assignment

$m$ odd

$m = 2k+1$

Choose $m = 5k+2$ and

$$ \text{Choose } \pi_i = \begin{cases} \frac{1}{2}m & 1 \le i \le 2k+2 \\ \frac{1}{3}m & 2k+3 \le i \le 5k+2 \end{cases} $$

to obtain

$$ \eta_m(4/0) = 1 + \frac{1}{36m} $$

FIGURE 7
$|S(p_i) - S(p_j)| \le \max [p_i, p_j]$. for all $r = 1, 2, \dots, k$.

**Proof:** The case $k=1$ is trivial so suppose $k \ge 2$. We proceed by induction on $r$. The basis $r=1$ is immediate, so suppose the result is true for some arbitrary $r, 1 \le r < k$, and consider $S(p_i) - S(p_j)$. Without loss of generality let $S(p_i) > S(p_j)$ and suppose contrary to the lemma, that $S(p_i) > S(p_j) + \max [p_i, p_j]$, and hence $R(p_i) > S(p_j)$. Since the $B_i$'s constitute an $L^*$-assignment we must have $p_i \le p_j$. Therefore, $S(p_{i,r+1}) - p_{i,r+1} > S(p_{j,r+1}) - p_{j,r+1} + \max [p_i, p_j]$ and $S(p_{i,r}) > S(p_{j,r}) + \max [p_i, p_j]$. which contradicts the inductive hypothesis. $\square$

**Theorem 7** For all sets $P$ and parameters $m, k$, and $n = mk$ we have.

$$ (20) \qquad \eta_m(L^*/O^*) \le \eta_m(L^*/O) \le \frac{m+1}{m-1} $$

**Proof :** From the definition of $\eta_m(L^*/O)$ provided by (5) we can write

$$ \eta_m(L^*/O) \le 1 + \frac{f(\delta_{L^*}) - f(\delta_0)}{\frac{m-1}{m} + f(\delta_0)} = 1 + \frac{\sum_{i=1}^{m} s_i^2 - \sum_{i=1}^{m} (s_i')^2}{\frac{m-1}{m} + f(\delta_0)} $$

From the last expression we justify

$$ (21) \qquad \eta_m(L^*/O) \le 1 + \frac{m}{m-1} \sum_{i=1}^{m} (S_i - S_i') (S_i + S_i') $$

If we can show that $S_i - S_i' \le 1/m, 1 \le i \le m$, then from (21) we can write

$$ \eta_m(L^*/O) \le 1 + \frac{m}{m-1} \left( \frac{1}{m} \right) \sum_{i=1}^{m} (S_i + S_i') = 1 + \frac{2}{m-1} $$

from which (20) follows directly. Thus, we shall be done once we show that $S_i - S_i' \le 1/m$.

As in theorem 6 let $p_1 \ge p_2 \ge \dots \ge p_j$ be just those RP's greater than or equal to $1/m$, and suppose they are assigned respectively to $B_1, \dots, B_j$ in the $L^*$-assignment and to $B'_1, \dots, B'_j$ in the $O$-assignment. Also, assume $S_{j+1} \ge S_{j+2} \ge \dots \ge S_m$ and $S'_{j+1} \ge S'_{j+2} \ge \dots \ge S'_m$. In the $L^*$-assignment no RP assigned beyond $1/m$ can be larger than any RP which terminates before $1/m$. It follows easily that
$S_i - S'_i \le S_m, 1 \le i \le j$, and since $S_m \le 1/m$, we have $S_i - S'_i \le 1/m, 1 \le i \le j$.
It remains, therefore, to consider $B_{j+1}, \dots, B_m$ and $B'_{j+1}, \dots, B'_m$.

We can verify, first of all, that $S_{j+1} - S_m \le 1/m$ from Lemma 7. Now let $r$ be the smallest integer such that $S_r - S'_r > 1/m$. (Clearly, $S_r > 1/m$). Since $S_r - S_m < 1/m$ and since $S'_i \le S'_r$ ($i > r$) it must be that $S'_i < S_m$, $i \ge r$. But $S'_i < S_m$, $i \ge r$, and $S_r > 1/m$ imply the existence of some $\ell$ ($j < \ell < r$) such that $S'_\ell \ge S_r > 1/m$, in order that the total probability mass be 1 in the 0-assignment. (Clearly, $\ell \le j$ is impossible since in any 0-assignment $R(p) < 1/m$ for all $p$). Hence, $S'_m > S_r - S'_m > 1/m$. This in turn implies the existence of an RP larger than $1/m$ but assigned in $B'_{j+1}, \dots, B'_m$, or an RP, $p$, such that $k(p) > S'_m$. The first event contradicts our definition of $B'_1, \dots, B'_j$ and the second violates Lemma 3. Hence, $S_i - S'_i < 1/m, 1 \le i \le m$. $\square$

Once again it is possible to obtain a least upper bound for the case $m = 2$. Omitting the details, it can be shown that one need simply maximize $\eta_2(L^*/O)$ over $t$ in Figure 8 and then take the limit $p \to 0$ and $k \to \infty$ to obtain

**Theorem 8** For $m = 2$ and an arbitrary set $P$ we have

$$ \eta_2(L^*/O) \le \frac{3+\sqrt{5}}{4} $$

and this bound is best possible.

By generalizing the examples shown in Figures 9 for $m = 4$ and $m = 5$ it is not difficult to verify for arbitrary $m$

$$ 1 + \frac{1}{4m} \le \text{l.u.b. } \eta_m(L^*/O) \le \frac{m+1}{m-1} $$

## V. Final Remarks

From an engineering point of view, we have established that L and L*-assignments provide efficient partitioning algorithms for minimizing expected access times, especially for moderately large $m$. From a mathematical point of view, a number of open problems remain. Certainly, one is led to expect that both bounds in Theorems 6 and 7 can be tightened. (Our conjecture at this point is that the least upper bounds are much closer to $1+1/36m$ and $1+1/4m$, respectively, than those given by Theorems 6 and 7.) The bound in Theorem 7 is the cruder of the two, and because of the inherent properties of the problem, it appears the simpler one to work on. In a future paper, we expect to show that examples of the sort on Figure 10,
<figure><img src="image_13.png" /></figure>

$n=2k$

<figure><img src="image_14.png" /></figure>

$$ 
\begin{aligned}
p_1 &= t \\
p_j &= p, \quad i < j \le m = 2k
\end{aligned}
 $$
<figure><img src="image_15.png" /></figure>

p chosen so that $\sum_{i=1}^{n} p_i = 1$

FIGURE 9
where $\eta_m(L^*/O)$ is minimized over $t$ and $z$, provide bounds for $\eta_m(L^*/L)$ and $\eta_m(L^*/O)$ which are extremely close to the best bounds.
<figure><img src="image_16.png" /></figure>

t, z, p chosen so that total probability mass is 1

FIGURE 10
REFERENCES

1. Knuth, D. E. *The Art of Programming, Vol. 3 (Sorting and Searching)*, Addison-Wesley, Reading, Mass. (1973).

2. Coffman, E. G., Jr and P. J. Denning, *Operating Systems Theory*, Prentice-Hall, Englewood Cliffs, N. J. (1973).

3. Karp, R. M., "Reducibility among Combinatorial Problems", *Complexity of Computer Computations*, R. E. Miller and J. W. Thatcher (Eds.), Plenum Press, New York (1972), pp. 85-103.

4. Graham, R. L., "Bounds on Multiprocessing Anomalies and Related Packing Algorithms", *Proc. of Spring Joint Computer Conference* (1972), pp. 205-218.

5. Cody, R., *Record Allocation on Drum-Type Storage Devices*, Ph. D. Thesis, Computer Science Dept., The Pennsylvania State University (1974).

6. Chandra, A. K. and C. K. Wong, "Worst-case Analysis of a Placement Algorithm Related to Storage Allocation", IBM Technical Report RC-4813, Yorktown Heights (1974).