En informática , los algoritmos de memoria externa o los algoritmos fuera del núcleo son algoritmos que están diseñados para procesar datos que son demasiado grandes para caber en la memoria principal de una computadora a la vez. Dichos algoritmos deben optimizarse para obtener y acceder de manera eficiente a los datos almacenados en la memoria de volumen lento ( memoria auxiliar ) como discos duros o unidades de cinta , o cuando la memoria está en una red informática . [1] [2] Los algoritmos de memoria externa se analizan en el modelo de memoria externa .
Modelo
Los algoritmos de memoria externa se analizan en un modelo de cálculo idealizado llamado modelo de memoria externa (o modelo de E / S , o modelo de acceso al disco ). El modelo de memoria externa es una máquina abstracta similar al modelo de máquina RAM , pero con un caché además de la memoria principal . El modelo captura el hecho de que las operaciones de lectura y escritura son mucho más rápidas en una caché que en la memoria principal , y que la lectura de bloques contiguos largos es más rápida que la lectura aleatoria con un cabezal de lectura y escritura de disco . El tiempo de ejecución de un algoritmo en el modelo de memoria externa se define por el número de lecturas y escrituras necesarias en la memoria. [3] El modelo fue introducido por Alok Aggarwal y Jeffrey Vitter en 1988. [4] El modelo de memoria externa está relacionado con el modelo de memoria caché inconsciente , pero los algoritmos en el modelo de memoria externa pueden conocer tanto el tamaño del bloque como el tamaño de la memoria caché . Por esta razón, el modelo a veces se denomina modelo con memoria caché . [5]
El modelo consta de un procesador con una memoria interna o caché de tamaño M , conectado a una memoria externa ilimitada . Tanto la memoria interna y externa se divide en bloques de tamaño B . Una operación de transferencia de entrada / salida o de memoria consiste en mover un bloque de B elementos contiguos de la memoria externa a la interna, y el tiempo de ejecución de un algoritmo está determinado por el número de estas operaciones de entrada / salida. [4]
Algoritmos
Los algoritmos en el modelo de memoria externa aprovechan el hecho de que al recuperar un objeto de la memoria externa se recupera un bloque completo de tamaño . Esta propiedad a veces se denomina localidad.
Buscando un elemento entre objetos es posible en el modelo de memoria externa usando un árbol B con factor de ramificación. Usando un árbol B, la búsqueda, inserción y eliminación se pueden lograr entiempo (en notación Big O ). Información teóricamente , este es el tiempo de ejecución mínimo posible para estas operaciones, por lo que usar un árbol B es asintóticamente óptimo . [4]
La clasificación externa es la clasificación en una configuración de memoria externa. La clasificación externa se puede realizar a través de la clasificación de distribución, que es similar a la clasificación rápida , o mediante un-clasificación de combinación de formas . Ambas variantes logran el tiempo de ejecución asintóticamente óptimo depara ordenar N objetos. Este límite también se aplica a la transformada rápida de Fourier en el modelo de memoria externa. [2]
El problema de la permutación es reorganizar elementos en una permutación específica . Esto se puede hacer ordenando, que requiere el tiempo de ejecución de ordenación anterior, o insertando cada elemento en orden e ignorando el beneficio de la localidad. Por lo tanto, la permutación se puede hacer en hora.
Aplicaciones
El modelo de memoria externa captura la jerarquía de la memoria , que no se modela en otros modelos comunes utilizados en el análisis de estructuras de datos , como la máquina de acceso aleatorio , y es útil para probar los límites inferiores de las estructuras de datos. El modelo también es útil para analizar algoritmos que funcionan en conjuntos de datos demasiado grandes para caber en la memoria interna. [4]
Un ejemplo típico son los sistemas de información geográfica , especialmente los modelos digitales de elevación , donde el conjunto de datos completo supera fácilmente varios gigabytes o incluso terabytes de datos.
Esta metodología se extiende más allá de las CPU de propósito general y también incluye la computación GPU , así como el procesamiento de señales digitales clásico . En la computación de propósito general en unidades de procesamiento de gráficos (GPGPU), las tarjetas gráficas potentes (GPU) con poca memoria (en comparación con la memoria del sistema más familiar, que a menudo se conoce simplemente como RAM ) se utilizan con una CPU a una velocidad relativamente lenta. Transferencia de memoria GPU (en comparación con el ancho de banda de cálculo).
Historia
Un uso temprano del término "out-of-core" como adjetivo es en 1962 en referencia a dispositivos que no son la memoria central de un IBM 360 . [6] Un uso temprano del término "fuera del núcleo" con respecto a los algoritmos aparece en 1971. [7]
Ver también
- Clasificación externa
- Algoritmo en línea
- Algoritmo de transmisión
- Algoritmo ajeno a la caché
- Memoria externa paralela
- Recorrido del gráfico de memoria externa
Referencias
- ^ Vitter, JS (2001). "Algoritmos de memoria externa y estructuras de datos: lidiar con DATOS MASIVOS". Encuestas de computación ACM . 33 (2): 209–271. CiteSeerX 10.1.1.42.7064 . doi : 10.1145 / 384192.384193 .
- ^ a b Vitter, JS (2008). Algoritmos y estructuras de datos para memoria externa (PDF) . Fundamentos y Tendencias en Informática Teórica . Serie sobre Fundamentos y Tendencias en Informática Teórica. 2 . Hanover, MA: Now Publishers. págs. 305–474. CiteSeerX 10.1.1.140.3731 . doi : 10.1561 / 0400000014 . ISBN 978-1-60198-106-6.
- ^ Zhang, Donghui; Tsotras, Vassilis J .; Levialdi, Stefano; Grinstein, Georges; Berry, Damon Andrew; Gouet-Brunet, Valerie; Kosch, Harald; Döller, Mario; Döller, Mario; Kosch, Harald; Maier, Paul; Bhattacharya, Arnab; Ljosa, Vebjorn; Nack, Frank; Bartolini, Ilaria; Gouet-Brunet, Valerie; Mei, Tao; Rui, Yong; Crucianu, Michel; Shih, Frank Y .; Fan, Wenfei; Ullman-Cullere, Mollie; Clark, Eugene; Aronson, Samuel; Mellin, Jonas; Berndtsson, Mikael; Grahne, Gösta; Bertossi, Leopoldo; Dong, Guozhu; et al. (2009). "Modelo de Computación I / O". Enciclopedia de sistemas de bases de datos . Springer Science + Business Media . págs. 1333-1334. doi : 10.1007 / 978-0-387-39940-9_752 . ISBN 978-0-387-35544-3.
- ^ a b c d Aggarwal, Alok; Vitter, Jeffrey (1988). "La complejidad de entrada / salida de la clasificación y problemas relacionados" . Comunicaciones de la ACM . 31 (9): 1116–1127. doi : 10.1145 / 48529.48535 .
- ^ Demaine, Erik (2002). Estructuras de datos y algoritmos ajenos a la caché (PDF) . Notas de la conferencia de la EEF Summer School sobre conjuntos de datos masivos. Aarhus: BRICS.
- ^ NASA SP . NASA. 1962. p. 276.
- ^ Computadoras en crisis . ACM. 1971. p. 296.
enlaces externos
- Fuera de Core SVD y QR
- Gráficos sin núcleo
- Diseño Scalapack