Algoritmo de memoria externa

En informática , los algoritmos de memoria externa o algoritmos fuera de memoria principal son algoritmos diseñados para procesar datos 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 memoria de gran capacidad 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 de computación idealizado 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 leer bloques largos contiguos es más rápido que leer aleatoriamente usando 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 en 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 del bloque como el tamaño de la caché . Por esta razón, el modelo a veces se denomina modelo consciente de la caché . ^{[ 5 ]}

El modelo consta de 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 completo 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, se puede lograr la búsqueda, inserción y eliminación en${\displaystyle O(\log _{B}N)}$tiempo (en notación Big O ). Desde el punto de vista de la teoría de la información , 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 ordenación externa es la ordenación en un entorno de memoria externa. La ordenación externa se puede realizar mediante ordenación por distribución, que es similar a quicksort , o mediante una${\displaystyle {\tfrac {M}{B}}}$ordenación por fusión de vías . Ambas variantes logran el tiempo de ejecución asintóticamente óptimo de${\displaystyle O\left({\frac {N}{B}}\log _{\frac {M}{B}}{\frac {N}{B}}\right)}$para 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 permutación consiste en reorganizar N elementos en una permutación específica . Esto se puede hacer mediante ordenación, 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. Por lo tanto, la permutación se puede realizar en${\displaystyle O\left(\min \left(N,{\frac {N}{B}}\log _{\frac {M}{B}}{\frac {N}{B}}\right)\right)}$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 resulta útil para demostrar límites inferiores para estructuras de datos. El modelo también es útil para analizar algoritmos que trabajan con 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 e incluye también 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, que a menudo se denomina simplemente RAM ) con una transferencia de memoria entre la CPU y la GPU relativamente lenta (en comparación con el ancho de banda de computación).

Un uso temprano del término "fuera de la memoria principal" como adjetivo se encuentra en 1962 en referencia a dispositivos que son distintos de la memoria principal de un IBM 360. [ ^{6 ] Un} uso temprano del término "fuera de la memoria principal" con respecto a algoritmos aparece en 1971. ^{[ 7 ]}

• Algoritmo que ignora la caché
• Recorrido de grafos de memoria externa
• Algoritmo en línea
• Memoria externa paralela
• Algoritmo de transmisión

• SVD y QR fuera del núcleo
• Gráficos fuera de núcleo
• Diseño de Scalapack