borne inférieure de la mémoire à accès aléatoire?

Voici une question peut-être naïve qui me pique: y a-t-il un $\Omega(\sqrt[3]{n})$limite inférieure asymptotique pour l'adressage aléatoire d'une mémoire arbitrairement grande? Ma cause de croyance est que le chemin le plus court vers une mémoire stockée physiquement doit être à travers un espace tridimensionnel, et la diagonale ici doit avoir une longueur minimale.

Par exemple, lors du tri arbitraire de nombreux éléments, l'adressage de ces éléments doit finalement coûter quelque chose de proportionnel à la distance, et même si vous avez un câble à grande vitesse entre chaque point dans un espace, il semble qu'il existe une limite géométrique limitée à plus haut que $\Omega(n \lg n)$.

Quel est le problème avec mon argument?

Si vous parlez de latence, oui, cela me semble juste. Une borne inférieure sur la distance implique une borne inférieure sur la latence, en raison de considérations de vitesse de la lumière. Cependant, dans la pratique, ces considérations de vitesse de la lumière ne dominent probablement pas tant que la quantité de mémoire n'est pas extrêmement importante.

Soit dit en passant, la situation est différente si nous parlons de bande passante (c'est-à-dire le nombre d'opérations de mémoire vive effectuées par seconde), plutôt que de latence. On peut traiter simultanément plusieurs opérations de mémoire à accès aléatoire, en utilisant des réseaux de tri.

Une mise en garde importante est que vous semblez supposer une architecture où nous avons un gros processeur à gauche et une grande mémoire à droite, et ils sont séparés d'une manière ou d'une autre. Cependant, ce n'est pas nécessairement la seule façon de structurer un calcul. On peut également structurer un calcul, par exemple, comme un calcul parallèle, où vous avez un maillage 2-D ou 3-D de petits processeurs chacun avec leur propre mémoire de travail locale. L'accès à votre mémoire locale peut désormais être très rapide, tandis que l'accès à une mémoire éloignée est lent. Dans un certain sens, il reste$\sqrt{n}$ ou $\sqrt[3]{n}$ lié d'exploitation, mais le $n$ est beaucoup plus petit pour la mémoire locale que pour la mémoire lointaine, donc si votre algorithme est conçu de manière à garantir que la plupart des opérations de mémoire se font sur la mémoire locale, alors vous pourrez peut-être "battre" la limite inférieure que vous avez décrite (dans certains sens).

En architecture informatique, on mesure souvent les performances d'un circuit par le $AT$ mesure: en d'autres termes, l'aire du circuit ($A$) multiplié par le temps nécessaire au circuit pour effectuer un calcul ($T$). Si vous le souhaitez, vous pouvez considérer cela comme un rapport prix / performances: c'est le prix (qui est supposé être proportionnel à la surface du circuit) divisé par la performance (le nombre de calculs pouvant être effectués par en second lieu, à savoir, l'inverse de$T$). Une architecture standard avec un seul processeur costaud et une grande mémoire n'est pas toujours l'architecture optimale. Parfois, vous pouvez obtenir de grandes accélérations (plus qu'un facteur constant) en utilisant le calcul parallèle ou d'autres architectures. Cela est dû au moins en partie au problème que vous avez mentionné: il est beaucoup plus rapide d'accéder à la mémoire la plus proche que d'accéder à la mémoire la plus éloignée. La mise en cache (par exemple, cache L1, cache L2, etc.) est également basée sur le même principe.

Ci-dessous est un exemple d'un article dans le monde de la cryptographie qui considère la conception de circuits à usage spécial pour des tâches cryptanalytiques et prend en compte ces problèmes. Par exemple, il a un tas de processeurs, une grande mémoire et un réseau de tri entre les deux pour acheminer les accès mémoire des processeurs à la mémoire. Cela permet à un grand nombre d'opérations de mémoire d'être "en vol" à la fois, même si cela n'élimine pas la latence.

• Le coût total des attaques cryptanalytiques . Michael J. Wiener. Journal of Cryptology, 2004.

Si vous voulez approfondir cette réflexion, il existe un débat intéressant (mais surtout théorique) sur la question de savoir si la bonne mesure est l'aire ou le volume, c'est-à-dire si la borne inférieure droite est $\sqrt{n}$ ou $\sqrt[3]{n}$. Oui, le monde est en trois dimensions, mais la dissipation thermique est en deux dimensions; un cube massif d'ordinateurs serait limité par sa capacité à dissiper la chaleur, qui évolue avec sa surface et non son volume. On peut continuer dans cette veine. Si cela ressemble à un sujet fascinant, voir Q.9 (pp.45-46) de l'article suivant:

• Fissures non uniformes dans le béton: la puissance du pré-calcul libre . Daniel J. Bernstein et Tanja Lange. ASIACRYPT 2013.

Voir les limites inférieures associées pour le calcul (et la mémoire, qui peut être considérée comme une forme de calcul) sensible à la vitesse de communication limitée, aux limites inférieures de la taille de l'unité et à la dimension spatiale fixe.

David C. Fisher: Vos algorithmes parallèles préférés pourraient ne pas être aussi rapides que vous le pensez. IEEE Trans. Ordinateurs 37 (2): 211-213 (1988)

En particulier, en dimension $d$, vous obtenez une limite inférieure de $\sqrt[d+1]{N}$, donc la racine cubique apparaît pour la dimension deux - appropriée pour la plupart des puces semi-conductrices aujourd'hui. Attention au cube DRAM de Micron!

La borne asymptotique théorique est également $O(\sqrt{n})$si nous voulons éviter que l' ordinateur ne s'effondre dans un trou noir .

Évidemment, cette restriction est levée si nous découvrons des trous de ver, auquel cas nous pouvons également faire fonctionner notre ordinateur dans un univers de poche.