En informática , los algoritmos de memoria externa o 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 recuperar y acceder de manera eficiente a los datos almacenados en la memoria masiva lenta ( 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 .
Los algoritmos de memoria externa se analizan en un modelo idealizado de computación llamado modelo de memoria externa (o modelo de E/S , o modelo de acceso a disco ). El modelo de memoria externa es una máquina abstracta similar al modelo de máquina RAM , pero con una 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 utilizando 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 la cantidad de lecturas y escrituras en la memoria requeridas. [3] El modelo fue introducido por Alok Aggarwal y Jeffrey Vitter en 1988. [4] El modelo de memoria externa está relacionado con el modelo ajeno a la caché , pero los algoritmos en el modelo de memoria externa pueden conocer tanto el tamaño de bloque como el tamaño de caché . Por esta razón, el modelo a veces se conoce como el modelo consciente de la caché . [5]
El modelo consiste en un procesador con una memoria interna o caché de tamaño M , conectada a una memoria externa ilimitada . Tanto la memoria interna como la externa están divididas en bloques de tamaño B . Una operación de entrada/salida o transferencia 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]
Los algoritmos del modelo de memoria externa aprovechan el hecho de que al recuperar un objeto de la memoria externa se recupera un bloque entero de tamaño B. Esta propiedad a veces se denomina localidad.
La búsqueda de un elemento entre N objetos es posible en el modelo de memoria externa utilizando un árbol B con factor de ramificación B. Utilizando un árbol B, la búsqueda, inserción y eliminación se pueden lograr en el tiempo (en notación Big O ). En teoría , este es el tiempo de ejecución mínimo posible para estas operaciones, por lo que el uso de un árbol B es asintóticamente óptimo . [4]
La ordenación externa es la ordenación en una configuración de memoria externa. La ordenación externa se puede realizar mediante la ordenación por distribución, que es similar a la ordenación rápida , o mediante la ordenación por combinación de dos vías . Ambas variantes logran el tiempo de ejecución asintóticamente óptimo de 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 consiste en reorganizar N elementos en una permutación específica . Esto se puede hacer ya sea ordenando, lo que requiere el tiempo de ejecución de ordenación mencionado anteriormente, o insertando cada elemento en orden e ignorando el beneficio de la localidad. De este modo, la permutación se puede realizar a tiempo.
El modelo de memoria externa captura la jerarquía de memoria , que no se modela en otros modelos comunes utilizados para analizar estructuras de datos , como la máquina de acceso aleatorio , y es útil para demostrar límites inferiores para 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 completo de datos 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 clásico de señales digitales . En la computación de propósito general en unidades de procesamiento gráfico (GPGPU), se utilizan tarjetas gráficas (GPU) potentes con poca memoria (en comparación con la memoria del sistema más conocida, a la que se suele denominar simplemente RAM ) con una transferencia de memoria de CPU a GPU relativamente lenta (en comparación con el ancho de banda de cómputo).
Un uso temprano del término "fuera del núcleo" como adjetivo aparece 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 algoritmos aparece en 1971. [7]
{{cite book}}: |journal=ignorado ( ayuda )