Qu'est-ce qui motive le modèle RAM?
Il semble que la plupart des analyses d'algorithmes d'aujourd'hui soient effectuées dans des modèles avec un accès aléatoire à temps constant, comme le modèle de mot RAM. Je ne connais pas grand-chose à la physique, mais de sources populaires, j'ai entendu dire qu'il y avait une limite au stockage d'informations par volume et à la vitesse de déplacement des informations, de sorte que les RAM ne semblent pas être physiquement réalisables. Les ordinateurs modernes ont tous ces niveaux de cache, ce qui, je dirais, ne les rend pas très semblables à de la RAM. Alors, pourquoi les algorithmes théoriques devraient-ils être définis dans la RAM?
Réponses
Permettez-moi de donner une vision différente de celle de vonbrand. Tout ce que vous avez dit est vrai: le modèle de RAM n'est pas réaliste pour un certain nombre de raisons, et s'il est possible d'en défendre différents aspects, une telle défense n'entre pas vraiment dans le vif du sujet.
Le cœur du problème - et la réponse à votre question - est que le modèle de RAM est la meilleure chose que nous ayons. Comparé à d'autres modèles acceptés, il modélise plus précisément le calcul réel. En particulier, la raison pour laquelle nous avons adopté le modèle de RAM était principalement une réponse aux machines de Turing, car nous avons constaté que l'utilisation de machines de Turing conduit à des problèmes artificiellement difficiles à résoudre en termes de complexité temporelle. Le modèle RAM résout clairement ce problème flagrant, et il a donc été accepté, même s'il reste loin d'être parfait.
Un exemple classique qui illustre le problème flagrant avec les machines de Turing est le problème de l'égalité des chaînes: donnée d'entrée
$$ w_1 \# w_2$$
où $w_1, w_2$ sont des séquences binaires et $\#$ est un séparateur, déterminant si $w_1 = w_2$. On peut montrer que toute machine de Turing pour le problème d'égalité prend$O(n^2)$temps. C'est inconfortable, car les machines de Turing sont ce que tout le monde considère comme le modèle universel de calcul - pourtant aucun ingénieur logiciel ou chercheur en algorithmes ne pense que l'égalité des chaînes prend vraiment$O(n^2)$temps. Alors qu'est-ce qui donne? L'égalité des chaînes doit être linéaire, nous inventons donc un nouveau modèle là où elle se trouve, et la meilleure solution disponible à l'heure actuelle est celle des machines Word RAM.
Peut-être qu'un jour dans le futur, nous proposerons un meilleur modèle - un modèle simple, conceptuellement clair et améliorant la RAM dans sa capacité à modéliser la complexité informatique réelle. Pour l'instant, nous ne pouvons nous contenter que du meilleur de ce que nous avons.
Dans une première approximation grossière, vous pouvez prendre le temps d'accéder à un mot en mémoire comme constant, indépendamment des accès précédents. Ie, le modèle de RAM.
Vous avez raison, les machines d'aujourd'hui ne ressemblent pas à de la RAM, il est payant (même généreusement) d'organiser l'accès aux données de manière aussi séquentielle que possible ou d'extraire le dernier bit d'information d'un (court!) Segment de mémoire avant de manipuler le suivant. Mais vous avez rarement la marge de manœuvre pour le faire, vos accès mémoire sont essentiellement aléatoires et le modèle n'est pas si loin de la vérité. De plus, les machines d'aujourd'hui ont beaucoup plus d'un processeur, le modèle n'en a qu'un. Et puis il y a le traitement vectoriel (faire la même opération sur un vecteur de données, pas un par un) comme le font les "instructions multimédias" (et encore plus en utilisant des cartes graphiques pour le traitement).
Un peu de discussion est donnée par exemple par la recherche binaire de Khoung est un cas pathologique pour les caches . Comme vous le voyez, analyser même des algorithmes simples et bien compris sous des modèles de temps d'accès à la mémoire plus réalistes est décourageant.
Le modèle RAM est motivé par une analyse asymptotique d'algorithmes conçus comme des calculs en mémoire à un seul thread.
Optimiser les performances pour des jeux d'instructions spécifiques, des caches et autres, c'est une chose. L'autre chose est d'être préparé à la croissance de la taille du problème. Pour estimer à quel point votre algorithme en mémoire évolue, vous voudrez probablement ignorer les petits facteurs et vous concentrer sur les grands$\mathcal{O}$notation. Gros$\mathcal{O}$ ne va pas tout optimiser pour vous, mais au moins cela peut vous dire que votre solution évolue bien (ou que vous devriez essayer quelque chose de différent).
La RAM suppose un petit jeu d'instructions fixe, où chaque opération fonctionne $\mathcal{O}(1)$. Notez que c'est un bon modèle si nous ne nous soucions que de la croissance asymptotique:
Le jeu d'instructions d'un processeur moderne n'est pas petit, mais nous pouvons prétendre qu'il l'est réellement. Ces op-codes supplémentaires ne font pas de différence dans le grand$\mathcal{O}$ notation.
Les CPU peuvent avoir des instructions dont l'exécution dépend de l'entrée. Encore une fois, nous pouvons les ignorer, car nous pouvons les modéliser en utilisant des instructions plus simples sans affecter les gros$\mathcal{O}$complexité. Il en va de même pour les niveaux de cache: leurs performances sont toujours limitées par une petite constante, donc travailler en$\mathcal{O}(1)$ par définition.
Oui, vous ne pouvez pas accéder à la mémoire en temps constant si elle ne cesse de croître. Heureusement, cela n'est jamais nécessaire grâce au bon sens. Personne n'indexe l'intégralité d'Internet dans la mémoire non persistante d'une machine solitaire à un seul thread.