Los registros son las ubicaciones más rápidas en la jerarquía de memoria. Pero desafortunadamente, este recurso es limitado. Se incluye en los recursos más restringidos del procesador de destino.
La asignación de registros es un problema NP-completo. Sin embargo, este problema se puede reducir a la coloración del gráfico para lograr la asignación y la asignación. Por lo tanto, un buen asignador de registros calcula una solución aproximada efectiva para un problema difícil.
El asignador de registros determina qué valores residirán en el registro y qué registro mantendrá cada uno de esos valores. Toma como entrada un programa con un número arbitrario de registros y produce un programa con un conjunto de registros finitos que puede encajar en la máquina de destino.
Asignación vs Asignación
Asignación: Asigna un espacio de nombres ilimitado a ese conjunto de registros de la máquina de destino.
- Reg. a reg. Modelo: asigna registros virtuales a registros físicos, pero derrama una cantidad excesiva en la memoria.
- Mem. a mem. Modelo: asigna algunos subconjuntos de la ubicación de la memoria a un conjunto de nombres que modelan el conjunto de registros físicos.
La asignación garantiza que el código se ajuste al registro de la máquina de destino. establecer en cada instrucción.
Asignación: Asigna un conjunto de nombres asignados a un conjunto de registros físicos de la máquina de destino.
- Se asume que la asignación se ha realizado para que el código se ajuste al conjunto de registros físicos.
- No se designan más de 'k' valores en los registros, donde 'k' es el no. de registros físicos.
La asignación del registro general es un problema completo de NP:
- Resuelto en tiempo polinomial, cuando (no. De registros requeridos) <= (no. De registros físicos disponibles).
- Se puede producir una asignación en tiempo lineal usando la coloración de gráficos a intervalos.
Asignación y asignación del registro local
La asignación dentro de un bloque básico se denomina Reg. Local. Asignación. Dos enfoques para el registro local. asignación: enfoque de arriba hacia abajo y enfoque de abajo hacia arriba.
El enfoque de arriba hacia abajo es un enfoque simple basado en el 'Recuento de frecuencia'. Identifique los valores que se deben mantener en los registros y los que se deben guardar en la memoria.
Algoritmo:
- Calcular una prioridad para cada registro virtual.
- Ordenar los registros en orden de prioridad.
- Asignar registros en orden de prioridad.
- Reescribe el código.
Moviéndose más allá de los bloques individuales
Más complicado porque el flujo de control.
Liveness y Live Ranges: los rangos en vivo consisten en un conjunto de definiciones y usos relacionados entre sí, ya que es decir, ningún registro individual puede ser común en un par de instrucciones / datos.
A continuación hay una forma de averiguar los rangos en vivo en un bloque. Un rango en vivo se representa como un intervalo [i, j], donde i es la definición y j es el último uso.
Asignación y asignación de registros globales
1. El problema principal de un asignador de registros es minimizar el impacto del código de derrame
- Tiempo de ejecución del código de derrame.
- Espacio de código para la operación de derrame.
- Espacio de datos para valores derramados.
2. La asignación global no puede garantizar una solución óptima para el tiempo de ejecución del código de derrame.
3. Primeras diferencias entre la asignación local y global:
- La estructura de un rango vivo global es naturalmente más compleja que la local.
- Dentro de un rango en vivo global, las referencias distintas pueden ejecutarse un número diferente de veces. (Cuando los bloques básicos forman un bucle)
4. Para tomar la decisión acerca de la asignación y las asignaciones, el asignador global utiliza en su mayoría el color del gráfico al crear un gráfico de interferencia.
5. El asignador de registro luego intenta construir un colorante k para esa gráfica donde 'k' es el no. de registros físicos.
En caso de que el compilador no pueda construir directamente un k-colouring para ese gráfico, modifica el código subyacente derramando algunos valores en la memoria y lo intenta de nuevo.
El derrame en realidad simplifica ese gráfico que asegura que el algoritmo se detendrá.
6. Global Allocator utiliza varios enfoques, sin embargo, veremos estrategias de asignación de arriba hacia abajo y de abajo hacia arriba. Subproblemas asociados con los enfoques anteriores.
Esta guia te puede ser de utilidad para preparar las oposiciones 2019 de Oficial Técnico de Sistemas Informáticos en Navarra Nivel C
Fecha actualización el 2021-06-23. Fecha publicación el 2019-06-23. Categoría: Oficial Técnico de Sistemas Informáticos Autor: Oscar olg Mapa del sitio Version movil