ISI374 – Arquitectura de Computadores Clase 13: Segmentación (Pipelining) Pt.2 Departamento de Ingeniería de Sistemas Universidad de Antioquia 2010-1

ISI374 – Arquitectura de ComputadoresClase 13: Segmentación (Pipelining) Pt.2

Departamento de Ingeniería de SistemasUniversidad de Antioquia

2010-1

ISI3

74 -

Arqu

itect

ura

de C

ompu

tado

res

(201

0-1)

2

Resumen

Riesgos (Hazards) Adelantamiento (forwarding, bypassing, short-circuiting) Reordenamiento de código Generalización de los conflictos de datos Riesgos de control

ISI3

74 -

Arqu

itect

ura

de C

ompu

tado

res

(201

0-1)

Recapitulación

Riesgos (Hazards)

Situaciones en las cuales la próxima instrucción no puede ejecutarse en el siguiente ciclo de reloj

Pueden obligar a detener (stall) el pipeline, evitando que se logre el speedup ideal

Riesgos estructurales Se presentan cuando dos instrucciones diferentes intentar usar el

mismo recurso simultáneamente» Acceso a memoria: emplear memorias de datos e instrucciones

independientes (I$ y D$)» Acceso al banco de registros: en el banco, las escrituras se realizan en la

primera mitad del ciclo, y las lecturas en la segunda

Riesgos de datos Ocurren cuando el pipeline modifica el orden de los accesos de

lectura/escritura a los operandos tal que este orden difiere del orden visto por una ejecución secuencial no segmentada

3

ISI3

74 -

Arqu

itect

ura

de C

ompu

tado

res

(201

0-1)

Recapitulación

Riesgos de datos y su impacto en el rendimiento

add $s0, $t0, $t1sub $t2, $s0, $t3

Cómo se pueden minimizar las paradas producidas por los riesgos de datos?

4

Bubble (burbuja), pipeline stall (parada del pipe)

ISI3

74 -

Arqu

itect

ura

de C

ompu

tado

res

(201

0-1)

Adelantamiento (Forwarding, bypassing, short-circuiting) Técnica hardware para solucionar algunos riesgos de datos

No es necesario esperar a que una instrucción se ejecute por completo para resolver el riesgo de datos

Es posible usar un resultado tan pronto como se calcula, sin tener que esperar a que sea escrito en el banco de registros

Requiere conexiones extras en el datapath

Los caminos de adelantamiento son válidos si la etapa de destino es posterior en el tiempo a la etapa de origen

5

ISI3

74 -

Arqu

itect

ura

de C

ompu

tado

res

(201

0-1)

Adelantamiento (Forwarding, bypassing, short-circuiting)

Ejemplo 1:

add $t0, $t1, $t2

sub $t3, $t0, $t4

and $t5, $t0, $t6

or $t7, $t0, $t8

nor $t9, $t0, $t9

6

ISI3

74 -

Arqu

itect

ura

de C

ompu

tado

res

(201

0-1)

Ejemplo 2:

add $t0, $t1, $t2

lw $t3, 0($t0)

sw $t3, 12($t0)


7

ISI3

74 -

Arqu

itect

ura

de C

ompu

tado

res

(201

0-1)

No todos los riesgos de datos pueden resolverse mediante adelantamiento

Riesgo de datos asociado con el uso de LOAD Un dato no está aún disponible cuando es requerido No es posible pasar un dato hacia atrás en el tiempo

Aún con adelantamiento es necesario detener el pipeline durante un ciclo


8

Versiónsimplista

ISI3

74 -

Arqu

itect

ura

de C

ompu

tado

res

(201

0-1)

No todos los riesgos de datos pueden resolverse mediante adelantamiento

Riesgo de datos asociado con el uso de LOAD

Pipeline sin detección de riesgo

ld $t1, 0(t0)sub $t3, $t1, $t2and $t4, $t1, $t5or $t6, $t1, $t7

Pipeline con detección de riesgo

ld $t1, 0(t0)sub $t3, $t1, $t2and $t4, $t1, $t5or $t6, $t1,$t7


9

No es posible el adelantamiento

ISI3

74 -

Arqu

itect

ura

de C

ompu

tado

res

(201

0-1)

Reordenamiento de código para evitar paradas del pipe Ejemplo:

Considere un segmento de código MIPS. Determine los riesgos y reordene el código para evitar paradas del pipeline

10

lw $t1, 0($t0)lw $t2, 4($t0)add $t3, $t1, $t2sw $t3, 12($t0)lw $t4, 8($t0)add $t5, $t1, $t4sw $t5, 16($t0)

ISI3

74 -

Arqu

itect

ura

de C

ompu

tado

res

(201

0-1)

Reordenamiento de código para evitar paradas del pipe Ejemplo:

Considere un segmento de código MIPS. Determine los riesgos y reordene el código para evitar paradas del pipeline

11



stall

stall

lw $t1, 0($t0)lw $t2, 4($t0)lw $t4, 8($t0)add $t3, $t1, $t2sw $t3, 12($t0)add $t5, $t1, $t4sw $t5, 16($t0)

11 ciclos13 ciclos

ISI3

74 -

Arqu

itect

ura

de C

ompu

tado

res

(201

0-1)

Generalización de los conflictos de datos

Los conflictos (riesgos) de datos se clasifican en tres tipos, de acuerdo con el orden de los accesos de lectura y escritura en las instrucciones

Read after write (RAW) Write after write (WAW) Write after read (WAR)

Por convención, los conflictos se nombran de acuerdo con el orden establecido en un programa, y que debe ser conservado por el pipeline

Dependencias: programas Conflictos, riesgos: organización del pipeline

12

ISI3

74 -

Arqu

itect

ura

de C

ompu

tado

res

(201

0-1)

Consideremos dos instrucciones i y j, con i antecediendo a j en el orden del programa

Hay un conflicto RAW cuando la instrucción j lee un operando fuente antes de que la instrucción i lo haya escrito, de tal manera que j lee un valor “viejo”

instr_i: add $t1, $t2, $t3instr_j: sub $t4, $t1, $t3

Son ocasionados por dependencias reales de datos Una instrucción load seguida de una instrucción tipo R que use

directamente el resultado de load produce un conflicto RAW

Conflictos Read after write (RAW)13

ISI3

74 -

Arqu

itect

ura

de C

ompu

tado

res

(201

0-1)

Conflictos Write after write (WAW)


Hay un conflicto WAW cuando la instrucción j escribe un operando antes de que éste sea escrito por la instrucción i

instr_i: mul.d $f2, $f4, $f6instr_j: lwc1 $f2, 100($t2)

La escritura se realiza en el orden equivocado (se conserva el valor escrito por i en lugar del valor escrito por j)

Se denomina dependencia de salida (output dependence) No ocurren en el pipeline de 5 etapas del MIPS

14

ISI3

74 -

Arqu

itect

ura

de C

ompu

tado

res

(201

0-1)

Conflictos Write after read (WAR)


Hay un conflicto WAR cuando la instrucción j escribe un destino antes de que éste sea leído por la instrucción i, tal que i toma de manera incorrecta el nuevo valor

instr_i: sub $t4, $t1, $t3instr_j: add $t1, $t2, $t3

Se denomina anti-dependencia No ocurren en el pipeline de 5 etapas del MIPS

15

ISI3

74 -

Arqu

itect

ura

de C

ompu

tado

res

(201

0-1)

Riesgos de control

17% de las instrucciones MIPS ejecutadas son saltos (bne, beq) (SPECint2006)

Los saltos determinan el flujo de programa La siguiente instrucción a ejecutar depende del resultado del salto

beq

instr. 1

instr. 2

instr. 3

instr. 4

16

ISI3

74 -

Arqu

itect

ura

de C

ompu

tado

res

(201

0-1)

Riesgos de control

De acuerdo con la ruta de datos que hemos construido, la decisión de tomar o no el salto se realiza en la etapa de ejecución (EX)

Por lo tanto, siempre se buscan dos instrucciones más después del salto, sin importar si éste se toma o no

Not taken branch, untaken branch: Salto no tomado. Aquel que implica que la siguiente instrucción a ejecutar es la subsiguiente

Taken branch: Salto tomado. Aquel que hace que el flujo de programa se dirija al destino del salto

Funcionalidad deseada de un salto: Si el salto no se toma (not taken branch), no desperdiciar tiempo y

continuar con la ejecución secuencialmente Si el salto se toma (taken branch), no ejecutar ninguna instrucción

después del salto, y solamente ir hasta la instrucción de destino del salto

17

ISI3

74 -

Arqu

itect

ura

de C

ompu

tado

res

(201

0-1)

Riesgos de control

A manera de definición: Un riesgo de control surge de la necesidad de tomar una decisión

(¿se toma o no se toma el salto?) basada en el resultado de una instrucción (branch) mientras otras se están ejecutando

Los riesgos de control ocurren con menos frecuencia que los riesgos de datos pero degradan mucho más el rendimiento

Para los riesgos de datos no existe una solución similar al adelantamiento (forwarding) para los riesgos de datos

Cómo se pueden tratar los riesgos de control:

Deteniendo el pipeline hasta que la decisión sea tomada (stall on branch)

Afecta el CPI Prediciendo el resultado del salto

Afecta el rendimiento sólo cuando la predicción es incorrecta

18

ISI3

74 -

Arqu

itect

ura

de C

ompu

tado

res

(201

0-1)

Riesgos de control

Solución inicial: Stall on branch

Detenerse hasta que la decisión de salto sea tomada para buscar la siguiente instrucción

Insertar burbujas (instrucciones nop, No Operation, aquellas que no hacen nada y sólo ocupan tiempo) para retrasar la búsqueda de la siguiente instrucción durante 2 ciclos

En nuestro caso, los saltos toman 3 ciclos de reloj cada uno (el comparador está en la etapa EX)

19

ISI3

74 -

Arqu

itect

ura

de C

ompu

tado

res

(201

0-1)

Riesgos de control

Optimización #1

Insertar un comparador para saltos en la segunda etapa (ID) Tan pronto como se decodifica la instrucción de salto, tomar una

decisión y ajustar el nuevo valor del PC

Como el salto se completa en la segunda etapa, sólo se introduce una burbuja

Los saltos toman 2 ciclos de reloj cada uno (el comparador está en la etapa ID)

Esto significa que los saltos están inactivos en las etapas 3, 4 y 5 (EX, MEM y WB, respectivamente)

20

ISI3

74 -

Arqu

itect

ura

de C

ompu

tado

res

(201

0-1)

Riesgos de control

Optimización #2. Redefinición de los saltos

Antes: Si el salto se toma, ninguna de las instrucciones que siguen al salto

se ejecutan por accidente

Ahora: Se tome o no el salto, la instrucción inmediatamente posterior al

salto se ejecuta (y se denomina branch delay slot, hueco de salto diferido o retardado)

El término delayed branch (salto diferido o retardado) significa que la instrucción que sigue al salto siempre se ejecuta

Esta optimización es la que emplea MIPS

21

ISI3

74 -

Arqu

itect

ura

de C

ompu

tado

res

(201

0-1)

Riesgos de control

Comportamiento del salto diferido (delayed branch)

Es trabajo del compilador lograr que la instrucción que ocupa el hueco diferido sea válida y útil (ver diapositiva #25)

22

ISI3

74 -

Arqu

itect

ura

de C

ompu

tado

res

(201

0-1)

Riesgos de control

Branch delay slot (Comentarios)

Como la instrucción que sigue al salto siempre se ejecuta:

Escenario del peor caso: insertar una burbuja en el hueco de salto retardado porque no hay otra alternativa

Escenario del caso más favorable: es posible encontrar una instrucción anterior al salto que pueda insertarse en el hueco de salto diferido sin que el flujo de programa se vea afectado

El reordenamiento de instrucciones es una práctica común para acelerar programas

El compilador debe ser muy hábil para encontrar las instrucciones adecuadas

Normalmente el 50% de las veces se hallan estas instrucciones

23

ISI3

74 -

Arqu

itect

ura

de C

ompu

tado

res

(201

0-1)

Riesgos de control24

Salto no diferido

or $t0, $t1, $t2add $s1, $s2, $s3sub $s4, $s5, $s6beq $s1, $s4, Exitnor $t2, $s1, $t3

Exit:

Salto diferido

add $s1, $s2, $s3sub $s4, $s5, $s6beq $s1, $s4, Exitor $t0, $t1, $t2nor $t2, $s1, $t3

Exit:

ISI3

74 -

Arqu

itect

ura

de C

ompu

tado

res

(201

0-1)

Riesgos de control

Gestión del hueco de salto diferido por parte del compilador

En las dos últimas opciones, la ejecución de la instrucción que se mueve no debe producir problemas si el salto va en la dirección contraria a la esperada

25

add $s1, $s2, $s3 beq $s2, $zero, LBL

. . .LBL:

hueco de salto

beq $s2, $zero, LBL

. . . LBL:

add $s1, $s2, $s3

LBL: sub $t4, $t5, $t6 . . . add $s1, $s2, $s3 beq $s1, $zero, LBL

hueco de salto

LBL: sub $t4, $t5, $t6LBLx: . . . add $s1, $s2, $s3 beq $s1, $zero, LBLx

sub $t4, $t5, $t6

se transformaen

se transformaen


or $t1, $t2, $t3 . . . LBL: sub $t4, $t5, $t6

hueco de salto


. . . LBL: sub $t4, $t5, $t6

or $t1, $t2, $t3

se transformaen

ISI3

74 -

Arqu

itect

ura

de C

ompu

tado

res

(201

0-1)

26

Lecturas recomendadas

Computer organization and design. The hardware/software Interface, 3rd ed., Chapter 6. D. Patterson & J. Hennessy. Morgan Kaufmann Publishers

Computer architecture. A quantitative approach, 3rd ed., Appendix A. J Hennessy and D. Patterson. Morgan Kaufmann Publishers

Documents

ISI374 – Arquitectura de Computadores Clase 13: Segmentación (Pipelining) Pt.2 Departamento de Ingeniería de Sistemas Universidad de Antioquia 2010-1