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

ARCHIVES

Allocation optimale
et quasi optimale
de la mémoire centrale
dans le tri
par fusion sur disque

Laurent Francin
L. Hyafil F.Prusker, J.Vuillemin

Rapport de Recherche n° 85

Novembre 1974
ALLOCATION OPTIMALE ET QUASI OPTIMALE DE LA MÉMOIRE CENTRALE
DANS LE TRI PAR FUSION SUR DISQUE

L. HYAFIL, F. PRUSKER, J. VUILLEMIN

Résumé :

Il existe une façon optimale d'allouer la mémoire centrale dans le tri par fusion sur disque. Nous étudions ici une méthode d'allocation plus simple que nous montrons être asymptotiquement optimale.

Abstract :

There exists an optimal strategy for allocating core memory in a disk merge process. In this paper, we study a simpler strategy which we prove to be asymptotically optimal.
# 1. INTRODUCTION

Dans [1], Ferguson a montré la façon optimale d'allouer la mémoire centrale au cours d'un tri par fusion sur périphérique à accès direct (disque, tambour, feuillets magnétiques,...). Utilisant cette stratégie d'allocation, Knuth [2] a décrit un algorithme permettant le calcul des schémas optimaux de fusion. Le temps de calcul de cet algorithme croissant de façon exponentielle avec le nombre initial de monotonies à fusionner, il est inutilisable dans la plupart des cas pratiques.

Le but de ce papier est de démontrer que l'emploi d'une méthode simplifiée d'allocation de mémoire (suggérée par Knuth [2]) conduit à des schémas de fusion quasi optimaux, dont nous montrons par ailleurs ([3]) qu'ils sont facilement calculables.

# 2. PRESENTATION DU PROBLEME

Pour trier un gros fichier en utilisant un périphérique à accès direct, on procède généralement de la manière suivante : dans une première phase, on génère, par un tri en mémoire centrale, une suite de monotonies (ou séquences) initiales sur le périphérique externe. Dans la phase suivante, on fusionne ces monotonies de façon répétitive, jusqu'à obtenir le fichier trié résultant. Un schéma de fusion est un arbre décrivant l'ordre dans lequel les monotonies initiales doivent être fusionnées.
Par exemple, si les séquences initiales sont $s_1, s_2, s_3$ et $s_4$,

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

décrivent quelques schémas de fusions possibles, parmi d'autres.

Si nous utilisons le premier schéma, nous aurons d'abord à fusionner $s_2, s_3$ et $s_4$ en une seule monotonie de taille égale à la somme des tailles de $s_2, s_3$ et $s_4$. Nous fusionnerons ensuite la monotonie obtenue avec $s_1$.

Le temps d'exécution (ou coût) d'un schéma est donc la somme des coûts de chacune des fusions élémentaires représentées par les noeuds de l'arbre. Nous nous proposons de comparer les coûts des meilleurs arbres correspondants à deux stratégies d'allocation de mémoire pour les fusions élémentaires, l'une optimale et l'autre moins rapide, mais plus simple à implémenter.

Nous nous bornerons au cas où les séquences initiales sont de tailles égales ; dans la pratique, ce sera approximativement vérifié avec toutes les méthodes connues de tri si les clés du fichier initial sont distribuées de façon aléatoire.

Une fusion élémentaire consiste à interclasser d monotonies $r_1, r_2, ..., r_d$ de tailles respectives $n_1, n_2, ..., n_d$ de façon à créer une monotonie $r_o$ de taille $n_o = \sum_{1 \le i \le d} n_i$. Supposons que l'on dispose d'une mémoire centrale de taille M pour réaliser cette fusion élémentaire. On peut diviser cette mémoire en $d+1$ tampons de tailles respectives $b_0, b_1, ..., b_d$ avec évidemment $\sum_{0 \le i \le d} b_i = M$. Les tampons de taille $b_1, ..., b_d$ seront utilisés comme tampons d'entrée et celui de taille $b_0$ comme tampon de sortie. Le processus est initialisé en remplissant chaque tampon d'entrée $b_i$ ($1 \le i \le d$) avec des enregistrements provenant de la i-ème monotonie. Les d sous-monotonies ainsi obtenues sont fusionnées, créant ainsi une nouvelle monotonie dans le tampon de sortie $b_o$. Lorsque l'un des tampons d'entrée est vide on le remplit depuis le périphérique ; lorsque le tampon de sortie est plein on le vide, et l'on continue ainsi jusqu'à épuisement des monotonies initiales.
Dans le calcul du temps pris par une fusion élémentaire, nous ne tiendrons compte que du temps d'occupation du périphérique, c'est-à-dire le temps d'accès et le temps de transfert. On pourrait faire entrer en ligne de compte d'autres facteurs, comme le temps de tri en mémoire centrale, mais cela ne modifierait pas la structure du modèle. Le temps de transfert est égal à $2T_T \cdot n_o$, réparti pour moitié entre le temps de lecture et le temps d'écriture, où $T_T$ est le temps de transfert unitaire dépendant du périphérique. D'autre part, comme il y a $n_i/b_i$ accès par tampon, le temps d'accès total sera $T_A \cdot \sum_{o \le i \le d} (n_i/b_i)$, où $T_A$ est le temps d'accès du périphérique. Le coût $F$ de la fusion est donc :

$$F = T_A \cdot \sum_{o \le i \le d} (n_i/b_i) + 2T_T \cdot n_o \quad (1)$$

### 3. ALLOCATION OPTIMALE DE LA MEMOIRE

La formule (1) conduit à un modèle, que nous appellerons Modèle 1 dans la suite, qui a été étudié par Ferguson [1]. Ce dernier a montré que la façon optimale d'allouer les tampons pour minimiser $F$ était de choisir :

$$b_i = M \cdot \frac{\sqrt{n_i}}{\sum_{o \le i \le d} \sqrt{n_i}} \quad (2)$$

D'après (1) et (2), le coût d'une fusion est donc :

$$F = \alpha [\sqrt{n_o} + \sum_{1 \le i \le d} \sqrt{n_i}]^2 + \beta \cdot n_o \quad (3)$$

$$\text{avec} \quad \alpha = \frac{T_A}{M} \quad \beta = 2T_T \quad (4)$$

Dans la suite, nous supposerons $\alpha > 0$. (Si $\alpha = 0$, le problème est trivial). Appelons $C_1(n)$ le coût d'un arbre optimal de tri-fusion de n monotonies initiales de tailles égales. Pour simplifier les notations, la longueur des monotonies initiales sera normalisée à l'unité de longueur, si bien que n désignera indifféremment le nombre de monotonies initiales ou la longueur de la monotonie résultante.

Calculons $C_1(n)$. L'arborescence représentant le schéma optimal de la fusion est de la forme :

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

où $T_1, \dots, T_d$ sont les sous-arbres du sommet. Le coût de cet arborescence est la somme du coût de la fusion finale et du coût de chacun des sous-arbres
$$C_1(n) = \alpha[\sqrt{n} + \sum_{1 \le i \le d} \sqrt{n_i}]^2 + \beta n + \sum_{1 \le i \le d} C_i$$

où $n_i$ est la taille de la monotonie résultante du schéma $T_i$ et $C_i$ est le coût de $T_i$. On voit facilement que les $T_i$ sont aussi des arbres optimaux et donc que $C_i = C_1(n_i)$. On en déduit que $C_1(n)$ est donné par :

$$\begin{cases} C_1(1) = 0 \\ C_1(n) = \min_{2 \le d \le n} \left\{ \min_{\sum_{1 \le i \le d} n_i = n} \left[ \alpha(\sqrt{n} + \sum_{1 \le i \le d} \sqrt{n_i})^2 + \beta n + \sum_{1 \le i \le d} C_1(n_i) \right] \right\} \end{cases} \quad (5)$$

Malheureusement, tous les algorithmes de calcul connus de $C_1(n)$ et des arbres optimaux correspondants prennent un temps exponentiel en $n$ (notons qu'il est facile de construire l'arbre optimal tout en calculant son coût, si bien que les deux problèmes se confondent). C'est pourquoi, Knuth [2] a proposé une méthode plus simple d'allouer les tampons, méthode que nous décrivons maintenant.

### 4. ALLOCATION SIMPLIFIÉE DE LA MEMOIRE

Intuitivement, si nous commençons le tri-fusion avec des séquences initiales de tailles égales, on peut penser que l'on aura jamais à fusionner des monotonies de tailles très différentes. Pour des raisons pratiques, il peut donc être intéressant d'allouer des tampons d'entrée de tailles égales, en optimisant seulement sur la taille du tampon de sortie. Avec cette nouvelle allocation de mémoire, la taille des tampons devient

$$b_o = \frac{M \sqrt{d}}{d + \sqrt{d}} \quad \text{et} \quad b_i = \frac{M}{d + \sqrt{d}} \quad \text{pour } 1 \le i \le d.$$

De la même manière que pour le Modèle 1, nous en déduisons l'expression de $C_2(n)$, coût de l'arbre optimal correspondant à ce nouveau modèle :

$$\begin{cases} C_2(1) = 0 \\ C_2(n) = \min_{2 \le d \le n} \left\{ \min_{\sum_{1 \le i \le d} n_i = n} \left[ \alpha(\sqrt{1+\sqrt{d}})^2 + \beta \right] \cdot n + \sum_{1 \le i \le d} C_2(n_i) \right\} \end{cases} \quad (6)$$

Ce nouveau modèle sera appelé Modèle 2, il a été étudié dans [2], [3], [4] et [5].

A l'aide de techniques de programmation dynamique, $C_2(n)$ peut être calculé en temps $O(n^2)$ et place mémoire $O(n)$. En étudiant les propriétés des arbres optimaux, nous avons réduit dans [3] le temps de calcul à
O(log n) et la place mémoire nécessaire à une constante. Il est donc
tentant de choisir ce modèle pour construire des arbres de tri-fusion.
Mais ce choix ne peut se justifier que si les arbres obtenus ne sont pas
trop mauvais par rapport à ceux du Modèle 1 ! En d'autres termes, nous
savons que $C_2(n) \ge C_1(n)$, mais nous ignorons si $C_1(n)$ et $C_2(n)$ sont
du même ordre de grandeur.

Une comparaison expérimentale jusqu'à n = 50 montre que $C_2$ et $C_1$
diffèrent au plus de 4 %. Il est impossible de pousser plus loin la
comparaison, les temps de calcul de $C_1(n)$ devenant vite prohibitifs.
En fait $C_1(n)$ et $C_2(n)$ sont toujours du même ordre de grandeur et sont
égaux asymptotiquement. C'est ce que montre le théorème suivant.

## 5. THEOREME.

Pour une configuration hardware donnée (c'est-à-dire pour $\alpha$ et $\beta$
donnés par (4)), il existe deux constantes $k$ et $K$, dépendant uniquement
de $\alpha$ et $\beta$, telles que

$$ \underline{k.n.log n} \le \underline{C_1(n)} \le \underline{C_2(n)} \le k.n.log n + \underline{K.n} \quad (7) $$

De plus l'égalité $\underline{C_1(n)} = \underline{C_2(n)} = k.n.log n$ est vérifiée infiniment souvent.

### Preuve:

Il est clair, d'après la définition de $C_1$ et $C_2$, que $C_1(n) \le C_2(n)$. D'autre part, nous avons montré dans [5], en utilisant des arbres particuliers, que $C_2(n) \le k.n.log n + K.n$ où $K$ dépend de $\alpha$ et $\beta$, et que $k$ est donné par :

$$ k = \min_{d \ge 2} \left[ \frac{\alpha(1+\sqrt{d})^2 + \beta}{\log d} \right] \quad (8) $$

Pour terminer la démonstration de (7), il reste donc à prouver que :

$$ C_1(n) \ge k.n.log n \quad (9) $$
La preuve se fait par récurrence sur n.

Le cas n = 1 est trivial. Supposons donc que l'inégalité (9) soit vérifiée pour m < n et montrons la pour n ; d'après (5), nous savons que

$$
C_1(n) = \alpha(\sqrt{n} + \sum_{1 \le i \le d} \sqrt{n_i})^2 + \beta.n + \sum_{1 \le i \le d} C_1(n_i)
$$

pour certains d, n₁, ..., nd vérifiant Σ nᵢ = n. Par récurrence,
1≤i≤d

$$
C_1(n) \geq \alpha(\sqrt{n} + \sum_{1 \le i \le d} \sqrt{n_i})^2 + \beta n + \sum_{1 \le i \le d} k \cdot n_i \cdot \log n_i
$$

Pour prouver (9), il suffit donc de montrer que pour tous les d, n₁, ..., nd
vérifiant Σ nᵢ = n, l'inégalité suivante est vérifiée

$$
\alpha \left( \sqrt{n} + \sum_{1 \le i \le d} \sqrt{n_i} \right)^2 + \beta n + \sum_{1 \le i \le d} k n_i \log n_i \ge k n \log n
$$

Posons $x_i = n_i/n$ et $k = k(\alpha,\beta)$ ; cette dernière inégalité devient

$$
\alpha \left( 1 + \sum_{1 \le i \le d} \sqrt{x_i} \right)^2 + \beta + \sum_{1 \le i \le d} k(\alpha, \beta) \cdot x_i \cdot \log x_i \ge 0 \quad (10)
$$

Il s'agit de montrer (10) quand $\alpha > 0$, $\beta \ge 0$, $x_i \ge 0$, $\sum_{1 \le i \le d} x_i = 1$.

En fait, on peut se restreindre au cas $\alpha = 1$ et $\beta = 0$. En effet,
il est évident que

$$
\min_{d \ge 2} \frac{\alpha(1 + \sqrt{d})^2}{\log d} + \beta \ge \alpha \cdot \min_{d \ge 2} \frac{(1 + \sqrt{d})^2}{\log d}
$$

ce qui s'écrit $k(\alpha,\beta) \ge \alpha.k(1,0)$. Le premier membre de l'inégalité (10)
est donc minoré par

$$
\alpha \left[ \left( 1 + \sum_{1 \le i \le d} \sqrt{x_i} \right)^2 + \sum_{1 \le i \le d} k(1,0) \cdot x_i \cdot \log x_i \right] .
$$

La preuve sera donc terminée si nous montrons que la fonction F

$$
F(x_1, \dots, x_d) = \left(1 + \sum_{1 \le i \le d} \sqrt{x_i}\right)^2 + \sum_{1 \le i \le d} k(1,0) \cdot x_i \cdot \log x_i \quad (11)
$$

est positive ou nulle sur le domaine D défini par xᵢ ≥ 0 et Σ xᵢ = 1.
Dans la suite, nous écrirons k pour k(1,0).
## Etude de la fonction F

La fonction F est une "bonne" fonction sur D : elle est continue et indéfiniment dérivable. Mais F est la somme d'une fonction concave $(1 + \sum \sqrt{x_i})^2$ et d'une fonction convexe $(\sum k x_i \log x_i)$, si bien que pour montrer qu'elle est positive ou nulle il nous faut étudier le signe de ses minimums sur D. Considérons d'abord les minimums de F à l'intérieur de D (c'est-à-dire quand $x_i > 0$).

### Minimums de F à l'intérieur de D.

Soit $X = (x_1, \dots, x_d)$ un extremum. Comme $\sum_{1 \le i \le d} x_i = 1$, les dérivées partielles $\frac{\partial F}{\partial x_i}(X)$ doivent toutes être égales, ce qui s'écrit :

$$k. \log x_1 + \frac{A}{\sqrt{x_1}} = \dots = k. \log x_d + \frac{A}{\sqrt{x_d}}$$

où $A = 1 + \sum_{1 \le i \le d} \sqrt{x_i}$. Comme la fonction $k \log x + \frac{A}{\sqrt{x}}$ ne possède qu'un seul minimum pour $x = \frac{A}{4k^2}$, les coordonnées $x_i$ de X peuvent ou bien être égales, ou bien prendre seulement deux valeurs $x_1$ et $x_2$ vérifiant :

$$x_1 < \frac{A^2}{4k^2} < x_2.$$

Dans le premier cas, les $x_i$ valant $1/d$, la fonction F s'écrit :

$$F(X) = (1 + \sqrt{d})^2 - k \log d$$

et la définition de $k$ pour $\alpha = 1$ et $\beta = 0$ nous montre que $F(X)$ est positive ou nulle, quelle que soit la nature de l'extremum X.

Dans le second cas, quand les $x_i$ ont deux valeurs possibles $x_1$ et $x_2$, nous allons étudier la fonction F dans un voisinage de X pour connaître la nature de l'extremum X. Il est bien connu que

$$F(X + U) - F(X) = t_U \frac{\delta^2 F}{\delta X^2}(X) . U + O(||U||^2) \quad (15)$$

où $\frac{\delta^2 F}{\delta X^2}(X)$ est la matrice dérivée seconde de F au point X, et $U = (u_1, \dots, u_d)$ est un vecteur vérifiant $\sum_{1 \le i \le d} u_i = 0$, puisque $X + U$ doit être dans le domaine D. La formule (15) nous montre que X n'est pas un minimum s'il existe un vecteur U qui rende la forme quadratique $\Phi(U) = t_U \frac{\delta^2 F}{\delta X^2}(X) . U$
négative. La fonction F étant symétrique par rapport aux $x_i$, nous pouvons supposer que les $\lambda$ premières coordonnées de X sont égales à $x_1$, et les $\mu$ suivantes ($\mu = d - \lambda$) égales à $x_2$. Un calcul simple montre que cette forme quadratique s'écrit :

$$ \Phi(U) = \Phi_1(u_1, \dots, u_\lambda) + \Phi_2(u_{\lambda+1}, \dots, u_d) $$

avec

$$ \begin{cases} \Phi_1(u_1, \dots, u_\lambda) = a \cdot \sum_{1 \le i \le \lambda} u_i^2 + b \cdot \left( \sum_{1 \le i \le \lambda} u_i \right)^2 \\ \Phi_2(u_{\lambda+1}, \dots, u_d) = c \cdot \sum_{\lambda+1 \le i \le d} u_i^2 + e \cdot \left( \sum_{\lambda+1 \le i \le d} u_i \right)^2 \end{cases} $$

où a, b, c, d sont définis par :

$$ a = \frac{1}{x_1} \left( k - \frac{A}{2\sqrt{x_1}} \right), \quad b = \frac{1}{2\sqrt{x_1}} \left( \frac{1}{\sqrt{x_1}} - \frac{1}{\sqrt{x_2}} \right), \quad c = \frac{1}{x_2} \left( k - \frac{A}{2\sqrt{x_2}} \right), \quad e = \frac{1}{2\sqrt{x_2}} \left( \frac{1}{\sqrt{x_2}} - \frac{1}{\sqrt{x_1}} \right) $$

De (13), on déduit que $a < 0$, $b > 0$, $c > 0$ et $e > 0$.

Si $\lambda \ge 2$, on rend $\Phi(U)$ négative en prenant $V = (u, -u, 0, \dots, 0)$. En effet, on a dans ce cas $\Phi(U) = \Phi_1(U) = 2u^2a$, et la preuve est terminée.

Cette méthode ne s'applique pas si $\lambda= 1$, ce qui correspond au minimum possible $X = (x_1, x_2, \dots, x_2)$. Comme $x_1 + \mu x_2 = 1$, on obtient, en posant $x_1 = x$ :

$$ F(x) = f_{\mu}(x) = \left(1 + \sqrt{x} + \sqrt{\mu} \sqrt{1-x}\right)^2 + k \times \log x + k(1-x) \log \frac{1-x}{\mu} $$

Il s'agit d'étudier $f_\mu(x)$ quant $\mu$ est un entier positif sur l'intervalle $I = [0, \frac{1}{\mu+1}]$, car nous avons supposé $x_1 < x_2$. On voit facilement que la fonction $(1 + \sqrt{x} + \sqrt{\mu}\sqrt{1-x})^2$ est croissante sur $I$ alors que la fonction $k \times \log x + k(1-x) \log \frac{1-x}{\mu}$ est décroissante. On en déduit :

$$ f_{\mu}(x) \ge (1 + \sqrt{\mu})^2 - k \log (1 + \mu) \quad (16) $$

Le second membre de (16) étant positif quand $\mu \ge 8$, il suffit donc d'étudier $f_\mu$ quand $1 \le \mu \le 7$. Une étude technique "ad hoc" effectuée avec l'aide de l'ordinateur montre que $f_\mu(x)$ est positif ou nul.

Minimum de F sur tout le domaine D.

A ce point de l'exposé, nous avons établi que F est positive ou nulle à l'intérieur du domaine D. Mais le minimum X de F peut être sur les bords de D. Dans ce cas, appelons $Y = (y_1, \dots, y_d)$ le point formé avec les d' coordonnées non nulles de X. Appelons aussi $F_d$ la fonction F
appliquée au domaine $D$ de dimension $d$ et $F_d$, la fonction $F$ appliquée au domaine $D'$ de dimension $d'$. Le point $Y$ ayant toutes ses coordonnées non nulles, se trouve donc à l'intérieur de $D'$. D'après l'étude précédente, nous en déduisons que $F_d, (Y) \ge 0$. Comme $F_d(X) = F_d(Y)$ par définition de $F$, nous avons bien $F_d(X) \ge 0$, ce qui termine la démonstration de l'inégalité (7).

## Validité de la borne inférieure

Montrons maintenant que $k \in \mathbb{N}$ et $\log n$ est une bonne fonction minorante, en ce sens qu'elle est atteinte infiniment souvent. Soit $\delta > 0$ l'entier défini par :

$$k = \min_{d \ge 2} \frac{\alpha(1 + \sqrt{d})^2 + \beta}{\log d} = \frac{\alpha(1 + \sqrt{\delta})^2 + \beta}{\log \delta} \quad (17)$$

Pour $n = \delta^p$, le coût de l'arbre de fusion $\delta$-parfait dans le Modèle 2 (l'arbre $\delta$-parfait est l'arbre dont les noeuds ont degré $\delta$ et dont toutes les feuilles sont au même niveau) est égal à :

$$[\alpha(1 + \sqrt{d})^2 + \beta]. \delta^p . p$$

et on voit facilement d'après (17), que ce terme est précisément $k \in \mathbb{N} \log n$. Finalement, pour $n = \delta^p$ l'arbre $\delta$-parfait sera optimal dans le Modèle 1 et le Modèle 2, et son coût vérifie

$$C_2(n) = C_1(n) = k \in \mathbb{N} \log n \quad \square$$

## 6. CONCLUSION

Finalement, le Modèle 2 conduit à des schémas de fusion pratiquement équivalents à ceux du Modèle 1 et donc quasi-optimaux. On aura donc toujours intérêt à choisir le Modèle 2 qui calcule les schémas de fusion en temps $O(\log n)$ et non en temps exponentiel comme le Modèle 1.

Nous pensons que cette étude est révélatrice d'un phénomène courant en informatique : soit un programme dont on veut optimiser un certain nombre de paramètres. Supposons que l'on connaisse un algorithme permettant d'optimiser ce choix de paramètres. Cet algorithme n'est utile que dans la mesure où le temps que fait gagner l'optimisation du programme n'est pas reperdu par le temps pris par l'algorithme d'optimisation lui-même !
Ce cas est courant, par exemple pour des problèmes liés à l'optimisation du code généré par un compilateur, et nous pensons qu'il y a souvent intérêt, comme c'est le cas ici, à rechercher une solution quasi-optimale dont l'algorithme de calcul est efficace.

## REFERENCES.

[1] D.E. Ferguson. "Buffer allocation in merge sorting"
Communication de l'ACM 14,7. Juillet 71, 476-478.

[2] D.E. Knuth. "The art of computer programming" vol 3, Addison Wesley. 1973, 361-378.

[3] L. Hyafil, F. Prusker, J. Vuillemin. "An efficient algorithm for computing optimal disk merge patterns"
Proc. of sixth annual ACM Symposium on Theory of Computing. Avril 74, 216-229.

[4] M. Schlumberger, J. Vuillemin. "Optimal disk merge patterns".
Acta Informatica 3, 25-35 (1973).

[5] L. Hyafil, F. Prusker, J. Vuillemin. "Design of optimal merge on direct access devices". Proc. IFIP Cong. 1974, 979-982.

## REMERCIEMENTS

Nous remercions Alain BAMBERGER pour les conseils qu'il nous a donnés dans la démonstration du théorème.