Présentation d’algorithmes existant en mémoires externes

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 transfé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.

Présentation d’algorithmes existant en mémoires externes

Notre premier exemple est l’inversion d’une matrice. Celle-ci est largement employée dans les applications scientifiques comme méthode directe pour résoudre les systèmes linéaires. Le calcul de l’inverse d’une matrice A peut être dérivé de sa factorisation dite LU. [61] présente, à cet effet, la factorisation LU par blocs. Pour cet algorithme parallèle de factorisation, la matrice est divisée en blocs de colonnes appelés super-blocs. La taille du super-bloc est déterminée par la quantité de mémoire physique disponible dans la mémoire principale : seuls les blocs du super-bloc courant sont dans cette mémoire centrale, les autres sont conservés sur les disques.

L’algorithme factorise la matrice de gauche à droite, super-bloc par super-bloc. Chaque fois qu’un nouveau super-bloc de la matrice est mis dans la mémoire principale (appelée le superbloc actif), tous les pivotements précédents et les mises à jour d’après un historique de l’algorithme sont appliquées au super-bloc actif. Une fois que le dernier super-bloc est factorisé, la matrice est relue pour appliquer le pivotement restant sur les précédents super-blocs. Notons que le calcul est fait «data in place», c’est-à-dire sans aucun échange des données de la matrice mais par des échanges des pivotements effectués. La matrice a donc tout d’abord été distribuée sur les processeurs.

Pour un bon équilibrage des charges, une distribution cyclique des données est employée. L’article [66] présente des algorithmes PRAM utilisant une mémoire externe centralisée pour des problèmes sur les graphes tels que le calcul des composants bi-connexes. L’un d’eux est le problème des 4 couleurs d’un graphe appliqué au problème dit du list ranking : déterminer pour chaque nœud v d’une liste, le rang de ce nœud défini par le nombre de liens depuis v jusqu’à la fin de la liste. La méthode utilisée pour résoudre un tel problème est de mettre à jour des groupes de nœuds de la liste (en recolorisant les nœuds du groupe) sans avoir à trier ou parcourir la liste entière. Comme avant, l’algorithme travaille groupe par groupe, avec seulement un groupe dans la mémoire centrale.