límite inferior en la memoria de acceso aleatorio?

Aquí hay una pregunta quizás ingenua que me ha estado hormigueando: ¿Hay un límite inferior asintótico para abordar aleatoriamente una memoria arbitrariamente grande? Mi causa de creencia es que el camino más corto a cualquier memoria almacenada físicamente debe ser a través del espacio tridimensional, y la diagonal aquí debe tener una longitud mínima.$\Omega(\sqrt[3]{n})$

Por ejemplo, al ordenar arbitrariamente muchos elementos, abordar estos elementos eventualmente debe costar algo proporcional a la distancia, e incluso si tiene un cable de alta velocidad entre cada punto en algún espacio, parece que hay un límite geométrico limitado en mayor que .$\Omega(n \lg n)$

¿Qué hay de malo en mi argumento?

Si estás hablando de latencia, sí, eso me parece correcto. Un límite inferior en la distancia implica un límite inferior en la latencia, debido a consideraciones de velocidad de la luz. Sin embargo, en la práctica, estas consideraciones sobre la velocidad de la luz probablemente no dominen hasta que la cantidad de memoria sea extremadamente grande.

Por cierto, la situación es diferente si hablamos de ancho de banda (es decir, el número de operaciones de memoria de acceso aleatorio realizadas por segundo), en lugar de la latencia. Uno puede procesar muchas operaciones de memoria de acceso aleatorio al mismo tiempo, utilizando redes de clasificación.

Una advertencia importante es que parece estar asumiendo una arquitectura en la que tenemos una gran CPU a la izquierda y una gran memoria a la derecha, y de alguna manera están separadas. Sin embargo, esa no es necesariamente la única forma de estructurar un cálculo. También se puede estructurar un cómputo, por ejemplo, como un cómputo paralelo, donde tiene una malla 2-D o 3-D de pequeños procesadores, cada uno con su propia memoria de trabajo local. Ahora acceder a su memoria local puede ser muy rápido, mientras que acceder a la memoria lejana es lento. En cierto sentido, todavía hay un o vinculado operativo, pero el$\sqrt{n}$$\sqrt[3]{n}$$n$ es mucho más pequeño para la memoria local que para la memoria lejana, por lo que si su algoritmo está diseñado de una manera que garantice que la mayoría de las operaciones de memoria se realicen en la memoria local, entonces podrá "superar" el límite inferior que describió (en algunos sentido).

En la arquitectura de la computadora, a menudo se mide el rendimiento de un circuito mediante la medida : en otras palabras, el área del circuito ( ) multiplicada por el tiempo que tarda el circuito en completar un cálculo ( ). Si lo desea, puede pensar en esto como una relación precio / rendimiento: es el precio (que se supone que es proporcional al área del circuito) dividido por el rendimiento (el número de cálculos que se pueden realizar por segundo, es decir, el inverso de$AT$$A$$T$$T$) Una arquitectura estándar con una sola CPU robusta y una gran memoria no siempre es la arquitectura óptima. A veces puede obtener grandes aceleraciones (más que un factor constante) mediante el uso de cómputo paralelo u otras arquitecturas. Esto se debe al menos en parte al problema exacto que mencionó: es mucho más rápido acceder a la memoria que está cerca de usted que acceder a la memoria que está lejos. El almacenamiento en caché (por ejemplo, caché L1, caché L2, etc.) también se basa en el mismo principio.

A continuación se muestra un ejemplo de un artículo en el mundo de la criptografía que considera el diseño de circuitos de propósito especial para tareas criptoanalíticas, y toma en cuenta estos problemas. Por ejemplo, tiene un montón de procesadores, una gran memoria y una red de clasificación entre los dos para enrutar los accesos de memoria de los procesadores a la memoria. Esto permite que una gran cantidad de operaciones de memoria estén "en vuelo" a la vez, aunque no elimine la latencia.

• El costo total de los ataques criptoanalíticos . Michael J. Wiener. Journal of Cryptology, 2004.

Si desea profundizar en esta línea de pensamiento, hay un debate interesante (pero sobre todo teórico) que uno puede tener sobre si la métrica correcta es área o volumen, es decir, si el límite inferior derecho es o . Sí, el mundo es tridimensional, pero la disipación de calor es bidimensional; un cubo masivo de computadoras estaría limitado por su capacidad de disipar el calor, que escala con su área de superficie, no con su volumen. Uno puede seguir adelante en esta línea. Si esto suena como un tema fascinante, vea la P.9 (pp. 45-46) del siguiente documento:$\sqrt{n}$$\sqrt[3]{n}$

• Grietas no uniformes en el hormigón: el poder de la precomputación libre . Daniel J. Bernstein y Tanja Lange. ASIACRYPT 2013.

Vea los límites inferiores relacionados para el cálculo (y la memoria, que puede verse como una forma de cálculo) sensibles a la velocidad de comunicación limitada, los límites inferiores en el tamaño de la unidad y la dimensión espacial fija.

David C. Fisher: Tus algoritmos paralelos favoritos podrían no ser tan rápidos como crees. IEEE Trans. Computadoras 37 (2): 211-213 (1988)

En particular, en la dimensión , obtienes un límite inferior de , por lo que la raíz cúbica aparece para la dimensión dos, apropiada para la mayoría de los chips de semiconductores de hoy. ¡Cuidado con el cubo DRAM de Micron!$d$$\sqrt[d+1]{N}$

El límite asintótico teórico también es si queremos evitar que la computadora se colapse en un agujero negro .$O(\sqrt{n})$

Obviamente, esta restricción se levanta si descubrimos agujeros de gusano, en cuyo caso también podemos ejecutar nuestra computadora en un universo de bolsillo.