4. mem-paso de completar salto/acceso a …riesgo de salto o de control en la figura siguiente se...

Ingeniería Informática. Ampliación de Estructura de Computadores. Curso 2010-11

Vicente Arnau Llombart 12/12/2011

6.3.3 Riesgo de Control.

Los riesgos por control en DLX son menos frecuentes que los riesgos por dependencia de datos, pero

al no haber una solución tan buena como el adelantamiento de datos, se convierten en una de las

principales causas de retrasos en la ejecución segmentada de las instrucciones.

Tal como definimos cada uno de los segmentos para DLX, si una instrucción actualiza el

valor del PC, este cambio no será efectivo hasta el cuarto segmento MEM. Recordar:

Esto implica que la segmentación tendrá que detenerse durante 3 ciclos de reloj, pues hasta el

final de este cuarto segmento no será conocida la dirección de la siguiente instrucción. Este riesgo se

conoce como:

Riesgo de salto o de control

En la figura siguiente se muestra un ejemplo de lo que acabamos de comentar. En el se

observa como iniciamos normalmente una instrucción de salto como otra cualquiera, pero cuando en

el segundo segmento la decodificamos y observamos que es un salto incondicional, ya dejamos de

ejecutar instrucciones segmentadas hasta conocer el nuevo valor que tomará el PC, y que lo

sabremos al final del cuarto segmento MEM.

Ciclos de Reloj

Instrucción 1 2 3 4 5 6 7 8 9 10 11

Salto Incondic. IF ID EX MEM WB

Instrucción i+1 IF detención detención IF ID EX MEM WB

Instrucción i+2 detención detención detención IF ID EX MEM WB

Instrucción i+3 detención detención detención IF ID EX MEM WB

Hay que resaltar que tres ciclos de reloj perdidos por cada salto es una cifra significativa.

En cualquier máquina, si se modifican valores de los registros o datos de memoria en los primeros

segmentos, hay que detener la segmentación; tanto para saltos como para bifurcaciones.

4. MEM-Paso de completar salto/acceso a memoria:

i) Referencia a memoria:

LMDR Mem[DMAR ó

Mem[DMAR SMDR

ii) Salto: El valor de PC es sustituido por la dirección de salto.

if (cond) : PC ALU-salida ;

ALU-salida1 ALU-salida



Por lo visto en el problema, es importantísimo el reducir el número de retrasos producidos por

riesgos de control. Para ello deberemos intentan conseguir dos cosas:

Averiguar si el salto es efectivo o no lo antes posible en la segmentación.

Calcular el PC efectivo lo antes posible.

Para optimizar al máximo la situación es conveniente hacer las dos cosas.

En DLX los saltos requieren examinar solamente la igualdad con 0. Por lo tanto seria posible

tomar una decisión al final del segmento ID si tuviésemos una lógica especial dedicada a este test, es

decir, un comparador. Necesitaríamos además un sumador independiente para calcular las dos

direcciones, la de salto y la de no salto (PC+4).

Deberíamos revisar la definición de las operaciones realizadas para cada uno de los

segmentos de DLX y dejarlas como se muestra a continuación:

Problema: Sea una máquina en la cual la frecuencia de instrucciones de saltos es de un 20%. Y de el total de

saltos un 60% son efectivos (saltan realmente).

Si la maquina ideal posee un IPC de 1, cuanto más rápida es la máquina ideal frente a esta máquina con riesgos de

control (los únicos).

Solución: El porcentaje de instrucciones que producen riesgos por control es

(20%)*(60%) = 0.2*0.6 = 0.12 por uno (12%).

por tanto, cada 100 instrucciones, 12 producirán retrasos de 3 ciclos de reloj.

Entonces el CPI de esta máquina se podrá calcular como

IPC REAL = Nº Ins /Nº Ciclos = 100 / (100+12*3) = 100/136 = 0.735

La relación entre los CPI de las dos máquinas será de 1/0.735=1.36, es decir un 36% más lenta que la máquina

real.

Problema: Cual es la perdida de velocidad si el retraso fuese solo de un ciclo en cada

instrucción de salto.



1. IF-Paso de búsqueda de instrucción:

IR Mem[PC ; PC PC+4

2. ID-Paso de búsqueda del registro/decodificación de instrucción.

A Rsl ; B Rs2;

BTA PC+((IR16 )16

## IR16..31)

IF (Rs1 op 0) PC BTA

3. EX: . . .

4. MEM: . . .

5. WB: . . .

El cálculo de la dirección de salto se realizará para todas las instrucciones y se guardará en BTA.

La evaluación de la condición de salto también se realizara para todas las instrucciones.

La última acción a realizar será la de escribir en el PC la dirección efectiva del salto. Esta acción se

debe realizar ya al final del ciclo y para entonces ya se debe de tener decodificada la instrucción para

saber que es un salto.

En caso de salto, ya no se realizará la ejecución de los últimos tres segmentos de la instrucción, tan

solo se pierde así un ciclo de reloj.

En algunas máquinas, poseen riesgos en los saltos de más ciclos de reloj. Por ejemplo, los

VAX poseen normalmente penalizaciones de 4 ciclos de reloj para los saltos.

Este retardo depende de la profundidad de la segmentación (nº de segmentos por instrucción),

llevando a valer 6 y 7 ciclos de reloj para máquinas con segmentación muy profunda.

Hemos visto como solo se pierde un ciclo, pero el procesador debe eliminar la instrucción que acaba

de ser leída del cauce segmentado, para ello utiliza una línea de control llamada IF.Flush, la cual

pone a cero el registro IR, simulando que se ha leído una instrucción nop. Todo esto puede

observarse en la siguiente figura:



El procesador de DLX, lo que hace es suponer que el salto nunca será tomado y solo cuando el salto

es efectivo vacía la entrada del cauce segmentado.

Segmentación para DLX minimizando riesgos de control.

1. IF-Paso de búsqueda de instrucción.

IR Mem[PC; NPC PC + 4;

2. ID-Paso de búsqueda del registro/decodificación de instrucción.

A Rsl ; B Rs2;

BTA NPC+((IR16 )16

## IR16..31)

IF (Rs1 op 0) PC BTA

Imm ((IR16)16

## IR16..31);

3. EX-Paso de dirección efectiva /ejecución.

i) Referencia a memoria:

ALUOutput A + Imm;

ii) Instrucción ALU sobre Registros:

ALUOutput A op B;

iii) Instrucción ALU sobre Registro-Dato Inmediato:

ALUOutput A op Imm;

4. MEM-Paso de completar salto/acceso a memoria.

Referencia a memoria: Acede a memoria para leer o escribir un dato.

LMD Mem[ALUOutput ó

Mem[ALUOutput B

5. WB-Paso de post-escritura (write-back):

Instrucción Aritmética:

Regs [IR16..20 ALUOutput;

Instrucción ALU sobre Registro-Dato Inmediato:

Regs [IR11..15 ALUOutput;

Instrucción de carga:

Regs [IR11..15 LMD;



Comportamiento dinámico de los saltos.

Las instrucciones de salto son muy utilizadas por los compiladores para la generación de código.

Veamos primero con que frecuencia son utilizadas en tres máquinas diferentes. (Figura 6.18).

Las frecuencias de saltos condicionales oscilan entre el 11% y el 17%.

Las frecuencias de saltos incondicionales oscilan entre el 2% y el 8%.

- Pero, ¿cuantos saltos condicionales son efectivos?.

- Recordemos el lo visto en temas anteriores: para DLX el 53% de los saltos son efectivos. Es una

valor típico para la mayoría de máquinas.



Problema: Vistos los datos de la gráfica anterior, si IPCIDEAL =1 , cuanto más rápida es esta

máquina ideal respecto a máquina con DLX que posee retardos por saltos y por dependencia

de datos.

Suponer que el nº de instrucciones de carga es del 13% y de ellas el 25% produce retrasos en

la segmentación.

Suponer que el 53% de los saltos condicionales, saltan realmente.

Solución: Calculémoslo.

Nº total de Instrucciones que producen retrasos:

2% (saltos) + 11%*53%(bifurcaciones) + 13%*25%(cargas) = 11,08%

El cociente entre los IPC será:

rápidamasIPC

IPCCCocienteIP

REAL

IDEAL _%108.111108.1100

08.111

08.111

100

1

La máquina ideal es 11% más rápida. (El IPC real es de 0.9).



Reducción de penalizaciones en saltos.

Vamos a analizar 4 métodos sencillos para tratar las detenciones, en tiempo de compilación, debidas

a los retrasos por los saltos. Son métodos estáticos y las predicciones son estimaciones en tiempos de

compilación. Más adelante ya estudiaremos como prevenirlos por hardware (es más complejo).

Método 1: Es el más sencillo y consiste simplemente en parar la segmentación en el momento que se

sabe que la instrucción es de salto o bifurcación, y no se reanuda hasta que se conozca la dirección de

salto (ya visto). Es la peor solución, y se puede realizar sin más que introducir NOP después de la

instrucción de salto, hasta que se sepa si se salta o no.

Método 2: Una pequeña mejora es suponer que no se va a realizar el salto (“predict-not-taken”). El

procesador continúa como si el salto no se realizara. El peligro está en que las instrucciones de

después del salto cambien el estado del procesador. Esto no se puede permitir, y se permite, en caso

de realizarse el salto, se deben restaurar estos valores.

Si el salto al final no se realiza, se sigue como si nada. Si se realiza, se empieza de nuevo leyendo la

nueva instrucción en la nueva dirección apuntada por el PC. La figura siguiente muestra ambas

situaciones (6.19).

Método 3: Otro esquema posible es predecir el salto como efectivo y empezar a ejecutar como

instrucción siguiente a la del salto la que indicará el PC en caso de ser efectivo dicho salto. En DLX

esto no se puede hacer pues no se conoce la dirección del salto hasta el final del segundo (ó cuarto)

segmento. Pero hay otros procesadores con juegos de instrucciones diferentes (con códigos de

condición), más potentes y lentas, que si que pueden realizar este tipo de predicción.



Método 4: Este método consiste en realizar lo que se conoce como salto retardado, utilizado

muchas unidades de control microprogramadas. La técnica consiste adelantar la ejecución de la

instrucción de salto (si se puede), para que así se sepa antes si se realiza o no el salto. Con ello se

evita los periodos muertos de retardo, pues se rellenan con instrucciones. Si el procesador determina

que el salto es efectivo, la instrucción siguiente no la anula, y sigue con la instrucción apuntada por

el nuevo valor de PC. Esto supone un cambio en la definición de segmentación.

Vemos algunos ejemplos del uso de esta técnica de compilación:

Caso 1 Caso 2 Caso 3

Antes: Antes: Antes:

ADD R1,R2,R3

si R2=0 entonces

retardo

...

MULT r6,r7,r8

SUB R4,R5,R6

MULT r6,r7,r8

...

ADD R1,R2,R3

si R1=0 entonces

retardo

ADD R1,R2,R3

si R1=0 entonces

retardo

SUB R4,R5,R6

...

MULT R14,R15,R16

Ins+1

Despues: Despues: Despues:

si R2=0 entonces

ADD R1,R2,R3

...

MULT r6,r7,r8

SUB R4,R5,R6

MULT r6,r7,r8

...

ADD R1,R2,R3

si R1=0 entonces

SUB R4,R5,R6

ADD R1,R2,R3

si R1=0 entonces

SUB R4,R5,R6

...

Ins-1

MULT R14,R15,R16

Ins+1

Caso 1: el hueco se llena con una instrucción anterior al salto. Es la mejor estrategia.

Caso 2: si no es posible aplicar el caso 1 por depender la condición de salto de un registro utilizado

con anterioridad, para este tipo de bucles, podemos llenar el hueco con la instrucción

primera en caso de ser efectivo el salto, es decir, con la primera instrucción del bucle. Dicha

instrucción debe ser copiada pues puede ser utilizada por otra vía.

Caso 3: para este tipo de salto se ejecuta en el tiempo de retardo la primera instrucción del bucle. A

de asegurarse el compilador que la ejecución de esta instrucción no crea ningún problema en

el funcionamiento global del programa ejecutado.



El caso 2 y 3 se pueden aplicar cuando el registro R4 es una variable temporal y la ejecución de

esta instrucción no altera la programación realizada.

Tanto en el caso 2 como en el 3 hay que realizar una copia de instrucción, aumentando el tamaño

del código final.

La tarea del software (compilador) es hacer que la instrucción sucesora sea válida y útil. Si no lo

consigue y su introducción puede acarrear problemas, se sustituye por un instrucción de NOP.

Vamos a analizar ahora las restricciones a cada caso y aquellas situaciones en las cuales se

comportan mejor. Para ello veamos la siguiente tabla.

Requerimiento ¿Cuando mejora el rendimiento?

Caso 1: Los saltos deben no depender de la/las

instrucción anterior.

Siempre.

Caso 2: Duplicar instrucción.

No alterar el programa por la duplicación

de esta instrucción.

Cuando es efectivo el salto, pues la ya tiene

realizada la primera instrucción del bucle.

Caso 3: Duplicar instrucción

No alterar el programa la ejecución en este

punto de esta instrucción.

Mejora cuando el salto no es efectivo, pues

ya tiene ejecutada la primera instrucción

del bucle.

Insistimos: Cuando los huecos no se pueden planificar se llenan con instrucciones de NOP (Not

Operation).

El principal problema esta en la planificación de que instrucciones pueden ser ejecutadas en

los huecos de retardo y la capacidad para que el compilador prediga con que frecuencia serán

efectivos los saltos.

En la página siguiente se muestra la efectividad de este tipo de planificaciones de saltos en

DLX., con un único hueco de retardo que se intenta llenar con instrucciones útiles. (F-6.22).

La barra sólida indica el porcentaje de huecos que son llenados con instrucciones

diferentes a NOP.

La barra sombrada indica el porcentaje de instrucciones que realizan una tarea útil. Cuando

se aplica el caso 1, siempre es útil la instrucción insertada, mientras que cuando se aplica

el caso 2 y 3 no siempre lo es, y de ahí esta diferencia entre las barras.

Vemos que en un 83%, 85% y 83% de los casos de sustitución, se realiza un trabajo útil.

Este valor es tan alto, recordar que solo el 53% de los saltos son efectivos, por que en la

mayoría de los casos la estrategia utilizada es la del caso 1, que siempre es útil la

sustitución.

El resultado final es que aproximadamente se eliminan la mitad de los retardos por saltos.

Para finalizar vamos a analizar una gráfica en la cual se hace un resumen de los retardos que

se producen para una máquina DLX de enteros, tanto por cargas como por saltos. Además se supone

que la cache de memoria no falla y por supuesto no se producen interrupciones.



Vemos como entre el 7 y el 15 por ciento de los ciclos de reloj son pérdidas por riesgos de datos o

de saltos.

El CPI efectivo para estas pruebas es de aproximadamente de 1.1.

La mejora aportada por la segmentación es de un factor 5.3.



Ejemplo: Aplicar los tres casos de la técnica del Salto retardado. ;===================================================

; SERIE.S :

;===================================================

.data 0x1000

n_dat: .word 16, 0

cte1: .double 6.7

cte2: .double 3.3

Ser_X: .double 1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8

.double 1.9, 2.0, 2.1, 2.2, 2.3, 2.4, 2.5

Ser_Y: .double 1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8

.double 1.9, 2.0, 2.1, 2.2, 2.3, 2.4, 2.5

Ser_Z: .double 1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8

.double 1.9, 2.0, 2.1, 2.2, 2.3, 2.4, 2.5

Ser_W: .space 16*8

.text 0x100

lw R16, n_dat

ld F6, cte1

ld F2, cte2

addi R1, R0, 0

eti: LD F10, Ser_X(R1)

LD F12, Ser_Y(R1)

LD F14, Ser_Z(R1)

MULTD F20, F10, F6

MULTD F22, F12, F2

ADDD F24, F20, F14

ADDD F26, F24, F22

SD Ser_W(R1), F26

ADDI R1, R1, 8

SUBI R16, R16, 1

BNEZ R16, eti

ADDD f28, f26, f26

NOP

TRAP 0



Mas Ejemplos de Salto Retardado:

Caso 1:

Programa inicial Con salto retardado (caso 1)

;====================================

; SALTO.S : INTRUCCIÓN IF-ELSE =

;====================================

.data

dato: .float 1.5, 2.0

CTE: .FLOAT 10.0

num: .word 2

.text 0x100

main: LF F10 , CTE

LF F4 , dato

LW R12, num

LF F6 , dato+8

BEQZ R12 , eti

MULTF F20 , F4 , F6

SF dato , F20

eti: subi R12, R12, 1

BEQZ R12 , eti2

ADDF F20 , F4 , F6

SF dato+8 , F20

eti2: trap 0

;====================================

; SALTO_R.S : INTRUCCIÓN IF-ELSE =

;====================================

.data

dato: .float 1.5, 2.0

CTE: .FLOAT 10.0

num: .word 2

.text 0x100

main: LF F10 , CTE

LF F4 , dato

LW R12, NUM

BEQZ R12 , eti

LF F6 , dato+8

MULTF F20 , F4 , F6

SF dato , F20

eti: subi R12, R12, 1

BEQZ R12 , eti2

Nop

ADDF F20 , F4 , F6

SF dato+8 , F20

eti2: trap 0



Caso 2: Programa inicial

Con salto retardado (caso 2)

;====================================


;====================================

.data

dato: .double 1.5, 2.0, 3.3, 4.4

CTE: .FLOAT 10.0

num: .word 4

.text 0x100

main: LD F10 , CTE

LW R4, num

ADDI R8, R0, 0

eti: LD F4 , dato(R8)

LD F6 , dato+8(R8)

MULTD F8, F4, F6

ADDI R8, R8, 8

SUBI R4, R4, 2

BEQZ R4 , eti

SD dato , F8

trap 0

;====================================


;====================================

.data

dato: .double 1.5, 2.0, 3.3, 4.4

CTE: .FLOAT 10.0

num: .word 4

.text 0x100

main: LD F10 , CTE

LW R4, num

ADDI R8, R0, 0

LD F4 , dato(R8)

eti: LD F6 , dato+8(R8)

MULTD F8, F4, F6

ADDI R8, R8, 8

SUBI R4, R4, 2

BEQZ R4 , eti

LD F4 , dato(R8)

SD dato , F8

trap 0





;====================================


;====================================

.data

valor: .double 3.0, 4.0

dato: .double 1.5, 2.0

res: .space 8

CTE: .FLOAT 10.0

num: .word 6

.text 0x100

main: LW R12, num

LD F4, valor

LD F6, valor+8

SUBI R12, R12, 2

BNEZ R12 , eti

LD F4 , dato(R0)

LD F6 , dato+8(R0)

MULTD F20 , F4 , F6

SD res , F20

eti: addi R12, R12, 2

ADDD F20 , F4 , F6

SD res, F20

eti2: trap 0

;====================================


;====================================

.data



res: .space 8

CTE: .FLOAT 10.0

num: .word 6

.text 0x100

main: LW R12, num

LD F4, valor

LD F6, valor+8

SUBI R12, R12, 2

BNEZ R12 , eti

NOP

LD F4 , dato(R0)

LD F6 , dato+8(R0)

MULTD F20 , F4 , F6

SD res , F20


ADDD F20 , F4 , F6

SD res, F20

eti2: trap 0

Problema: aplica el caso 1 y el 2 del salto retardado al código de la anterior ventana.





;====================================


;====================================

.data



res: .space 8

CTE: .FLOAT 10.0

num: .word 6

.text 0x100

main: LW R12, num

LD F4, valor

LD F6, valor+8

SUBI R12, R12, 2

BNEZ R12 , eti

LD F4 , dato(R0)

LD F6 , dato+8(R0)

MULTD F20 , F4 , F6

SD res , F20


ADDD F20 , F4 , F4

SD res, F20

eti2: trap 0

;====================================


;====================================

.data



res: .space 8

CTE: .FLOAT 10.0

num: .word 6

.text 0x100

main: LW R12, num

LD F4, valor

LD F6, valor+8

SUBI R12, R12, 2

BNEZ R12 , eti

LD F6 , dato+8(R0)

LD F4 , dato(R0)

MULTD F20 , F4 , F6

SD res , F20


ADDD F20 , F4 , F4

SD res, F20

eti2: trap 0

4. mem-paso de completar salto/acceso a …riesgo de salto o de control en la figura siguiente se...

Documents