Renombrado de Registros y Especulación Dinámica

Register Renaming and Dynamic Speculation: an Alternative Approach

El renombrado de registros es una de las técnicas utilizadas para aumentar el paralelismo de instrucciones. Consiste básicamente en tener un número de registro físicos mayor que el expuesto por la arquitectura, llamados normalmente registros lógicos, de usuario o públicos . De esta forma, y siguiendo determinadas reglas, un mismo registro lógico puede ser renombrado a como distintos registros físicos en distintas instrucciones. Veámoslo con un ejemplo:

(1) r1 := r2 / r4(2) r2 := r1 + r3 (3) r1 := r5 + r8 (4) r4 := r1 – r7		(1) r1 := r2 / r4(2) r2 := r1 + r3 (3) r9 := r5 + r8 (4) r4 := r9 – r7
Fig. 1		Fig . 2

En el primer código (Fig. 1) la antidependencia (WAR) existente entre las instrucciones (2) y (3) no permiten la ejecución en paralelo de ambas (aunque dispongamos de suficientes recursos hardware). Renombrando r1 como r9, como aparece en el ejemplo de la derecha (Fig. 2), eliminamos esa dependencia. El renombrado de registros mediante hardware pretende realizar estos cambios de forma dinámica para aumentar el grado de paralelismo de los programas compilados de forma genérica.
El renombrado de registro se realiza habitualmente en la fase de decodificación de instrucciones. Sin embargo, los autores de este artículo proponen hacerlo en la fase de búsqueda de instrucción. De esta forma se elimina complejidad de la fase de decodificación que trabaja (como las subsiguientes fases) en todo momento con los registros físicos en lugar de lógicos. Para realizar este renombrado, la solución propuesta se apoya en una estructura llamada Tabla de Asignación (Mapping Table) en la que se guarda únicamente el último renombrado realizado para cada registro lógico. No es necesario guardar la historia de renombrados para cada registro, puesto que al realizarse estos para cada instrucción en el orden del programa, las instrucciones usan siempre el último valor de sus registros fuente, que estarán guardados en los últimos registros físicos asignados a los lógicos.
Cada vez que un registro necesita ser renombrado se acude al depósito de registros físicos disponibles (pool) y se toma uno. Como el número de registros no es infinito, tenemos que ir liberándolos en cuanto detectemos que no son ya necesarios para poder reutilizarlos. Las reglas que se sigue para determinarlo son:

1. El resultado de la operación que generó la asignación de registro físico es escrito en este.
2. Todas las instrucciones lanzadas que necesitan dicho valor ya lo han leído.
3. El registro físico ha sido liberado (el registro lógico ha sido asignado a otro registro físico)

Para poder realzar estas comprobaciones se añade a la Tabla de Asignación una serie de campos:

1. Un contador que mantiene el número de instrucciones que están esperando dicho valor. Se incrementa cuando una instrucción (que necesite el valor) es lanzada y se decrementa cuando una instrucción (que necesite el valor) lo lee. Si está a cero significa que ninguna instrucción necesitará ya ese valor.
2. Un bit de que indica si el resultado se ha escrito o no (Completado) en el registro. Cuando el registro se saca del depósito de registros libres se coloca a falso y cuando se escribe el valor de la operación, se coloca a verdadero.
3. Un bit que indica cuándo el registro está asignado (valor falso) o no (verdadero) a un registro virtual (No asignado)

Vamos a ver el funcionamiento de esta estructura con un ejemplo paso a paso con el código mostrado en la figura 3:

(1) r1 := r2 + r3(2) r3 := r1 * r2 (3) r1 := r2 – r3 (4) r1 := r1 + r1

Fig. 3

Estado Inicial

	Insn-Fetch	Op-Fetch	Execute	Write-Back	Map	Register File
T1	r1 := r2 + r31) Asignamos p5 a r1: Lo marcamos como no completado y mapeado, y cambiamos el próximo registro libre a p6 2) Marcamos como no mapeado p1. En el próximo ciclo se marcará como próximo registro libre. 3) Incrementamos los contadores de uso de p2 y p3				r1 p5 r2 p2 r3 p3 r4 p4 Free p6	p1 T 0 T 27 p2 F 1 T 4 p3 F 1 T 128 p4 F 0 T 33 p5 F 0 F p6 T 0 T p7 T 0 T p8 T 0 T
T2	r3 := r1 * r21) Asignamos p6 a r3 2) Marcamos p3 como no mapeado 3) Incrementamos los contadores de uso de p5 (r1) y p2 (r2)	p5 := p2 + p31) Leemos p2 y p3 2) Decrementamos sus contadores de uso.			r1 p5 r2 p2 r3 p6 r4 p4 Free p1	p1 T 0 T 27 p2 F 1 T 4 p3 T 0 T 128 p4 F 0 T 33 p5 F 1 F p6 F 0 F p7 T 0 T p8 T 0 T
T3	r1 := r2 – r31) Asignamos p1 a r1 2) Marcamos p5 como no mapeado. 3) Incrementamos los contadores de p2 (r2) y p6 (r3)	p6 := p5 + p21) Leemos p5 y p2 2) Decrementamos sus contadores.	p5 := p2 + p3		r1 p1 r2 p2 r3 p6 r4 p4 Free p3	p1 F 0 F 27 p2 F 1 T 4 p3 T 0 T 128 p4 F 0 T 33 p5 T 0 F p6 T 1 F p7 T 0 T p8 T 0 T
T4	r1 := r1 + r11) Asignamos p3 a r1 2) Marcamos p1 como no mapeado. 3) Incrementamos el contador de p1 dos veces	p1 := p2 – p61) Leemos p2 y p6 2) Decrementamos sus contadores.	p6 := p5 + p2	p5 := p2 + p31) Escribimos el resultado en p5 2) Marcamos p5 como completado.	r1 p3 r2 p2 r3 p6 r4 p4 Free p5	p1 T 2 F 27 p2 F 0 T 4 p3 F 0 F 128 p4 F 0 T 33 p5 T 0 T 132 p6 T 0 F p7 T 0 T p8 T 0 T

Saltos y especulación

Todo diseño que permita la ejecución de instrucciones en un orden distinto del original del programa debe proporcionar un mecanismo que permita la recuperación del estado tras una predicción de salto errónea, cuando se permite la ejecución especulativa. Con el renombrado de registros, para poder dar marcha atrás y recuperar el estado previo a un salto (tomado o no) predicho erróneamente, además de los valores de los registros debemos poder recuperar el contenido de la Tabla de Asignación. Se debe guardar el contenido de esta tabla cada vez que aparece una instrucción de salto, bien mediante el uso de una estructura de tipo pila o bien usando algún mecanismo de interrupciones precisas.
Con renombrado de registros, cuando distintas instrucciones hacen uso de un mismo registro virtual como destino se realizan distintas asignaciones de registros físicos a este. Los antiguos valores de los registros virtuales, guardados en distintos registros físicos, no se pierden a no ser que uno de estos quede disponible para ser reutilizado. Si evitamos reutilizar los registros físicos correspondientes a estados antiguos del procesador, al restaurar el estado de la Tabla de Asignación recuperamos los valores antiguos de los registros virtuales. Para evitar la reasignación de esos registros físicos aún útiles, se debe incorporar una nueva restricción para la liberación de un registro físico: un registro se considera que no está asignado si no lo está, además de en la Tabla de Asignación, en una de las tablas de correspondencia guardadas (estados anteriores).

Resumen del artículo Register renaming and dynamic speculation: an alternative approach de Mayan Moudgill  (Department of Computer Science, Cornell University, Ithaca, NY),  Keshav Pingali  (Department of Computer Science, Cornell University, Ithaca, NY) y Stamatis Vassiliadis (School of Electrical Engineering, Cornell University, Ithaca, NY and IBM Corporation, Enterprise Systems, Poughkeepsie, NY).