ISI374 – Arquitectura de Computadores Clase 12: Segmentación (Pipelining) Pt.1 Departamento de...
-
Upload
zacarias-lusco -
Category
Documents
-
view
28 -
download
0
Transcript of ISI374 – Arquitectura de Computadores Clase 12: Segmentación (Pipelining) Pt.1 Departamento de...
ISI374 – Arquitectura de ComputadoresClase 12: Segmentación (Pipelining) Pt.1
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
La recurrente analogía con una lavandería Latencia, throughput Pasos en la ejecución de una instrucción MIPS Procesador MIPS segmentado Rendimiento del procesador segmentado Speedup del pipeline ISA y pipeline Riesgos (Hazards)
ISI3
74 -
Arqu
itect
ura
de C
ompu
tado
res
(201
0-1)
La recurrente analogía con una lavandería
Tenemos cuatro canastas de ropa sucia para lavar, secar, doblar y guardar en el armario
El lavado toma 30 minutos
El secado toma 30 minutos
El doblado toma 30 minutos
Ubicar la ropa en el armario toma 30 minutos
3
A B C D
ISI3
74 -
Arqu
itect
ura
de C
ompu
tado
res
(201
0-1)
Lavado secuencial4
El lavado secuencial toma 8 horas para 4 canastas
30Time
3030 3030 30 3030 3030 3030 3030 3030
6 PM 7 8 9 10 11 12 1 2 AM
Task
Order
B
C
D
A
ISI3
74 -
Arqu
itect
ura
de C
ompu
tado
res
(201
0-1)
Lavado segmentado (pipelined)5
El lavado segmentado toma 3.5 horas para 4 cargasSpeedup = 8 / 3.5 = 2.3
¿Qué pasa si el número de canastas es grande?Speedup Número de etapas
Ej: 500 canastas toman (4+499)×0.5 = 251.5 horasSpeedup = 500× 2 / 251.5 = 3.98
Task
Order
B
C
D
A
12 2 AM6 PM 7 8 9 10 11 1
Time303030 3030 3030
ISI3
74 -
Arqu
itect
ura
de C
ompu
tado
res
(201
0-1)
LatenciaTiempo necesario para ejecutar completamente una tarea (retardo)
ThroughputCantidad de trabajo realizado en un periodo de tiempo (tasa)
Recordatorio6
ISI3
74 -
Arqu
itect
ura
de C
ompu
tado
res
(201
0-1)
Lecciones de la analogía
La segmentación no reduce la latencia de una tarea, sino que eleva el throughput de un proceso completo
Varias tareas operan simultáneamente usando recursos diferentes
Speedup potencial: número de etapas del pipe
El speedup se reduce porque hay que llenar (fill) y vaciar (flush) el pipeline (2.3× contra 4× en este ejemplo)
7
6 PM 7 8 9 10Time
303030 3030 3030Task
Order
B
C
D
A
ISI3
74 -
Arqu
itect
ura
de C
ompu
tado
res
(201
0-1)
Lecciones de la analogía
Supongamos que las tareas de lavar y ubicar la ropa en el armario ahora toman 20 minutos cada una. ¿Qué tanto más rápido es el nuevo pipeline?
La rata del pipeline está limitada por la etapa más lenta
Etapas desequilibradas del pipeline reducen el speedup
8
6 PM 7 8 9 10Time
302030 3030 3020Task
Order
B
C
D
A
Secuencial= 6.67 h
Segmentado= 3.17 hSpeedup= 2.11
ISI3
74 -
Arqu
itect
ura
de C
ompu
tado
res
(201
0-1)
Pasos en la ejecución de una instrucción MIPS
1. IF: (Instruction Fetch) Búsqueda de la instrucción, actualización del PC
2. ID: (Instruction Decode) Decodificación de la instrucción, lectura del banco de registros
3. EX: (Execution) Instrucción de acceso a memoria: Cálculo de la dirección Instrucción aritmético-lógica: Cálculo de la operación
4. MEM: (Memory) Load: Lectura de la memoria de datos Store: Escritura de la memoria de datos
5. WB: (Write Back) Escritura del resultado en el banco de registros
9
ISI3
74 -
Arqu
itect
ura
de C
ompu
tado
res
(201
0-1)
Procesador MIPS segmentado
Tendremos cinco etapas, una por cada paso de ejecución de una instrucción
Cada etapa del pipeline se completa en un ciclo de reloj Cada instrucción toma el mismo número de etapas (5) para
ejecutarse, aunque algunas de ellas estén inactivas algunas veces
Mejora el throughput aunque la latencia de cada instrucción no se reduce
10
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
Instr. i
Instr. i+1Instr. i+2Instr. i+3
Instr. i+4
Time
cc 1
cc 2
cc 3
cc 4
cc 5
cc 6
cc 7
cc 8
cc 9
Una vez el pipeline está lleno, se finaliza una instrucción cada ciclo (CPI = 1)
ISI3
74 -
Arqu
itect
ura
de C
ompu
tado
res
(201
0-1)
Rendimiento del procesador segmentado
Ciclo de reloj del procesador monociclo asumiendo que los retrasos de todos los componentes son despreciables (incluidos los cables), excepto los de los siguientes, cuyo retraso se indica:
Unidades de memoria: 200 ps ALU y sumadores: 200 ps Banco de registros (R/W): 100 ps
Ciclo de reloj para la versión monociclo: 800 ps Ciclo de reloj de la versión segmentada: 200 ps
11
Tipo de instrucció
n
Memoria de
instrucciones
Lectura banco de registros
Operación ALU
Memoria de datos
Escritura banco de registros
Total
Tipo R 200 100 200 0 100 600 ps
Load word 200 100 200 200 100 800 ps
Store word
200 100 200 200 700 ps
Branch 200 100 200 500 ps
ISI3
74 -
Arqu
itect
ura
de C
ompu
tado
res
(201
0-1)
Rendimiento del procesador segmentado12
Monociclo (Tc= 800ps)
Segmentado (Tc= 200ps)
El tiempo de ciclo del pipeline está limitado por la etapa más lenta
ISI3
74 -
Arqu
itect
ura
de C
ompu
tado
res
(201
0-1)
Speedup del pipeline
Si todas las etapas están balanceadas, es decir, todas tardan el mismo tiempo:
Tiempo entre instruccionessegmentado =
Bajo condiciones ideales y con un gran número de instrucciones, el speedup de la segmentación es aproximadamente igual al número de etapas del pipeline
Si no está balanceado, el speedup es menor
La segmentación eleva el rendimiento incrementando la tasa de ejecución de instrucciones (throughput), sin reducir el tiempo de ejecución de una instrucción individual (latencia)
La tasa de ejecución de instrucciones es la medida que importa porque los programas ejecutan miles de millones de instrucciones
13
Tiempo entre instruccionesno segmentado
Número de etapas del pipe
ISI3
74 -
Arqu
itect
ura
de C
ompu
tado
res
(201
0-1)
ISA y segmentación
La ISA del MIPS fue diseñada para una ejecución segmentada Todas las instrucciones son de la misma longitud
Facilita la búsqueda de instrucciones en la primera etapa (IF) y su decodificación en la segunda (DE)
Pocos formatos de instrucción Los campos de registros fuente ocupan el mismo lugar en cada
formato Esta simetría permite que en la segunda etapa se lea el banco de
registros a la misma vez que se determina el tipo de instrucción Los operandos de memoria sólo aparecen en las instrucciones
load y store La etapa de ejecución (EX) se usa para calcular la dirección de
memoria, y el acceso se produce en la siguiente etapa (MEM) Cada instrucción escribe a lo sumo un resultado y lo hace en las
últimas etapas (MEM, WB) Alineamiento de memoria
Los accesos a memoria se realizan en un solo ciclo de reloj
14
ISI3
74 -
Arqu
itect
ura
de C
ompu
tado
res
(201
0-1)
Representación gráfica del pipeline
Útil para: Saber cuántos ciclos de reloj toma la ejecución de un código Saber qué hace una unidad funcional en un ciclo determinado Si ocurre un riesgo (hazard), saber porqué y saber cómo resolverlo
15
ISI3
74 -
Arqu
itect
ura
de C
ompu
tado
res
(201
0-1)
Riesgos (Hazards)
El principio de la segmentación es simple pero su implementación introduce una serie de problemas
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
Los riesgos se pueden resolver esperando, pero será el controlador del pipeline quien los detecte y resuelva
Tipos: Riesgos estructurales (Structural hazards) Riesgos de datos (Data hazards) Riesgos de control (Control hazards)
16
ISI3
74 -
Arqu
itect
ura
de C
ompu
tado
res
(201
0-1)
Riesgos estructurales
Se presentan cuando dos instrucciones diferentes intentar usar el mismo recurso simultáneamente
Ej: ¿Qué sucede si el procesador tiene una memoria de un puerto, compartida para datos e instrucciones?
Solución:» Emplear memorias de datos e instrucciones independientes (I$ y D$).» En general, replicar los recursos necesarios para permitir todas las
combinaciones posibles de instrucciones en el pipeline
17
ISI3
74 -
Arqu
itect
ura
de C
ompu
tado
res
(201
0-1)
Riesgos estructurales
¿Qué sucede con los accesos al banco de registros? Para resolver el riesgo estructural al momento de acceder al banco
de registros, las escrituras se realizan en la primera mitad del ciclo, y las lecturas en la segunda
18
add $t0, $t1, $t2
Instr. 1
Instr. 2
add $s2, $t0, $s3
Flanco de reloj quecontrola la lectura de operandos del banco de registros
Flanco de reloj quecontrola la escritura de resultados en el banco de registros
Clock
ISI3
74 -
Arqu
itect
ura
de C
ompu
tado
res
(201
0-1)
Riesgos de datos
Ocurren cuando una instrucción no puede ser ejecutada porque depende del resultado de una instrucción previa que no lo ha producido aún
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
19
ISI3
74 -
Arqu
itect
ura
de C
ompu
tado
res
(201
0-1)
Riesgos de datos
Considere la ejecución segmentada de la siguiente secuencia de instrucciones:
add $t0, $t1, $t2
sub $t3, $t0, $t4
and $t5, $t0, $t6
or $t7, $t0, $t8
nor $t9, $t0, $t9
20
ISI3
74 -
Arqu
itect
ura
de C
ompu
tado
res
(201
0-1)
Riesgos de datos
Considere la ejecución segmentada de la siguiente secuencia de instrucciones:
add $t0, $t1, $t2
sub $t3, $t0, $t4
and $t5, $t0, $t6
or $t7, $t0, $t8
nor $t9, $t0, $t9
Las dependencias de datos hacia atrás en el tiempo ocasionan riesgos de datos
21
ISI3
74 -
Arqu
itect
ura
de C
ompu
tado
res
(201
0-1)
Riesgos de datos
Los riesgos de datos pueden afectar seriamente el rendimiento Una primera solución para evitarlos consiste en producir paradas en
el pipeline para satisfacer las dependencias de datos
add $s0, $t0, $t1 # También aplica con lwsub $t2, $s0, $t3
22
Bubble (burbuja), pipeline stall (parada del pipe)
ISI3
74 -
Arqu
itect
ura
de C
ompu
tado
res
(201
0-1)
23
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