Algoritmo de memória externa

Na computação, os algoritmos de memória externa ou algoritmos fora do núcleo são algoritmos projetados para processar dados que são grandes demais para caber na memória principal de um computador de uma só vez. Esses algoritmos devem ser otimizados para buscar e acessar com eficiência os dados armazenados em memória lenta (memória auxiliar), como discos rígidos ou unidades de fita, ou quando a memória está em uma rede de computadores. Os algoritmos de memória externa são analisados no modelo de memória externa.

Modelo

O cache à esquerda contém ${\tfrac {M}{B}}$ blocos de tamanho $B$ cada, totalizando M objetos. A memória externa à direita é ilimitada

Os algoritmos de memória externa são analisados em um modelo idealizado de computação chamado modelo de memória externa (ou modelo de E/S ou modelo de acesso ao disco). O modelo de memória externa é uma máquina abstrata semelhante ao modelo de máquina RAM, mas com um cache além da memória principal. O modelo captura o fato de que as operações de leitura e gravação são muito mais rápidas em um cache do que na memória principal e que a leitura de blocos contíguos longos é mais rápida do que a leitura aleatória usando um cabeçote de leitura e gravação de disco. O tempo de execução de um algoritmo no modelo de memória externa é definido pelo número de leituras e gravações necessárias na memória. O modelo foi introduzido por Alok Aggarwal e Jeffrey Vitter em 1988. O modelo de memória externa está relacionado ao modelo de esquecimento de cache, mas no modelo de memória externa os algoritmos podem saber tanto o tamanho do bloco quanto o tamanho do cache. Por esse motivo, o modelo às vezes é chamado de modelo com reconhecimento de cache.

O modelo consiste em um processador com cache ou memória interna de tamanho M, conectado a uma memória externa ilimitada. Tanto a memória interna quanto a externa são divididas em blocos de tamanho B. Uma operação de entrada/saída ou transferência de memória consiste em mover um bloco de B elementos contíguos da memória externa para a interna, e o que determina o tempo de execução de um algoritmo é o número dessas operações de entrada/saída.

Algoritmos

No modelo de memória externa os algoritmos tiram proveito do fato de que ao recuperar um objeto da memória externa obtém-se um bloco inteiro de tamanho $B$. Essa propriedade às vezes é chamada de localidade.

A procura por um elemento entre $N$ objetos é possível no modelo de memória externa usando uma árvore B com fator de ramificação $B$. Usando uma árvore B, pode-se realizar a busca, inserção e exclusão em $O(\log _{B}N)$ tempo (na notação Big O). Em termos da teoria da informação, esse é o tempo mínimo de execução possível para essas operações, portanto, usar uma árvore B é assintoticamente ideal.

A ordenação externa é a ordenação em uma configuração de memória externa. A ordenação externa pode ser feita por meio de ordenação por distribuição, que é semelhante ao quicksort, ou por meio de um ordenação por intercalação de ${\tfrac {M}{B}}$ vias. Ambas as variantes atingem o tempo de execução assintoticamente ótimo de $O({\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}})$ para ordenar N objetos. Esse limite também se aplica à transformada rápida de Fourier no modelo de memória externa.

O problema de permutação é reorganizar $N$ elementos em uma permutação específica. Isso pode ser feito tanto por classificação, que requer o tempo de execução de classificação acima, quanto inserindo cada elemento em ordem e ignorando o benefício da localidade. Assim, a permutação pode ser feita em um tempo $O(\min(N,{\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}}))$.

Aplicações

O modelo de memória externa captura a hierarquia de memória, que não é modelada em outros modelos comuns usados na análise de estruturas de dados, como a máquina de acesso aleatório, e é útil para provar limites inferiores para estruturas de dados. O modelo também é útil para analisar algoritmos que trabalham em conjuntos de dados muito grandes para caber na memória interna.

Um exemplo típico são os sistemas de informações geográficas, especialmente os modelos digitais de elevação, onde o conjunto completo de dados facilmente excede vários gigabytes ou mesmo terabytes de dados.

Essa metodologia se estende além das CPUs de uso geral e também inclui a computação em GPU, bem como o processamento de sinal digital clássico. Na computação de uso geral em unidades de processamento gráfico (GPGPU), placas gráficas poderosas (GPUs) com pouca memória (em comparação com a memória de sistema mais usual, que é mais frequentemente chamada simplesmente de RAM) são utilizadas com uma transferência relativamente lenta de CPU para GPU (quando comparada com a largura de banda de computação).

História

Um dos primeiros usos do termo "out-of-core" como adjetivo foi em 1962, em referência a dispositivos que não são a memória central de um IBM 360. Um dos primeiros usos do termo "out-of-core" em relação a algoritmos ocorreu em 1971.

Ligações externas

• SVD e QR fora do núcleo
• Computação gráfica fora do núcleo
• Projeto Scalapack