Procesamiento de las Instrucciones de Salto

PROCESAMIENTO DE LAS INSTRUCCIONES DE SALTO

Esta sección se dedica, precisamente, al estudio del procesamiento eficiente de las instrucciones de salto en un superescalar

Para el estudio del procesamiento de los saltos en el ámbito de los procesadores segmentados empezaremos recordando los aspectos que encierra dicho procesamiento:

INTRODUCCIÓN

Un procesador Superescalar, al ser un procesador

segmentado, también sufre un reducción de prestaciones

considerable como consecuencia de los cambios en la

secuencia de instrucciones que debe introducirse en el

cauce cuando se produce un salto. Es preciso resaltar, el

efecto de los saltos en los superescalares es todavía más

grave, dado que al captarse, decodificarse y emitirse

varias instrucciones por ciclo puede ocurrir que, en

determinados códigos, prácticamente en cada ciclo haya

una instrucción de salto. Además, aumenta el número de

instrucciones que podrían introducirse incorrectamente

en el cauce y dar lugar a un uso ineficiente de los

recursos.

DETECCIÓN DE LA INSTRUCCIÓN DE SALTO:

cuanto antes se detecte que una instrucción es de salto antes puede empezar a procesarse como tal.De esta forma se puede reducir la posible penalización que ocasionan estas instrucciones si se produjese el salto.

Existen varias posibilidades para la detección temprana de las instrucciones de salto:

DETECCIÓN PARALELA: Hay una etapa específica para detectar instrucciones de salto que opera en paralelo con una etapa común de decodificación. Esta alternativa se utiliza en los procesadores Alpha.

DETECCIÓN ANTICIPADA: Además de utilizarse la decodificación paralela, se analizan las últimas líneas de la cola de instrucciones captadas antes de que pasen a la unidad de decodificación. El PowerPC 603 usa esta estrategia.

DETECCIÓN INTEGRADA EN LA CAPTACIÓN: En el momento en que se captan las instrucciones se detecta si la instrucción es de salto o no (para eso se pueden utilizar los bits de predecodificación, como hemos indicado antes). Esta opción se utiliza, por ejemplo, en el PowerPC 640.

GESTIÓN DE SALTOS CONDICIONALES NO RESUELTOS: si en el momento en que la instrucción de salto evalúa la condición de salto, ésta no se ha terminado de evaluar todavía, se dice que el salto o la condición de salto no se ha resuelto, Para resolver este problema, los procesadores superescalares suelen utilizar el procesamiento especulativo del salto. La instrucción de salto condicional comprueba el valor de los bits de estado adecuados según sea la condición que determine el salto. Esta forma de realizar los saltos condicionales establece una dependencia entre las instrucciones que viene determinada por la ubicación de dichas instrucciones, en lugar de aparecer explícitamente a través de los operandos de cada instrucción.

Gestión de Saltos Condicionalesla gestión de datos condicionales no resueltos se produce en el momento

en que la instrucción de salto evalúa la condición de salto, si esta no se ha terminado de evaluar todavía, se dice que el salto o la condición de salto no se ha resuelto. Para resolver este problema, los procesadores superescalares suelen utilizar el procesamiento especulativo de salto.

Otras alternativas podría ser el utilizar un registro de estados a cuyos bits se asignan determinados significados (bits de signo, de cero, de desbordamiento u overflow, etc) y son modificados al ejecutar una instrucción de acuerdo con las características del resultado (cero, positivo, etc) La instrucción de salto condicional comprueba el valor de los bits de estado adecuados según sea la condición que determine el salto. Esta forma de realizar los saltos condicionales establece una dependencia entre las instrucciones que viene determinada por la ubicación, en lugar de aparecer explícitamente a través de los operandos de cada instrucción.

Establecimientos Condición Salto

Bits de estado Comprobación Directa

Existen bits de estado que se modifican al realizar operaciones o mediante operaciones que actúan específicamente sobre el valor del registro de bits de estado

Los resultados de las operaciones se comprueban directamente respecto a las condiciones específicas mediante instrucciones específicas.Dos Instrucciones Una Instrucción

add r1,r2,r3 beq Cerodiv r5,r4,r1...Cero

add r1,r2,r3cmpeq r7,r1,Cerobeq r7,cerodiv r5,r4,r1...Cero

add r1,r2,r3beq r1,Cerodiv r5,r4,r1...Cero

IBM/360PDP-11,VAXX-86, PentiumPower PC,Spac

Am 29000 Cray MIPS, MC881X0HP PADEC ALPHA

Dependencia que limita las prestaciones en VLIW y superescalares

3.4.1. ALTERNATIVAS PARA LA GESTIÓN DE LOS SALTOS CONDICIONALES

Una vez que se ha detectado una instrucción de salto y se ha determinado la dirección de destino, interesa conocer cuanto antes si se verifica la condición de salto para empezar a captar lo más pronto posible las instrucciones desde la dirección de destino del salto, si finalmente hay que realizar el salto, y evitar que se introduzcan en el cauce instrucciones que no deben procesarse.

En los procesadores superescalares existen varias posibilidades para gestionar los saltos condicionales no resueltos para minimizar la penalización derivada del posible retardo en la evaluación de la condición de salto.

Bloquear La Instrucción De Salto, que no puede progresar en el cauce hasta que no se haya terminado de evaluar la condición. Esta alternativa corresponde, realmente, a la situación más desfavorable desde el punto de vista de las prestaciones y, en ese sentido se puede tomar como punto de partida para posibles mejoras.

Procesamiento Especulativo de Los Saltos. El procedimiento se basa en estimar de alguna forma el camino que, con más probabilidad, va a seguir la ejecución cuando se haya evaluado la condición de salto.

Múltiples Caminos. En este caso si cada vez que llega una instrucción de salto, el procesador empezaría a captar y procesar instrucciones de los dos caminos alternativos. Esta opción es la más costosa en cuanto a demanda de recursos en el procesador

Tabla 3.8

3.4.1.1. ALTERNATIVA PARA LA PREDICCIÓN DE SALTOS

La predicción de saltos se basa en la idea de que el comportamiento de una instrucción de salto condicional presenta una cierta regularidad, y por tanto puede predecirse con una cosa de aciertos suficientemente elevada.

En caso de que se produzca un error en la predicción, habrá por tanto una penalización que será tanto mayor cuanto más se tarde en recuperar la situación de ejecución correcta.

Así, como en cualquier otra técnica de procesamiento especulativo, interesa disponer de un procedimiento de predicción con una tasa de aciertos lo más elevada posible y una implementación que permita la recuperación rápida de los errores. Se describirá alternativas para la predicción:

Técnicas De Predicción Fija, que son aquellas en las que el procesador toma siempre la misma decisión ante cualquier instrucción de salto condicional empieza a ejecutar instrucciones a partir de la dirección de destino del salto, o sigue captando las instrucciones que siguen a la instrucción de salto.

Predicción Verdadera, la decisión depende de las características propias de la instrucción de salto condicional concreta que se esté ejecutando por eso se dice que son de predicción verdadera en contraposición a los anteriores. Esas características propias de la instrucción de salto pueden ser atributos que no cambian a lo largo de las posibles ejecuciones sucesivas de la instrucción. En este caso se habla de predicción estática. también puede tenerse en cuenta el perfil de saltos/no saltos que se han ido produciendo en las sucesivas ejecuciones anteriores de la instrucción de salto, o incluso de otras instrucciones de salto próximas en este caso, si se considera la historia de la instrucción de salto se trata de un procedimiento de predicción dinámica

Esquemas De Predicción Fija. Sólo hay dos alternativas posibles para los esquemas de predicción fija: la aproximación de salto siempre no tomado y la de salto siempre tomado.

Salto Siempre No Tomado, para toda instrucción de salto cuya condición no está resuelta se considera que lo más probable es que no se produzca el salto. Por lo tanto, el procesador continúa captando instrucciones por donde iba.

BTA (Branch Target Address )

Salto Siempre Tomado, se considera que toda instrucción de salto condicional no resuelta da lugar a un salto, por lo que se empiezan a captar instrucciones a partir de la dirección de destino del salto, En previsión de que se pueda producir un error en la predicción, se guarda el valor del contador de programa PC que apunta a la instrucción siguiente a la instrucción de salto condicional.

Esquemas de predicción estática. El presupuesto básico de estos esquemas es que ciertos atributos de la instrucción de salto están relacionados con la probabilidad de que dicha instrucción ocasione o no un salto. Por tanto, la predicción se hace sobre la base de dichos atributos. Se habla de predicción estática porque se trata de características que no cambian al ejecutar el código. Algunos ejemplos de esquemas de predicción estática son los siguientes:

Predicción basada en el código de operación: según el tipo de instrucción de salto condicional se considero más probable que se produce el salto o que no. Este tipo de esquemas se utiliza en el MC88110 (1993) y en el PowerPC (1993).

Predicción basada en el desplazamiento del salto: si el desplazamiento es positivo (se trata de un salto hacia adelante, a direcciones mayores que la de la instrucción de salto) se predice, usualmente, que el salto no se producirá, y si el desplazamiento es negativo (salto hacia atrás) se predice, usualmente, que el salto se producirá. En los procesadores Alpha 21064 (1992) y PowerPC 603 (1993) se utiliza . este esquema de predicción.

Predicción dirigida por el compilador: a través de una serie de bits que existen en las instrucciones de salto (bits de predicción), el compilador puede fijar la predicción que se va a realizar para la instrucción. Para fijar esos bits el compilador puede tener en cuenta resultados obtenidos a partir de ejecución de trazas del programa que indiquen qué tipo de comportamiento es el más probable para cada instrucción de salto. Entre los procesadores que implementan esta posibilidad están el PowerPC 603 (1993) y el PA8000 (1996).

Se pretende utilizar el comportamiento observado de salto/no salto de cada instrucción de salto condicional, para establecer la predicción a realizar cuando esa instrucción vuelva a captarse. El presupuesto básico de la predicción dinámica es que lo más probable es que el resultado de salto/no salto de una instrucción sea similar al que se tuvo en las ejecuciones pasadas de dicha instrucción (en la anterior o en las n ejecuciones anteriores). En este esquema, para cada instrucción de salto condicional debe guardarse algún tipo de información que condense el comportamiento pasado y permita realizar la predicción.

Comparado con la predicción fija y la predicción estática, este esquema es el que suele presentar las mejores prestaciones, a costa de una implementación más costosa. A su vez, los esquemas de predicción dinámica se pueden clasificar en función de la forma de almacenar el comportamiento pasado de la instrucción de salto. Así, se habla de:

Esquemas de predicción dinámica

Predicción Dinámica Implícita: Se almacena únicamente la dirección de la instrucción que se ejecutó tras la instrucción de salto la última vez que se captó esta. La dirección puede ser la dirección de destino del sal to, lo que equivale a predecir que se produce el salto, o bien la dirección de la instrucción siguiente a la de salto, con lo que se predice que el salto no se produce.

Predicción Dinámica Explícita: para cada instrucción de salto condicional, existe un conjunto de bits que codifican la información relativa al comportamiento pasado de la instrucción en cuestión. Estos bits se denominan bits de historia. El número de bits de historia que se guardan para cada instrucción depende del tipo de esquema de predicción dinámica explícita que se haga.

www.themegallery.com

www.themegallery.com

ejemplo En un programa, una instrucción de salto condicional

(a una instrucción anterior) dada tiene el siguiente comportamiento en una ejecución de dicho programa:

SSNNNSSNSNSNSSSSSN

donde S significa que se produce el salto, y N, que no. Se utiliza:a) Predicción fija (siempre se considera que no se va a producir el salto)b) Predicción estática (si el desplazamiento es negativo se toma, y si es positivo, no)c) Predicción dinámica con dos bits, inicialmente en el estado (11).d) Predicción dinámica con tres bits, inicialmente en el estado (111).

Nota: La penalización por saltos incorrectamente predichos es de 5 ciclos, y para los saltos correctamente predichos, 0 ciclos.

a) SSNNNSSNSNSNSSSSSN => S = 11 => 55ciclos

b) SSNNNSSNSNSNSSSSSN => S = 7 => 35ciclos

c)

S S N S N S

SSNNNSSNSNSNSSSSSN00110111111110000111 saltos mal predichos 55c

111

011 001

000

SSNNNSSNSNSNSSSSSN001101110111100001

10 saltos mal predichos 50c

110 100

010101

Tras la predicción el procesador continua ejecutando instrucciones especulativamente hasta que se termina de evaluar la condición de salto. El intervalo de tiempo entre el comienzo de la ejecución especulativa de instrucciones y la resolución de salto puede ser muy largo y, además, puede variar considerablemente en cada caso. Durante la ejecución especulativa de un salto condicional puede suceder que se capten nuevas instrucciones de salto condicional que tampoco estén resueltas. En general, cuanto mayor sea el numero de instrucciones que se ejecutan especulativamente es muy elevado y la predicción es incorrecta, la penalización asociada al procesamiento de la instrucción de salto es mayor. Teniendo eso en cuenta, hay dos características importantes del procesamiento especulativo de instrucciones de salto: el nivel de especulación y el grado de especulación.

El Nivel de especulación es el numero de instrucciones de salto condicional que pueden ejecutarse especulativamente. En el caso de que se permita la ejecución especulativa de varias instrucciones de salto no resueltas, habrá que guardar los correspondientes estados de ejecución.

El grado de especulación indica la etapa hasta la que se procesan las instrucciones que constituyen el camino especulativo después del salto condicional. Así, por ejemplo, en el Power 1 solo hasta la captación; en el PowerPC 601, las de captación, descodificación y emisión; y en el PowerPC 603 pueden procesarse todas las etapas, excepto la de finalización.

ACCESO A LA SECUENCIA DE SALTO Y RECUPERACION DE UNA PREDICCION INCORRECTA

Los saltos condicionales que san lugar a un salto (saltos condicionales tomados “taken”) son mas probables que los que no dan lugar a salto (saltos no tomados “not taken”). Por eso, seria interesante reducir al máximo el tiempo de acceso a la secuencia de instrucciones a partir de la dirección de salto y reducir la penalización para las predicciones incorrectas.