Modelo de Memoria Externa

Los discos magnéticos están divididos en pistas (anillos concéntricos) y sectores (limitados por dos radios de círculo consecutivos). La intersección de una pista y un sector es un bloque o página. Un bloque típicamente almacena unos pocos KBs. Sin embargo, algunos discos tienen varios platos que giran simultáneamente, y la unión del mismo bloque en todos los platos se trata como un único bloque, esta vez de unas decenas de KBs.

El disco magnético escribe a través de un cabezal, que es un dispositivo mecánico que se debe mover a la pista correcta. Esta operación se llama "seek", y toma unas decenas de milisegundos. Luego debe esperar a que el sector pase girando por debajo del cabezal. Este es el "tiempo de latencia", que suma unos pocos milisegundos más. Finalmente, se lee el bloque completo, a una velocidad de unos pocos MBs por segundo. Si se leen bloques contiguos de esa pista, ya no se vuelve a pagar el tiempo de seek ni latencia. Incluso, si se leen bloques de pistas contiguas, sólo se paga un tiempo mínimo adicional.

Esto significa que acceder a un elemento en una posición aleatoria cuesta milisegundos, mientras que acceder al elemento al lado de uno leído cuesta microsegundos. Los algoritmos que trabajan en disco son mucho más rápidos si realizan pocos accesos aleatorios y muchos secuenciales. Dado que la RAM accede a los datos en nanosegundos, los accesos aleatorios a disco son un millón de veces más lento que en memoria principal, y los secuenciales son mil veces más lentos.

En el caso de los SSDs, no existen los componentes mecánicos, por lo que da lo mismo acceder al bloque contiguo que a uno aleatorio. Pero sigue siendo cierto que se leen bloques completos y que su lectura es bastante costosa, unas decenas de microsegundos (diez mil veces más lentos que la RAM).

El modelo de memoria externa que usaremos abstrae de estas dos arquitecturas, las más populares. La memoria externa está formada por bloques de tamaño $B$. Se leen y escriben bloques completos. La lectura o escritura son tan caras que despreciamos las operaciones del algoritmo en CPU y RAM. Simplemente contamos el número de I/Os, es decir, lecturas y escrituras de bloques. La diferencia entre leer bloques consecutivos o aleatorios no se considera en el modelo. El algoritmo tiene una memoria RAM de tamaño $M$, que medida en bloques es de tamaño $m = \frac{M}{B}$. El input es de tamaño $N$, y se presenta en disco en forma contigua, ocupando $n = \frac{N}{B}$ bloques.

Por ejemplo, el costo de un algoritmo que lee secuencialmente un arreglo es $O(n)$. En cambio, uno que lea el arreglo accediendo a sus elementos en un orden aleatorio es $O(N)$, miles de veces mayor en la práctica. En general, lo peor que puede pasar con un algoritmo que se ejecuta en RAM en tiempo $T(N)$ es que al pasarlo a memoria externa también requiera $T(N)$ I/Os, pues éstos son millones de veces más lentos que la operación en RAM. Pero con un diseño adecuado, se puede hacer bastante mejor en muchos casos relevantes.

Veremos estructuras de memoria secundaria para buscar elementos en conjuntos ordenados (árboles de búsqueda) y sin orden (hashing), para colas de prioridad, y algoritmos de ordenamiento.