Algorithme de mémoire externe - External memory algorithm

En informatique , les algorithmes de mémoire externe ou les algorithmes hors cœur sont des algorithmes conçus pour traiter des données trop volumineuses pour tenir dans la mémoire principale d' un ordinateur à la fois. Ces algorithmes doivent être optimisés pour extraire et accéder efficacement aux données stockées dans une mémoire de masse lente (mémoire auxiliaire ) comme des disques durs ou des lecteurs de bande , ou lorsque la mémoire se trouve sur un réseau informatique . Les algorithmes de mémoire externe sont analysés dans le modèle de mémoire externe .

Modèle

Le cache de gauche contient des blocs de taille chacun, pour un total de M objets. La mémoire externe à droite est illimitée. ${\ displaystyle {\ tfrac {M} {B}}}$${\ displaystyle B}$

Les algorithmes de mémoire externe sont analysés dans un modèle de calcul idéalisé appelé modèle de mémoire externe (ou modèle d'E / S , ou modèle d'accès au disque ). Le modèle de mémoire externe est une machine abstraite similaire au modèle de machine RAM , mais avec un cache en plus de la mémoire principale . Le modèle capture le fait que les opérations de lecture et d'écriture sont beaucoup plus rapides dans un cache que dans la mémoire principale , et que la lecture de longs blocs contigus est plus rapide que la lecture aléatoire à l'aide d'une tête de lecture et d'écriture de disque . La durée d'exécution d'un algorithme dans le modèle de mémoire externe est définie par le nombre de lectures et d'écritures dans la mémoire requise. Le modèle a été introduit par Alok Aggarwal et Jeffrey Vitter en 1988. Le modèle de mémoire externe est lié au modèle sans mémoire cache , mais les algorithmes du modèle de mémoire externe peuvent connaître à la fois la taille du bloc et la taille du cache . Pour cette raison, le modèle est parfois appelé modèle prenant en charge le cache .

Le modèle se compose d'un processeur avec une mémoire interne ou un cache de taille M , connecté à une mémoire externe illimitée . Tant la mémoire interne et externe sont divisés en blocs de taille B . Une opération d'entrée / sortie ou de transfert de mémoire consiste à déplacer un bloc de B éléments contigus de la mémoire externe vers la mémoire interne, et le temps d'exécution d'un algorithme est déterminé par le nombre de ces opérations d'entrée / sortie.

Algorithmes

Les algorithmes du modèle de mémoire externe tirent parti du fait que la récupération d'un objet à partir de la mémoire externe récupère un bloc entier de taille . Cette propriété est parfois appelée localité. ${\ displaystyle B}$

La recherche d'un élément parmi les objets est possible dans le modèle de mémoire externe à l'aide d'un arbre B avec facteur de branchement . En utilisant un arbre B, la recherche, l'insertion et la suppression peuvent être réalisées dans le temps (en notation Big O ). Information Théoriquement , il s'agit du temps de fonctionnement minimum possible pour ces opérations, donc l'utilisation d'un arbre B est asymptotiquement optimale . ${\ displaystyle N}$${\ displaystyle B}$${\ displaystyle O (\ log _ {B} N)}$

Le tri externe est un tri dans un paramètre de mémoire externe. Le tri externe peut être effectué via le tri de distribution, qui est similaire au tri rapide , ou via un tri par fusion -way . Les deux variantes réalisent le runtime asymptotiquement optimal pour trier N objets. Cette limite s'applique également à la transformée de Fourier rapide dans le modèle de mémoire externe. ${\ displaystyle {\ tfrac {M} {B}}}$${\ displaystyle O ({\ tfrac {N} {B}} \ log _ {\ tfrac {M} {B}} {\ tfrac {N} {B}})}$

Le problème de permutation est de réorganiser les éléments en une permutation spécifique . Cela peut être fait soit par tri, ce qui nécessite le runtime de tri ci-dessus, soit en insérant chaque élément dans l'ordre et en ignorant l'avantage de la localité. Ainsi, la permutation peut se faire dans le temps. ${\ displaystyle N}$${\ displaystyle O (\ min (N, {\ tfrac {N} {B}} \ log _ {\ tfrac {M} {B}} {\ tfrac {N} {B}}))}$

Applications

Le modèle de mémoire externe capture la hiérarchie de la mémoire , qui n'est pas modélisée dans d'autres modèles courants utilisés dans l'analyse des structures de données , telles que la machine à accès aléatoire , et est utile pour prouver les limites inférieures des structures de données. Le modèle est également utile pour analyser les algorithmes qui fonctionnent sur des ensembles de données trop volumineux pour tenir dans la mémoire interne.

Un exemple typique est les systèmes d'information géographique , en particulier les modèles d'élévation numériques , où l'ensemble de données complet dépasse facilement plusieurs gigaoctets, voire téraoctets de données.

Cette méthodologie va au-delà des processeurs à usage général et comprend également le calcul GPU ainsi que le traitement du signal numérique classique . Dans le calcul général sur des unités de traitement graphique (GPGPU), de puissantes cartes graphiques (GPU) avec peu de mémoire (par rapport à la mémoire système plus familière, qui est le plus souvent appelée simplement RAM ) sont utilisées avec un processeur relativement lent. Transfert de mémoire GPU (par rapport à la bande passante de calcul).

Histoire

Une première utilisation du terme "out-of-core" comme adjectif est en 1962 en référence à des périphériques qui sont autres que la mémoire centrale d'un IBM 360 . Une première utilisation du terme «out-of-core» en ce qui concerne les algorithmes apparaît en 1971.

Voir également

• Tri externe
• Algorithme en ligne
• Algorithme de streaming
• Algorithme inconscient du cache
• Mémoire externe parallèle
• Traversée du graphe de la mémoire externe

Les références

Liens externes

• Hors SVD et QR de base
• Plus de graphiques de base
• Conception Scalapack