limite inferior na memória de acesso aleatório?

Aqui está uma pergunta talvez ingênua que me formigou: Existe algum $\Omega(\sqrt[3]{n})$limite inferior assintótico para endereçar memória arbitrariamente grande aleatoriamente? Minha causa de crença é que o caminho mais curto para qualquer memória armazenada fisicamente deve ser através do espaço tridimensional, e a diagonal aqui deve ter um comprimento mínimo.

Por exemplo, ao classificar arbitrariamente muitos elementos, o endereçamento desses elementos deve eventualmente custar algo proporcional à distância, e mesmo se você tiver um cabo de alta velocidade entre todos os pontos de um determinado espaço, parece que existe um limite geométrico limitado em mais alto que $\Omega(n \lg n)$.

O que há de errado com meu argumento?

Se você está falando sobre latência, sim, isso parece certo para mim. Um limite inferior na distância implica um limite inferior na latência, devido a considerações de velocidade da luz. No entanto, na prática, essas considerações sobre velocidade da luz provavelmente não dominam até que a quantidade de memória seja extremamente grande.

A propósito, a situação é diferente se estamos falando de largura de banda (ou seja, o número de operações de memória de acesso aleatório executadas por segundo), em vez de latência. Pode-se processar muitas operações de memória de acesso aleatório simultaneamente, usando redes de classificação.

Uma ressalva importante é que você parece estar assumindo uma arquitetura em que temos uma grande CPU à esquerda e uma grande memória à direita, e elas são separadas de alguma forma. No entanto, essa não é necessariamente a única maneira de estruturar uma computação. Também é possível estruturar uma computação, por exemplo, como uma computação paralela, na qual você tem uma malha 2D ou 3D de pequenos processadores, cada um com sua própria memória de trabalho local. Agora, o acesso à memória local pode ser muito rápido, enquanto o acesso à memória remota é lento. Em certo sentido, ainda existe um$\sqrt{n}$ ou $\sqrt[3]{n}$ ligado operacional, mas o $n$ é muito menor para a memória local do que para a memória remota, portanto, se o seu algoritmo for projetado de maneira a garantir que a maioria das operações de memória seja para a memória local, você poderá "vencer" o limite inferior que você descreveu (em alguns sentido).

Na arquitetura de computadores, geralmente se mede o desempenho de um circuito pelo $AT$ medida: em outras palavras, a área do circuito ($A$) multiplicado pelo tempo que leva para o circuito concluir um cálculo ($T$) Se desejar, você pode pensar nisso como uma relação preço / desempenho: é o preço (que é considerado proporcional à área do circuito) dividido pelo desempenho (o número de cálculos que podem ser executados por segundo, ou seja, o inverso de$T$) Uma arquitetura padrão com uma única CPU robusta e uma grande memória nem sempre é a arquitetura ideal. Às vezes, você pode obter grandes acelerações (mais que um fator constante) usando computação paralela ou outras arquiteturas. Isso se deve, pelo menos em parte, exatamente ao problema mencionado: é muito mais rápido acessar a memória que está perto de você do que acessar a memória que está longe. O armazenamento em cache (por exemplo, cache L1, cache L2 etc.) também é baseado no mesmo princípio.

Abaixo está um exemplo de artigo no mundo da criptografia que considera o design de circuitos para fins especiais para tarefas criptoanalíticas e leva esses problemas em consideração. Por exemplo, ele possui vários processadores, uma grande memória e uma rede de classificação entre os dois para rotear os acessos de memória dos processadores para a memória. Isso permite que um alto número de operações de memória esteja "em vôo" de uma vez, mesmo que não elimine a latência.

• O custo total dos ataques criptoanalíticos . Michael J. Wiener. Jornal de Criptologia, 2004.

Se você deseja aprofundar-se nessa linha de pensamento, existe um debate interessante (mas principalmente teórico) sobre se a métrica certa é área ou volume, ou seja, se o limite inferior direito é $\sqrt{n}$ ou $\sqrt[3]{n}$. Sim, o mundo é tridimensional, mas a dissipação de calor é bidimensional; um enorme cubo de computadores seria limitado por sua capacidade de dissipar o calor, que escala com sua área de superfície, não com seu volume. Pode-se continuar em frente nesse sentido. Se isso soa como um tópico fascinante, consulte Q.9 (pp.45-46) do seguinte artigo:

• Rachaduras não uniformes no concreto: o poder da pré-computação livre . Daniel J. Bernstein e Tanja Lange. ASIACRYPT 2013.

Consulte os limites inferiores relacionados para computação (e memória, que pode ser vista como uma forma de cálculo) sensíveis à velocidade de comunicação limitada, limites inferiores no tamanho da unidade e dimensão espacial fixa.

David C. Fisher: Seus algoritmos paralelos favoritos podem não ser tão rápidos quanto você pensa. IEEE Trans. Computers 37 (2): 211-213 (1988)

Em particular, na dimensão $d$, você obtém um limite inferior de $\sqrt[d+1]{N}$, então a raiz cúbica aparece na dimensão dois - apropriada para a maioria dos chips semicondutores atualmente. Cuidado com o cubo DRAM da Micron!

O limite assintótico teórico também é $O(\sqrt{n})$se queremos evitar que o computador entre em colapso em um buraco negro .

Obviamente, essa restrição será levantada se descobrirmos buracos de minhoca; nesse caso, também podemos rodar nosso computador em um universo de bolso.