Algoritmo para cubrir rangos de memoria?

Question

Tengo un conjunto de rangos como {(2-8), (13-22), (380-7931), (40032-63278)}. En aras de la simplicidad, podemos suponer que no se superponen (los rangos de solapamiento ya se han fusionado).

Mi objetivo es "cubrir" estos rangos utilizando combinaciones de un conjunto dado de "longitudes" como {4, 64, 1024, 16384}. Estoy obligado a usar como máximo N longitudes, como N = 32. No me importa cuántas "longitudes" utilizo siempre que esté por debajo de mi máximo, pero quiero minimizar el área total "extra": números "cubiertos" por longitudes que no están en el conjunto inicial de rangos.

El ejemplo {(2-8)} cubierto por (2-66) (se utiliza una longitud de 64) tiene 58 números "adicionales". {(2-8)} cubierto por {(2-6), (6-10)} (dos longitudes de 4) tiene solo 2 números "adicionales" y es preferible.

Mi aplicación en el mundo real implica la preprogramación de un MMU TLB fijo para garantizar que solo ciertos rangos de direcciones de memoria sean accesibles (por lo tanto TLB no representa un acceso prohibido &). Me gustaría cubrir los rangos lo más estrictamente posible para detectar las violaciones más temprano que tarde, pero solo tengo 32 ranuras para trabajar y 4 tamaños de página fijos. Puedo sintonizar mi código a mano con un nivel de rendimiento adecuado, pero tengo curiosidad por saber si hay una solución más elegante/de propósito general para el problema. Parece estar relacionado con el problema de la mochila, pero lo suficientemente diferente que ha sido difícil de buscar.

Answer 1

Esto se puede formular como la variación de Shortest path problem.

necesitamos cubrir un conjunto de rangos de longitud total M con al más Npáginas. Las páginas pueden tener L diferentes longitudes, no están alineadas (pueden colocarse en cualquier dirección).La diferencia entre el área total "extra" y la longitud total de páginas es igual a la constante M, que permite minimizar la longitud total de páginas.

Construyamos un gráfico relacionado con este problema. Cada dirección de memoria en cualquier rango tiene el vértice correspondiente en el gráfico. Cada vértice tiene L bordes salientes, correspondientes a Lpáginas, comenzando en la dirección dada. La longitud de cada borde es igual a página longitud. Cada borde viene a algunos vértice en el gráfico, dependiendo de donde correspondiente página extremos:

1. Página termina en alguna posición desocupada. Edge llega al vértice correspondiente a la dirección de inicio del primer rango después de esta posición.
2. Página termina dentro de algunos rango. Edge llega al vértice correspondiente a la dirección final de la página.
3. La página termina en la posición desocupada, con la dirección, más grande que la dirección de cualquier gama. Edge llega al destino vertex. (La dirección inicial de la primera línea corresponde a origen vértice, y deberíamos encontrar la ruta más corta entre estos dos vértices).

Desde el gráfico resultante es una, camino más corto DAG se puede encontrar en el tiempo lineal, mediante el procesamiento de los vértices en un orden topológico (o, incluso más simple, en orden de direcciones de memoria correspondiente).

Para cada vértice, mantenga una matriz de N pares {path-length, back-pointer}. Mientras que el algoritmo de ruta más corta visita cualquier vértice, indexe esta matriz con el número de saltos en la ruta, y si la ruta es más corta que la longitud de ruta almacenada, reemplace {longitud de ruta, punto de retroceso}. Cuando se procesa cada vértice, busque la ruta más corta en la matriz de pares, que pertenece al destino, vértice, luego reconstruya la ruta utilizando los indicadores de retroceso. Esta ruta describe la cobertura óptima.

Peor complejidad de tiempo de la caja O (L * M * N) está determinada por el número máximo de bordes (L * M) y el número de elementos en la matriz, pertenecientes a cada vértice (N). Si rangos son escasos, la mayoría de los bordes vienen a la dirección inicial de algunos rango, la mayoría de los vértices, correspondientes a las direcciones internas no se utilizan, y la complejidad del tiempo es mucho menor.

Este algoritmo requiere O (M * N) del espacio, pero para sparse rangos este puede ser significativamente disminuido si ponemos todos los vértices de gráficos (o tal vez todos los pares longitud/puntero) en un mapa hash.

Answer 2

Considere que los rangos que desea cubrir son intervalos de muy bajo valor (llamémoslos "rangos") y los espacios (llámelos "extras") son intervalos muy costosos. Ahora queremos minimizar el costo total con un máximo de N intervalos (llamadas "cubiertas") que cubren todos los "rangos" y pueden contener algunos "extras". El algoritmo de abajo es codicioso por naturaleza.

Primero tome todos los intervalos que desea cubrir ("rangos") y también los "extras" entre ellos.

1) Cúbralos con un intervalo grande de min a max de los "rangos".

2) Iterar y eliminar los "extras" más costosos (es decir, la mayor extensión) entre y también contar el divison como crear una "cubierta" adicional, hasta que el número de cubiertas sea N o se quede sin costosos "extras".

Answer 3

enfoque profundo de abajo arriba, que funciona cuando cada longitud es un múltiplo de la última:

de inicio con un conjunto de intervalos de longitud mínima que cubren todas las gamas mínimamente. Combina las carreras más largas de forma iterativa hasta que vayas por debajo del recuento de rango máximo.

En su caso, en un TLB, es probable que tenga restricciones de alineación que harán que el problema sea un poco más complicado.