ISI374 – Arquitectura de Computadores Clase 13: Segmentación (Pipelining) Pt.2 Departamento de...
-
Upload
teodosio-clemente -
Category
Documents
-
view
6 -
download
0
Transcript of ISI374 – Arquitectura de Computadores Clase 13: Segmentación (Pipelining) Pt.2 Departamento de...
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)
Adelantamiento (Forwarding, bypassing, short-circuiting)
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
Adelantamiento (Forwarding, bypassing, short-circuiting)
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
Adelantamiento (Forwarding, bypassing, short-circuiting)
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
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)
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)
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)
Consideremos dos instrucciones i y j, con i antecediendo a j en el orden del programa
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)
Consideremos dos instrucciones i y j, con i antecediendo a j en el orden del programa
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
add $s1, $s2, $s3 beq $s1, $zero, LBL
or $t1, $t2, $t3 . . . LBL: sub $t4, $t5, $t6
hueco de salto
add $s1, $s2, $s3 beq $s1, $zero, LBL
. . . 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