La complexité de la densité de l'espace et séquentialité

Question

Je cherche une terminologie standard, des mesures et / ou des applications de la prise en compte de la densité et séquentialité des algorithmes.

Quand on mesure les algorithmes que nous avons tendance à donner le grand-Oh notation tel que O $ (n) $ et généralement nous mesurons la complexité du temps. Un peu moins souvent, mais encore souvent, nous allons également mesurer la complexité de l'espace d'un algorithme.

Compte tenu des systèmes informatiques actuels mais la densité de la mémoire et l'ordre dans lequel il est accédé joue un rôle majeur dans l'exécution pratique de l'algorithme. En effet, il existe des scénarios où la complexité du temps algortihme de $ O (\ log n) $ avec Disperse accès mémoire aléatoire peut être plus lent qu'un O $ (n) $ algorithme avec accès séquentiel à la mémoire dense. Je ne l'ai pas vu ces aspects abordés dans la théorie formelle avant; il doit sûrement exister et je suis simplement ignorants ici.

Quelles sont les mesures standard, les termes et les approches de cette densité de l'espace et l'accès séquentialité?

Answer 1

Il y a quelques modèles qui prennent en compte le nombre de transferts de mémoire un algorithme de marques. L'un des plus réussis est le ceux modèle cache-idéal introduit par et al frigo, algorithmes Cache-inconscient, 1999 . Il est basé sur le modèle de mémoire externe introduite par Aggarwal et Vitter, entrée / complexité de sortie du tri et des problèmes, 1988. cache oublieux des structures de données dans le Manuel des structures de données et des applications . Si vous préférez des vidéos, Demaine couvre toutes les bases et peut-être encore plus sur le MIT introduction aux conférences algorithmes .

Le modèle ne nécessite aucune connaissance du nombre de niveaux dans la hiérarchie de mémoire. De plus, il n'y a pas de paramètres tels que la longueur cache en ligne ou cache taille à configurer. Une propriété est que si un algorithme fonctionne de manière optimale dans le modèle de cache idéal, il fonctionne de manière optimale sur tout k $ $ hiérarchie mémoire -level. De plus, les algorithmes qui ne fonctionnent de manière optimale dans le modèle sont appelés cache-inconscient. Ils offrent les avantages de la simplicité, la robustesse et la portabilité sur les algorithmes de cache-courant, dont l'utilisation des ressources doit être gérée de façon explicite.

Le modèle cache idéal comporte deux mesures de complexité. La première est la complexité du travail, qui est le temps de fonctionnement classique d'un algorithme dans le modèle de RAM. La seconde vient du modèle de mémoire externe, qui est le nombre de transferts de mémoire. Le modèle cache idéal modifie cependant le modèle de mémoire externe de plusieurs façons. Il a une stratégie de remplacement de bloc optimale, le remplacement automatique et complète associativité. Toutes ces hypothèses sont justifiées par une collection de réduction par et al Frigo.

structures algorithmes et données sont ensuite analysées dans le modèle. Par exemple, considérez la recherche binaire classique. Les fils d'exécution à une répétition

$$ T (N) = T (N / 2) + O (1). $$

En regardant l'arbre de récursivité, chaque niveau attribue un $ \ log N $ facteur qui donne la solution de $ \ theta (\ log N) $. Lors de l'analyse des algorithmes dans le modèle de RAM, nous supposons souvent le cas de base de $ T (1) = O (1) $ pour nos récurrences. Cependant, dans le modèle de cache-idéal, nous laissons souvent la fracture de l'algorithme le problème tout le chemin, mais considérons le point où le problème soit compatible avec la cache ou FITS dans O $ (B) $ nombre de blocs de mémoire. En fait ici, nous pouvons nous pouvons améliorer notre analyse en utilisant une plus forte cas de base de $ T (O (B)) = O (1) $. Avec cela, la recherche binaire classique $ encourt \ Theta (\ log N - \ log B) $ les transferts de mémoire. Qui plus est, la recherche binaire classique est pas dans le modèle optimal du cache-idéal. Il existe des moyens plus intelligents nécessaires pour atteindre le $ optimal \ Theta (\ log_B N) $ lié.

Je suppose que le succès du modèle provient du fait qu'il est facile et amusant de travailler avec, et cela fonctionne aussi dans la pratique, ce qui signifie qu'il a été assez efficace pour prédire les coûts d'un algorithme sur des systèmes réels. Il y a beaucoup d'algorithmes de cache-inconscients et des structures de données. Par exemple, nous avons des algorithmes de cache-inconscients pour de nombreux problèmes en géométrie algorithmique, la numérisation des ensembles dynamiques, bio-informatique, calculs pochoir, algèbre linéaire, la construction de tableau de suffixe et pour certains problèmes de graphes fondamentaux en utilisant les files d'attente prioritaires cache oublieux. Les principales techniques qui sont efficaces o sont à balayage linéairef mémoire et diviser pour régner.

Dans la pratique, la conclusion générale a été telle que les algorithmes de cache-inconscients des algorithmes de RAM souvent surperformer. Cependant, les algorithmes de cache-aware sont généralement encore plus rapide, car ils sont à l'écoute pour une taille de problème spécifique et de la hiérarchie de la mémoire. Pour un bel exemple voir Ladner et al., Une comparaison de cache Aware et cache Inconscient statique Recherche arbres utilisation du programme Instrumentation 2002 .