MÉMOIRES EXTERNES EN BSML

Introduction

Pour remédier aux problème des grandes quantités de données à traiter, une première solution pour augmenter la capacité de mémoire disponible est d’employer le mécanisme de mémoire virtuelle des systèmes d’exploitation modernes. Ce mécanisme de pagination a été établi comme une méthode standard pour contrôler et fournir, via les mémoires externes, une plus grande capacité de mémoire qui est nécessaire aux applications.

Son principal avantage est de permettre aux applications de disposer d’un grand espace de mémoire virtuelle, sans avoir à tenir compte de la gestion de ces disques. Malheureusement, cette solution est inefficace pour la pratique du calcul scientifique et ce quel que soit le système de pagination utilisé [60]. Les algorithmes et les structures de données existants sont souvent mal adaptés aux applications out-of-core. Pour obtenir de meilleurs temps d’exécution, ce genre d’application doit alors être restructuré avec des algorithmes comportant explicitement des entrées/sorties sur les données 

Mémoires externes

Modèle EM-BSP

Les ordinateurs modernes comportent typiquement plusieurs niveaux de mémoire tels que la mémoire principale (appelé couramment mémoire vive ou RAM), les caches (ou tampons) systèmes du processeur et des périphériques ainsi que la mémoire externe sous la forme de disques durs. Ce grand nombre de niveaux rend la modélisation complète d’un ordinateur bien trop compliquée et de tels modèles auraient l’inconvénient de ne pas pouvoir être portables.

Nous nous limitons donc à un modèle à deux niveaux (mémoire principale et mémoires externes), tel qu’il est décrit dans [269], car la différence de rapidité d’accès entre les disques et la mémoire principale est bien plus significative qu’avec les autres niveaux. Sur ce principe, [93] a étendu le modèle BSP pour inclure des mémoires externes locales (appelées aussi mémoires secondaires dans un modèle à deux niveaux). La figure 9.1 illustre cette idée. Chaque processeur de la machine BSP, a, en plus de sa mémoire principale, une mémoire externe (EM) sous la forme d’un ensemble de disques. Cette idée étend le modèle BSP en sa version avec mémoire externe, appelée EM-BSP, avec les paramètres suivants : 

M est la taille en octets de la mémoire principale en chaque processeur, 2. D est le nombre de disques en chaque processeur, 3. B est la taille en octets d’un bloc de transfert en chaque disque, 4. G est le ratio de capacité de calcul local (nombre d’opérations de calculs locaux) divisé par la capacité locale d’entrées/sorties (nombre de blocs de taille B pouvant être tranférés entre les disques et la mémoire principale) par unité de temps. Dans de nombreuses machines parallèles, tous les ordinateurs composant la machine BSP ont bien le même nombre de disques.

Ce modèle, dans l’esprit d’uniformité du modèle BSP, se restreint à ce cas. Notons aussi que le modèle interdit différentes tailles de mémoires principales. Chaque disque est noté par D0, D1, . . . , DD−1 et est constitué d’une séquence de plages (tracks en anglais). Chacune de ces plages est en accès direct et contient exactement un bloc de B octets. Chaque processeur peut utiliser, de manière concurrente, tous ces D disques et ainsi transférer depuis ou vers la mémoire principale D × B octets en une seule opération d’entrée/sortie.

Cette opération aura alors un coût constant G. Dans une telle opération, seule une plage par disque est accessible. Il n’est pas spécifié quelle est la plage utilisée en chaque disque. Notons qu’une opération impliquant moins de disques n’entraîne pas l’utilisation d’une autre constante que G : toute opération d’écriture ou de lecture sur les disques se fera en un temps constant G. Notons aussi que chaque ordinateur composant la machine BSP est capable de contenir plusieurs blocs provenant des disques, c’est-à-dire M ≫ DB